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.
Parent
Children
- \([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 [3][4; pg. 327].
- Tetracode — The tetracode is a lexicode [2].
Cousins
- Linear binary code — Binary lexicodes are linear [2].
- Lattice-based code — Lexicographic codes are \(q\)-ary analogues of laminated lattices [5][4; 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].
- Golay code — The extended Golay code is a lexicode [2,6][4; pg. 327].
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]
- R. A. Wilson, On lexicographic codes of minimal distance 4, Atti Sem. Mat. Fis. Univ. Modena 33 (1984)
- [4]
- F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes. Elsevier, 1977.
- [5]
- G. Hoehn, “Self-dual Codes over the Kleinian Four Group”, (2000) arXiv:math/0005266
- [6]
- M. J. T. Guy, unpublished.
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