# The lexicographic construction

A q-ary, length n, minimum distance d lexicode is traditionally defined constructively based on a lexicographic (i.e. dictionary) ordering of vectors in which, for example, 01111 comes before 10000. The construction starts with the set = { and greedily adds, until exhaustion, the lexicographically earliest vector (in the vector space qn) whose Hamming distance from is at least d.

For example, the codewords of the binary lexicode (i.e. q = 2) of length n = 3 and minimum distance d = 2 are marked by a in Figure  and would be computed left-to-right across the figure.

This greedy construction always generates a linear code [9,14]. Thus, we may completely describe a dimension k lexicode by finding its k generators using what we call the lexicographic construction. This construction starts with the zero code and greedily adds the lexicographically earliest generator of distance d from the code; k such iterations form the dimension k code . Figure 2.2 demonstrates this construction for d = 3, resulting in a (7, 4, 3) binary code.

We may understand the lexicographic construction more analytically by making use of the covering radius of each intermediate code in the iteration. The covering radius of a length n code is the smallest integer with the property that Hamming balls of radius centered at codewords of the code will cover every vector of qn. In other words, is the maximum distance of a vector in qn from the code. As an example, one can readily see that the binary lexicode in Figure 2.1 has a covering radius of 1 because every vector in 23 is at most of Hamming distance 1 from a code vector.

An iteration of the lexicographic construction on an intermediate code whose covering radius is and minimum distance is d can thus be understood as the addition of a generator vector:

where 1d-, known as the generator padding, has the usual meaning of (d - ) successive 1's, and the function returns the lexicographically earliest vector of distance from . As is customary, we use . | . to denote concatenation.

It is not surprising that the non-trivial2.1linear codes generated by the lexicographic construction described above are precisely the lexicodes.

Theorem 2..1   Over a finite field q, a non-trivial (n, k, d ) code is a lexicode if and only if it is produced by the lexicographic construction, namely .

Proof.  We first prove that kd is always a lexicode, by induction on k for an arbitrary, fixed d. For the base case it is clear that is a (d, 1, d ) lexicode. Now assume as an inductive hypothesis that kd is the same as the (n, k, d ) lexicode  . From the definition of the lexicographic construction, k+1d has parameters (n + , k + 1, d ), where is the covering radius of kd. Consider the (n + , k', d ) lexicode constructed by repeatedly choosing the appropriate lexicographically-earliest vectors in qn+. Clearly, we generate in the process of this construction, so that and, by the inductive hypothesis, . Moreover, the vector

is the lexicographically earliest vector of distance from . Thus, it must be the case that vCk' and, since Ck' is linear, .

In addition, any vector vqn+ that is in but not in k+1d would necessarily have its n right-most bits at distance from k+1d, and its other bits at distance from k+1d, as we can see in Figure 2.3. Noting that our non-triviality assumption implies that < d, we may now use the triangle inequality to see that the distance from v to k+1d (and consequently also ) must be at most

This contradicts our constructive definition of  , so it must be that .

For the converse assertion of the theorem, we need to show that a non-trivial (n, k, d ) lexicode can be constructed by the lexicographic construction. The code kd produced by k iterations of the minimum-distance d lexicographic construction is clearly a lexicode, from the first part of the proof. Since all distance d lexicodes are ordered by inclusion, as we saw in the first part of this proof, we may conclude that either or . However and are both non-trivial dimension k codes, so it follows that they must be equal.

width4pt depth2pt height6pt

Theorem 2.1 allows us to bypass the codeword-by-codeword lexicode construction, and instead directly compute the generator matrix of a desired lexicode.

Subsections
http://people.bu.edu/trachten