Lexicographic code

Lexicographic code[1,2]

Description

A \(q\)-ary code whose codewords are constructed greedily and iteratively by starting with zero and adding codewords whose distance is the desired minimum distance of the code.

Cousins

Linear binary code— Binary lexicodes are linear [2].
Lattice-based code— Lexicographic codes are \(q\)-ary analogues of laminated lattices [4][3; pg. 162].
Combinatorial design— Some lexicodes yield Steiner systems [2].
Binary quadratic-residue (QR) code— The \([18,9,6]\) binary QR code is a lexicode [2].

Member of code lists

Primary Hierarchy

Parents

Lexicographic code

Children

\([24, 12, 8]\) Extended Golay code

The extended Golay code is a lexicode [2,5][3; pg. 327].

\([2^r-1,2^r-r-1,3]\) Hamming code

Hamming codes are lexicodes [2].

Single parity-check (SPC) code

SPCs are lexicodes [2].

Hexacode

Hexacodewords can be arranged in an order from smallest to largest, with each codeword differing at four places from the next [6][3; pg. 327].

Tetracode

The tetracode is a lexicode [2].

References

[1]: Levenshtein, V. I. (1960). A class of systematic codes. In Doklady Akademii Nauk (Vol. 131, No. 5, pp. 1011-1014). Russian Academy of Sciences.
[2]: J. Conway and N. Sloane, “Lexicographic codes: Error-correcting codes from game theory”, IEEE Transactions on Information Theory 32, 337 (1986) DOI
[3]: F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
[4]: G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
[5]: M. J. T. Guy, unpublished.
[6]: R. A. Wilson, On lexicographic codes of minimal distance 4, Atti Sem. Mat. Fis. Univ. Modena 33 (1984)

Page edit log

Victor V. Albert (2024-08-16) — most recent

Cite as:

“Lexicographic code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/lexicographic

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/q-ary_digits/lexicographic.yml.