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
_{q}^{n}) 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
_{q}^{n}. In other words, is the
maximum distance of a vector in
_{q}^{n} 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
_{2}^{3} 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
1^{d-}, 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-trivial^{2.1}linear codes generated by the lexicographic construction described
above are precisely the lexicodes.

**Proof. **We first prove that
_{k}^{d} 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
_{k}^{d} is the same as the (*n*, *k*, *d* )
lexicode
. From the definition of the lexicographic
construction,
_{k+1}^{d} has parameters
(*n* + , *k* + 1, *d* ), where
is the covering radius of
_{k}^{d}.
Consider the
(*n* + , *k'*, *d* ) lexicode
constructed by
repeatedly choosing the appropriate lexicographically-earliest vectors
in
_{q}^{n+}. Clearly, we generate
in the
process of this construction, so that
and, by
the inductive hypothesis,
. Moreover,
the vector

In addition, any vector
*v*_{q}^{n+} that is in
but not in
_{k+1}^{d} would necessarily have its *n*
right-most bits at
distance from
_{k+1}^{d}, and its other bits at distance
from
_{k+1}^{d}, 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+1}^{d} (and consequently also
) must be at most

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
_{k}^{d}
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.