Our first bound is a recursive upper bound on the covering
radius
of the m-th code of an arbitrary G-family. We
shall use the term
to refer to the corresponding term in
Definition 1 for this m-th code.
Proof. Consider constructing
G m from
G m-1 using
Theorem 2.5. Any two coset leaders l and
(l ) of
G m-1 must each have weight at most
, by the definition of the covering radius. Consider the
weight of a corresponding coset leader of
G m, based on
Theorem 2.5:
for all
a![$ \mbox{$\,\inn\,$}$](img43.png)
2
. Since the
G-construction implicitly demands that
d, we
may conclude that any coset leader of
G m must have weight no
greater than
![\begin{displaymath}
\ensuremath {\left\lfloor \frac{d}{2} \right\rfloor}+ \rho_{m-1}
\end{displaymath}](img249.png)
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
![\begin{displaymath}
n_0 > 3 \ensuremath {\left\lfloor \frac{d-1}{2} \right\rfloor},
\end{displaymath}](img253.png)
it necessarily follows that
![\begin{displaymath}
\rho_m \ \geq \ \ensuremath {\left\lfloor \frac{d-1}{2} \rig...
...nsuremath {\left\lfloor \frac{d-\rho_{m-1}}{2} \right\rfloor}.
\end{displaymath}](img257.png)
Part of the proof of this theorem rests on a simple combinatorial
lemma, which we provide without proof.
Subsections
http://people.bu.edu/trachten