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

From alpha
Jump to navigation Jump to search
(Created page with "लेक्सिकोग्राफ़िक कोड या लेक्सिकोड्स उल्लेखनीय रूप से अच्छे गुणो...")
 
Line 21: Line 21:
  | 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 लेक्सिकोड में निम्नलिखित उदाहरण में एक्स द्वारा चिह्नित वेक्टर शामिल होंगे:
एक [[परिमित क्षेत्र]] पर लंबाई एन और न्यूनतम दूरी डी का एक लेक्सिकोड ऑल-जीरो सदिश से शुरू करके और अब तक जोड़े गए सदिश से न्यूनतम [[हैमिंग दूरी]] डी के अगले सदिश ([[शब्दकोषीय क्रम]] में) को जोड़कर उत्पन्न किया जाता है। उदाहरण के तौर पर, न्यूनतम दूरी 2 की लंबाई-3 लेक्सिकोड में निम्नलिखित उदाहरण में एक्स द्वारा चिह्नित सदिश सम्मिलित होंगे:


:{| class="wikitable"
:{| class="wikitable"
Line 56: Line 56:
|
|
|}
|}
यहां डी-बिट न्यूनतम हैमिंग दूरी द्वारा सभी एन-बिट लेक्सिकोड की एक तालिका है, जिसके परिणामस्वरूप अधिकतम 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 775:


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


Line 790: Line 791:


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

Revision as of 22:32, 5 August 2023

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


निर्माण

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

Vector In code?
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]


कार्यान्वयन

निम्नलिखित सी लेक्सिकोग्राफ़िक कोड उत्पन्न करता है और गोले कोड (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;                                                             
        }                                                                           
    }                                                                               
}


कॉम्बिनेटरियल गेम थ्योरी सिद्धांत = लेक्सिकोग्राफ़िक कोड का सिद्धांत कॉम्बिनेटरियल गेम सिद्धांत से निकटता से जुड़ा हुआ है। विशेष रूप से, दूरी डी के बाइनरी लेक्सिकोग्राफ़िक कोड में कोडवर्ड ग्रुंडी के खेल के एक प्रकार में जीतने वाली स्थिति को कूटबद्ध करते हैं, जो पत्थरों के ढेर के संग्रह पर खेला जाता है, जिसमें प्रत्येक चाल में किसी एक ढेर को अधिकतम डी - 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://alpha.indicwiki.in/index.php?title=लेक्सिकोग्राफ़िक_कोड&oldid=274841"