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:

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

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

d $\displaystyle \le$ 2 $\displaystyle {n - d \over k-1}$ - 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

d $\displaystyle \le$ $\displaystyle {2n - (k - 1) \over k+1}$  =  $\displaystyle {2(n+1) \over k+1}$ - 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:

d $\displaystyle \le$ 2$\displaystyle \left\lfloor\vphantom{{n+1 \over k+1}}\right.$$\displaystyle {n+1 \over k+1}$$\displaystyle \left.\vphantom{{n+1 \over k+1}}\right\rfloor$ - 1 (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 $\displaystyle \le$$\displaystyle \left\lfloor\vphantom{{n \over k+1}}\right.$$\displaystyle {n \over k+1}$$\displaystyle \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.