A qary, 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 = {0} and greedily adds, until exhaustion, the lexicographically earliest vector 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 lefttoright across the figure.
This greedy construction always generates a linear code [3,5,9]. Thus, we may completely describe a dimension k lexicode by finding k basis vectors (known as ``generators'') using what we call the lexicographic construction. This construction starts with the zero code and greedily adds the lexicographically earliest vector of distance d from the linear space spanned by the previously added vectors; k such iterations form the dimension k code . Table 1 demonstrates this construction for d = 3; the resulting code is a (7, 4, 3) binary code, meaning that it has length 7, dimension 4, and minimum distance 3.

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 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 :The 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 a dimension k, minimum distance d lexicode. From the definition of the lexicographic construction, _{k + 1}^{d} has parameters (n + d  , k + 1, d ), where is the covering radius of _{k}^{d}. Consider the (n + d  , k', d ) lexicode constructed by repeatedly choosing the appropriate lexicographicallyearliest vectors in _{q}^{n + d  }. 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 and, since is linear, .In addition, any vector v_{q}^{n + d  } that is in but not in _{k + 1}^{d} would necessarily have its n rightmost bits at distance from _{k + 1}^{d}, and its other bits at distance from _{k + 1}^{d}. Noting 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
This contradicts our constructive definition of , so it must be that .
For the converse assertion of the theorem, we
need to show that a nontrivial (n, k, d ) lexicode
can be
constructed by the lexicographic construction. The code
_{k}^{d}
produced by k iterations of the minimumdistance 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 nontrivial^{5} dimension k codes, so
it follows that they must be equal.
width4pt depth2pt height6pt
Theorem 1 allows us to bypass the codewordbycodeword lexicode construction, and instead directly compute the generator matrix of a desired lexicode.