Bounding Length

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.

Corollary 2..11   For any trivially seeded, minimal G-code,

nm  $\displaystyle \leq$ $\displaystyle \left(\vphantom{m+\frac{1}{2}}\right.$m + $\displaystyle {\frac{{1}}{{2}}}$$\displaystyle \left.\vphantom{m+\frac{1}{2}}\right)$$\displaystyle {\frac{{d+4}}{{3}}}$ - $\displaystyle {\frac{{2}}{{3}}}$

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:

$\displaystyle \sum_{{i=1}}^{{m}}$$\displaystyle \rho_{i}^{}$ $\displaystyle \geq$ $\displaystyle \sum_{{i=1}}^{{m}}$$\displaystyle \left(\vphantom{{d - \frac{\rho_{i-1}}{2} - 2}}\right.$d-$\displaystyle {\frac{{\rho_{i-1}}}{{2}}}$-2$\displaystyle \left.\vphantom{{d - \frac{\rho_{i-1}}{2} - 2}}\right)$  
  $\displaystyle \geq$ m(d - 2) - $\displaystyle {\frac{{1}}{{2}}}$$\displaystyle \sum_{{i=0}}^{{{m}-1}}$$\displaystyle \rho_{{i}}^{}$  

Noting that for trivially seeded codes, $\rho_0 = \ensuremath {\left\lfloor \frac{d}{2} \right\rfloor}$ and $ \rho_{m}^{}$ $ \geq$ 0, we may reduce this to:

$\displaystyle {\frac{{3}}{{2}}}$$\displaystyle \sum_{{i=1}}^{{{m}}}$$\displaystyle \rho_{i}^{}$  $\displaystyle \geq$  m(d - 2) - $\displaystyle {\frac{{1}}{{2}}}$($\displaystyle \rho_{0}^{}$ - $\displaystyle \rho_{{m}}^{}$$\displaystyle \geq$  m(d - 2) - $\displaystyle {\frac{{d}}{{4}}}$

Furthermore, since we are dealing with minimal G-codes,

nm  =  $\displaystyle \sum_{{i=0}}^{{m}}$$\displaystyle \left(\vphantom{ d-\rho_i }\right.$d - $\displaystyle \rho_{i}^{}$$\displaystyle \left.\vphantom{ d-\rho_i }\right)$  =  md - $\displaystyle \sum_{{i=1}}^{{m}}$$\displaystyle \rho_{i}^{}$

so that we may now conclude the proof:

nm  =  md - $\displaystyle \sum_{{i=1}}^{{m}}$$\displaystyle \rho_{i}^{}$  $\displaystyle \leq$  md - $\displaystyle {\frac{{2}}{{3}}}$$\displaystyle \left(\vphantom{
{m}(d-2) - \frac{d}{4}}\right.$m(d - 2) - $\displaystyle {\frac{{d}}{{4}}}$$\displaystyle \left.\vphantom{
{m}(d-2) - \frac{d}{4}}\right)$  $\displaystyle \leq$  $\displaystyle {\frac{{m}}{{3}}}$(d + 4) + $\displaystyle {\frac{{d}}{{6}}}$



width4pt depth2pt height6pt

In the case of a G-family seeded by a non-trivial code of length n0 and covering radius $ \rho_{0}^{}$, Corollary 2.11 may be easily generalized to:

nm  $\displaystyle \leq$  n0 + $\displaystyle {\frac{{m(d+4)+\rho_0}}{{3}}}$ + $\displaystyle {\frac{{d}}{{6}}}$

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 $\displaystyle \geq$ \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} (9)

Specifically, Corollary 2.11 asymptotically binds k $ \geq$ 3$ {\frac{{n}}{{d}}}$ whereas Equation (2.14) binds k $ \geq$ 2$ {\frac{{n}}{{d}}}$. Nevertheless, both of these bounds are weak as illustrated by Appendix A.1.

http://people.bu.edu/trachten