Bounding the Covering Radius

Our first bound is a recursive upper bound on the covering radius $\rho_{m}^{}$ of the m-th code of an arbitrary $\ensuremath{{\mathfrak{G}}}$-family. We shall use the term $\Delta_{m}^{}$ to refer to the corresponding term in Definition 1 for this m-th code.

Lemma 1   For any $\ensuremath{{\mathfrak{G}}}$-family of codes and m > 1,

$$\rho_m \ \leq \ \ensuremath {\left\lfloor \frac{d}{2} \right\rfloor}+\rho_{m-1}.$$

Proof: Consider constructing $\mathfrak{G}_{m}^{}$ from $\mathfrak{G}_{m-1}^{}$ using Theorem 3. Any two coset leaders l and $\kappa$(l ) of $\mathfrak{G}_{m-1}^{}$ must each have weight at most $\rho_{m-1}^{}$, by the definition of the covering radius. Consider the weight of a corresponding coset leader of $\mathfrak{G}_{m}^{}$, based on Theorem 3:

$$\left\{\vphantom{\ensuremath{\operatorname{wt}}(a \mid l), \ensuremath{\operatorname{wt}}\left(\bar{a} \mid \kappa_v(l)\right)}\right. \left(\vphantom{\bar{a} \mid \kappa_v(l)}\right. \bar{a} \kappa_{v}^{} \left.\vphantom{\bar{a} \mid \kappa_v(l)}\right) \left.\vphantom{\ensuremath{\operatorname{wt}}(a \mid l), \ensuremath{\operatorname{wt}}\left(\bar{a} \mid \kappa_v(l)\right)}\right\}$$ min

$$\leq \min \left\{\ensuremath{\operatorname{wt}}(a)+\rho_{m-1}, \ensuremath{\operatorname{wt}}(\bar{a})+\rho_{m-1} \right\}$$

$$\leq \ensuremath {\left\lfloor {\Delta_m}/2 \right\rfloor}+ \rho_{m-1}$$

for all a$\mbox{$ \inn $}$$\mathbb {F}$₂^$\Delta_{m}$. Since the $\ensuremath{{\mathfrak{G}}}$-construction implicitly demands that $\Delta_{m}^{}$ $\leq$ d, we may conclude that any coset leader of $\mathfrak{G}_{m}^{}$ must have weight no greater than

$$\ensuremath {\left\lfloor \frac{d}{2} \right\rfloor}+ \rho_{m-1}$$

which bounds the covering radius of $\mathfrak{G}_{m}^{}$ and proves the lemma.

width4pt depth2pt height6pt

With some combinatorial analysis, we can also establish a recursive lower bound on the covering radius of $\ensuremath{{\mathfrak{G}}}$-codes. Specifically, we shall make use of the following simple combinatorial lemma, which we provide without proof.

Lemma 2   If a > 3b > 0 then

$$\chooseb \sum_{i=0}^{b-1} \choosei$$ (10)

Theorem 4   For any $\ensuremath{{\mathfrak{G}}}$-family of codes whose seed code has length

$$n_0 > 3 \ensuremath {\left\lfloor \frac{d-1}{2} \right\rfloor},$$

it necessarily follows that

$$\rho_m \ \geq \ \ensuremath {\left\lfloor \frac{d-1}{2} \ri... ...nsuremath {\left\lfloor \frac{d-\rho_{m-1}}{2} \right\rfloor}.$$

Proof: Following convention, we let $t = \ensuremath {\left\lfloor (d-1)/2 \right\rfloor}$ denote the number of errors that the codes of a $\ensuremath{{\mathfrak{G}}}$-family can correct. It is well-known that each vector in $\mathbb {F}$₂^{n_{m - 1}} of weight $\leq$ t must be a unique coset leader for $\mathfrak{G}_{m-1}^{}$. Moreover, using our assumption about n₀ (which also holds for n_m, since n_m $\geq$ n₀), Lemma 2 implies that

$$\choose {t} \sum_{i=0}^{t-1} \choosei$$ (11)

The left-hand side of (14) is the number of vectors of weight t, while the right-hand side is the number of vectors of weight < t. Thus, by the pigeon-hole principle, there must be at least one coset leader $l\mbox{$\,\inn\,$}\ensuremath{ {\mathfrak{G}}_{m-1}}$ of weight t whose companion $\kappa$(l ) has weight at least t. Since $\Delta_{m}^{}$ $\geq$ d - $\rho_{m-1}^{}$ for any $\ensuremath{{\mathfrak{G}}}$-code, we may choose $a=0^{\ensuremath {\left\lfloor {\Delta_m}/2 \right\rfloor}}1^{\ensuremath {\left\lceil {\Delta_m}/2 \right\rceil}}$ to get:

$$\rho_{m}^{} \geq \left\{\vphantom{wt(\langle a \mid l\rangle), \ensuremath{\operatorname{wt}}\left( \langle \bar{a} \mid \kappa_v(l) \rangle \right)}\right. \langle \rangle \left(\vphantom{ \langle \bar{a} \mid \kappa_v(l) \rangle }\right. \langle \bar{a} \kappa_{v}^{} \rangle \left.\vphantom{ \langle \bar{a} \mid \kappa_v(l) \rangle }\right) \left.\vphantom{wt(\langle a \mid l\rangle), \ensuremath{\operatorname{wt}}\left( \langle \bar{a} \mid \kappa_v(l) \rangle \right)}\right\}$$

$$= \ensuremath {\left\lfloor \frac{{\Delta_m}}{2} \right\rfloor}+ t$$

$$\geq \ensuremath {\left\lfloor \frac{d-\rho_{m-1}}{2} \right\rfloor}+ \ensuremath {\left\lfloor \frac{d-1}{2} \right\rfloor}.$$

width4pt depth2pt height6pt

The result in Theorem 4 also applies to all $\mathfrak{G}$-families trivially seeded with the code $\mathbb {S}$_d.

Lemma 3   For any trivially seeded $\ensuremath{{\mathfrak{G}}}$-family of codes,

$$\rho_m \ \geq \ \ensuremath {\left\lfloor \frac{d-1}{2} \ri... ...nsuremath {\left\lfloor \frac{d-\rho_{m-1}}{2} \right\rfloor}.$$

If a $\ensuremath{{\mathfrak{G}}}$-family is trivially seeded, then, necessarily, n₀ = d and $\rho_0 = \ensuremath {\left\lfloor \frac{d}{2} \right\rfloor}$. Thus,

$$n_1 = n_0 + (d - \rho_0) = d + \ensuremath {\left\lceil \fra... ...ceil}> 3 \ensuremath {\left\lfloor \frac{d-1}{2} \right\rfloor}$$

so that Theorem 4 applies to the remaining codes in the family.

We now turn our attention to generating mappings which produce codes whose information rate is locally maximized. More specifically, for any code $\ensuremath{{\mathbb{C}}}$ with covering radius $\rho_{\ensuremath{{\mathbb{C}}}}^{}$, we will consider only generating mappings f with the property that the Hamming distance from $\ensuremath{{\mathbb{C}}}$ to $f(\ensuremath{{\mathbb{C}}})$ is exactly $\rho_{\ensuremath{{\mathbb{C}}}}^{}$. We will call such mappings minimal generating mappings, and the corresponding family of codes minimal $\mathfrak{G}$-codes, because they locally minimize length (and hence locally maximize information rate) for a given dimension and minimum-distance.

As an example, the generating mappings for the traditional lexicodes and the trellis-oriented lexicodes are both minimal. We may now easily strengthen Lemma 1 by observing in its proof that $\Delta_{m}^{}$ = d - $\rho_{m-1}^{}$ for minimal $\ensuremath{{\mathfrak{G}}}$-codes.

Corollary 1   For any minimal $\ensuremath{{\mathfrak{G}}}$-family of codes,

$$\rho_m \ \leq \ \ensuremath {\left\lfloor \frac{d+\rho_{m-1}}{2} \right\rfloor}.$$

The covering radius bounds we have developed for $\ensuremath{{\mathfrak{G}}}$-codes translate naturally to length bounds.