`
`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
`
`Apple v. Caltech
`IPR2017-00219
`
`Replacement - Apple 1203
`
`
`
`PROCEEDINGS
`
`THIRTY-SIXTH ANNUAL ALLERTON CONFERENCE
`ON COMMUN'ICATION. CONTROL. AND COMPIFTIVG
`
`Tamer Basar
`Bruce Hajck
`Conference (To-Chairs
`
`Conference held
`Septemhcr 23 - 25, I998
`Allcrton House
`Monticello. Illinois
`
`Sponsored by
`The Coordinated Science Laboratory
`The Department of EIcclriélirlind Computer Engineering
`UNIVERSHEKUS; ILLINOIS
`Urbana-(fiampaign
`
`ii
`
`
`
`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: dariusmshannon.jp1.nasa.gov,
`
`(hui, rjm)@systems.caltech.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 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 conjccture about the behavior of the ensemble (maximuni-likelihood
`decoder) word error probability as the word length approches infinity. We prove this
`conjecture for a simple class of rate l/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 l/(l + D). We believe this represents the first rigorous proof of a
`coding theorem for turbolike codes.
`
`1. Introduction.
`
`The 1993 discovery of turbo codes by Berrou. Glavicux. 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 [Sb/Nd exceeds some threshold. Our proof technique is to derive an
`explicit expression for the ensemble input-output. weight enumerath (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 —+ 0c. Unfortunately the diffi-
`culty of the first step. i.e.. the computation of the ensemble IOWB, has kept us from
`full success, except for some very simple coding systems, which we call repeat and ac-
`cumulatc 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. NOR-9505975,
`AFOSR grant no. 5F49620-97—1—0313, and grant from Qualcomm.
`
`20l
`
`
`
`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 maximum-likelihood
`
`word error probability for block codes.
`Consider a binary linear (12,19) block code C with code rate r = k/n. The (output)
`weight enumerator (WE) for C is the sequence of numbers A0, .
`. . _ A", where A). 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 Aw)“ 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 memoryless
`binary-input channel, using maximum likelihood decoding, has the well-known form
`71
`
`(2-1)
`
`(2.2)
`
`PW 3 2A,,»
`h=l
`n
`k
`
`= Z (Z A“) z“.
`
`211:]
`
`h=l
`
`In (2.1) and (2.2), the function 2:h represents an upper bound on the pairwise error
`probability for two codewords separated by Hamming (output) distance h. For AWGN
`channels. 2 = (mi/""0 where Eb/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 q encoders (circles) and q — l
`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 sq = {1, 2, .
`.
`. ,q} and subsets of 5,7 by s; = {i E 5,,
`: C, connected to input},
`so = {i E 3.,
`: C, connected to output }, and its complement 50. The overall system
`depicted in Figure 1 is then an encoder for an (11,1'V) block code with n = 2,90 71,-.
`If we know the IOWE Agim‘s for the constituent codes C,, we can calculate
`the average IOWE Aw), for the overall system (averaged over the set of all pessible
`interleavers), using the uniform interleauer technique
`(A uniform interleaver is
`defined as a probabilistic device that maps a given input word of weight in into all
`distinct
`permutations of it with equal probability p = l/ (1').) The result is
`
`Q A“)
`Aw.h= Z Z Affilhin (‘33:;
`" "5'0 h .l' 3
`i=2
`fir..-»
`‘ E o
`
`(3.1)
`
`202
`
`
`
`In (3.1) we have w; = w ifi e s]. and w.- = h,- if C.- is preceeded by 01- (see Figure 2.).
`We do not give a proof of formula (3.1), but it is intuitively plausible if we note that
`the term Aszihl/ is the probability that a random input word to C; of weight w.-
`will produce an output word of weight hi.
`For example, for the (112 +713 +114, N) encoder of Figure 1 the formula (3.1) becomes
`
`
`
` (2) (3) (4)
`__ 2 AU) Al”?th Awafis Aim-hi
`4
`‘ "’v" _
`'51-,”
`N3)
`N3
`Ni
`h‘.h3.h3.h4
`w;
`1113)
`(WA)
`(Ago-ha-t-h‘nh)
`
`(‘0
`(3)
`(2)
`
`2 AU) Aunhz Aftth Abnhn
`N)
`(m)
`("0'
`A,.hg.n3.h4
`:41
`hi
`hi
`(h2+ha+h‘uh)
`
`
`
`output
`
`Figure 1. A “turbo-like" code with
`S] = {1.2}, so = {2,3,4},30 =
`
`
`
`Figure 2. C; (an (m, N‘) encoder) is connected to Cj
`(an (111, NJ) encoder) by an interleaver of size N]. We
`hi.
`have the “boundary conditions” NJ = n. and w,
`
`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
`
`
`
`infinity. If Ax“ denotes the [OWE when the input block has length N, we introduce
`the following notation for the union bound (2.2) for systems of this type:
`1:
`N
`
`(4.1)
`
`PUB‘i—i’z ( AL.) 2".
`
`111:]
`
`h=l
`
`Next we define, for each fixed w 2 l and h 2 l.
`
`(4.2)
`
`(1(u1. h) = lim sup logN A3,.”
`N—cc
`
`It follows from this definition that if 111 and h are fixed.
`
`Afihz" = 0(N"(w~">+*)
`
`as N —; 00,
`
`for any 6 > 0. Thus if we define
`
`(4.3)
`
`i3," =
`
`o(w. h).
`
`it follows that for all m and h,
`
`Ag'hzh = 0(Na”+‘)
`
`as N —a 30‘
`
`for any 6 > 0. The parameter 6M, which we shall call the interleaving gain exponent
`(ICE), 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 l.
`
`The IGE Conjecture. There exists a positive number 70, which depends on the (1
`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)
`
`193,8 = 0(Ni’M)
`
`Eq. (4.4) implies that if [3M < 0, then for a given Eb/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.1
`In [7], we discuss the calculation of 01(w. h) and {31" for a concatenated system of
`the type depicted in Figure 1, using analytical tools introduced in
`and
`For
`example, for the parallel concatenation of q codes, with q - l interleavers, we have
`
`3M S ‘Q + 21
`
`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. Suffice it to say that the interleaving gain exponent for bit error probability
`is HM -1.
`
`204
`
`
`
`
`
`As another example. consider the serial concatenation of two convolutional codes.
`if the inner code is recursive then.
`
`if,” S -
`
`19
`
`1
`
`+1,
`
`where d"
`rm, is the minimum distance of the out-er code. Therefore, for serial concate-
`nated codes. if d‘} 2 3 there is interleaving gain for word error probability. (If the inner
`code is nonrecursive :33; Z 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 ICE conjecture. We call these codes repeat and accumulate
`(RA) codes. The general idea is shewn 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 l/(l + D). but we prefer to think of it as
`a block code whose input block [1],. .
`. .r,.] and output block [311.
`.
`.
`. .y,.] are related
`by the formula
`
`lli=I1
`
`3/2 =11+I2
`
`y3=11+172+173
`
`
`
`
`rate llq
`N
`[w]
`repetition
`[qw]
`
`
`qN x qN
`permutation
`matrix
`
`
`
`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. cnumcrators for both the. (gran) repetition code, and the (71,71)
`accumulator code. The. outer repetition code is trivial: if the input block has length n,
`we have
`
`.
`
`(a) _
`
`‘4in — { (")
`
`0
`
`u!
`
`ithéqw
`
`h = ([11).
`
`205
`
`
`
` {firs..
`
`E ’
`
`i.
`
`
`33,1‘4‘5'v:
`
`’1‘Afi'filin12:159:31It‘HJoiinéanggflbfiifllz
`
`The inner accumulator code is leSS trivial, but it is possible to show that (again assuming
`the input block has length n):
`
`(53)
`
`A53. =
`
`(hulk—i 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)
`
`QN AW) AU)
`= Z w.h.qx~ hhh
`hl=0
`(qru)
`N
`N-h
`h—l
`(w) (LEW/2‘!) ([qw/ZI—l)
`qw
`(W)
`
`'
`
`From (5.4) it is easy to compute the parameters a(w,h) and am in (4.2) and (4.3).
`The result is
`
`(5.5)
`(5.6)
`
`a(w,h) = —
`[in = - [
`
`2
`
`
`VIEW-l,
`
`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 6M = —1. so the ICE conjecture is
`P39 = 0(N“) for Eb/No > '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 h/2 (N)(4N-h)(h—l
`pa}? = Z Z w
`2::N) 2111—1 zh‘
`h =2 111:]
`My
`
`Denote the (u:.h)t,h term in the sum (5.7) by Tutu), h):
`
`Twang/amt» =
`
`(z) (41:: (22:,
`N
`(2.”)
`
`Using standard techniques (e.g.
`(Iv-h):
`
`[8, Appendix A]), it is possible to show that for all
`
`(5.8)
`
`TN(w'h) S DQMF(I-ul+l082 11‘
`
`where D = 4/fi is a constant. a; = 10/4N, y = h/4N.
`
`F(x.y) =
`
`y
`
`206
`
`.
`
`
`
`is the. binary entropy function. The
`and H2(J.‘) = —:r log2(1t) - (l - z)log2(1 — 1:)
`maximum of the function F(I,y) in the range 0 5 2x 5 y S l — 2:: occurs at (1.3;) =
`(0100,0371) and is 0.562281, so that if log? 2 < «0.562281, the exponent in (5.8) will
`be negative.
`Let us therefore assume that log2 z < -0.562'281, which is equivalent to Eb/No =
`—(1/r)lnz = —4lnz 2 4 - ln2 ~ 0.562231 = 1.559 = [.928 dB.
`If E is defined to be
`= — log; 2 + 0.562281, it follows from (5.8) for all to and h,
`
`(5.9)
`
`T‘v(w, h) 5 02-”.
`
`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 —o 00. 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 chase for which it. is not. To this end. define
`
`def 3
`hN = E log2 N.
`
`and write
`
`4N h/2
`
`Pk? = Z 2 mm. h)
`h:2w=i
`
`hN h/2
`4N
`h/2
`= Z Z TN(w,h) + Z Z TN(w,h)
`h=2w=l
`h=hiv+lw=1
`
`= s. + 52.
`
`It's easy to verify that when N is large enough. .4wH'h/Awlh < 1 for h S hN and
`In S h/‘2 5 hie/2. which shows Aw).
`is a decreasing function of w for large N. Thus
`the sum 31 can be overboundcd as follows (we omit, some details):
`
`h” h/2
`s, = Z Z T~(w.h)
`h=2 u-=1
`
`’15:
`
`hN h/z
`= ZTy-(Lh) + Z Z TN(w-h)
`hz’l
`[1:2 “3:2
`’15: h/2
`= 0w“) + Z 2 new. h)
`h=2 w:2
`
`hN h/z
`s (xiv-U + Z 2 Alma"
`h=2 [11:2
`hN M2
`= 0(N“) + Z Z 0(h3/N2)zh
`h=2w=2
`
`= 0m”) + ()(hfv/Nz)
`= 0(N“).
`
`207
`
`
`
`
`
`1.
`
`g l l} l l i l
`
`For the sum 32. we bound each term T~(m, h) by (5.9):
`
`4.\-' M2
`
`52: Z szvtuuh)
`h=hx +1 u1=l
`4 N
`M2
`
`sxzmw
`liyJ-l 111.21
`4N
`
`= 0/2 X ’12-”
`h~+1
`
`m
`
`3DH
`II o
`
`A
`
`‘2’ Eh-VUIN +1)
`
`(.-V "3 log: N)
`:V_2).
`
`We have therefore shown that for the ensemble of q = 4 RA codes.
`1.928 dB.
`
`if Eb/No >
`
`(5.10)
`
`P5? = 51+ 5... = 0(N‘ 1) + 0(N'l) = 0(;v-‘),
`
`which as we saw above. is the [GE conjecture in this case.
`Although the union bound gives a proof of the ICE conjecture for RA codes. the
`resulting value of “m is by no means 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 7., 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"
`70 for RA codes with q in the range 3 s q S 8 using both the classical union bound
`and the ViterbivViterbi 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
`7., can be reduced still further. for example by using the bound of
`instead of the
`Viterbi~Viterbi bound.
`
`(1
`
`3
`
`4
`
`5
`
`(5
`
`7
`
`8
`
`RA Codes (Union Bound)
`Random Cr)ch (Union Bound}
`
`RA Codes (Viterbi Bound)
`Random Codes (V iterbi Bound)
`
`Binary Shannon Limit
`
`1.631
`1.670
`1.721
`1.798
`1.928
`2.200
`1.620
`1.651
`1.694
`1.775
`1.853
`2.031
`0.313 —0.125 ~04“)? -—O.59'.-? —O.731
`1.112
`0.214 —O.‘22-1 —O.486 —0.662 —0.789 —().885
`
`—0.-'195 -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 performance of RA codes with maximum-
`The results of this paper show that
`likelihood decoding is very good. However,
`the complexity of ML decoding of RA
`
`208
`
`
`
`
`
`‘1'" '—‘T_
`r“
`B "—‘ 'r‘
`r.-.__._ ____ __ ____
`
`‘1'"
`
`'
`
`- -
`-
`-—~
`-— - -
`0
`0
`I4r
`+
`
`union bound random codes
`viterbi bound random codes
`Shannon limit binary input
`union bound RA codes
`viterbi bound RA codes
`
`
`
`4
`
`7
`
`s
`
`5 4
`
`
`
`0.4
`
`0.5
`Code Rate R
`
`0.6
`
`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»
`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 cutoil' 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.
`
`"Near Shannon limit error—
`1. C. Berrou. A. Glavicux. and P. T hitimajshima.
`corrccting coding and decoding:
`turbo codes." Proc.
`1993 IEEE' International
`Conference on Communzcatmm. Geneva, Switzerland (May 1993). pp. 1064—1070.
`2. S. Benedetto and G. Montorsi. “Unveiling turbo codes: some results on parallel
`concatenated coding schemes”. [E’le Trans. on Inf. Theory, vol. 42. no. 2 (March
`1996). pp. 409428..
`S. 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. Pollarn. “Serial concatenation
`
`4.
`
`8.
`
`of interleaved codes: performance analysis. design. and iterative decoding.“ IEEE
`Trans. on Information Theory, vol. 44. no. 3. (May 1998). pp. 909—926.
`
`209
`
`