Lexicographic codes or lexicodes are greedily generated
error-correcting code
In computing, telecommunication, information theory, and coding theory, an error correction code, sometimes error correcting code, (ECC) is used for controlling errors in data over unreliable or noisy communication channels. The central idea is ...
s with remarkably good properties. They were produced independently by
Vladimir Levenshtein
Vladimir Iosifovich Levenshtein ( rus, Влади́мир Ио́сифович Левенште́йн, p=vlɐˈdʲimʲɪr ɨˈosʲɪfəvʲɪtɕ lʲɪvʲɪnˈʂtʲejn, a=Ru-Vladimir Iosifovich Levenstein.oga; 20 May 1935 – 6 September 2017) was a ...
and by
John Horton Conway
John Horton Conway (26 December 1937 – 11 April 2020) was an English mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches ...
and
Neil Sloane
__NOTOC__
Neil James Alexander Sloane (born October 10, 1939) is a British-American mathematician. His major contributions are in the fields of combinatorics, error-correcting codes, and sphere packing. Sloane is best known for being the creator ...
.
The binary lexicographic codes are
linear code In coding theory, a linear code is an error-correcting code for which any linear combination of codewords is also a codeword. Linear codes are traditionally partitioned into block codes and convolutional codes, although turbo codes can be seen as ...
s, and include the
Hamming code
In computer science and telecommunication, Hamming codes are a family of linear error-correcting codes. Hamming codes can detect one-bit and two-bit errors, or correct one-bit errors without detection of uncorrected errors. By contrast, the sim ...
s and the
binary Golay code
In mathematics and electronics engineering, a binary Golay code is a type of linear error-correcting code used in digital communications. The binary Golay code, along with the ternary Golay code, has a particularly deep and interesting connection ...
s.
[
]
Construction
A lexicode of length ''n'' and minimum distance ''d'' over a finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
is generated by starting with the all-zero vector and iteratively adding the next vector (in lexicographic order
In mathematics, the lexicographic or lexicographical order (also known as lexical order, or dictionary order) is a generalization of the alphabetical order of the dictionaries to sequences of ordered symbols or, more generally, of elements of a ...
) of minimum Hamming distance
In information theory, the Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. In other words, it measures the minimum number of ''substitutions'' required to chan ...
''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:
:
Here is a table of all n-bit lexicode by d-bit minimal hamming distance, resulting of maximum 2m codewords dictionnary.
For example, F4 code (n=4,d=2,m=3), extended Hamming code (n=8,d=4,m=4) and especially Golay code (n=24,d=8,m=12) shows exceptional compactness compared to neighbors.
:
All odd d-bit lexicode distances are exact copies of the even d+1 bit distances minus the last dimension, so
an odd-dimensional space can never create something new or more interesting than the d+1 even-dimensional space above.
Since lexicodes are linear, they can also be constructed by means of their basis.
Implementation
Following C generate lexicographic code and parameters are set for the Golay code (N=24, D=8).
#include
#include
int main()
Combinatorial game theory
The theory of lexicographic codes is closely connected to combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
. In particular, the codewords in a binary lexicographic code of distance ''d'' encode the winning positions in a variant of Grundy's game
Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two ...
, 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.[
]
Notes
External links
Bob Jenkins table of binary lexicodes
*{{OEIS el, sequencenumber=A075928, name=List of codewords in binary lexicode with Hamming distance 4 written as decimal numbers.
Trellises and Factor Graphs
Error detection and correction