Lexikografisk kod

Lexikografiska koder eller lexikon är girigt genererade felkorrigerande koder med anmärkningsvärt goda egenskaper. De producerades oberoende av Vladimir Levenshtein och av John Horton Conway och Neil Sloane . De binära lexikografiska koderna är linjära koder och inkluderar Hamming-koderna och de binära Golay-koderna .

Konstruktion

En lexikon med längden n och minsta avstånd d över ett ändligt fält genereras genom att börja med vektorn helt noll och iterativt addera nästa vektor (i lexikografisk ordning ) med minsta Hamming-avstånd d från de vektorer som lagts till hittills. Som ett exempel skulle längd-3-lexikonet för minsta avstånd 2 bestå av vektorerna markerade med ett "X" i följande exempel:

Vektor I koden?
000 X
001
010
011 X
100
101 X
110 X
111


Här är en tabell över alla n-bitars lexikon efter d-bits minimala hammingsavstånd, vilket resulterar i maximalt 2 m kodordslexikon. Till exempel F 4- kod (n=4,d=2,m=3), utökad Hamming-kod (n=8,d=4,m=4) och speciellt Golay-kod (n=24,d=8,m =12) visar exceptionell kompakthet jämfört med grannar.

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

Alla udda d-bitars lexikonavstånd är exakta kopior av de jämna d+1 bitarnas avstånd minus den sista dimensionen, så ett udda dimensionellt utrymme kan aldrig skapa något nytt eller mer intressant än det d+1 jämndimensionella utrymmet ovan.


Eftersom lexikon är linjära kan de också konstrueras med hjälp av sin bas .

Genomförande

Följande C genererar lexikografisk kod och parametrar ställs in för Golay-koden (N=24, D=8).

 
 
                  
                                                                           
                                                                                    
       0         
     0                                                         
     0                                                              
          

                                                                                    


         
     0          
                                 
            0   
                  
                            
                                                                                    
                        
             0     
                                                              
                                                                
                                                                           
                                                                                   
                                                                                   
 #include  <stdio.h>  #include  <stdlib.h>  int  main  ()  {  /* GOLAY CODE generation */  int  i  ,  j  ,  k  ;  int  _pc  [  1  <<  16  ]  =  {  };  // PopCount Makro  för  (  i  =  ;  i  <  (  1  <<  16  );  i  ++  )  för  (  j  =  ;  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  =  ;  i  <  (  1  <<  N  );  i  ++  )  {  // Skanna alla tidigare  för  (  k  =  j  -1  ;  k  >=  ;  k  --  )  // lexikon.  if  (  pc  (  z  [  k  ]  ^  i  )  <  D  )  // Omvänd  kontrollbrytning  ;  // är mycket snabbare...  if  (  k  ==  -1  )  {  // Lägg till ny lexikon  för  (  k  =  ;  k  <  N  ;  k  ++  )  // & skriv ut  printf  (  "%d"  ,  (  i  > >  k  )  &  1  );  printf  (  " : %d  \n  "  ,  j  );  z  [  j  ++  ]  =  i  ;  }  }  }

Kombinatorisk spelteori

Teorin om lexikografiska koder är nära kopplad till kombinatorisk spelteori . Framför allt kodar kodorden i en binär lexikografisk kod av distans d de vinnande positionerna i en variant av Grundys spel , som spelas på en samling stenhögar, där varje drag består av att ersätta valfri hög med högst d − 1 mindre högar, och målet är att ta den sista stenen.

Anteckningar

  1. ^ Levenšteĭn, VI (1960), "Об одном классе систематических кодов" [En klass av systematiska koder], Doklady Akademii Nauk SSSR (på ryska), 131 ( 5): 1011–1014, 1011–1012, 9014   ; Engelsk översättning i sovjetisk matematik. Doklady 1 (1960), 368–371
  2. ^ a b c   Conway, John H. ; Sloane, NJA (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 08381977
  3. ^   Trachtenberg, Ari (2002), "Designing lexicography codes with a given trellis complexity", IEEE Transactions on Information Theory , 48 (1): 89–100, doi : 10.1109/18.971740 , MR 1866958

externa länkar

Hämtad från " https://en.wikipedia.org/w/index.php?title=Lexicographic_code&oldid=1091904251 "