Lexicographic code

Lexicographic codes or lexicodes are greedily generated error-correcting codes with remarkably good properties. They were produced independently by Vladimir Levenshtein[1] and by John Horton Conway and Neil Sloane.[2] The binary lexicographic codes are linear codes, and include the Hamming codes and the binary Golay codes.[2]

Construction

A lexicode of minimum distance d and length n over a finite field is generated by starting with the all-zero vector and iteratively adding the next vector (in lexicographic order) of minimum Hamming distance d from the vectors added so far. As an example, the length-3 lexicode of minimum distance 2 would consist of the vectors marked by an "X" in the following example:

Vector In code?
000 X
001
010
011 X
100
101 X
110 X
111

Since lexicodes are linear, they can also be constructed by means of their basis.[3]

Combinatorial game theory

The theory of lexicographic codes is closely connected to combinatorial game theory. In particular, the codewords in a binary lexicographic code of distance d encode the winning positions in a variant of Grundy's game, played on a collection of heaps of stones, in which each move consists of replacing any one heap by at most d − 1 smaller heaps, and the goal is to take the last stone.[2]

Notes
  1. Levenšteĭn, V. I. (1960), "Об одном классе систематических кодов" [A class of systematic codes], Doklady Akademii Nauk SSSR (in Russian), 131 (5): 1011–1014, MR 0122629; English translation in Soviet Math. Doklady 1 (1960), 368–371
  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
gollark: It is possible to make it use memory for storage though.
gollark: Blame the establishment.
gollark: It's the only thing most people actually remember him making, though.
gollark: I connected a closed timelike curve to the osmarks.tk central server.
gollark: Yes, I get most of my information from the future.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.