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 two-to-one correspondence between (vector, coset-leader) pairs (a, l ) and the cosets of . In fact, for each a2n 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
g(a, l ) will have weight not less than
 , 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.