Lexicographic codes: Error-correcting codes from game theory

Author

Conway, John H. ; Sloane, N. J A

Volume

Issue

fYear

1986

fDate

5/1/1986 12:00:00 AM

Firstpage

337

Lastpage

348

Abstract

Lexicographic codes, or lexicodes, are defined by various versions of the greedy algorithm. The theory of these codes is closely related to the theory of certain impartial games, which leads to a number of surprising properties. For example, lexicodes over an alphabet of size $B=2^{a}$ are closed under addition, while if $B = 2^{2^{a}}$ the lexicodes are closed under multiplication by scalars, where addition and multiplication are in the nim sense explained in the text. Hamming codes and the binary Golay codes are lexieodes. Remarkably simple constructions are given for the Steiner systems $S(5,6,12)$ and $S(5,8,24)$ . Several record-breaking constant weight codes are also constructed.

Keywords

Error-correction coding; Constraint theory; Error correction codes; Game theory; Greedy algorithms; Hamming distance; Lattices; Mathematics; Statistics;

fLanguage

English

Journal_Title

Information Theory, IEEE Transactions on

Publisher

ieee

ISSN

0018-9448

Type

jour

DOI

10.1109/TIT.1986.1057187

Filename

1057187

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=941709