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 IF_q. Then

$$\le \left\lfloor\vphantom{ \frac{n}{k+1} }\right. {\frac{{n}}{{k+1}}} \left.\vphantom{ \frac{n}{k+1} }\right\rfloor \left\lfloor\vphantom{ \frac{n+1}{k+1} }\right. {\frac{{n+1}}{{k+1}}} \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.