लेक्सिकोग्राफ़िक कोड: Difference between revisions

From Vigyanwiki
(Created page with "लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणो...")
 
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणों के साथ लालच से उत्पन्न [[त्रुटि-सुधार कोड]] हैं। इनका निर्माण स्वतंत्र रूप से किया गया था
लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणों के साथ आतुरतापुर्वक से उत्पन्न [[त्रुटि-सुधार कोड]] हैं। इनका निर्माण स्वतंत्र रूप से व्लादिमीर लेवेनशेटिन<ref>{{citation
व्लादिमीर लेवेनशेटिन<ref>{{citation
  | last = Levenšteĭn | first = V. I. | authorlink = Vladimir Levenshtein
  | last = Levenšteĭn | first = V. I. | authorlink = Vladimir Levenshtein
  | issue = 5
  | issue = 5
Line 11: Line 10:
  | url = http://mi.mathnet.ru/dan39976
  | url = http://mi.mathnet.ru/dan39976
  | volume = 131
  | volume = 131
  | year = 1960}}; English translation in ''Soviet Math. Doklady'' 1 (1960), 368–371</ref> और [[जॉन हॉर्टन कॉनवे]] और [[नील स्लोएन]] द्वारा।<ref name=conslo>{{citation
  | year = 1960}}; English translation in ''Soviet Math. Doklady'' 1 (1960), 368–371</ref> और [[जॉन हॉर्टन कॉनवे]] और [[नील स्लोएन]] द्वारा  किया गया था।<ref name="conslo">{{citation
  | last1 = Conway | first1 = John H. | author1-link = John Horton Conway
  | last1 = Conway | first1 = John H. | author1-link = John Horton Conway
  | last2 = Sloane | first2 = N. J. A. | author2-link = Neil Sloane
  | last2 = Sloane | first2 = N. J. A. | author2-link = Neil Sloane
Line 21: Line 20:
  | title = Lexicographic codes: error-correcting codes from game theory
  | title = Lexicographic codes: error-correcting codes from game theory
  | volume = 32
  | volume = 32
  | year = 1986}}</ref> बाइनरी लेक्सिकोग्राफ़िक कोड [[रैखिक कोड]] होते हैं, और इसमें [[हैमिंग कोड]] और [[ बाइनरी भाषा में कोड ]] शामिल होते हैं।<ref name=conslo/>
  | year = 1986}}</ref> बाइनरी लेक्सिकोग्राफ़िक कोड [[रैखिक कोड]] होते हैं, और इसमें [[हैमिंग कोड]] और [[ बाइनरी भाषा में कोड | बाइनरी गोले  कोड]] सम्मिलित होते हैं।<ref name="conslo" />
 
 




== निर्माण ==
== निर्माण ==
एक [[परिमित क्षेत्र]] पर लंबाई एन और न्यूनतम दूरी डी का एक लेक्सिकोड ऑल-जीरो वेक्टर से शुरू करके और अब तक जोड़े गए वैक्टर से न्यूनतम [[हैमिंग दूरी]] डी के अगले वेक्टर ([[शब्दकोषीय क्रम]] में) को जोड़कर उत्पन्न किया जाता है। उदाहरण के तौर पर, न्यूनतम दूरी 2 की लंबाई-3 लेक्सिकोड में निम्नलिखित उदाहरण में एक्स द्वारा चिह्नित वेक्टर शामिल होंगे:
एक [[परिमित क्षेत्र]] पर अवधि n और न्यूनतम दूरी d का एक लेक्सिकोड ऑल-जीरो वेक्टर से प्रारंभ करके और अब तक जोड़े गए वेक्टर से न्यूनतम [[हैमिंग दूरी]] d के अगले वेक्टर ([[शब्दकोषीय क्रम]] में) को जोड़कर उत्पन्न किया जाता है। उदाहरण के लिए, न्यूनतम दूरी 2 की लंबाई-3 लेक्सिकोड में निम्नलिखित उदाहरण में X द्वारा चिह्नित वेक्टर सम्मिलित होंगे:


:{| class="wikitable"
:{| class="wikitable"
|-
|-
! Vector
!वेक्टर
! In code?
!कोड में?
|-
|-
| 000
| 000
Line 56: Line 57:
|
|
|}
|}
यहां डी-बिट न्यूनतम हैमिंग दूरी द्वारा सभी एन-बिट लेक्सिकोड की एक तालिका है, जिसके परिणामस्वरूप अधिकतम 2 है<sup>म</sup> कोडवर्ड डिक्शनरी।
यहां D-बिट न्यूनतम हैमिंग दूरी द्वारा N-बिट लेक्सिकोड की एक तालिका है, जिसके परिणामस्वरूप अधिकतम 2<sup>m</sup> कोडवर्ड डिक्शनरी है।
उदाहरण के लिए, एफ<sub>4</sub> कोड (n=4,d=2,m=3), विस्तारित हैमिंग कोड (n=8,d=4,m=4) और विशेष रूप से गोले कोड (n=24,d=8,m=12) पड़ोसियों की तुलना में असाधारण कॉम्पैक्टनेस दिखाता है।
 
उदाहरण के लिए, F<sub>4</sub> कोड (n=4,d=2,m=3), विस्तारित हैमिंग कोड (n=8,d=4,m=4) और विशेष रूप से गोले कोड (n=24,d=8,m=12) निकटतम की तुलना में असाधारण सघनता दिखाता है।
:{| class="wikitable"
:{| class="wikitable"


Line 774: Line 776:


|}
|}
सभी विषम डी-बिट लेक्सिकोड दूरियां अंतिम आयाम को घटाकर सम डी+1 बिट दूरियों की सटीक प्रतियां हैं, इसलिए
सभी अयुग्म D-बिट लेक्सिकोड दूरियां अंतिम आयाम को घटाकर सम d+1 बिट दूरियों की सटीक प्रतियां हैं,  
एक विषम-आयामी स्थान उपरोक्त d+1 सम-आयामी स्थान की तुलना में कभी भी कुछ नया या अधिक दिलचस्प नहीं बना सकता है।


चूंकि लेक्सिकोड्स रैखिक होते हैं, इसलिए उनका निर्माण उनके आधार (रैखिक बीजगणित) के माध्यम से भी किया जा सकता है।<ref>{{citation
इसलिए एक अयुग्म-आयामी स्थान उपरोक्त d+1 सम-आयामी स्थान की तुलना में कभी भी कुछ नया या अधिक चित्ताकर्षक नहीं बना सकता है।
 
चूंकि लेक्सिकोड्स रैखिक होते हैं, इसलिए उनका निर्माण उनके आधार के माध्यम से भी किया जा सकता है।<ref>{{citation
  | last = Trachtenberg | first = Ari
  | last = Trachtenberg | first = Ari
  | doi = 10.1109/18.971740
  | doi = 10.1109/18.971740
Line 790: Line 793:


== कार्यान्वयन ==
== कार्यान्वयन ==
निम्नलिखित सी लेक्सिकोग्राफ़िक कोड उत्पन्न करता है और गोले कोड (एन = 24, डी = 8) के लिए पैरामीटर सेट किए जाते हैं।
निम्नलिखित C लेक्सिकोग्राफ़िक कोड को उत्पन्न करता है, और गोले कोड (N = 24, डी = 8) के लिए पैरामीटर समुच्चय किए जाते हैं।
<syntaxhighlight lang="c">
<syntaxhighlight lang="c">
#include <stdio.h>
#include <stdio.h>
Line 822: Line 825:
</syntaxhighlight>
</syntaxhighlight>


 
== [[कॉम्बिनेटरियल गेम थ्योरी|कॉम्बिनेटोरियल गेम थ्योरी]] ==
[[कॉम्बिनेटरियल गेम थ्योरी]] सिद्धांत =
लेक्सिकोग्राफ़िक कोड का सिद्धांत कॉम्बिनेटरियल खेल सिद्धांत से निकटता से जुड़ा हुआ है। विशेष रूप से, दूरी d के बाइनरी लेक्सिकोग्राफ़िक कोड में कोडवर्ड ग्रुंडी के खेल के एक प्रकार में जीतने वाली स्थिति को कूटबद्ध करते हैं, जो पत्थरों के ढेर के संग्रह पर खेला जाता है, जिसमें प्रत्येक चाल में किसी एक ढेर को अधिकतम d - 1 लघु से प्रतिस्थापित करना होता है , और लक्ष्य आखिरी पत्थर लेना होता है।<ref name="conslo" />
लेक्सिकोग्राफ़िक कोड का सिद्धांत कॉम्बिनेटरियल गेम सिद्धांत से निकटता से जुड़ा हुआ है। विशेष रूप से, दूरी डी के बाइनरी लेक्सिकोग्राफ़िक कोड में कोडवर्ड ग्रुंडी के खेल के एक प्रकार में जीतने वाली स्थिति को कूटबद्ध करते हैं, जो पत्थरों के ढेर के संग्रह पर खेला जाता है, जिसमें प्रत्येक चाल में किसी एक ढेर को अधिकतम डी - 1 छोटे से प्रतिस्थापित करना होता है ढेर, और लक्ष्य आखिरी पत्थर लेना है।<ref name=conslo/>




Line 836: Line 838:
*{{OEIS el|sequencenumber=A075928|name=List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers. }}
*{{OEIS el|sequencenumber=A075928|name=List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers. }}
*[http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html  Error-Correcting Codes on Graphs: Lexicodes], [http://oeis.org/search?q=Trellises Trellises and Factor Graphs]
*[http://ipsit.bu.edu/phdthesis_html/phdthesis_html.html  Error-Correcting Codes on Graphs: Lexicodes], [http://oeis.org/search?q=Trellises Trellises and Factor Graphs]
[[Category: त्रुटि का पता लगाना और सुधार करना]]


[[Category: Machine Translated Page]]
[[Category:CS1 maint]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Templates Vigyan Ready]]
[[Category:त्रुटि का पता लगाना और सुधार करना]]

Latest revision as of 10:03, 23 August 2023

लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणों के साथ आतुरतापुर्वक से उत्पन्न त्रुटि-सुधार कोड हैं। इनका निर्माण स्वतंत्र रूप से व्लादिमीर लेवेनशेटिन[1] और जॉन हॉर्टन कॉनवे और नील स्लोएन द्वारा किया गया था।[2] बाइनरी लेक्सिकोग्राफ़िक कोड रैखिक कोड होते हैं, और इसमें हैमिंग कोड और बाइनरी गोले कोड सम्मिलित होते हैं।[2]



निर्माण

एक परिमित क्षेत्र पर अवधि n और न्यूनतम दूरी d का एक लेक्सिकोड ऑल-जीरो वेक्टर से प्रारंभ करके और अब तक जोड़े गए वेक्टर से न्यूनतम हैमिंग दूरी d के अगले वेक्टर (शब्दकोषीय क्रम में) को जोड़कर उत्पन्न किया जाता है। उदाहरण के लिए, न्यूनतम दूरी 2 की लंबाई-3 लेक्सिकोड में निम्नलिखित उदाहरण में X द्वारा चिह्नित वेक्टर सम्मिलित होंगे:

वेक्टर कोड में?
000 X
001
010
011 X
100
101 X
110 X
111

यहां D-बिट न्यूनतम हैमिंग दूरी द्वारा N-बिट लेक्सिकोड की एक तालिका है, जिसके परिणामस्वरूप अधिकतम 2m कोडवर्ड डिक्शनरी है।

उदाहरण के लिए, F4 कोड (n=4,d=2,m=3), विस्तारित हैमिंग कोड (n=8,d=4,m=4) और विशेष रूप से गोले कोड (n=24,d=8,m=12) निकटतम की तुलना में असाधारण सघनता दिखाता है।

n \ d 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
1 1
2 2 1
3 3 2 1
4 4 3 1 1
5 5 4 2 1 1
6 6 5 3 2 1 1
7 7 6 4 3 1 1 1
8 8 7 4 4 2 1 1 1
9 9 8 5 4 2 2 1 1 1
10 10 9 6 5 3 2 1 1 1 1
11 11 10 7 6 4 3 2 1 1 1 1
12 12 11 8 7 4 4 2 2 1 1 1 1
13 13 12 9 8 5 4 3 2 1 1 1 1 1
14 14 13 10 9 6 5 4 3 2 1 1 1 1 1
15 15 14 11 10 7 6 5 4 2 2 1 1 1 1 1
16 16 15 11 11 8 7 5 5 2 2 1 1 1 1 1 1
17 17 16 12 11 9 8 6 5 3 2 2 1 1 1 1 1 1
18 18 17 13 12 9 9 7 6 3 3 2 2 1 1 1 1 1 1
19 19 18 14 13 10 9 8 7 4 3 2 2 1 1 1 1 1 1
20 20 19 15 14 11 10 9 8 5 4 3 2 2 1 1 1 1 1
21 21 20 16 15 12 11 10 9 5 5 3 3 2 2 1 1 1 1
22 22 21 17 16 12 12 11 10 6 5 4 3 2 2 1 1 1 1
23 23 22 18 17 13 12 12 11 6 6 5 4 2 2 2 1 1 1
24 24 23 19 18 14 13 12 12 7 6 5 5 3 2 2 2 1 1
25 25 24 20 19 15 14 12 12 8 7 6 5 3 3 2 2 1 1
26 26 25 21 20 16 15 12 12 9 8 7 6 4 3 2 2 2 1
27 27 26 22 21 17 16 13 12 9 9 7 7 5 4 3 2 2 2
28 28 27 23 22 18 17 13 13 10 9 8 7 5 5 3 3 2 2
29 29 28 24 23 19 18 14 13 11 10 8 8 6 5 4 3 2 2
30 30 29 25 24 19 19 15 14 12 11 9 8 6 6 5 4 2 2
31 31 30 26 25 20 19 16 15 12 12 10 9 6 6 6 5 3 2
32 32 31 26 26 21 20 16 16 13 12 11 10 7 6 6 6 3 3
33 ... 32 ... 26 ... 21 ... 16 ... 13 ... 11 ... 7 ... 6 ... 3

सभी अयुग्म D-बिट लेक्सिकोड दूरियां अंतिम आयाम को घटाकर सम d+1 बिट दूरियों की सटीक प्रतियां हैं,

इसलिए एक अयुग्म-आयामी स्थान उपरोक्त d+1 सम-आयामी स्थान की तुलना में कभी भी कुछ नया या अधिक चित्ताकर्षक नहीं बना सकता है।

चूंकि लेक्सिकोड्स रैखिक होते हैं, इसलिए उनका निर्माण उनके आधार के माध्यम से भी किया जा सकता है।[3]


कार्यान्वयन

निम्नलिखित C लेक्सिकोग्राफ़िक कोड को उत्पन्न करता है, और गोले कोड (N = 24, डी = 8) के लिए पैरामीटर समुच्चय किए जाते हैं। 

#include <stdio.h>
#include <stdlib.h>
int main() {                /* GOLAY CODE generation */
    int i, j, k;                                                                    
                                                                                    
    int _pc[1<<16] = {0};         // PopCount Macro
    for (i=0; i < (1<<16); i++)                                                     
    for (j=0; j < 16; j++)                                                          
        _pc[i] += (i>>j)&1;
#define pc(X) (_pc[(X)&0xffff] + _pc[((X)>>16)&0xffff])
                                                                                    
#define N 24 // N bits
#define D 8  // D bits distance
    unsigned int * z = malloc(1<<29);
    for (i=j=0; i < (1<<N); i++)      
    {                             // Scan all previous
        for (k=j-1; k >= 0; k--)  // lexicodes.
            if (pc(z[k]^i) < D)   // Reverse checking
                break;            // is way faster...
                                                                                    
        if (k == -1) {            // Add new lexicode
            for (k=0; k < N; k++) // & print it
                printf("%d", (i>>k)&1);                                             
            printf(" : %d\n", j);                                                   
            z[j++] = i;                                                             
        }                                                                           
    }                                                                               
}

कॉम्बिनेटोरियल गेम थ्योरी

लेक्सिकोग्राफ़िक कोड का सिद्धांत कॉम्बिनेटरियल खेल सिद्धांत से निकटता से जुड़ा हुआ है। विशेष रूप से, दूरी d के बाइनरी लेक्सिकोग्राफ़िक कोड में कोडवर्ड ग्रुंडी के खेल के एक प्रकार में जीतने वाली स्थिति को कूटबद्ध करते हैं, जो पत्थरों के ढेर के संग्रह पर खेला जाता है, जिसमें प्रत्येक चाल में किसी एक ढेर को अधिकतम d - 1 लघु से प्रतिस्थापित करना होता है , और लक्ष्य आखिरी पत्थर लेना होता है।[2]


टिप्पणियाँ

  1. ↑ Levenšteĭn, V. I. (1960), "Об одном классе систематических кодов" [A class of systematic codes], Doklady Akademii Nauk SSSR (in Russian), 131 (5): 1011–1014, MR 0122629{{citation}}: CS1 maint: unrecognized language (link); English translation in Soviet Math. Doklady 1 (1960), 368–371
  2. ↑ 2.0 2.1 2.2 Conway, John H.; Sloane, N. J. A. (1986), "Lexicographic codes: error-correcting codes from game theory", IEEE Transactions on Information Theory, 32 (3): 337–348, doi:10.1109/TIT.1986.1057187, MR 0838197
  3. ↑ Trachtenberg, Ari (2002), "Designing lexicographic codes with a given trellis complexity", IEEE Transactions on Information Theory, 48 (1): 89–100, doi:10.1109/18.971740, MR 1866958


बाहरी संबंध

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=लेक्सिकोग्राफ़िक_कोड&oldid=253228’