लेक्सिकोग्राफ़िक कोड

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

निर्माण

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

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

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

उदाहरण के लिए, F₄ कोड (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 सम-आयामी स्थान की तुलना में कभी भी कुछ नया या अधिक चित्ताकर्षक नहीं बना सकता है।

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

कार्यान्वयन

निम्नलिखित 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 लघु से प्रतिस्थापित करना होता है , और लक्ष्य आखिरी पत्थर लेना होता है।

बाहरी संबंध

• Bob Jenkins table of binary lexicodes
• On-line generator for lexicodes and their variants
• OEIS sequence A075928 (List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.)
• Error-Correcting Codes on Graphs: Lexicodes, Trellises and Factor Graphs