Tanner Graphs

We will show that each of the three relations (3.11),(3.13),(3.14) between n, k, and d derived in Section4.2 implies (3.9), providing d is an integer in (3.11),(3.13) and d is an odd integer in (3.14). In order to make the appendix self-contained, we now re-state these inequalities:

$$\le \left\lfloor\vphantom{{n - d \over k-1}}\right. {n - d \over k-1} \left.\vphantom{{n - d \over k-1}}\right\rfloor$$ (9)

$$\le {n-d+1 \over k-1}$$ (11)

$$\le {n - d \over k-1}$$ (12)

Notice that what we are trying to establish has nothing to do with graphs or codes; this is just manipulation of integer inequalities. In particular, we have following simple lemma.

Lemma11. If a $\leq$ b/c and a, b, c are positive integers, then a $\leq$ (b + a)/(c + 1).

The proof of Lemma11 is straightforward, and is left to the reader. We first deal with (3.14), assuming d is odd. Taking the common denominator and applying (twice) Lemma11, we see that (3.14) implies

$$\le {2n - (k - 1) \over k+1} {2(n+1) \over k+1}$$ (20)

Since (d + 1)/2 is an integer for odd d, it follows from (20) that $(d+1)/2 \le \mbox{\ensuremath{\lfloor {(n{+}1)/(k{+}1)} \rfloor}}$. This may be re-written as:

$$\le \left\lfloor\vphantom{{n+1 \over k+1}}\right. {n+1 \over k+1} \left.\vphantom{{n+1 \over k+1}}\right\rfloor$$ (21)

If n + 1 $\not\equiv$ 0 mod (k + 1) then $\mbox{\ensuremath{\lfloor {(n+1)/(k+1)} \rfloor}} = \mbox{\ensuremath{\lfloor {n/(k+1)} \rfloor}}$, and (21) clearly implies (3.9). If (n + 1)/(k + 1) is an integer, then (21) is precisely the equivalent form of (3.9) given in (3.12).

It is easy to see that if d is an odd integer, then (3.11) implies (3.14). Since this case was already established above, it remains to prove (3.11) for even d. Using once again Lemma11, we see that (3.11) implies d$\le$2n/(k + 1), or equivalently d /2$\le$n/(k + 1). Since d /2 is an integer for even d, we can take the integer part of n/(k + 1) in the above expression. It follows that for even d, we have

d $$\le$$$$\left\lfloor\vphantom{{n \over k+1}}\right.$$$${n \over k+1}$$$$\left.\vphantom{{n \over k+1}}\right\rfloor$$

which clearly implies (3.9). Finally, it can be readily seen that if d is an integer, then (3.13) implies (3.11). Hence, our proof of Theorem5 is now complete.