emphaaSF
`
`%,diene
`
`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 INinois at Urbana-Champaign
`
`Apple v. Caltech
`IPR2017-00701
`Apple 10031117
`Replacement - Apple 1117
`
`

`

`PROCEEDINGS
`
`THIRTY-SIXTH ANNUAL ALLERTON CONFERENCE
`ON COMMUNICATION, CONTROL, AND COMPUTING
`
`Tamer Basar
`Bruce Hajek
`Conference Co-Chairs
`
`Conference held
`September 23 - 25, 1998
`Allerton House
`Monticello, Hlinois
`
`Sponsored by
`The Coordinated Science Laboratory
`
`The Department of Bueaat Computer Engineering
`cnemeaRiry oF ILLINOIS
`Gaaecrnamuens
`
`ii
`
`

`

`Coding Theoremsfor “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.caltech.edu
`
`Abstract.
`
`In this paper we discuss AWGNcoding 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 codeis a rate 1 convolutional code with
`transfer function 1/({1 + D). We believe this represents the first rigorous proofof 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 allowpractical encoding and decoding algorithms. This paperis an attempt
`to illuminate the first of these two attributes, i.e., the “near Shannonlimit” capabilities
`of turbo-like codes on the AWGN channel.
`Our specific goal is to prove AWGN coding theoremsfor 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 andinter-
`connection topology, we attempt to show that as the block length approaches infinity,
`the ensemble (overall possible interleavers) maximumlikelihood error probability ap-
`proaches zero if E,/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 worderror probability approaches zero as N -» oc. Unfortunately the diffi-
`culty of the first step, i.e., the computation of the ensemble I[OWE, 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 techniquewill yield coding theorems
`for a much widerclass of interleaved concatenated codes. In anycase, it is satisfying to
`have rigorously proved coding theorems for evena 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,
`AFOSRgrant no. 5F49620-97-1-0313, and grant from Qualcomm.
`
`201
`
`1
`
`

`

`In Section 3 we
`channel, which is seen to depend on the code’s weight enumerator.
`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
`performanceis 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 rate r = k/n. The (output)
`weight enumerator (WE) for C is the sequence of numbers Ap,..., An, where A, de-
`notes the number of codewords in C with (output) weight h. The input-output weight
`enumerator (IOWE) for C is the array of numbers Ayn, w = 0,1,...,4,h =0,1,...,n
`Ay, denotes the number of codewords in C with input weight w and output weight h.
`The union bound onthe worderror probability Py of the code C over a memoryless
`binary-input channel, using maximum likelihood decoding, has the well-known form
`n
`Pw < 35 Anz*
`h=1
`n
`k
`
`(2.1)
`
`(2.2)
`
`=)" (> Aun] z
`
`h=1
`
`\w=1
`
`In (2.1) and (2.2), the function z* represents an upper bound on the pairwise error
`probability for two codewords separated by Hamming (output) distance h. For AWGN
`channels, z = e~"*/No where E,,/No 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 g 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, whichis 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 cal] a code of this type a “turbo-like” code.
`Define s, = {1,2,...,q} and subsets of sy by s; = {i €
`sg : C; connected to input},
`so = {i €
`sq: C; connected to output }, and its complement 30. The overall system
`depicted in Figure 1 is then an encoder for an (n, N) block code with n = Deas n;.
`If we know the IOWE ADa, 5 for the constituent codes C;, we can calculate
`the average IOWE A,» for the overall system (averaged over theset ofall possible
`defined as a probabilistic device that maps a given input wna of weight w into all
`interleavers), using the uniform interleaver technique
`[2].
`(A uniform interleaver is
`distinct (™) permutations of it with equal probability p = 1/ (™).) The result is
`q AM)
`(2)
`=> YS aa TR
`
`AyrE20 hy, 31€3oO
`EAgeh
`
`202
`
`2
`
`

`

`In (3.1) we have w; = w if i € s;, and w; = A, if C; is preceeded by C; (see Figure 2.).
`We do not give a proof of formula (3.1), but it is intuitively plausible if we note that
`the term AS): / Gs is the probability that a random input word to C; of weight w;
`will produce an output word of weight );.
`For example, for the (nz +n3+74, N) encoderof Figure 1 the formula (3.1) becomes
`
`gt
`A
`“wh =
`
`5
`hy hghg dg
`(hg thgthy=h)
`
`A®) A?) AM)
`
`w2,hg
`“*ws hy
`“"we he
`Na)
`Na)
`Na)
`we
`ws
`wa
`
`q)
`wry
`
`as ? Au‘hy (*)
`
`
`Q) wh
`
`a
`
`Ay. Ag.tg ha
`{hgthgthg =r)
`
`
`
`output
`
`output
`
`output
`
`Figure 1. A “turbo-like” code with
`sp = {1,2},s0 = {2,3,4}, 30 = {1}.
`
`
`
`Figure 2. C; (an (ni, Ni) encoder) is connected to Cj
`(an (n;, Nj) encoder) by an interleaver of size N,. We
`have the “boundary conditions” N, = n, and w; = hj.
`
`4. The Interleaving Gain Exponent Conjecture.
`in which
`In this section we will consider systems of the form depicted in Figure 1,
`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
`
`3
`
`

`

`infinity. If A¥,, denotes the IOWE when the input block has length N, we introduce
`the following notation for the union bound (2.2) for systems of this type:
`n
`N
`
`(4.1)
`
`pues) @ A] zh
`
`h=1
`
`\w=1
`
`Next we define, for each fixed w > 1 and h > 1,
`
`(4.2)
`
`a(w, h) = limsup log, AN,.
`N—oo
`
`It follows from this definition that if w and Aarefixed,
`
`ANnz® = O(NS™+4)
`
`as N > 09,
`
`for any « > 0. Thusif we define
`
`(4.3)
`
`By = max Tmax aw, h).
`
`it follows that for all w and h,
`
`ANaz” = O(N8™ rs
`
`as N > 00,
`
`for any € > 0. The parameter Gay, 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 anyfixed E,,/No > yo,as the block length N becomes large,
`
`(4.4)
`
`PYP = O(NS™)
`
`Eq. (4.4) implies that if Gay < 0, then for a given Ey/No > yo 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 a{(w,h) and Gy, 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 gq — 1 interleavers, we have
`
`Bu < = + 2;
`
`with equality if and onlyif each of the component codesis recursive. For a “classical”
`turbo code with q = 2, we have Gay = 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.
`
`! 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 By — 1.
`
`204
`
`
`
`4
`
`

`

`As another example, consider the serial concatenation of two convolutional codes.
`If the inner code is recursive then,
`
`+1
`
`By < - || +1,
`
`where dp... is the minimumdistance of the outer code. Therefore, for serial concate-
`nated codes, if d? > 3 there is interleaving gain for word error probability. (If the inner
`code is nonrecursive Gj; > 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
`Nis repeated g times, scrambled by an interleaver of size qN, and then encoded by
`arate 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 ofit as
`a block code whose input block {4),...,2,] and output block [y),.... Yn} are related
`by the formula
`
`w= Fh
`
`y2 = 7, +22
`
`Y¥3 =F, +F2+ 73
`
`Yn = Ly + Lot Tt +b Bas
`
`(5 1)
`
`LENGTH
`
`[WEIGHT]
`
`
`
`
`N
` rate i/q
`
`repetition
`[w]
`{qw]
`{qw]
`
`aN x GN
`permutation
`matrix
`
`rate l
`1/{(1+D)
`
`Figure 3. Encoder for a (¢N,.N) repeat and accumulate
`code. The numbers above the input-output lines
`indicate the length of the corresponding block, and
`those below thelines 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 codeis trivial: if the input block has length n,
`we have
`
`(5.2)
`
`(o) _
`
`Aniki ~ { (#)
`
`f9
`
`ifh A qw
`
`ifA= qu.
`
`205
`
`5
`
`

`

`The inner accumulator codeis less trivial, but it is possible to show that (again assuming
`the input block has length 7):
`
`Aon = (Tai) (tora a)
`©)
`It follows then from the general formula (3.1), that for the (¢N, N) RA code represented
`by Figure 3, the ensemble IOWEis
`
`(i) _{n-h
`
`h-1l
`
`qN_
`
`alo)
`
`(3)
`
`AN) = >; Aun Ah, h
`N
`h,=0
`(ad
`3
`_
`— (a) (Suzi) (reeyat—1)
`aN)
`Ca)
`
`(5.4)
`
`w,
`
`From (5.4) it is easy to compute the parameters a(w,h) and By,
`Theresult is
`
`in (4.2) and (4.3).
`
`(5.5)
`(5.6)
`
`= 2)w
`
`alu [4]
`Bu = - |
`
`—2
`
`
`
`4
`
`q
`
`:
`:
`
`It follows from (5.6) that an RA code can have word error probability interleaving gain
`only if g > 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 muchas possible, we will assume for the
`rest of this section that g = 4, the extension to arbitrary g > 3 being straightforward
`but rather lengthy. For g = 4, (5.6) becomes 8), = —1, so the IGE conjecture is
`PYP = O(N~!) for E,/No > 70 in this instance.
`The union bound (2.2) for the ensemble of g = 4 RA codes is, because of (5.4),
`
`(5.7)
`
`4N h/2 ea (AR —*y( A-1
`PYP = S00 eee
`h=2w=l
`Cea)
`
`Denote the (w,h)th term in the sum (5.7) by Ty (w, A):
`N) (4N=h)(h-1
`
`Tn (w, hh)A,nz" = Ck oa (es zh
`(ae)
`
`Using standard techniques (e.g.
`(w.h),
`
`[8, Appendix A]), it is possible to show that for all
`
`(5.8)
`
`Tn (w, h) < DQhF(.y)+log, 7
`
`where D = 4/\/7 is a constant, « = w/4N, y = h/4N,
`
`F(z,y) =——
`
`206
`
`6
`
`

`

`and H2(x) = —a log,(a) — (1 — x)log,(1 — x) is the binary entropy function. The
`maximumof the function F(z,y) in the range 0 < 2x < y < 1 — 2z occurs at (z,y) =
`(0.100, 0.371) and is 0.562281, so that if log, z < -0.562281, the exponentin (5.8) will
`be negative.
`Let us therefore assumethat log, z < —0.562281, which is equivalent to E,/No =
`—(1/r)Inz = —4|nz > 4-1n2- 0.562281 = 1.559 = 1.928 dB.
`If F is defined to be
`— log, z + 0.562281, it follows from (5.8) for all w and A,
`
`(5.9)
`
`Ty(w,h) < D227",
`
`What (5.9) tells us is that if By/Ny > 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
`
`ef 3
`
`hves log, NV,
`
`;
`
`and write
`
`4N h/2
`= 5 S- Ty (w.h)
`A=2w=1
`
`hy h/2
`4N
` h/2
`= SoS Ty(w.h) + SSS Ty(w,h)
`h=Qw=1
`Ashy+lw=1
`
`= Si + So.
`
`It's easy to verify that when N is large enough, Aw+1,/Awa <1 for h < hy and
`w < h/2 < hy /2, which shows A,,, is a decreasing function of w for large N. Thus
`the sum S; can be overbounded as follows (we omit somedetails):
`
`hy hf2
`= 300 Tr(w,h)
`h=2w=1
`
`hy h/2
`
`= St(1,h) +> 2,Taw.h)
`ON + 3D Pale h)
`
`h=2w=
`hy h/2
`
`=? w=?
`
`hy h/2
`S$ O(N!) + 3° SO Aone”
`A=2w=2
`
`hy &/2
`N-*) + $° S> O(A3/N*)2"
`h=2w=2
`= O(N!) + O(h3,/N?)
`= O(N~'),
`
`207
`
`7
`
`

`

` ||
`
`8
`
`For the sum $2, we bound each term Ty (1, h) by (5.9):
`
`anoohf2
`Sx= S> So Tv(w.h)
`h=hyntlua=t
`4N h/2
`23; yore
`Ay+iwel
`
`4Nn
`.
`= D/2>~ ha-*F
`hAntl
`2° ERN(hy +1)
`
`1A oO5bI
`
`ti 2
`
`(N~ logs NV)
`cy,
`
`We have therefore shown that for the ensemble of gq = 4 RA codes. if £,/No >
`1.928 dB.
`
`(5.10)
`
`P&B = S$, +S, =O(N~')+0(N7!) = O(N7!),
`
`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 49 is by no means the best possible.
`Indeed,
`if we use the recent
`Viterbi- Viterbi improved union bound [9] to bound the sum S»2. we can lower the value
`of y considerably, e.g. for g = 4 from 1.928 dB to 0.313 dB. In Figure 4 and Table | we
`display our numerical results on RA codes. There we compare the “cutoff threshold”
`“uy for RA codes with g in the range 3 < gq < 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
`y can be reducedstill further, for example by using the bound of[6] instead of the
`Viterbi- Viterbi bound.
`
`q
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`RA Codes (Union Bound)
`Random Codes (Union Bound)
`RA Codes (Viterbi Bound)
`RandomCodes (Viterbi Bound)
`Binary ShannonLimit
`
`1.631
`L670
`1.721
`1.798
`1.928
`2.200
`1.620
`1.651
`1.694
`1.775
`1.853
`2.031
`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 maxizmum-
`likelihood decoding is very good. However,
`the complexity of ML decoding of RA
`
`208
`
`

`

`
`
`
`
`iie
`7+} ~ 77
`union bound random codes
`eae viterbi bound random codes
`*= = +
`shannonlimit binary input
`j
`*
`*
`union bound RA codes
`6+}
`
`|* +—viterbi bound RA codes
`
`
`
`a1Aaasdrinaimieiebeneaeicedcemsiensmmnanenitccare
`
`%.ee,te
`
`"‘
`
`\
`
`5‘ <\4‘
`
`s\\
`
`‘ *
`
`\
`
`>) -
`
`|;
`
`|
`i
`
`:
`06
`
`;
`0.7
`
`0.8
`
`09
`
`a
`
`+
`
`ee
`
`a er
`
`.Se
`
`\ “
`
`03
`
`0.4
`
`0.5
`Code Rate R
`
`Figure 4. Comparing the RA code “cutoff threshold” to
`the cutoff rate of random codes using both theclassical
`union bound and the Viterbi-Viterbi improved union bound.
`
`codes, like thatof 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 g = 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 g = 3 appears to be less than 1 dB,
`compared to the upper bound of 1.112 dB found in Table 1.
`
`References.
`L
`
`to
`
`C. Berrou, A. Glavieux. and P. Thitimajshima, “Near Shannonlimit error-
`correcting coding and decoding:
`turbo codes,” Proc.
`1993 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”, JEEE Trans. on Inf. Theory, vol. 42, no. 2 (March
`1996), pp. 409-428..
`8. Benedetto and G. Montorsi, “Design of parallel concatenated convolutional
`codes,” IEEE Transactions on Communications, vol. 44, no. 5, (May 1996) pp. 591-
`600.
`S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Serial concatenation
`of interleaved codes: performance analysis, design, and iterative decoding,” [REE
`Trans. on Information Theory, vol. 44, no. 3, (May L998), pp. 909-926.
`
`209
`
`9
`
`