Generalization

The lexicographic construction may be extended to produce codes with desired characteristics using the generalized lexicographic construction, abbreviated G-construction. The G-construction replaces the ``lexicographically earliest'' heuristic used in building lexicodes with an arbitrary function. This allows us to generate arbitrary greedy codes in which various properties are grafted upon the good code parameters of the lexicodes. More formally,

Definition 1   The generalized lexicographic construction is boot-strapped with a linear (n, k, d ) seed code $\mathbb {C}$ and iteratively constructs the family of codes

$$G(f,\mathbb{C}) \ = \ \left\{ \ensuremath{ {\emph G}_{\,i} \... ...b{C} \right) }\, : \, i \mbox{$\,\inn\,$} \mathbb{Z} \right\}$$

using a mapping from codes to vectors:

$$\mathbb {C} \subseteq \mathbb {F} \longmapsto \mbox{$\,\inn\,$} \mathbb {F}$$ (9)

where we define

$$\mathbb {F}$$_q^* = $$\bigcup_{{i=1}}^{\infty}$$$$\mathbb {F}$$_qⁱ.

The construction follows the scheme:

• G ₀$\left(\vphantom{ f,\mathbb{C} }\right.$f,$\mathbb {C}$$\left.\vphantom{ f,\mathbb{C} }\right)$ is trivially the code $\mathbb {C}$
• G _i$\left(\vphantom{ f,\mathbb{C} }\right.$f,$\mathbb {C}$$\left.\vphantom{ f,\mathbb{C} }\right)$ is computed by adding to G _i-1$\left(\vphantom{ f,\mathbb{C} }\right.$f,$\mathbb {C}$$\left.\vphantom{ f,\mathbb{C} }\right)$ the generator

  $$\left(\vphantom{1^{\Delta_i} \biggm\vert \, \lambda_i \, }\right. \Delta_{i} \biggm\vert \lambda_{i}^{} \left.\vphantom{1^{\Delta_i} \biggm\vert \, \lambda_i \, }\right)$$ (9)

  
  
  where $\lambda_i = f\left(\ensuremath{ {\emph G}_{\,i-1}}\right)$ and $\Delta_i=d - \mbox{\textit{minimum Hamming distance from $\lambda_i$\ to the code \ensuremath{ {\emph G}_{\,i-1} \left( f,\mathbb{C} \right) }}}$.

We will call f ( ^. ) the generating mapping of the construction. The familiar lexicode family of minimum distance d is thus the simple special case $G(\ensuremath{f_{\mbox{\small lexi}}},\mathbb{S}_d)$, where we use the trivial seed code $\mathbb {S}$_d$\mbox{$\stackrel{\rm def}{=}$}${0^d, 1^d}. The code in Figure 2.2 is ${\mathfrak{G}}_{\,3} \left( \ensuremath{f_{\mbox{\small lexi}}},\mathbb{S}_3 \right)$, as can be verified by hand.

The G-construction serves to homogenize its seed code, since each iteration builds a subcode with the same minimum distance. Thus, there are many linear codes which do not fit into the mold of this construction. For example, the linear code given by the following generator matrix cannot be constructed with the G-construction:

1110000
0001111

For sake of simplicity we shall concern ourselves only with binary codes in the remainder of this chapter, though the extension to q-ary codes is fairly straighforward.