Groundwork: auxiliary lemmas

For the sake of brevity, we will consider only binary codes, although our proof readily extends to codes over an arbitrary finite field. Furthermore, with a slight abuse of notation, we will not distinguish between equivalent codes: namely, given a parity-check matrix H for a code $\ensuremath{\mathbb{C}}$, we will often freely permute the columns of H while still referring to the resulting matrix as a parity-check matrix for $\ensuremath{\mathbb{C}}$.

The following lemma will be the basis for the induction in our proof of Theorem 3.6.

Lemma 3..7   Let H be a cycle-free binary matrix. Then at least one of the following statements is true:

$\bullet$.

The matrix H contains a row of weight two or less;

$\Diamond$.

The matrix H contains three identical columns of weight one;

$\star$.

The matrix H contains two identical columns of weight one, and furthermore the row of H which contains the nonzero entries of these two columns has weight three.

Proof.  Let T(H) be the Tanner graph of H. We now construct another graph $\cal {G}$, called the row-graph of H, whose vertex set y₁, y₂,..., y_r-s corresponds to the rows of H. The edge set of $\cal {G}$ is derived from the columns of H of weight $\ge$2, so that a column of weight w in H contributes w - 1 edges to $\cal {G}$. An example illustrating the construction of the row-graph $\cal {G}$ for a  6×8 cycle-free matrix is depicted in Figure 3.3.

Figure 3.3: A cycle-free matrix, its Tanner graph, and its row-graph $\cal {G}$.

Specifically, there is an edge between y_i and y_j in $\cal {G}$ iff i < j and there exists a column (a₁, a₂,..., a_r-s)^t in H, such that a_i = a_j = 1 while a_i+1 = a_i+2 = ^... = a_j-1 = 0. Notice that each such edge (y_i, y_j) in $\cal {G}$ corresponds to a path of length two in T(H): namely $\langle$(y_i, x_p),(x_p, y_j)$\rangle$, where p denotes the position at which the column (a₁, a₂,..., a_r-s)^t is to be found in H. It follows that if there is a cycle in $\cal {G}$, then there is a cycle in T(H). Since T(H) is cycle-free, then so is $\cal {G}$. As such, $\cal {G}$ necessarily contains at least two vertices of degree $\le$1, in view of (3.2). Let y^* be one such vertex in $\cal {G}$, and let a^* = (a₁, a₂,..., a_n-s) be the corresponding row of H. If $\ensuremath{\operatorname{wt}}(a^*) \le 2$, then ($\bullet$) is true. If $\ensuremath{\operatorname{wt}}(a^*) = 3$ and deg y^* = 0, then ($\Diamond$) is true. If $\ensuremath{\operatorname{wt}}(a^*) = 3$ and deg y^* = 1, then ($\star$) is true. Finally, if $\ensuremath{\operatorname{wt}}(a^*) \ge 4$, then ($\Diamond$) is true, regardless of whether deg y^* = 0 or deg y^* = 1.

width4pt depth2pt height6pt

Let $\ensuremath{\mathbb{C}}$ be an (n, k, d ) cycle-free binary linear code, and let H be an r×n cycle-free parity-check matrix for $\ensuremath{\mathbb{C}}$, where r = n - k. We say that H is in s-canonical form if this matrix has the following structure:

$$\left[\vphantom{\, \begin{array}{c\vert c} & \\ [-2.50ex] \mbox{... ...ex] \hline\\ [-1.85ex] \mbox{$B$\,} & \mbox{\,$I_{s}$} \end{array} \: }\right. \begin{array}{c\vert c} & \\ [-2.50ex] \mbox{$A$\,} & \mbox{\lar... ...}$} \\ [.45ex] \hline\\ [-1.85ex] \mbox{$B$\,} & \mbox{\,$I_{s}$} \end{array} \left.\vphantom{\, \begin{array}{c\vert c} & \\ [-2.50ex] \mbox{... ...ex] \hline\\ [-1.85ex] \mbox{$B$\,} & \mbox{\,$I_{s}$} \end{array} \: }\right]$$ (9)

where all the rows of B have weight $\le$1, and I_s is the s×s identity matrix, for some s in the range 0$\le$s$\le$r. Notice that if s = 0 then (3.7) reduces to H = A (which means that every matrix is in 0-canonical form), while if s = r then the corresponding canonical form is H = [B   |   I_r]. We will use the shorthand H = A|_sB to denote the s-canonical form in (3.7).

Lemma 3.7 trivially generalizes to matrices in s-canonical form.

Lemma 3..8   Let H = A|_sB be a cycle-free binary matrix in s-canonical form, and suppose that s < r. Then at least one of the following statements is true:

$\bullet$.

The matrix A contains a row of weight two or less;

$\Diamond$.

The matrix A contains three identical columns of weight one;

$\star$.

The matrix A contains two identical columns of weight one, and furthermore the row of H which contains the nonzero entries of these two columns has weight three.

Proof.  Evidently T(A) is a subgraph of T(H), obtained by retaining only the first n - s symbol vertices x₁, x₂,..., x_n-s, the first r - s check vertices y₁, y₂,..., y_r-s, and all the edges between these vertices. Since T(H) is cycle-free by assumption, so is T(A). Thus, Lemma 3.7 applies to complete the proof.

width4pt depth2pt height6pt

We will say that an r×n matrix H is in reduced canonical form, if H = A|_sB and either s = r or all the rows of A have weight $\ge$3. It is a non-trivial fact that every cycle-free parity-check matrix can be put into such a form.

Lemma 3..9   Let $\ensuremath{\mathbb{C}}$ be an (n, k, d ) cycle-free binary linear code. Then there exists a cycle-free parity-check matrix for $\ensuremath{\mathbb{C}}$, which is in reduced canonical form.

Proof.  Let H be an arbitrary cycle-free parity-check matrix for $\ensuremath{\mathbb{C}}$. We first put H in s-canonical form, for the highest possible s, by means of row and column permutations. This is achieved by considering all the rows of H of weight one, for which the nonzero entry * is contained in a column of weight one, and all the rows of H of weight two such that at least one of the two  *'s is contained in a column of weight one. Under an appropriate column permutation, these rows of H will form the submatrix [B   |   I_s] in (3.7). If there are no such rows, then s = 0 and H = A. Since row and column permutations preserve the cycle-free property of H, this procedure produces a cycle-free parity-check matrix H' = A|_sB for $\ensuremath{\mathbb{C}}$, which is in canonical form, although not necessarily reduced.

Since H' = A|_sB is full-rank by assumption, all the rows of A have weight $\ge$1. The key observation is that certain elementary operations on the rows of H' allow us to eliminate rows of weight one and two in A, while still preserving the cycle-free property.

Indeed, suppose that A has a row (a₁, a₂,..., a_r-s) of weight one, with a single * in position i. Then we can add this row to all the rows of H' that are nonzero at position i. This procedure is equivalent to deleting all but one of the edges incident at the symbol vertex x_i in T(H'), which certainly does not create new cycles. Following this procedure, the single * in (a₁, a₂,..., a_r-s) is contained in a column of weight one. Hence we can transform the resulting cycle-free parity-check matrix for $\ensuremath{\mathbb{C}}$ into the form A'|_s+1B', by means of row and column permutations, thereby eliminating the row of weight one in A.

Now suppose that A has a row (a₁, a₂,..., a_r-s) of weight two, with the two *'s in positions i and j, and let y^* be the corresponding check vertex in T(H'). We again add this row to all the rows of H' that are nonzero at position i. Let (b₁, b₂,..., b_n) be such a row, and let y' denote the corresponding check vertex of T(H'). If b_j = b_i = *, then T(H') contains the cycle  $\langle$(x_i, y^*),(y^*, x_j),(x_j, y'),(y', x_i)$\rangle$. Since T(H') is cycle-free, we conclude that b_i = * while b_j = 0. Hence, adding row (a₁, a₂,..., a_n) to (b₁, b₂,..., b_n) corresponds to deleting the edge (y', x_i) in T(H') while introducing a new edge (y', x_j), as illustrated in Figure 3.4.

Figure: Part of the Tanner graph for $\ensuremath{\mathbb{C}}$ before and after the elementary row operation.

However, this new edge cannot close a cycle, since T(H') is cycle-free and a path from y' to x_j already exists in T(H'): indeed $\langle$(y', x_i),(x_i, y^*),(y^*, x_j)$\rangle$ is such a path. Following all these elementary row operations, the * at position i in (a₁, a₂,..., a_n) is contained in a column of weight one. Thus we can again transform the resulting cycle-free parity-check matrix for $\ensuremath{\mathbb{C}}$ into the form A'|_s+1B', thereby eliminating the row of weight two in A.

We iteratively repeat the process described in the foregoing two paragraphs, until either s = r or all the rows of A have weight $\ge$3. This procedure produces a cycle-free parity-check matrix for  $\ensuremath{\mathbb{C}}$ that is in reduced canonical form.

width4pt depth2pt height6pt

If the reduced canonical form in Lemma 3.9 is achieved in the extreme case s = r, then it is easy to prove the claim of Theorem 3.6.

Lemma 3..10   Let $\ensuremath{\mathbb{C}}$ be an (n, k, d ) cycle-free binary linear code. If there is a parity-check matrix for $\ensuremath{\mathbb{C}}$ of the form H = [B   |   I_r], where r = n - k and the rows of B have weight $\le$1, then the minimum distance of $\ensuremath{\mathbb{C}}$ satisfies the upper bound of Theorem 3.6.

Proof.  If B contains a column of weight w, then clearly d$\le$w + 1. Since B is an r×k matrix, there will always be at least one column with maximum weight ${\frac{{wt(B)}}{{k}}}$, so that

d $$\le$$ $${\frac{{\ensuremath{\operatorname{wt}}(B)}}{{k}}}$$ + 1.

Moreover, all the rows of B have weight $\le$1, so that

$$\le {\ensuremath{\operatorname{wt}}(B) \over k} \le {r \over k} {n \over k}$$ (9)

As d is an integer, this implies that $d \le \mbox{\ensuremath{\lfloor {n/k} \rfloor}}$. It is easy to see that $\mbox{\ensuremath{\lfloor {n/k} \rfloor}} \le 2 \mbox{\ensuremath{\lfloor {n/(k\!+\!1)} \rfloor}}$, unless k = 1 and n is odd. But, in the latter case, both (3.6) and (3.8) reduce to d$\le$n.

width4pt depth2pt height6pt