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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणों के साथ लोभ से उत्पन्न [[त्रुटि-सुधार कोड]] हैं। इनका निर्माण स्वतंत्र रूप से किया गया था
लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणों के साथ आतुरतापुर्वक से उत्पन्न [[त्रुटि-सुधार कोड]] हैं। इनका निर्माण स्वतंत्र रूप से किया गया था।


व्लादिमीर लेवेनशेटिन<ref>{{citation
व्लादिमीर लेवेनशेटिन<ref>{{citation
Line 58: Line 58:
|
|
|}
|}
यहां 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) निकटतम की तुलना में असाधारण सघनता दिखाता है।
Line 777: Line 777:


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


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


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


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


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




Revision as of 16:37, 13 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=253019’