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 v$\mbox{$\,\inn\,$}$$\mathbb {F}$₂ⁿ, is the leader of the coset containing l + v. It is denoted $\kappa_{v}^{}$(l ), or $\kappa$(l ) in context.

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

Theorem 2..5   Consider an (n, k, d ) code $\ensuremath{\mathbb{C}}$ with a fixed set $\mathcal {S}$ of coset leaders, and the linear code $\ensuremath{\mathbb{C}}'$ spanned by $\ensuremath{\mathbb{C}}~\cup~\left\{ (1^{\Delta} \vert \lambda) \right\}$ for some $\lambda$$\mbox{$\,\inn\,$}$$\mathbb {F}$₂ⁿ and $\Delta$$\mbox{$\,\inn\,$}$$\mathbb {Z}$. Then the set $\mathcal {S}$' of coset leaders of $\ensuremath{\mathbb{C}}'$ can be obtained from $\mathcal {S}$ according to the following bijective correspondence:

$$\phi$$ : a, l$$\mbox{$\,\inn\,$}$$$$\mathcal {S}$$ $$\longmapsto$$ l'$$\mbox{$\,\inn\,$}$$$$\mathcal {S}$$'

where a$\mbox{$\,\inn\,$}${$\langle$0|$\mathbb {F}$₂^$\Delta$-1$\rangle$} and l' is defined by the property

l' = $$\left\{\vphantom{ \begin{array}{lr} \langle a\vert l\rangle& \te... ...} \left\langle \bar{a}\vert\kappa_\lambda(l) \right\rangle. \end{array}}\right.$$$$\begin{array}{lr} \langle a\vert l\rangle& \text{if } \ensuremat... ...name{wt}} \left\langle \bar{a}\vert\kappa_\lambda(l) \right\rangle. \end{array}$$

Figure 2.6 demonstrates the use of the $\phi$ correspondence to generate the coset leaders of the (7, 3, 4) binary lexicode $\ensuremath{\mathcal{L}_{4}^{3}}$ from the coset leaders of the (6, 2, 4) binary lexicode $\ensuremath{\mathcal{L}_{4}^{2}}$ over the base field $\mathbb {F}$₂. Specifically, in this example, $\lambda = \ensuremath{f_{\mbox{\small lexi}}}(\ensuremath{\mathcal{L}_{4}^{2}}) = 001011$ and $\Delta=d-\ensuremath{\operatorname{wt}}(\lambda)=4-3=1$ The coset leaders of $\ensuremath{\mathcal{L}_{4}^{2}}$ are

l$$\mbox{$\,\inn\,$}$$S = {0, 1, 10, 100, 1000, 10000, 100000, 10010}

and the resulting coset leaders of $\ensuremath{\mathcal{L}_{4}^{3}}$ are

l'$$\mbox{$\,\inn\,$}$$S' = {0, 1, 10, 100, 1000, 10000, 100000, 1000000}

Figure 2.6: A list of coset leaders of the (7, 3, 4) lexicode. It is derived from the coset leaders of the (6, 2, 4) lexicode using Theorem 2.5 with $\lambda$ = 010010 and $\Delta$ = 1. Spaces between bits are used to highlight concatenations.

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

$$\mbox{$\stackrel{\rm def}{=}$} \langle \rangle \mbox{$\stackrel{\rm def}{=}$} \left\langle\vphantom{ \bar{a}~\vert~\kappa_\lambda(l)}\right. \bar{{a}} \kappa_{\lambda}^{} \left.\vphantom{ \bar{a}~\vert~\kappa_\lambda(l)}\right\rangle$$ (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 $\ensuremath{\mathbb{C}}'$. This is clear because:

$$\langle \left[\vphantom{ a+\bar{a} }\right. \bar{{a}} \left.\vphantom{ a+\bar{a} }\right] \left[\vphantom{ l+ \kappa(l) }\right. \kappa \left.\vphantom{ l+ \kappa(l) }\right] \rangle$$ g(a, l )  +  h(a, l )

$$\langle \Delta \left[\vphantom{ l+ (l+\lambda+c) }\right. \lambda \left.\vphantom{ l+ (l+\lambda+c) }\right] \rangle \mbox{$\,\inn\,$} \mathbb {C}$$

$$= \ \left\langle 1^\Delta \mid \lambda\right\rangle + \left\langle 0^\Delta \mid c\right\rangle$$

$$\mbox{$\,\inn\,$}\ensuremath{\mathbb{C}}'$$

Here $\Delta$ 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 $\ensuremath{\mathbb{C}}'$. More specifically, these two vectors are in the same coset precisely when l and l' are in distinct cosets of  $\ensuremath{\mathbb{C}}$ and $\bar{{a}}$ $\not=$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^$\Delta$ nor 1^$\Delta$. Alternatively, its leading bits are 0^$\Delta$ but its trailing bits are the sum of distinct coset leaders $l+ l' \not\inn \ensuremath{\mathbb{C}}$. Both possibilities preclude g(a, l )+ g(a', l') from being a codeword of $\ensuremath{\mathbb{C}}'$, 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 $\ensuremath{\mathbb{C}}'$. In fact, for each a$\mbox{$\,\inn\,$}$$\mathbb {F}$₂ⁿ and coset leader l of $\ensuremath{\mathbb{C}}$, the coset of g(a, l ) contains only the vectors:

$$\left\{\vphantom{ \begin{array}{l} \left\langle a \mid (l+c) \rig... ...e \\ \left\langle \bar{a} \mid (l+\lambda+c)\right\rangle \end{array}}\right.$$$$\begin{array}{l} \left\langle a \mid (l+c) \right\rangle \\ \left\langle \bar{a} \mid (l+\lambda+c)\right\rangle \end{array}$$

for any $c \mbox{$\,\inn\,$}\ensuremath{\mathbb{C}}$.

In addition, for any $c \mbox{$\,\inn\,$}\ensuremath{\mathbb{C}}$, g(a, l ) cannot have weight greater than the weight of $\left\langle\vphantom{ a\vert(l+c)}\right.$a|(l + c)$\left.\vphantom{ a\vert(l+c)}\right\rangle$, because l is a coset leader, and h(a, l ) cannot have weight greater than $\left\langle\vphantom{\bar{a}\vert(l+\lambda+c)}\right.$$\bar{{a}}$|(l + $\lambda$ + c)$\left.\vphantom{\bar{a}\vert(l+\lambda+c)}\right\rangle$. Thus, all the vectors in the coset containing g(a, l ) will have weight $\geq \min \{\ensuremath{\operatorname{wt}}(\operatorname{g}(a,l)),\ensuremath{\operatorname{wt}}(\operatorname{h}(a,l))\}$, so that either g(a, l ) or h(a, l ) must be a coset leader in $\ensuremath{\mathbb{C}}'$. Since g(a, l ) and h(a, l ) are correspondences, $\mathcal {S}$' is the complete set of coset leaders of $\mathcal {C}$'.

width4pt depth2pt height6pt