By summing Theorem 2.7 over many iterations, we may
obtain a lower bound on the length nm of the m-th code
of any minimal G-family.
Proof. Consider summing a weaker inequality obtained from
Theorem 2.7
by eliminating the floor function. Summing over iterations
1...m of the G-construction we get:
Noting that for trivially seeded codes,
and
0, we may reduce this to:
![$\displaystyle {\frac{{3}}{{2}}}$](img311.png)
![$\displaystyle \sum_{{i=1}}^{{{m}}}$](img312.png)
m(
d - 2) -
![$\displaystyle {\frac{{1}}{{2}}}$](img61.png)
(
![$\displaystyle \rho_{0}^{}$](img290.png)
-
![$\displaystyle \rho_{{m}}^{}$](img313.png)
)
m(
d - 2) -
Furthermore, since we are dealing with minimal G-codes,
so that we may now conclude the proof:
nm =
md -
![$\displaystyle \sum_{{i=1}}^{{m}}$](img304.png)
md -
![$\displaystyle {\frac{{2}}{{3}}}$](img303.png)
m(
d - 2) -
![$\displaystyle {\frac{{d}}{{4}}}$](img314.png)
![$\displaystyle {\frac{{m}}{{3}}}$](img320.png)
(
d + 4) +
width4pt depth2pt height6pt
In the case of a G-family seeded by a non-trivial code of length
n0 and covering radius
, Corollary 2.11 may
be easily generalized to:
Clearly, Corollary 2.11 applies to all lexicodes and
trellis-oriented lexicodes. It is a asymptotically tighter than the
similar bound given by Brualdi and Pless [9, Theorem3.5]:
k ![\begin{displaymath}\begin{cases}
n-2-\ensuremath {\left\lfloor \log_2(n-1) \rig...
...d-4} \right\rfloor}&\text{if } d \equiv 2 \pmod{4}. \end{cases}\end{displaymath}](img323.png) |
(9) |
Specifically, Corollary 2.11 asymptotically binds
k
3
whereas Equation (2.14) binds
k
2
. Nevertheless, both of these bounds are weak as
illustrated by Appendix A.1.
http://people.bu.edu/trachten