Apple v. Caltech
`IPR2017-00297
`Apple 10031017
`Replacement - Apple 1017
`
`

`

`PR()(.'EF.DlN(2S
`
`THIRTY-SIXTH ANNUAL ALLERTON (.'ONFF.REe\'CE
`ON C'OMMU\‘l(‘!\Tl0N. CONTROL. AND COMPIFTIVG
`
`Tamer Basar
`Bruce Hajek
`Conference Co-Chairs
`
`Conference held
`Seplem her 23 - 25. I908
`Allerton House
`Monticello. Illinois
`
`Sponsored by
`The Coordinated Science l.nhoralor_\
`The Department of Eleetrietlllfiind Computer Engineering
`(?NIVERSI1?\r"(':):-' ILLINOIS
`Lirbana-(‘giampaign
`
`

`

`Coding Theorems for “Turbo-Like" Codes’
`
`Dariush Divsalar, Hui J in, and Robert .l. McEliece
`Jet Propulsion Laboratory and California Institute of Technology
`Pasadena. California USA
`
`E-mail: clariush<9sha.nnon.jp1.nasa.gov,
`
`(hui. rjm)@systems.ca.1tech.edu
`
`Abstract.
`
`In this paper we discuss AWG.\’ coding theorems for ensetnbles of coding systems which
`are built from fixed convolutional codes interconnected with random interleavcrs. 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 offer a general conjccturc about the behavior of the ensernble [maximum-likelihood
`decoder) word error probability as the word length approchcs infinity. We prove this
`conjecture for a simple class of rate 1/q serially concatenated codes‘ where the outer
`code is a 41-fold repetition code and the inner code is a rate 1 convolutional code with
`transfer function 1/ (1 + D). W'e 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. Glavicux. and Thitimajshima [1] has
`mvolutionizcd 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 El,/No’ exceeds some threshold. Our proof technique is to derive an
`explicit expression for the ensemble input-output weight enurnerator (IOWE) and then
`to use this expression.
`in combination with either the classical union bound, or the
`recent “improvcd" union bound of Vitcrbi and \/'it.erl)i [9], to show that the maximum
`likelihood word error probability approaches zero as N —+ oc. Unfortunately the diffi-
`culty of the first step, i.c.. 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-
`rzumulalc 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 Divsalr-Lr’s work, and a portion of Robert McElie<:e’s work, was performed
`at JPL under contract with NASA. The remainder of McE|iece's work, and Hui Jin's
`work, was performed at Caltech and supported by NSF grant no. NCR—9505975,
`AFOSR grant no. 5F49G20-97-1-0313. and grant from Qualcomm.
`
`20l
`
`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 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 ma.ximum—likelihood
`
`word error probability for block codes.
`Consider a binary linear (n, It) block code C with code rate r = Ic/n. The (output)
`weight enume-rator (WE) for C is the sequence of numbers A0, .
`.
`.
`, 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 A,,,_;,, w = 0, 1, . .
`. , k, h = 0,1,...,n:
`AW, 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 C over a rnemoryless
`binary-input channel, using maximum likelihood decoding, has the well-known form
`7|
`
`(2.1)
`
`(2.2)
`
`PW g Z/i;,z"
`h=1
`n
`k
`
`= Z (2 AW.) 2".
`
`h=l w=1
`
`ln (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. 2 = e""5°/""° where E4,/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 l, 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; 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 s,, = (1, 2, .
`.
`. ,q} and subsets of sq by s; = {i 6 sq : C, connected to input},
`50 = {i E s,,
`: C',- connected to output }, and its complement E0. The overall system
`depicted in Figure 1
`is then an encoder for an (11, N) block code with n = §:‘€_,o n,-.
`If we know the IOWE A::_’.,h‘s for the constituent codes Ci, we can calculate
`the average IOWE Aw), for the overall system (averaged over the set of all possible
`interleavers), using the umforrn interleauer technique [2].
`(A uniform interleaver is
`defined as a probabilistic device that maps a given input word of weight 11; into all
`distinct
`permutations of it with equal probability p = 1/(‘:‘).) The result is
`
`<3-1)
`
`q A(i)'h.
`Aw.»-= Z Z A$3.~.H Vii.)
`1:2
`hen-‘E_-'9 h.;t'€'s'o
`WI
`
`202
`
`2
`
`

`

`In (3.1) we have w.- = w ifi 6 $1. and w.- = h,- 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?_,,_/ 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; +113 +114, N) encoder of Figure 1 the formula (3.1) becomes
`
`(2)
`(3)
`(4)
`4 h _ 2 AU)
`Awmhz Amalia A1041‘:
`- w. *
`w ,h —N"T‘ N
`(h"I+-:'.i~:2-“Ah,
`‘
`(111:
`W3)
`I
`2
`a
`«=-
`(2)
`uhh:
`'4
`(N)
`w
`
`(4)
`(3)
`Anmu Ahlnhl
`(21)
`(21)
`
`(1)
`Z ""'-’"
`h1.hq.h3.h4
`(hg-Q-h3+I:‘=h)
`
`'
`
`output
`
`Figure 1. A “turbo-like" code with
`S] = {1,2},so = {2,3,4},§o =
`
`
`
`Figure 2. Q (an (n,-, N.) encoder) is connected to C)‘
`(an (121, NJ) encoder) by an interleaver of size N]. We
`have the “boundary conditions" N, = n, and w, = h..
`
`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 Am“ 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)
`
`P“B"é‘: (
`
`=1
`
`h
`
`A;,"f_,_) 2".
`
`u.-:1
`
`Next we define. for each fixed w 2 l and h 2 1.
`
`(4.2)
`
`a(w, h) = lim suplogN A$",,.
`N-oc
`
`It follows from this definition that if w and h are fixed.
`
`A,‘:‘,'_,,z” = 0(N"<'”-“>+=)
`
`as N —» oc,
`
`for any 6 > 0. Thus if we define
`
`(4.3)
`
`£33.; =
`
`a(w. h).
`
`it follows that for all in and h,
`
`A;'X',‘z" = om-"’~+<)
`
`as N —» 30.
`
`for any 6 > 0. The parameter GM, which we shall call the rnterlea-v-ing gain exponent
`(IGE), was first introduced in
`and [3] for parallel concatenation and later in
`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 70, 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 E,./No > 'yo,as the block length N becomes large,
`
`(4.4)
`
`P3,” = 0(N”M)
`
`Eq. (4.4) implies that if [in < 0, then for a given El,/No > '70 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. Ii) and BM for a concatenated system of
`the type depicted in Figure 1, using analytical tools introduced in
`and
`For
`example, for the parallel concatenation of (1 codes, with q — l interleavers, we have
`
`[Zn 5 -‘I + 2,
`
`with equality if and only if each of the component codes is recursive. For a “classical"
`turbo code with q = 2, we have HM = 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. Suflicc it to say that the interleaving gain exponent for bit error probability
`is HM - l.
`
`204
`
`4
`
`

`

`As another example. consider the serial concatenation of two convolutional codes.
`If the inner code is recursive then.
`
`.if.ir S -
`
`1°
`
`.4
`
`1
`
`+1»
`
`where 11?,“ is the minimum distance of the outer code. Therefore, for serial concate-
`nated codes. if :1’; 2 3 there is interleaving gain for word error probability. (If the inner
`code is nonre.-cursive 433; 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. VVe 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, S(.'l'EU‘Hl)l(‘(l 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 l/(1 + D), but we prefer to think of it as
`a block code whose input block [-.n....,.c,.] and output block [y1.....y,,] are related
`by the formula
`
`.7/i=1:
`
`‘J2 =3'~i +I2
`
`y3=.I'1+;l.'g+;l.'3
`
`
`
`LENGTH
`'
`race 1/q
`repetition
` [WEIGHT] [qw]
`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 cornrsponding block, and
`those below the lines indiczite 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 enumcrators for both the (qn, n) repetition code, and the (ma)
`iiccumulator code. The outer repetition code is trivial: if the input block has length n,
`we have
`
`'
`(5.2)
`
`(0) =
`A...,;.
`
`0
`{ (3)
`
`if fl. $5 qw
`if ;. = ,,w_
`
`205
`
`5
`
`

`

`The inner accumulator code is less trivial. but it is possible to show that (again assuming
`the input block has length 11):
`
`(5.3)
`
`A2» = (:1u;2’1)(t’;23i1)-
`
`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)
`
`(IN
`(0)
`(ii
`__ E Aw.h|Ah;.h
`w,h “
`(QN)
`h,=0
`1711/
`
`('L')((i,’.‘f,};5‘..)(f,,.Z.‘/'2i_-i)
`(W) “QLU
`
`From (5.4) it is easy to compute the parameters a(w,h) and :3," in (4.2) and (4.3).
`The result is
`
`(55)
`
`(5.6)
`
`or(w,h)=—[
`2
`(I1 - 2)!!!‘
`HM = _ [(4 E 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 ICE 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 /3M = -1, so the ICE conjecture is
`PVW3 = 0(N“) for Eb/ND > 70 in this instance.
`The union bound (2.2) for the ensemble of q = 4 RA codes is. because of (5.4).
`
`(5.7;
`
`4N “/7
`we = _s_j 2
`h=2 212:]
`
`(4N—h)( h-l
`(4!!!)
`
`Denote the (u:.h)th term in the sum (5.7) by TN(w. h):
`
`mu». h)"é'Aw,..z'* =
`
`(5) "':.;’*> ;;:*.> ,,.
`4w
`(W)
`”
`
`"
`
`Using standard techniques (e.g.
`(w.h)_.
`
`[3, Appendix A]). it is possible to show that for all
`
`(5.8)
`
`TN(u.-. h) 5 D2’*iF<*-W*‘°*== “.
`
`where D = 4/\/'7? is a constant. 2: = w/4N, y = h/4N.
`
`Fm) = —§H2<4x> +<1— y)H2<-33;) + yH2(?,£>,
`U
`
`206
`
`
`
`
`
`13‘).;;;;,-,,2'w».y..-;-.~;;r;:;.,.-v.-.--(5.:
`
`
`
`
`
`6
`
`

`

`is the binary entropy function. The
`and H2(:r) = -mlog2(:r) — (l - z'}log2(1 — 1:)
`nmximum of the function F(:r,y) in the range 0 3 2x 5 y 5 l — 2:1: occurs at (I,y) =
`(0.100.0.371) and is 0.562281, so that if log 2 < --0.562281, the exponent in (5.8) will
`be negative.
`Let us therefore assume that log? 2 < —0.562281, which is equivalent to Eb/No =
`——(1/r)lnz = —4lnz 3 4 - ln‘2 ~ 0.562281 = 1.559 = 1.928 dB.
`If E is defined to be
`E = — log? 2 + 0.562281, it follows from (5.8) for all to and h.
`
`(5.9)
`
`T,~,r(w,h) 5 D2"‘E.
`
`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 tliosc for which it is not. To this end, define
`
`c 3
`.
`h,\,-d=!—E log: N.
`
`and write
`
`«IN h/'2
`
`Pk.-B = Z Z T_.v(uv. h)
`h,:2w=l
`
`hiv 5/2
`4N
`5/2
`= Z Z T~<w.h) + Z Z T~<w.h>
`h==2w=1
`h=A,y+l u.'=l
`
`= S; + 82.
`
`It's easy to verify that when N is large enough. .4..,,+1_;./A.,,‘;. < 1 for h 3 h,\- and
`w _<_ h/?. 5 h_.x,-/2. which shows Aw}. is a decreasing function of w for large N. Thus
`the sum S1 can be overhoundecl as follows (we omit some details):
`
`I”, hf?
`S. = 2 2 T.-<w.h)
`h=2 u‘=l
`
`h.v
`hN 5/2
`= ZT_v(l.h) + Z Z T~(xu.h)
`h:-.2
`h:2n.-:2
`
`hp;
`5/1’-
`: ()(.-V") + Z Z '13,-(u:,Iz)
`h=:2w=2
`
`AN h/2
`
`S (.)(1V_l) + Z 2 /l2,hZh
`h=2 u.-:2
`
`[IN ’|/3
`= 0(N- ') + Z Z 0<h3/Nos“
`h-=2 w=2
`
`= 0(N") + ()(h?\,/N2)
`= O(N").
`
`207
`
`7
`
`

`

`For the sum S3. we bound each term ’I”,v(u.=, h) by (5.9):
`
`a.v M2
`
`5'2: 2 Z7‘..v(u~.h)
`.'I=h,\,' +1 u«'=l
`-IN ’3/'3
`
`S 2 ED?”
`h,\>+1wr.l
`4N
`
`= D/2 Z n2-"'=‘
`h~+l
`
`'2’ Eh” UIN -:- ll
`
`ill/'\ 0U
`
`H
`
`51
`
`( ,-V ”3 Iog._, N)
`‘Y
`N-~).
`
`We have t.liere1'or<'. shown that for tlw exisexxrlulv of q = -1 RA codes.
`1.928 dB.
`
`if Eb/No >
`
`(5.10)
`
`P5.“ = 51+ 5-,. = ow’ 1) + o(;\"") = o(.v-1).
`
`which as vvo saw above. is t|u- [GE conje.ct.I.m.> in this case.
`Although the union bound gives a proof of the ICE conjecture for RA codes. the
`resulting value of '30 is by no ineans the best possible.
`Indeed.
`if we use the recent
`Viterbi-Viterbi improved union bound
`to bound the sum 52. we can lower the value
`of 71. consider-ably, 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. Tlu:re we compare the "cutoff threshold"
`‘:0 for RA mdos with q in the range 3 3 q 5 8 using both the classical union bound
`and the Viterbi—\I'it.erbi improved union bound to the i'utofl' threshold for the ensemble
`of all cmles (i.e.. “raurionr mdt-is") of a fixed rate. We believe that those values of
`7., mm be reduccci still further. for 4-zxnniple by using the bound of
`instead of the
`Vitcrbi—Vitorbi bound.
`
`r1
`
`RA Codes (Union Bound)
`Random Coclos (Union Bound)
`
`3
`
`4
`
`2.200
`2.031
`
`1.928
`1.853
`
`5
`
`1.798
`1.775
`
`6
`
`1.721
`1.694
`
`7
`
`8
`
`1.670
`1.651
`
`[.631
`[.620
`
`RA Codes (Vir..erbi Bound)
`Random Codes (Vitorbi Bound)
`
`0.313 -0.125 -0.402 -0.592 -0.731
`1.112
`0.214 -0322-1 -0.486 —0.662 -0.789 -0.885
`
`Binary Shannon Limit
`
`—-0.-195 -0.794 -0.963 -1.071 -1.150 -1.210
`
`Table 1.
`
`:\‘iuncrical data glezinerl from Figure 4.
`
`6. Performance of RA Codes with Iterative Decoding.
`
`the performance of RA codes with 1na.'mmurn-
`The results of this paper show that
`likelihood decoding is very good. However,
`the complexity of ML decoding of RA
`
`208
`
`8
`
`

`

`
`
`3 "‘ 1*"
`
`r-—
`
`-"7 M :-7é— --r-'
`
`.
`
`.
`
`*1
`
`-*r
`
`-——1
`
`r- - -
`-——~
`-- — -
`0
`0
`v+
`4»
`
`5
`
`union bound random codes
`vilerbi bound random codes
`shannon limit binary input
`union bound RA codes
`viterbi bound RA codes
`
`g
`
`__.,_L._..h.__L_._.__.._;......___J.__...4...__L?____L_.,
`
` 7
`
`
`
`
`
`0
`
`0.1
`
`0.2
`
`0.3
`
`0.4
`
`0.5
`Code Rate R
`
`0.6
`
`0.7
`
`0.8
`
`9.Q
`
`Figure 4. Comparing the RA code "cutolf 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 cocles. 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. W'e wrote :1 computer program to imple-
`ment this “turbo-like" decoding for RA coclcs 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-
`corrccting coding and decoding:
`turbo codes." Proc.
`109.? IEEE Intemational
`Conference on Cornmunuzatzons. Geneva, Switzerland (May 1993). pp. 1064-1070.
`2. S. Bcxxetletto and G. Montorsi. “Unveiling turbo codes: some results on parallel
`concatenated coding sclienis-5”. IEICE Trans. on Inf. Theory. vol. 42, no. 2 (March
`1996), pp. 409 »-428..
`S. Benedetto and G. Montorsi. “Design of parallel czoncatenated convolutional
`codes." IEEE Tran.sac£~ion..~; on C-'01n17luTl‘lCOi'l01ls. vol. 44. no. 5. (May 1996) pp. 591-
`600.
`S. Benedetto. D. Divsalar. G. Montorsi. and F. Pollara. “Serial cmicntenation
`
`4.
`
`3.
`
`of interleaved codes: performance analysis. design. and iterative decoding.“ IEEE
`Trans. on Info7'rna£1'rm Thczury, vol. 44. no. 3. (May i998). pp. 909-926.
`
`209
`
`9
`
`