The minimum distance of cycle-free codes

The following theorem gives an upper bound on the minimum distance of cycle-free linear codes. Later in this section, we will show that this bound is tight for all values of n and k.

Theorem 3..6   Let $\ensuremath{\mathbb{C}}$ be an (n, k, d ) cycle-free linear code over IFq. Then

d $\displaystyle \le$ $\displaystyle \left\lfloor\vphantom{ \frac{n}{k+1} }\right.$$\displaystyle {\frac{{n}}{{k+1}}}$$\displaystyle \left.\vphantom{ \frac{n}{k+1} }\right\rfloor$ + $\displaystyle \left\lfloor\vphantom{ \frac{n+1}{k+1} }\right.$$\displaystyle {\frac{{n+1}}{{k+1}}}$$\displaystyle \left.\vphantom{ \frac{n+1}{k+1} }\right\rfloor$ (9)

Observe that for k/n$ \ge$0.5, the bound in (3.6) reduces to d$ \le$2. This simple special case was dealt with in Theorem 3.3. The proof of Theorem 3.6 for general n and k is considerably more involved and will be presented in Section 3.4.2, after we establish a series of auxiliary lemmas in the next subsection.