लेक्सिकोग्राफ़िक कोड: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| (5 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 12: | 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> और [[जॉन हॉर्टन कॉनवे]] और [[नील स्लोएन]] | | 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 22: | 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> बाइनरी लेक्सिकोग्राफ़िक कोड [[रैखिक कोड]] होते हैं, और इसमें [[हैमिंग कोड]] और [[ बाइनरी भाषा में कोड | बाइनरी | | year = 1986}}</ref> बाइनरी लेक्सिकोग्राफ़िक कोड [[रैखिक कोड]] होते हैं, और इसमें [[हैमिंग कोड]] और [[ बाइनरी भाषा में कोड | बाइनरी गोले कोड]] सम्मिलित होते हैं।<ref name="conslo" /> | ||
== निर्माण == | == निर्माण == | ||
एक [[परिमित क्षेत्र]] पर अवधि n और न्यूनतम दूरी d का एक लेक्सिकोड ऑल-जीरो | एक [[परिमित क्षेत्र]] पर अवधि n और न्यूनतम दूरी d का एक लेक्सिकोड ऑल-जीरो वेक्टर से प्रारंभ करके और अब तक जोड़े गए वेक्टर से न्यूनतम [[हैमिंग दूरी]] d के अगले वेक्टर ([[शब्दकोषीय क्रम]] में) को जोड़कर उत्पन्न किया जाता है। उदाहरण के लिए, न्यूनतम दूरी 2 की लंबाई-3 लेक्सिकोड में निम्नलिखित उदाहरण में X द्वारा चिह्नित वेक्टर सम्मिलित होंगे: | ||
:{| class="wikitable" | :{| class="wikitable" | ||
|- | |- | ||
! | !वेक्टर | ||
!कोड में? | !कोड में? | ||
|- | |- | ||
| Line 58: | Line 57: | ||
| | | | ||
|} | |} | ||
यहां D-बिट न्यूनतम हैमिंग दूरी द्वारा | यहां D-बिट न्यूनतम हैमिंग दूरी द्वारा N-बिट लेक्सिकोड की एक तालिका है, जिसके परिणामस्वरूप अधिकतम 2<sup>m</sup> कोडवर्ड डिक्शनरी है। | ||
उदाहरण के लिए, F<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) निकटतम की तुलना में असाधारण सघनता दिखाता है। | ||
| Line 777: | Line 776: | ||
|} | |} | ||
सभी | सभी अयुग्म D-बिट लेक्सिकोड दूरियां अंतिम आयाम को घटाकर सम d+1 बिट दूरियों की सटीक प्रतियां हैं, | ||
एक | इसलिए एक अयुग्म-आयामी स्थान उपरोक्त d+1 सम-आयामी स्थान की तुलना में कभी भी कुछ नया या अधिक चित्ताकर्षक नहीं बना सकता है। | ||
चूंकि लेक्सिकोड्स रैखिक होते हैं, इसलिए उनका निर्माण उनके आधार | चूंकि लेक्सिकोड्स रैखिक होते हैं, इसलिए उनका निर्माण उनके आधार के माध्यम से भी किया जा सकता है।<ref>{{citation | ||
| last = Trachtenberg | first = Ari | | last = Trachtenberg | first = Ari | ||
| doi = 10.1109/18.971740 | | doi = 10.1109/18.971740 | ||
| Line 794: | Line 793: | ||
== कार्यान्वयन == | == कार्यान्वयन == | ||
निम्नलिखित C लेक्सिकोग्राफ़िक कोड उत्पन्न करता है और गोले कोड (N = 24, डी = 8) के लिए पैरामीटर समुच्चय किए जाते हैं। | निम्नलिखित C लेक्सिकोग्राफ़िक कोड को उत्पन्न करता है, और गोले कोड (N = 24, डी = 8) के लिए पैरामीटर समुच्चय किए जाते हैं। | ||
<syntaxhighlight lang="c"> | <syntaxhighlight lang="c"> | ||
#include <stdio.h> | #include <stdio.h> | ||
| Line 827: | Line 826: | ||
== [[कॉम्बिनेटरियल गेम थ्योरी|कॉम्बिनेटोरियल गेम थ्योरी]] == | == [[कॉम्बिनेटरियल गेम थ्योरी|कॉम्बिनेटोरियल गेम थ्योरी]] == | ||
लेक्सिकोग्राफ़िक कोड का सिद्धांत कॉम्बिनेटरियल | लेक्सिकोग्राफ़िक कोड का सिद्धांत कॉम्बिनेटरियल खेल सिद्धांत से निकटता से जुड़ा हुआ है। विशेष रूप से, दूरी d के बाइनरी लेक्सिकोग्राफ़िक कोड में कोडवर्ड ग्रुंडी के खेल के एक प्रकार में जीतने वाली स्थिति को कूटबद्ध करते हैं, जो पत्थरों के ढेर के संग्रह पर खेला जाता है, जिसमें प्रत्येक चाल में किसी एक ढेर को अधिकतम d - 1 लघु से प्रतिस्थापित करना होता है , और लक्ष्य आखिरी पत्थर लेना होता है।<ref name="conslo" /> | ||
| Line 839: | 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: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]
टिप्पणियाँ
- ↑ 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.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
- ↑ 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
