`
`TI-IIRTY-SIXTH ANNUAL ALLERTON CONFERENCE
`ON COMMUNICATION, CONTROL AND COMPUTDIG
`
`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
`
`(cid:74)
`
`(cid:36)(cid:83)(cid:83)(cid:79)(cid:72)(cid:3)12(cid:20)(cid:26)
`Apple 1217
`
`
`
`PROCEEDINGS
`
`THIRTY-SIXTH ANNUAL. ALLERTON CONFERENCE
`ON COMMUNICATION. CONTROL. AND COMPUTING
`
`Tamer Basar
`Bruce I-lajek
`Conference Co-Chairs
`
`Conference held
`September 23 - 25. I998
`Allerton House
`Monticello. Illinois
`
`Sponsored by
`The Coordinated Science Laboratory
`The Department of Electricfaifiand Computer Engineering
`UNlVERSI1?‘:'-'l(II)‘;' ILLINOIS
`Urbnna-(gilampaign
`
`Hughes, Exh. 1011, p. 2
`
`(cid:74)(cid:74)
`
`
`
`Coding Theorems for “Turbo-Like” Codes’
`
`Dariush Divsalar, Hui J in, and Robert J. McEliece
`Jet Propulsion Laboratory and California Institute of Technology
`Pasadena. California USA
`
`E—mail: dariuslwshannon.jp1.nasa.gov.
`
`(hui , rjm) @systems.ca1tech. edu
`
`Abstract.
`
`In this paper we discuss AWGN 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
`We ofier a general conject me 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 Barron. 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-
`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-
`connection topology, we attempt to show that as the block length approaches infinity,
`the ensemble {over all possible interleavers) maximum likelihood error probability ap-
`proaches zero if Eb/No" exceeds some threshold. Our proof technique is to derive an
`explicit expression for the ensemble input-output weight enumerator (IOWE) and then
`to use this expression,
`in combination with either the classical union bound, or the
`recent “improved" union bound of Viterbi and Viterbi [9], to show that the maximum
`likelihood word error probability approaches zero as N —~ oo. Unfortunately the diifi-
`culty of the first step, ie, the computation of the ensemble IOWE, has kept us from
`full success, except for some very simple coding systems, which we call repeat and ac-
`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 maximurmljkelihood word error probability for block codes on the AWGN
`
`* Dariush Divsalar’s work, and a portion of Robert McEliece‘s work, was performed
`at J PL 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. 51349620-9?-1-U313, and grant from Qualcomm.
`
`201
`
`Hughes, Exh. 1011, p. 3
`
`
`
`In Section 3 we
`channel, which is seen to depend on the code‘s weight e-numerator.
`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 interleave:
`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 ICE 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 (11,, 1:) block code C with code rate 1' = It/n. The (output)
`weight enumemtor
`for C is the sequence of numbers Ag, . .
`. , A,.,, where Al, de-
`notes the number of codewords in C with (output) weight h. The input-output weight
`enumemtor (IOWE) for C is the array of numbers A,,,‘;,, is = 0,1,...,k, h = 0,1,...,n:
`A,,,‘;, denotes the number of codewords in C with input weight in and output weight h..
`The union bound on the word error probability PW of the code C over a memoryless
`binary-input channel, using maximum likelihood decoding, has the well-known form
`
`(2.1)
`
`(2.2)
`
`Pw 5 ixihzh
`
`h=1
`n
`
`J:
`
`= Z (Z A,,,,;,) 2*.
`
`uJ=1
`
`h=1
`
`In (2.1) and (2.2), the function 2"‘ represents an upper bound on the pairwise error
`probability for two codewords separated by Hamming (output) distance h. For AWGN
`channels, .2 = e"'E°(N° where E5/No is the signal-to-noise ratio per bit.
`
`3. The Class of “'I‘urbo-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
`The
`ith code C,
`is an (ng,N,) linear block code, and the ith encoder is preceded by an
`interleaver (permuter) P; of size N,-, except G1 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 3. graph-theoretic tree. We call a code of this type a “turbo-like" code.
`Define sq = {1, 2, .
`.
`. , q} and subsets of sq by 3; = {i E sq : C; connected to input},
`so = {i 6 sq:
`: C, connected to output }, and its complement E9. The overall system
`depicted in Figure 1 is then an encoder for an (n, N) biock code with n = 2,580 11,-.
`If we know the IOWE A331,“ ‘s for the constituent codes C,-, we can calculate
`the average IOWE A,,_.,;, for the overall system (averaged over the set of all possible
`interleavers), using the umform interlea-uer technique
`[2].
`(A uniform interleaver is
`defined as a. probabilistic device that maps a given input word of weight ‘LU into all
`distinct
`permutations of it with equal probability p = 1/ ‘).) The result is
`
`(3']')
`
`(1 AU)
`A"""h = Z Z A21)--‘I1 H ::':iIhi
`MNEIO h.=iEԤo
`1'-=2 Wt)
`2n‘.—_n
`
`202
`
`Hughes, Exh. 1011, p. 4
`
`
`
`In (3.1) we have 111,- = w ifé E s;, and w.- = h) if 0;‘ is preceeded by 03- (see Figure 2.).
`We do not give a. proof of formula (3.1), but it is intuitively plausible if we note that
`the term
`is the probability that a. random input word to C5 of weight wg
`will produce an output word of weight h,-.
`For example, for the (rag +113 +114, N ) encoder of Figure 1 the formula. (3.1) becomes
`
`A
`
`=
`
`AU}
`
`{h2+hs+’H=’|‘.'
`
`At?)
`192.52
`
`(£212)
`
`A(3) A“)
`103.913
`II-MJM
`
`(is)
`
`(:3
`
`= E
`h1.ha.PI3.1'|.g
`(h2+h3+h.'=h)
`
`mi
`
`1
`
`Ai4E,)ha A5l3;}.h3 A.El4;_),h4 I
`
`output
`
`Figure 1. A “turbo-like" code with
`Sf = «[1,2]-,s.9 = {2,3,4},§o =
`
`
`
`Figure 2. C; (an (n.,v, N,-) encoder) is connected to C,-
`(an (nj, Nj) encoder) by an interleaver of size Ni. We
`have the “boundary conditions” N; = 11,- and w,- = h,-.
`
`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 A3,, denotes the IOVVE when the input block has length N, we introduce
`the following notation for the union bound (2.2) for systems of this type:
`
`(4-1)
`
`la‘€«B“%‘i
`
`ll=1
`
`A‘'.:’_,.) z".
`
`10:1
`
`Next we define, for each fixed to 2 1 and h 2 1.
`
`(4.2)
`
`or('w, P2.) = lim sup logN Aflh.
`N—vao
`
`It follows from this definition that if 1.0 and h are fixed,
`
`Afihz" = O(N°'l‘“'M'*")
`
`as N ~> oo,
`
`for any 5 > 0. Thus if we define
`
`(4.3)
`
`15!-4' =
`
`o:(w. la).
`
`it follows that for all is and h,
`
`.4fi_,,i** = o(NfiM+E)
`
`as N —. oo,
`
`for any E > O. The parameter BM, which we shall call the interleaving gain exponent
`(ICE), was first introduced in [2] and [3] for pa.raJlel 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 79, which depends on the qr
`component convolutional codes and the tree structure of the overall system, but not
`on N, such that for any fixed En/No > ")fo,8S the block length N becomes large,
`
`(4.4)
`
`P553 = O(N"”)
`
`Eq. (4.4) implies that if £31” < 0, then for a given Er,/Nu > we the word error prob-
`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.’
`In [7], we discuss the calculation of o(w, h) and EM for a. concatenated system of
`the type depicted in Figure 1, using analytical tools introduced in [3] and
`For
`example, for the parallel concatenation of q codes, with q — 1 interleavers, we have
`
`J6M'S-'q+2i
`
`with equality if and only if each of the component codes is recursive. For a “classical”
`turbo code with q = 2, we have EM = 0, so there is no word error probability inter-
`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. Sufiice it to say that the interleaving gain exponent for bit error probability
`is fig“ — 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,
`
`I32»: 5 -
`
`+1.
`
`where dfiee is the minimum distance of the outer code. Therefore, for serial concate-
`nated codes, if d} 3 3 there is interleaving gain for word error probability. (If the inner
`code is nonrecursive £33.; 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 I (1 + D}, but we prefer to think of it as
`a. block code whose input block [.I1,... ,:I:,.] and output block [y1, . .. ,y,..] are related
`by the formula
`
`y1=5F1
`
`yg =31 +12
`
`ya =31 +32 +13
`
`y,.=;c1+:.rg+:c3+---+:.c,,.
`
`
`
`rate “Q
`repetition
`
`qN X qN
`permutation
`matrix
`
`N
`[w]
`
`LENGTH
`[WEIGHT]
`
`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 (q'n.,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)
`
`0
`
`0
`
`Aida = { (")
`
`if h 96 qw
`if h = qty.
`
`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):
`
`(53)
`
`AS?“ = iilwizfil (r-J}:.3 1-1)’
`
`It follows then from the general formula (3.1), that for the (qN, N) RA code represented
`by Figure 3, the ensemble IOWE is
`
`(5.4)
`
`w,h '*
`
`Aw) __ E AEt?.)h;A.S:1}.h
`‘—“*—'
`(ii
`_
`h,=o
`-
`: (*.:,*>(r.*:'.,,tJ(..,.:,',.L.)_
`(it
`
`From (5.4) it is easy to compute the parameters o:(w,h) and ,3“ in (4.2) and (4.3).
`The result is
`
`(5-5)
`(5.6)
`
`-==<w.h) : -
`as =— (“E”).
`
`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 possibie, we will asstune for the
`rest of this section that q = 4, the extension to arbitrary q 33 3 being straightforward
`but rather lengthy. For q = 4, (5.6) becomes BM = -1, so the IGE conjecture is
`P1}? = 0(N"') for Eb/Nu > 79 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
`h—1
`P§{.B = Z Z zh.
`h=2'u.-.-:1
`
`41»
`
`Denote the (w,h)th term in the sum (5.7) by TN (w,h):
`H--1
`N 4N—h
`)(2u.r-1 zh‘
`21»
`(it)
`
`TN(w’h}d£fAwIhZh =
`
`Using standard techniques (e.g.
`Cw-*1):
`
`[8, Appendix A]), it is possible to show that for all
`
`(53)
`
`TN(w_h) 3 D2h[F{:=-v}+1os2 =1‘
`
`where D = 4/\/1? is a. constant, 5: = w/4N, y = h./4N,
`
`:
`
`F(I.y) =
`
`—§H2(4m) + (1 — y)H2(%f;) + yszfif)
`y
`
`.
`
`206
`
`Hughes, Exh. 1011, p. 8
`
`
`
`is the binary entropy function. The
`and H2(I) = +a:log2(x} - [1 — s:)log2(1 — 2:)
`maximum of the function F(:c,y) in the range 0 5 2:: -3 y 3 1 — 2:: occurs at (:J:,y) =
`(0.100, 0.371) and is 0.562281, so that if log, z < —0.562281, the exponent in (5.8) will
`be negative.
`Let us therefore assume that logg 2 < —0.562281, which is equivalent to Eb/No =
`—(1/r)lnz = -4111: 2 4 - 1112 - 0.562281 = 1.559 = 1.928 dB.
`If E is defined to be
`E = — log; 2 + 0.562231, it follows from (5.8) for 3.11 w and h,
`
`(5.9)
`
`TN(w, :2) 5 D2"‘E.
`
`What (5.9) tells us is that if Eb/N9 > 1.928 dB, most of the terms in the union bound
`(5.?) 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
`
`as 3
`hN — E log; N,
`
`and write
`
`4N h/2
`PUB = Z Z TN(w, h)
`h=2w=1
`
`hm h/2
`4N
`= Z 2 comb; + Z
`h=2w=1
`.a=.a,.,+1w=1
`
`h/2
`
`T.~(w,h)
`
`= 31 + 32.
`
`It‘s easy to verify that when N is large enough, Aw+1‘,=;fAw_,r; < 1 for h 3 Em and
`w 5 h/ 2 5 hN/2, which shows AM, is a decreasing function of w for large N. Thus
`the sum 5'; can be overbounded as follows (we omit some details):
`
`_I.,,, M2
`81 = Z Z cmw, h)
`h=2‘-U'.I=1
`
`hm
`J‘lN M2
`= ZT,y(1,h) + Z Z TN('w, h)
`h=2
`!:-_-2 11:22
`
`9:” M2
`= ouv-‘) + Z Z T~(w,h)
`hr-2 111:2
`
`bu 5/2
`g O(N“) + Z Z A2,,,z*'
`h=2 w=2
`
`rm, h/2
`= o{N-11+ Z Z 0[.-H3/N2)z"
`h=2 w=2
`
`= o(N-1) +0(hi,/N?)
`= o(N-1).
`
`207
`
`Hughes, Exh. 1011, p. 9
`
`
`
`For the sum S2, we bound each term TN(w, h) by (5.9):
`
`4N M2
`32 = Z Z T.~(w.h)
`h=1«.,.,+1w=1
`4N PI/2
`
`IA
`
`:3 202'”
`l1N+l. 111:1
`-KIN
`
`=9/2 Z 112-”
`hN+1
`
`2_E'l""' hu +1
`
`5 Dmfl
`
`= O(N‘3 log; N)
`= o(N“2).
`
`We have therefore shown that for the ensemble of q = 4 RA codes, if E1,/No )-
`1.928 dB,
`
`(5.10)
`
`13$“=s1+s2=o(N")+o(N-1)=o(N-1).
`
`which as we saw above, is the ICE conjecture in this case.
`Although the union bound gives a proof of the IGE conjecture for RA codes, the
`resulting value of "rug
`is by no means the best possible.
`Indeed,
`if we use the recent
`Viterbi-Viterbi improved union bound [9] to bound the sum S3, we can lower the value
`of ‘ya considerably, eg. 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"
`79 for RA codes with q in the range 3 3 qr 3 8 using both the classical union bound
`and the Viterbi-Viterbi improved union bound to the cutofl’ threshold for the ensemble
`of all codes (i.e., “random codes") of a fixed rate. We believe that these values of
`70 can be reduced still further, for example by using the bound of [6] instead of the
`Viterbi-Viterbi bound.
`
`q
`
`3
`
`4
`
`5
`
`6
`
`7
`
`3
`
`RA Codes (Union Bound)
`Random Codes (Union Bound)
`
`2.200
`2.031
`
`1.928
`1.853
`
`1.798
`1.775
`
`1.721
`1.694
`
`1.670
`1.651
`
`1.631
`1.620
`
`RA Codes (Viterbi Bound)
`Random Codes (Viterbi Bound)
`Binary Shannon Limit
`
`0.313 -0.125 -0.402 -0.592 -0731
`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-
`hlcelihood decoding is very good. However, the complexity of ML decoding of RA
`
`208
`
`Hughes, Exh. 1011, p. 10
`
`
`
`union bound random codes
`viterbi bound random codes
`Shannon limit binary input
`union bound FIA codes
`viterbi bound RA codes
`
`0
`
`0.1
`
`0.2
`
`0.3
`
`0.4
`
`0.5
`Code Flata Fl
`
`0.6
`
`0.?
`
`0.8
`
`(1.9
`
`Figure 4. Comparing the RA code “cutofl' 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-
`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 cutofl 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.
`
`2.
`
`1. C. Berrou, A. Glavieux, and P. Thitirnajshima, “Near Shannon limit error-
`correcting coding and decoding:
`turbo codes,“ Proc.
`19.93 IEEE International
`Conference on Communications, Geneva, Switzerland (May 1993), pp. 1064-1070.
`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..
`S. Benedetto and G. Montorsi, “Design of parallel concatenated convolutional
`codes," IEEE Transactions on. Communications, vol. 44, no. 5, [May 1996} pp. 591-
`600.
`
`3.
`
`4. S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Serial concatenation
`of interleaved codes: performance analysis, design, and iterative decoding,“ IEEE
`Trans. on Inforrnotion Theory, vol. 44, no. 3, [May 1998). pp. 909-926.
`
`209
`
`Hughes, Exh. 1011, p. 11