Lexikographischer Code - Lexicographic code
Lexikografische Codes oder Lexikoden sind gierig erzeugte Fehlerkorrekturcodes mit bemerkenswert guten Eigenschaften. Sie wurden unabhängig von Vladimir Levenshtein sowie von John Horton Conway und Neil Sloane produziert . Die binären lexikografischen Codes sind lineare Codes und umfassen die Hamming-Codes und die binären Golay-Codes .
Konstruktion
Ein Lexikode mit minimalem Abstand d und Länge n über einem endlichen Feld wird erzeugt, indem mit dem All-Null-Vektor begonnen und iterativ der nächste Vektor (in lexikographischer Reihenfolge ) mit minimalem Hamming-Abstand d von den bisher hinzugefügten Vektoren hinzugefügt wird. Beispielsweise würde der Lexikode der Länge 3 des Mindestabstands 2 aus den Vektoren bestehen, die im folgenden Beispiel mit einem "X" gekennzeichnet sind:
Vektor In Code? 000 X. 001 010 011 X. 100 101 X. 110 X. 111
Da Lexikoden linear sind, können sie auch anhand ihrer Basis konstruiert werden .
Kombinatorische Spieltheorie
Die Theorie der lexikografischen Codes ist eng mit der kombinatorischen Spieltheorie verbunden . Insbesondere codieren die Codewörter in einem binären lexikografischen Code der Entfernung d die Gewinnpositionen in einer Variante von Grundys Spiel , das auf einer Sammlung von Steinhaufen gespielt wird, wobei jeder Zug darin besteht, einen Haufen durch höchstens d - 1 kleiner zu ersetzen Haufen, und das Ziel ist es, den letzten Stein zu nehmen.
Anmerkungen
- ^ Levenšteĭn, VI (1960), "ladб одном классе систематических кодов" [Eine Klasse systematischer Codes], Doklady Akademii Nauk SSSR (in russischer Sprache), 131 (5): 1011–1014, MR 0122629;; Englische Übersetzung in sowjetischer Mathematik. Doklady 1 (1960), 368–371
- ^ a b c Conway, John H . ; Sloane, NJA (1986), "Lexikografische Codes: Fehlerkorrekturcodes aus der Spieltheorie", IEEE Transactions on Information Theory , 32 (3): 337–348, doi : 10.1109 / TIT.1986.1057187 , MR 0838197
- ^ Trachtenberg, Ari (2002), "Entwerfen von lexikografischen Codes mit einer gegebenen Gitterkomplexität", IEEE Transactions on Information Theory , 48 (1): 89–100, doi : 10.1109 / 18.971740 , MR 1866958
