# 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 be an (n, k, d ) cycle-free linear code over IFq. Then

 d   + (9)

Observe that for k/n0.5, the bound in (3.6) reduces to d2. 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.

Subsections

http://people.bu.edu/trachten