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:

min$\displaystyle \left\{\vphantom{\ensuremath{\operatorname{wt}}(a \mid l), \ensuremath{\operatorname{wt}}\left(\bar{a} \mid \kappa_v(l)\right)}\right.$wt(a | l ), wt$\displaystyle \left(\vphantom{\bar{a} \mid \kappa_v(l)}\right.$$\displaystyle \bar{{a}}$ | $\displaystyle \kappa_{v}^{}$(l )$\displaystyle \left.\vphantom{\bar{a} \mid \kappa_v(l)}\right)$$\displaystyle \left.\vphantom{\ensuremath{\operatorname{wt}}(a \mid l), \ensuremath{\operatorname{wt}}\left(\bar{a} \mid \kappa_v(l)\right)}\right\}$ $\textstyle \leq$ $\displaystyle \min \left\{\ensuremath{\operatorname{wt}}(a)+\rho_{m-1}, \ensuremath{\operatorname{wt}}(\bar{a})+\rho_{m-1} \right\}$  
  $\textstyle \leq$ $\displaystyle \ensuremath {\left\lfloor {\Delta_m}/2 \right\rfloor}+ \rho_{m-1}$  

for all a$ \mbox{$\,\inn\,$}$$ \mathbb {F}$2$\scriptstyle \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

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