Generalization

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

$\begin{displaymath} \ensuremath{{\mathfrak{G}}}(f,\ensuremath{{\mathbb{C}}}) \ =... ... \right) }\, : \, i \mbox{$\,\inn\,$}\{0,1,2,\ldots\} \right\} \end{displaymath}$

using a mapping from codes to vectors:

f (^.) : $\displaystyle \mathbb {C}$ $\displaystyle \subseteq$ $\displaystyle \mathbb {F}$ _q^* $\displaystyle \longmapsto$ v $\displaystyle \mbox{$\,\inn\,$}$ $\displaystyle \mathbb {F}$ _q^*.

(1)

The construction follows the scheme:

$\mathfrak{G}_{0}^{}$ $\left(\vphantom{ f,{\mathbb{C}} }\right.$ f, $\mathbb {C}$ $\left.\vphantom{ f,{\mathbb{C}} }\right)$ is trivially the code $\ensuremath{{\mathbb{C}}}$ ;
$\mathfrak{G}_{i}^{}$ $\left(\vphantom{ f,{\mathbb{C}} }\right.$ f, $\mathbb {C}$ $\left.\vphantom{ f,{\mathbb{C}} }\right)$ is computed by adding to $\mathfrak{G}_{i-1}^{}$ $\left(\vphantom{ f,{\mathbb{C}} }\right.$ f, $\mathbb {C}$ $\left.\vphantom{ f,{\mathbb{C}} }\right)$ the generator

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

where $\lambda_i = f\left(\ensuremath{ {\mathfrak{G}}_{i-1} \left( f,{\mathbb{C}} \right) }\right)$ and $\Delta_{i}^{}$ is defined to be d minus the Hamming distance from $\lambda_{i}^{}$ to the code $\mathfrak{G}_{i-1}^{}$ $\left(\vphantom{ f,{\mathbb{C}} }\right.$ f, $\mathbb {C}$ $\left.\vphantom{ 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 $\ensuremath{{\mathfrak{G}}}(\ensuremath{f_{\mbox{\small lexi}}},{\mathbb{S}}_d)$ , where we use the trivial seed code $\mathbb {S}$ _d $\mbox{$\stackrel{\mathrm{\mbox{def}}}{=}$}$ {0^d, 1^d}. The code in Table 1 is ${\mathfrak{G}}_{\,3} \left( \ensuremath{f_{\mbox{\small lexi}}},{\mathbb{S}}_3 \right)$ , as can be verified by hand.

Despite its generality, there are many linear codes that cannot be constructed using a non-trivial application of the $\mathfrak{G}$ -construction. The code given by the following basis vectors is one such example:

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