Lexikografický kód - Lexicographic code - Wikipedia
Lexikografické kódy nebo lexikody jsou generovány chamtivě kódy opravující chyby s pozoruhodně dobrými vlastnostmi. Byly vyrobeny samostatně společnostíVladimir Levenshtein[1] a tím John Horton Conway a Neil Sloane.[2] Binární lexikografické kódy jsou lineární kódy a zahrnují Hammingovy kódy a binární Golay kódy.[2]
Konstrukce
Lexikoda o minimální vzdálenosti d a délka n přes konečné pole je generován spuštěním nulového vektoru a opakovaným přidáním dalšího vektoru (v lexikografický řád ) minima Hammingova vzdálenost d z dosud přidaných vektorů. Například lexikáda délky 3 s minimální vzdáleností 2 by se skládala z vektorů označených v následujícím příkladu znakem „X“:
Vektor V kódu? 000 X 001 010 011 X 100 101 X 110 X 111
Vzhledem k tomu, že lexikódy jsou lineární, mohou být také konstruovány pomocí jejich základ.[3]
Kombinatorická teorie her
S teorií lexikografických kódů úzce souvisí kombinatorická teorie her. Zejména kódová slova v binárním lexikografickém kódu vzdálenosti d kódovat výherní pozice ve variantě Grundyho hra, hrál na hromadě hromád kamenů, ve kterých každý pohyb spočívá v nahrazení jakékoli hromádky maximálně d - 1 menší hromada a cílem je vzít poslední kámen.[2]
Poznámky
- ^ Levenšteĭn, V. I. (1960), „Об одном классе систематических кодов“ [Třída systematických kódů], Doklady Akademii Nauk SSSR (v Rusku), 131 (5): 1011–1014, PAN 0122629; Anglický překlad v Sovětská matematika. Doklady 1 (1960), 368–371
- ^ A b C Conway, John H.; Sloane, N. J. A. (1986), "Lexikografické kódy: kódy opravující chyby z teorie her", Transakce IEEE na teorii informací, 32 (3): 337–348, doi:10.1109 / TIT.1986.1057187, PAN 0838197
- ^ Trachtenberg, Ari (2002), „Navrhování lexikografických kódů s danou složitostí mřížoví“, Transakce IEEE na teorii informací, 48 (1): 89–100, doi:10.1109/18.971740, PAN 1866958