# Relation between cosets

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 G-construction. Specifically, the G-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 G-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.

Definition 2   The companion of a coset leader l, with respect to a vector v2n, is the leader of the coset containing l + v. It is denoted (l ), or (l ) in context.

We show that one iteration of the lexicographic construction produces a code whose coset leaders are the lower-weight vectors between a| u and |(u), for each vector a of appropriate size and coset leader u in the original code. Here refers to the complement of a.

Theorem 2..5   Consider an (n, k, d ) code with a fixed set of coset leaders, and the linear code spanned by for some 2n and . Then the set ' of coset leaders of can be obtained from according to the following bijective correspondence:

: al l''

where a{0|2-1} and l' is defined by the property

l' =

Figure 2.6 demonstrates the use of the correspondence to generate the coset leaders of the (7, 3, 4) binary lexicode from the coset leaders of the (6, 2, 4) binary lexicode over the base field 2. Specifically, in this example, and The coset leaders of are

lS = {0, 1, 10, 100, 1000, 10000, 100000, 10010}

and the resulting coset leaders of are

l'S' = {0, 1, 10, 100, 1000, 10000, 100000, 1000000}

Proof of Theorem 2.5 We introduce the following notation to simply the proof:

 g(a, l )  a | l and h(a, l )   | (l ). (9)

This proof then rests upon two observations. The first observation is that g(a, l ) and h(a, l ) are always in the same coset of the new code . This is clear because:

 g(a, l )  +  h(a, l ) =  a +   |  l + (l ) =  1   |  l + (l + + c), forc

Here is the padding value, as presented in the statement of the theorem.

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:

for any .

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). Thus, all the vectors in the coset containing g(a, l ) will have weight , 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

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