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: Of course not.
gollark: [REDACTED], obviously.
gollark: Or if they have orbital laser backup, like all modern bees do.
gollark: Protocol Π2-ψ being activated.Insert rhyme with activated after this:
gollark: Do not expose your bees to liberal thought. Bees know that the iron guide of the queen is good for the hive. But what happens if you make the bees socialist? What happens? They will overthrow the class system! They will say workers and soldiers are equal, even if it is not so! There will be hive anarchy everywhere! The bees will work for pleasure and not for the hive, which is very anarchistic! Socialism is bad for bees.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.