Generalization

The lexicographic construction may be extended to produce codes with desired characteristics using the generalized lexicographic construction, which we abbreviate as the $\mathfrak{G}$-construction. The $\mathfrak{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.

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

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

using a mapping from codes to vectors:

$$\mathbb {C} \subseteq \mathbb {F} \longmapsto \mbox{$\,\inn\,$} \mathbb {F}$$ (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

  $$\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)$$ (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:

1110000
0001111

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.