Bounding Length

By summing Theorem 2.7 over many iterations, we may obtain a lower bound on the length n_m of the m-th code of any minimal G-family.

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

n_m  $$\leq$$ $$\left(\vphantom{m+\frac{1}{2}}\right.$$m + $${\frac{{1}}{{2}}}$$$$\left.\vphantom{m+\frac{1}{2}}\right)$$$${\frac{{d+4}}{{3}}}$$ - $${\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:

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

$$\geq {\frac{{1}}{{2}}} \sum_{{i=0}}^{{{m}-1}} \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:

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

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

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

so that we may now conclude the proof:

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

width4pt depth2pt height6pt

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

n_m  $$\leq$$  n₀ + $${\frac{{m(d+4)+\rho_0}}{{3}}}$$ + $${\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]:

$$\geq \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}$$ (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.