`
`Proceedings
`
`THIRTY-SIXTH ANNUAL ALLERTON CONFERENCE
`ON COMMUNICATION, CONTROL AND COMPUTING
`
`September 23 - 25, 1998
`
`Allerton House, Monticello, Illinois
`Sponsored by the
`Coordinated Science Laboratory and the
`Department of Electrical and Computer Engineering of the
`University of Illinois at Urbana-Champaign
`
`Hughes, Exh. 1011, p. 1
`
`Hughes, Exh. 1011, p. 1
`
`
`
`PROCEEDINGS
`
`THIRTY-SIXTH ANNUAL ALLERTON CONFERENCE
`ON COMMUNICATION, CONTROL, AND COMPUTING
`
`Tamer Ba~ar
`Bruce Hajek
`Conference Co-Chairs
`
`Conference held
`September 23 - 25, I 998
`Allerton House
`Monticello, Illinois
`
`Sponsored by
`The Coordinated Science Laboratory
`and
`The Department of Electrical and Computer Engineering
`of the
`UNIVERSITY OF ILLINOIS
`at
`Urbana-Champaign
`
`Hughes, Exh. 1011, p. 2
`
`
`
`Coding Theorems for "Turbo-Like" Codes*
`
`Dariush Divsalar, Hui Jin, and Robert J. McEliece
`Jet Propulsion Laboratory and California Institute of Technology
`Pasadena, California USA
`E-mail: dariush@shannon. jpl. nasa. gov, (hui, rjm)@systems. cal tech. edu
`
`Abstract.
`In this paper we discuss A WGN coding theorems for ensembles of coding systems which
`are built from fixed convolutional codes interconnected with random interleavers. We
`call these systems "turbo-like" codes and they include as special cases both the classical
`turbo codes {1,2,3} and the serial concatentation of interleaved convolutional codes {4}.
`We offer a general conjecture about the behavior of the ensemble (maximum-likelihood
`decoder) word error probability as the word length approches infinity. We prove this
`conjecture for a simple class of rate 1/ q serially concatenated codes where the outer
`code is a q-fold repetition code and the inner code is a rate 1 convolutional code with
`transfer function 1/ (1 +D) . We believe this represents the first rigorous proof of a
`coding theorem for turbo-like codes.
`
`1. Introduction.
`The 1993 discovery of turbo codes by Berrou, Glavieux, and Thitimajshima [1] has
`revolutionized the field of error-correcting codes. In brief, turbo codes have enough
`randomness to achieve reliable communication at data rates near capacity, yet enough
`structure to allow practical encoding and decoding algorithms. This paper is an attempt
`to illuminate the first of these two attributes, i.e., the "near Shannon limit" capabilities
`of turbo-like codes on the AWGN channel.
`Our specific goal is to prove AWGN coding theorems for a class of generalized con(cid:173)
`catenated convolutional coding systems with interleavers, which we call "turbo-like"
`codes. This class includes both parallel concatenated convolutional codes (classical
`turbo codes) [1, 2, 3] and serial concatenated convolutional codes [4] as special cases.
`Beginning with a code structure of this type, with fixed component codes and inter(cid:173)
`connection topology, we attempt to show that as the block length approaches infinity,
`the ensemble (over all possible interleavers) maximum likelihood error probability ap(cid:173)
`proaches zero if Eb/ No exceeds some threshold. Our proof technique is to derive an
`explicit expression for the ensemble input-output weight enumerator (lOWE) and then
`to use this expression, in combination with either the classical union bound, or the
`recent "improved" union bound of Viterbi arid Viterbi [9], to show that the maximum
`likelihood word error probability approaches zero as N-+ oo. Unfortunately the diffi(cid:173)
`culty of the first step, i.e., the computation of the ensemble lOWE, has kept us from
`full success, except for some very simple coding systems, which we call repeat and ac(cid:173)
`cumulate codes. Still, we are optimistic that this technique will yield coding theorems
`for a much wider class of interleaved concatenated codes. In any case, it is satisfying to
`have rigorously proved coding theorems for even a restricted class of turbo-like codes.
`Here is an outline of the paper. In Section 2 we quickly review the classical union
`bound on maximum-likelihood word error probability for block codes on the AWGN
`* Dariush Divsalar's work, and a portion of Robert McEliece's work, was performed
`at JPL under contract with NASA. The remainder of McEliece's work, and Hui Jin's
`work, was performed at Caltech and supported by NSF grant no. NCR-9505975,
`AFOSR grant no. 5F49620-97-1-0313, and grant from Qualcomm.
`
`201
`
`Hughes, Exh. 1011, p. 3
`
`
`
`channel, which is seen to depend on the code's weight enumerator. In Section 3 we
`define the class of "turbo-like" codes, and give a formula for the average input-output
`weight enumerator for such a code. In Section 4 we state a conjecture (the interleaver
`gain exponent conjecture) about the ML decoder performance of turbo-like codes. In
`Section 5, we define a special class of turbo-like codes, the repeat-and-accumulate codes,
`and prove the IGE conjecture for them. Finally, in Section 6 we present performance
`curves for some RA codes, using an iterative, turbo-like, decoding algorithm. This
`performance is seen to be remarkably good, despite the simplicity of the codes and the
`suboptimality of the decoding algorithm.
`
`2. Union Bounds on the Performance of Block Codes.
`In this section we will review the classical union bound on the maximum-likelihood
`word error probability for block codes.
`Consider a binary linear (n, k) block code C with code rater= k/n. The (output)
`weight enumerator (WE) for C is the sequence of numbers Ao , . . . , An , where Ah de(cid:173)
`notes the number of codewords inC with (output) weight h. The input-output weight
`enumerator (lOWE) for Cis the array of numbers Aw,h, w = 0, 1, . .. , k , h = 0, 1, .. . , n:
`Aw,h denotes the number of codewords in C with input weight w and output weight h.
`The union bound on the word error probability Pw of the code Cover a memoryless
`binary-input channel, using maximum likelihood decoding, has the well-known form
`
`(2.1)
`
`(2.2)
`
`= t (t Aw,h) Zh .
`
`h=l w=l
`In (2.1) and (2.2), the function z h represents an upper bound on the pairwise error
`probability for two codewords separated by Hamming (output) distance h. For AWGN
`channels, z = e-rE. / No where Eb/N0 is the signal-to-noise ratio per bit.
`
`3. The Class of "Turbo-Like" Codes.
`In this section, we consider a general class of concatenated coding systems of the type
`depicted in Figure 1, with q encoders (circles) and q- 1 interleavers (boxes) . The
`ith code C; is an (n;, N;) linear block code, and the ith encoder is preceded by an
`interleaver (permuter) P; of size N; , except C 1 which is not preceded by an interleaver,
`but rather is connected to the input. The overall structure must have no loops, i.e., it
`must be a graph-theoretic tree. We call a code of this type a "turbo-like" code.
`Define sq = { 1, 2, ... , q} and subsets of sq by s 1 = { i E sq : C; connected to input} ,
`so = {i E Sq : C; connected to output}, and its complement so . The overall system
`depicted in Figure 1 is then an encoder for an (n, N) block code with n = 2::,;iE•o n; .
`If we know the lOWE A~~.h, 's for the constituent codes C;, we can calculate
`the average lOWE Aw,h for the overall system (averaged over the set of all possible
`interleavers), using the uniform interleaver technique
`[2].
`(A uniform interleaver is
`defined as a probabilistic device that maps a given input word of weight w into all
`distinct (~') permutations of it with equal probability p = 1/(~') . ) The result is
`q A(il
`
`(3.1)
`
`Aw,h = h;~o h;~o A~;,h, [! (~:')'
`
`Eh,=h
`
`202
`
`Hughes, Exh. 1011, p. 4
`
`
`
`In (3.1) we have W; = w if i E S[, and W; = hj if C; is preceeded by cj (see Figure 2.).
`We do not give a proof of formula (3.1), but it is intuitively plausible if we note that
`the term A~~.hj(~;) is the probability that a random input word to C; of weight w;
`will produce an output word of weight h; .
`For example, for the (n 2 +n3 +n4 , N) encoder of Figure 1 the formula (3.1) becomes
`
`Aw,h =
`
`ht,h2 , hJ , h4
`( h2+hJ+h4=h )
`
`input
`
`output
`
`output
`
`~------------------~ output
`
`Figure 1. A "turbo-like" code with
`Sf = {1 , 2}, SO = {2,3,4}, SO = {1}.
`
`Figure 2. Ci (an (ni, Ni) encoder) is connected to Ci
`(an ( nj , Nj) encoder) by an interleaver of size Nj . We
`have the "boundary conditions" Nj = n; and Wj = hi.
`
`4. The Interleaving Gain Exponent Conjecture.
`In this section we will consider systems of the form depicted in Figure 1, in which
`the individual encoders are truncated convolutional encoders, and study the behavior
`of the average ML decoder error probability as the input block length N approaches
`
`203
`
`Hughes, Exh. 1011, p. 5
`
`
`
`infinity. If A;:; h denotes the lOWE when the input block has length N, we introduce
`the following ri.otation for the union bound (2.2) for systems of this type:
`
`(4.1)
`
`Next we define, for each fixed w ~ 1 and h ~ 1,
`
`(4.2)
`
`a(w, h)= limsuplogN A;:; h ·
`N-+oo
`'
`
`It follows from this definition that if w and h are fixed,
`A;:;,hzh = O(Noc(w, h)+<)
`
`as N-> oo,
`
`for any E > 0. Thus if we define
`
`(4.3)
`
`f3M = ma.xma.xa(w, h).
`h~1 w~1
`
`it follows that for all w and h,
`
`as N-> oo,
`
`for any E > 0. The parameter f3M, which we shall call the interleaving gain exponent
`(IGE), was first introduced in [2) and [3) for parallel concatenation and later in [4) for
`serial concatenation. Extensive numerical simulations, and theoretical considerations
`that are not fully rigorous lead to the following conjecture about the behavior of the
`union bound for systems of the type shown in Figure 1.
`
`The IGE Conjecture. There exists a positive number 'Yo, which depends on the q
`component convolutional codes and the tree structure of the overall system, but not
`on N , such that for any fixed En/No> /o,as the block length N becomes large,
`
`(4.4)
`
`Eq. (4.4) implies that if f3M < 0, then for a given Eb/No >'Yo the word error prob(cid:173)
`ability of the concatenated code decreases to zero as the input block size is increased.
`This is summarized by saying that there is word error probability interleaving gain. 1
`In [7), we discuss the calculation of a(w, h) and f3M for a concatenated system of
`the type depicted in Figure 1, using analytical tools introduced in
`(3) and
`[4) . For
`example, for the parallel concatenation of q codes, with q - 1 interleavers, we have
`f3M :S -q + 2,
`
`with equality if and only if each of the component codes is recursive. For a "classical"
`turbo code with q = 2, we have f3M = 0, so there is no word error probability inter(cid:173)
`leaving gain. This suggests that the word error probability for classic turbo codes will
`not improve with input block size, which is in agreement with simulations.
`
`1 There is a similar conjecture for the bit error probability which we do not discuss in
`this paper. Suffice it to say that the interleaving gain exponent for bit error probability
`is !3M- 1.
`
`204
`
`Hughes, Exh. 1011, p. 6
`
`
`
`As another example, consider the serial concatenation of two convolutional codes.
`If the inner code is recursive then,
`
`(3 <-ldfree+1j+1
`2
`'
`M-
`
`where d~ree is the minimum distance of the outer code. Therefore, for serial concate(cid:173)
`nated codes , if dj 2 3 there is interleaving gain for word error probability. (If the inner
`code is nonrecursive f3M 2 0 and there is no interleaving gain.)
`
`5. A Class of Simple Turbo-Like Codes.
`In this section we will introduce a class of turbo-like codes which are simple enough
`so that we can prove the IGE conjecture. We call these codes repeat and accumulate
`(RA) codes. The general idea is shown in Figure 3. An information block of length
`N is repeated q times, scrambled by an interleaver of size qN, and then encoded by
`a rate 1 accumulator. The accumulator can be viewed as a truncated rate-1 recursive
`convolutional encoder with transfer function 1/(1 +D), but we prefer to think of it as
`a block code whose input block (xi, ... , Xn] and output block (YI , ... , Yn] are related
`by the formula
`
`(5.1)
`
`YI =XI
`Yz =xi+ xz
`Y3 = XI + Xz + X3
`
`Yn = X1 + X2 + X3 + · · · + Xn.
`
`LENGTH
`
`N
`
`[WEIGHT]
`
`[w]
`
`rate 1/q
`repetition
`
`qN
`
`[qw]
`
`qN
`
`[qw]
`
`rate 1
`1/(1+D}
`
`qN
`
`[h]
`
`qN X qN
`permutation
`matrix
`
`Figure 3. Encoder for a (qN , N) repeat and accumulate
`code. The numbers above the input-output lines
`indicate the length of the corresponding block, and
`those below the lines indicate the weight of the block.
`
`To apply the union bound from Section 2 to the class of RA codes, we need the
`input-output weight enumerators for both the (qn, n) repetition code, and the (n, n)
`accumulator code. The outer repetition code is trivial: if the input block has length n,
`we have
`
`(5 .2)
`
`(o)
`Aw,h =
`
`{ 0
`(;:;)
`
`if h =I qw
`if h = qw.
`
`205
`
`Hughes, Exh. 1011, p. 7
`
`
`
`The inner accumulator code is less trivial, but it is possible to show that (again assuming
`the input block has length n):
`
`(5.3)
`
`(n- h) ( h- 1
`
`)
`rw/21- 1 °
`
`(i)
`Aw ,h == Lw/2J
`
`It follows then from the general formula (3.1), that for the (qN, N) RA code represented
`by Figure 3, the ensemble lOWE is
`
`(5.4)
`
`qN A(o) A(i)
`A (N) == "'"'
`w ,h, h1 ,h
`L
`(qqNw)
`w ,h
`h,=O
`)
`( N)(qN-h)( h-1
`lqw/ 2J
`[qw / 21-1
`w
`(~~)
`
`From (5.4) it is easy to compute the parameters a(w, h) and f3M in (4.2) and (4.3).
`The result is
`
`(5.5)
`
`(5.6)
`
`et(w,h) ==- r(q-22)wl
`f3M __ f(q-2)1
`-
`I
`2
`
`·
`
`It follows from (5.6) that an RA code can have word error probability interleaving gain
`only if q 2: 3.
`We are now prepared to use the union bound to prove the IGE conjecture for RA
`codes. In order to simplify the exposition as much as possible, we will assume for the
`rest of this section that q == 4, the extension to arbitrary q 2: 3 being straightforward
`but rather lengthy. For q == 4, (5.6) becomes f3M == -1, so the IGE conjecture is
`p~B == O(N- 1
`) for Eb/No >'Yo in this instance.
`The union bound (2.2) for the ensemble of q == 4 RA codes is, because of (5.4) ,
`
`(5.7)
`
`4N h / 2 (N) (4N -h) ( h-1 )
`2w-1
`P UB _ "'"' "'"' w
`2w
`- L L
`(4N)
`W
`h=2w=1
`4w
`
`h
`z
`
`Denote the (w, h)th term in the sum (5.7) by TN(w , h) :
`(N) (4N -h) ( h-1)
`2w
`(!~)
`
`2w-1
`
`h
`z
`
`T (
`N w,
`
`h _
`h) d~fA
`-
`w,hz
`-
`
`w
`
`Using standard techniques (e.g. [8, Appendix A]), it is possible to show that for all
`(w,h),
`
`(5.8)
`
`where D == 4/.Jif is a constant, x == w/4N, y == h/4N,
`
`206
`
`Hughes, Exh. 1011, p. 8
`
`
`
`and H2( x) = -xlog2 (x)- (1- x)log2 (1- x) is the binary entropy function. The
`maximum of the function F(x, y) in the range 0 ~ 2x ~ y ~ 1- 2x occurs at (x, y) =
`(0.100, 0.371) and is 0.562281, so that if log2 z < -0.562281 , the exponent in (5.8) will
`be negative.
`Let us therefore assume that log2 z < -0.562281 , which is equivalent to Eb /No =
`-(1/r)lnz = -4lnz ~ 4 ·ln2 · 0.562281 = 1.559 = 1.928 dB. If E is defined to be
`E = -log2 z + 0.562281, it follows from (5.8) for all w and h,
`
`(5.9)
`
`What (5.9) tells us is that if Eb/No > 1.928 dB , most of the terms in the union bound
`(5.7) will tend to zero rapidly, as N -+ oo. The next step in the proof is to break the
`sum in (5.7) into two parts, corresponding to those terms for which (5.9) is helpful,
`and those for which it is not. To this end, define
`
`and write
`
`clef 3
`hN = Elog 2 N ,
`
`4N h/ 2
`p~B = L L TN(w , h)
`h=2 w=1
`4N
`hN h/ 2
`= LLTN(w, h)+ L
`h=2w=1
`
`h/ 2
`LTN(w, h)
`
`It's easy to verify that when N is large enough, Aw+1,h/Aw ,h < 1 for h ~ h N and
`w ~ h/2 ~ h N/2, which shows Aw,h is a decreasing function of w for large N . Thus
`the sum S 1 can be overbounded as follows (we omit some details) :
`
`hN h(2
`sl = LLTN(w, h )
`h=2 w=l
`hN h/2
`hN
`= LTN(l , h)+ L LTN(w , h )
`h=2 w=2
`h=2
`hN h/ 2
`=O(N- 1)+ LLTN(w,h)
`h=2w=2
`hN h/2
`) + L L A2,hZh
`h=2w=2
`hN h/ 2
`= O(N - 1) + L L O(h3 /N2)z h
`h=2w=2
`) + O(h~/N 2 )
`= O(N - 1
`=O(N- 1 ) .
`
`~ O(N- 1
`
`207
`
`Hughes, Exh. 1011, p. 9
`
`
`
`For the sum S2, we bound each term TN(w , h) by (5.9):
`
`h /2
`4N
`S2= L LTN(w,h)
`
`4N h/2
`:::; L
`l:::DThE
`
`4N
`= D /2 L hThE
`
`2-EhN(hN + 1)
`:S D
`(1 - 2-E) 2
`= O(N- 3 log2 N)
`= o(N- 2
`).
`
`We have therefore shown that for the ensemble of q = 4 RA codes, if Eb/ N0 >
`1.928 dB,
`
`(5.10)
`
`which as we saw above, is the IGE conjecture in this case.
`Although the union bound gives a proof of the IGE conjecture for RA codes, the
`resulting value of /o is by no means the best possible. Indeed, if we use the recent
`Viterbi-Viterbi improved union bound [9] to bound the sum 5 2 , we can lower the value
`of /o considerably, e.g. for q = 4 from 1.928 dB to 0.313 dB. In Figure 4 and Table 1 we
`display our numerical results on RA codes. There we compare the "cutoff threshold"
`/o for RA codes with q in the range 3 :S q :S 8 using both the classical union bound
`and the Viterbi-Viterbi improved union bound to the cutoff threshold for the ensemble
`of all codes (i.e., "random codes") of a fixed rate. We believe that these values of
`/o can be reduced still further, for example by using the bound of [6] instead of the
`Viterbi-Viterbi bound.
`
`q
`RA Codes (Union Bound)
`Random Codes (Union Bound)
`RA Codes (Viterbi Bound)
`Random Codes (Viterbi Bound)
`Binary Shannon Limit
`
`3
`7
`5
`8
`4
`6
`1.631
`1.670
`1. 721
`1. 798
`1.928
`2.200
`1.853
`2.031
`1.620
`1.651
`1.694
`1. 775
`0.313 -0.125 -0.402 -0.592 -0.731
`1.112
`0.214 -0.224 -0.486 -0.662 -0.789 -0.885
`-0.495 -0.794 -0.963 -1.071 -1.150 -1.210
`
`Table 1. Numerical data gleaned from Figure 4.
`
`6. Performance of RA Codes with Iterative Decoding.
`The results of this paper show that the performance of RA codes with maximum(cid:173)
`likelihood decoding is very good. However, the complexity of ML decoding of RA
`
`208
`
`Hughes, Exh. 1011, p. 10
`
`
`
`random codes
`union bound
`random codes
`viterbi bound
`shannon limit binary input
`union bound RA codes
`viterbi bound RA codes
`
`*
`+
`
`*
`+
`
`. *-
`~ .. .:..- *' - *- - -
`
`+
`
`+
`+~ ____- .
`++ + : - - - - - - • .
`.
`
`.. -.. -.. -··-
`
`I
`/
`,/
`
`/
`
`.
`
`/
`
`/
`
`/
`
`/
`· ; ·.
`
`0.1
`
`0.2
`
`0.3
`
`0.4
`
`0.5
`Code RateR
`
`0.6
`
`0.7
`
`0.8
`
`0.9
`
`Figure 4. Comparing the RA code "cutoff threshold" to
`the cutoff rate of random codes using both the classical
`union bound and the Viterbi-Viterbi improved union bound.
`
`codes, like that of all turbo-like codes, is prohibitively large. But an important feature
`of turbo-like codes is the availability of a simple iterative, message passing decoding
`algorithm that approximates ML decoding. We wrote a computer program to imple(cid:173)
`ment this "turbo-like" decoding for RA codes with q = 3 (rate 1/3) and q = 4 (rate
`1/4), and the results are shown in Figure 5. We see in Figure 4, for example, that
`the empirical cutoff threshold for RA codes for q = 3 appears to be less than 1 dB,
`compared to the upper bound of 1.112 dB found in Table 1.
`
`References.
`1. C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon limit error(cid:173)
`correcting coding and decoding: turbo codes," Proc. 1993 IEEE International
`Conference on Communications, Geneva, Switzerland (May 1993), pp. 1064- 1070.
`2. S. Benedetto and G. Montorsi , "Unveiling turbo codes: some results on parallel
`concatenated coding schemes" , IEEE Trans. on Inf. Theory, vol. 42, no. 2 (March
`1996), pp. 409-428 ..
`3. S. Benedetto and G. Montorsi, "Design of parallel concatenated convolutional
`codes," IEEE Transactions on Communications, vol. 44, no. 5, (May 1996) pp. 591-
`600.
`4. S. Benedetto, D. Divsalar, G. Montorsi, and F . Pollara, "Serial concatenation
`of interleaved codes: performance analysis , design, and iterative decoding," IEEE
`Trans. on Information Theory, vol. 44, no. 3, (May 1998) , pp. 909-926.
`
`209
`
`Hughes, Exh. 1011, p. 11
`
`