RA C1.tex Draft of 7 Jul 1999 11:47 a.m.RA Codes Achieve AWGN Channel Capacity∗Hui Jin and Robert J. McElieceCalifornia Institute of TechnologyPasadena, California USAE-mail: (hui, rjm)@systems.caltech.eduAbstract.In ref. [3] we introduced a simplified ensemble of serially concatenated “turbo-like”codes which we called repeat-accumulate, or RA codes. These codes are very easy todecode using an iterative decoding algorithm derived from belief propagation on theappropriate Tanner graph, yet their performance is scarcely inferior to that of full-fledged turbo codes. In this paper, we prove that on the AWGN channel, RA codeshave the potential for achieving channel capacity. That is, as the rate of the RA codeapproaches zero, the average required bit Eb/N0for arbitrarily small error probabilitywith maximum-likelihood decoding approaches log 2, which is the Shannon limit. Inview of the extreme simplicity of RA codes, this result is both surprising and suggestive.1. Introduction.In ref. [3] we introduced a class of turbo-like codes, the repeat and accumulate (RA)codes, which are simple enough to allow a fairly complete theoretical analysis, yetpowerful enough to perform nearly as well as full-fledged turbo codes. The generalidea is shown in Figure 1. An information block of length k is repeated q times,scrambled by a pseudorandom permutation (interleaver) of size qk, and then encodedby a rate 1 accumulator. The accumulator can be viewed as a truncated rate-1 recursiveconvolutional encoder with transfer function 1/(1+D), but we prefer to think of it as ablock encoder whose input block [x1,...,xn] and output block [y1,...,yn] are relatedby the formula(1.1)y1= x1y2= x1+ x2y3= x1+ x2+ x3...yn= x1+ x2+ x3+ ···+ xn.In other words, the outputs of the accumulator are the mod-2 partial sums of the inputs.An RA code as just described is therefore a (qk, k) linear block code, but because ofthe unspecified interleaver, there are a large number, (qk)! to be precise, RA codes withthese parameters.For the theorist, the most important thing about RA codes is that their combina-torial properties are reasonably well understood [3],[4]. For the practitioner, the mostimportant thing is the experimentally verified fact [3] that if an iterative decoding al-gorithm derived from belief propagation on the appropriate Tanner graph is applied* This work was supported by NSF grant no. CCR-9804793, and grants from Sonyand Qualcomm.1Prep. q acc.kqk qk qk Figure 1. Encoder for a (qk, k) RA code. The “rep.q” component repeats its k-bit input block q times; the“P ” block represents an arbitrary permutation of itsqk-bit input block; and the “acc.” is an accumulator,whose outputs are the mod-2 partial sums of its inputs.to them, their AWGN channel performance is scarcely inferior to that of full-fledgedturbo codes. In this paper, we will give a partial explanation of the latter property,by using the former property to show that on the AWGN channel, RA codes havethe potential for achieving channel capacity. That is, as the rate of the RA code ap-proaches zero, the average required bit Eb/N0for arbitrarily small error probabilitywith maximum-likelihood decoding approaches log 2, which is the Shannon limit. Theremaining problem, of course, is to explain why the low-complexity but suboptimaliterative decoding algorithm performs so well.2. An Ensemble AWGN Coding Theorem for RA Codes.Our main theorem deals not with any particular RA code, but with the average, orensemble performance, as the block length approaches infinity. Therefore we begin witha brief description of what we mean by an ensemble of codes.An ensemble of linear codes is a sequence Cn1, Cn2,... of sets of linear codes of acommon rate R, where Cniis a set of (ni,ki) codes with ki/ni= R. We assume thatthe sequence n1,n2,... approaches infinity. If C is an (n, k) code in the ensemble, theweight enumerator of C is the listA0(C),A1(C),...,An(C),where Ah(C) is the number of words of weight h in C. The average weight enumeratorfor the set Cnis defined as the listA(n)0(C), A(n)1(C),...,A(n)n(C),where(2.1)A(n)hdef=1|Ck|XC∈CkAh(C) for h =0, 1,...,n.Also, we define the spectral shape of Cn,(2.2) rn(δ)def=1nlogA(n)bδnc, for 0 <δ<1,and the ensemble spectral shape :(2.3) r(δ)def= limn→∞rn(δ) for 0 <δ<1,2where we are implicitly assuming that the limit exists.As a special case, consider the ensemble of rate R =1/q RA codes. Here thesequence n1,n2,n3... is q, 2q, 3q,..., and the set Cqkconsists of (qk)! linear (n, k)block codes, all with n = qk. In [3][4] it was shown that the spectral shape for thisensemble of codes is given by the formula(2.4) rq(δ) = max0≤u≤min(2δ,2−2δ)½f(u, δ)+H(u)q¾,where(2.5) f(u, δ)def= − H(u)+(1− δ)H(u2(1 − δ))+δH(u2δ),and H(u)=−(u log u +(1− u) log(1 − u)) is the (natural) entropy function. Figure 2shows the function rq(δ) for q =4.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1−0.100.10.2δ=h/Nr(δ)Weight Spectrum of 4−RA codeFigure 2. The function r4(δ)In [4], using a bound derived in [2], we proved that if we define, for each integerq ≥ 2,(2.6) co(q)def= sup0<δ<11 − δδ1 − e−2rq(δ)2and(2.7) γqdef= qc0(q),3then if q ≥ 3, and Eb/N0>γq,asn →∞, the average maximum-likelihood word errorprobability for the ensemble of rate 1/q RA codes approaches 0. A short table of thesethresholds, together with the corresponding AWGN Shannon limit, is given below.qR γq(dB) Shannon (dB)21/23.384 0.18431/30.792 −0.49541/4 −0.052 −0.79451/5 −0.480 −0.96361/6 −0.734 −1.07171/7 −0.900 −1.1581/8 −1.015 −1.210............∞ 0(−1.592) −1.592For example, the q = 3 line of this table tells us that if Eb/N0> 0.792 dB, then asn →∞, the word error probability for the ensemble of rate 1/3 RA codes approacheszero.1On the other hand, for Eb/N0< −0.495 dB, (the Shannon limit for binary codesof rate 1/3) as n →∞, the word error probability for any sequence of codes of rate 1/3must approach 1.In the table, and more clearly in Figure 3, we see that as the rate R approacheszero, the Shannon limit approaches log 2 = −1.592 dB. This is of course well known,and in fact the value −1.592 dB is usually referred to as the Shannon limit for theAWGN channel. The interesting thing for us, however, is that the RA code thresholdsalso seem to approach −1.592 dB. This empirical observation is in fact true, and it isthe object of this paper to prove the following theorem.2.1