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