So far we have addressed the computation of various generating mappings. In this and subsequent sections we will complete our analysis by addressing the theoretical mechanism which supports the construction. Specifically, the construction establishes an important relationship between the coset leaders of the codes produced at successive iterations. This relationship allows us to efficiently compute the coset leaders of many codes (and hence their generator matrices) as well as to determine bounds on their code parameters. We describe this relationship by first associating a companion with each coset leader. Recall that a coset leader is a designated vector of minimum weight in a given coset.
We show that one iteration of the lexicographic construction produces a code whose coset leaders are either a u or (u) (depending on which has lower Hamming weight), for each vector a of appropriate size and coset leader u in the original code. Here refers to the complement of a.
Proof: We introduce the following notation to simplify the proof:
g(a, l ) + h(a, l )  = a +  l + (l )  
= 1^{}  l + (l + + c), forc  
The second observation of this proof is that g(a, l ) and g(a', l') are generally not in the same coset of . More specifically, these two vectors are in the same coset precisely when l and l' are in distinct cosets of and a'. To see this we analyze the two possibilities for the sum g(a, l )+ g(a', l'). In the first case, its leading bits are neither 0^{} nor 1^{}. Alternatively, its leading bits are 0^{} but its trailing bits are the sum of distinct coset leaders . Both possibilities preclude g(a, l )+ g(a', l') from being a codeword of , proving the observation.
Based on the above two observations, g(^{ . },^{ . }) and h(^{ . },^{ . }) represent the same twotoone correspondence between (vector, cosetleader) pairs (a, l ) and the cosets of . In fact, for each a_{2}^{n} and coset leader l of , the coset of g(a, l ) contains only the vectors:
In addition, for any
,
g(a, l ) cannot have weight
greater than the weight of
a(l + c), because l is
a coset leader, and
h(a, l ) cannot have weight greater than
(l + + c). Therefore, all the vectors
in the
coset containing
g(a, l ) will have weight not less than
[3]
, so that either
g(a, l ) or
h(a, l ) must be a coset leader in
. Since
g(a, l ) and
h(a, l ) are correspondences,
^{} is
the complete set of coset leaders of
.
width4pt depth2pt height6pt
Table 3 demonstrates the use of the correspondence of Theorem 3 to generate the coset leaders of the (7, 3, 4) binary lexicode from the coset leaders of the (6, 2, 4) binary lexicode . In essence, the correspondence indicates that the coset leaders of a code are augmented permutations of the coset leaders of its predecessor in the construction. One such permutation produces the lexicodes, whereas other permutations produce the various other codes described in this paper.
