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 G-family. We shall use the term $\Delta_{m}^{}$ to refer to the corresponding term in Definition 1 for this m-th code.

Lemma 2..6   For any G-family of codes and m > 1,

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

Proof.  Consider constructing G _m from G _m-1 using Theorem 2.5. Any two coset leaders l and $\kappa$(l ) of 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 G _m, based on Theorem 2.5:

$$\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\} \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 G-construction implicitly demands that $\Delta_{m}^{}$ $\leq$ d, we may conclude that any coset leader of 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 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 G-codes.

Theorem 2..7   For any 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} \rig... ...nsuremath {\left\lfloor \frac{d-\rho_{m-1}}{2} \right\rfloor}.$$

Part of the proof of this theorem rests on a simple combinatorial lemma, which we provide without proof.

Lemma 2..8   If a > 3b > 0 then

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