pp. 173-182 173 New results on serial concatenated and accumulated-convolutional turbo code performance Audrey M. VITERBI* Andrew J. VITERBI* Abstract Previous methods for analyzing serial concatenated turbo codes employing union error bounds are extended to determine the complete output weight enumeration fimction of the code: this provides the opportunity to employ a more refined bound due to Polytrev, with consi- derably improved results limited, however, to block lengths of about 256 bits by computational constraints. The method is then applied to a new class of "accumulated- convolutional" codes, which is a simple special subclass ~f serial concatenated codes inspired by the "repeat-accu- mulate" codes of Divsalar et al. Performance appears to be superior to that of conventional codes and results are obtained for nutch longer block lengths, with impressive results in regions approaching channel capacity. Key words: Error correcting code, Turbo code, Error probability, Convolutional code. blocs bien plus longs, sont impressionnants dans Ia rggion approchant la capacitg du canal. Mots cl@ : Code correcteur erreur, Turbo code, Probabilit6 erreur, Code convolutif. Contents I. Introduction II. Weight enumeration functions and rate-weight dis- tributions III. The tangential-sphere improved union bound IV. Accumulated convolutional codes V. Conclusion Appendix References (10 ref ) I. INTRODUCTION NOUVEAUX RI~SULTATS SUR LES PERFORMANCES DES TURBO CODES SI~RIES CONSTRUITS A PARTIR DE CODES CONVOLUTIFS AVEC ACCUMULATION R6sum6 Des mdthodes usuelles employant la borne de l'union pour analyser les turbo codes concatdnds en sdrie sont dtendues pour dgterminer la fonction complkte d'dnumd- ration de poids en sortie d'un code ; on peut utiliser une borne plus fine proposde par Polytrev, borne qui amd- liore considdrablement les rdsultats. Cette borne est cependant limitde, pour des raisons de complexitd de cal- cul it des blocs de longueur de l'ordre de 256. La mdthode est ici appliqude gt une nouvelle classe de codes ~ convolutifs accumulds ~, qui est une simple classe par- ticulikre de codes concatdnds en sdrie, inspirds des codes it ~ rdpdtition-accumulation ~ de Divsalar et al. Les per- formances obtenues sont supdrieures gt celles des codes classiques et les rdsultats, qui sont obtenus pour des Ever since Shannon established the discipline of information theory, it has been known that codes exist for which error probability decreases monotonically to zero as the length of the code grows to infinity. Even stronger results were established in the fifties and sixties indicating that, for most codes, the error probability decreases exponentially with the length of the code for all rates less than capacity. This optimistic scenario was, however, clouded by the facts that no well defined code construction seemed to exhibit this performance, and more importantly, to achieve it the decoding algo- rithm operations generally grow exponentially with code length. Early emphasis was on algebraic code construction and corresponding decoding algorithms, which fell short of the ideal performance. Later convo- lutional codes with sequential decoding algorithms afforded the possibility of long codes with exponentially decreasing error probabilities, but with two serious drawbacks : this performance was limited to rates below the computational cutoff rate, considerably below chan- * QUALCOMM Incorporated, San Diego, CA 92121, USA 1/10 ANN. TI~LI~COMMUN., 54, n ~ 3-4, 1999
`
`Hughes, Exh. 1031, p. 1
`
`

`
`174 A. VITERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE nel capacity, and the probability of failure to decode exhibited a Pareto distribution with respect to available buffer memory. Nevertheless, convolutional codes gra- dually became the standard means for reducing the required channel signal-to-noise ratio (Eb/No) in wire- less communication, magnetic recording and other applications wherein the interference was primarily additive Gaussian noise. With short code constraint lengths, the optimal decoder could be implemented practically, and performance, while far from the ideal, achieved a coding gain in terms of dB of the Eb/N o of a Gaussian channel which was approximately half the dif- ference between uncoded performance and that corres- ponding to channel capacity. Further improvements were achieved by concatena- ting such a relatively short convolutional code as an inner code, with an outer block code, generally the Reed- Solomon algebraic code which employed a higher-order alphabet whose size corresponded approximately to 2 x where K is the constraint length of the inner convolutio- hal code. This approach became the standard for NASA interplanetary missions as well as for satellite direct broadcasting and achieved very low error probabilities down to Eo/N o approximately corresponding to cutoff rate. To approach closer to capacity, much longer convo- lutional constraint lengths and outer block lengths were implemented, but their complexity exceeded practical limits for all but well funded space missions. A major limitation of these concatenated decoder implementa- tions was the generation of hard decisions out of the inner decoder to be used as input to the outer decoder. Improvements were shown to result from replacing these hard decisions by soft decisions generated according to an appropriate metric. Much better performance was demonstrated by empi- rical means in 1993 using parallel concatenated turbo codes with iterative soft decision decoding between com- ponents of the concatenated code. Specifically, Berrou et al [1] generated a posteriori probability (APP) soft deci- sion metrics in decoding the first component and used these in decoding the second, in turn generating APP soft decisions for the second component which were fed back to soft decode the first component once again, continuing to iterate between components for a number of times. The unexpectedly excellent results, using relatively simple codes but large interleavers between component codes, gave rise to a new era in error-correcting coding with a totally different perspective than what had been the traditional view. The first theoretical results on turbo codes, due to Benedetto et al [2] showed that bit error probability for optimally decoded parallel concatenated codes (at high EJN o) decreased only inversely with block length, rather than exponentially. Benedetto et al [3] later showed that the conventional serially concate- nated code, with an appropriate interleaver, when opti- mally decoded, exhibited an error probability which for large EI/N o decreases as a power of the interleaver length approximately equal to half the free distance of the outer convolutional code. While much progress has been made in the selection, implementation and evaluation of both parallel and serial turbo codes, there remain two important open issues : a) determination of whether iterative soft decision APP decoding approaches, with increasing numbers of iterations, the optimal maximum likelihood decoding of the composite code ; b) analytical evaluation of optimal decodeur error probabilities, particularly for very long interleavers at Eb/N o approaching channel capacity. The first issue is still open. This paper deals with the second issue. While union bounds have been evaluated numerically [4], they diverge at the cutoff rate. Here we obtain a complete determination of the output weight enumeration function and, using this and a recent refine- ment on the union bound, we obtain tighter bounds on error probability which remain finite for all Eb/N o, and small for values well below that corresponding to cutoff rate. We obtain extensive results for a new class of codes, which we call "accumulated convolutional codes," inspired by the recent surprising results of Div- salar et al [5] II. WEIGHT ENUMERATION FUNCTIONS AND RATE-WEIGHT DISTRIBUTIONS For any binary block code of K inputs and N outputs, we may define the input-output weight enumeration function 00WEF) K N (1) T(W, Z) = ~, ~ To,, W ~ Z" k=l n=l where Tk, ' is the number of codewords of (output) weight n generated by input sequences of weight k. We also define (2) An(W) = )_~ T/," W ~ k as the input weight enumeration function, being the enu- merating polynomial of all input weights which generate codewords of weight n, and define (3) B,(Z~ = Z T~,, Z" n as the output weight enumeration function, being the enumerating polynomial of all (output) codewords gene- rated by an input of weight k. Note also that (4) T(W,Z) = ~ A,, (W) Z" = ~ B k (Z) W k n k For an additive white Gaussian noise (AWGN) channel with antipodal binary inputs - WE s, where E. = E~R, with R being the code rate, it is well known [6] that the union-Chernoff bounds on block and bit error probabili- ties are, respectively, AN~. TELI~COMMUN., 54, n ~ 3-4, 1999 2/10
`
`Hughes, Exh. 1031, p. 2
`
`

`
`A. VITERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE PE < T (W = 1, Z = e - EJNo) (5) dT _ es/UO) Pb <--~(W= 1,Z=e The weight enumeration functions of turbo codes, whether parallel or serially concatenated, can be obtai- ned from their component codes by employing the arti- fice of Benedetto et al which involved taking the ensemble average over alt possible interleaver permuta- tions. Figures l a and l b show the typical configurations K input~ K IIIplJIs __ L L [ --I I~ ~-- --t N outputs .... / - FIG. 1. -- Turbo code examples a) parallel concatenated, b) serial concatenated. - Note each G(D) may be a matrix of polynomials, representing a rate k/n code hk'enwles de turbo codes for parallel and serial concatenated codes. In each case the interleaver permutation is assumed to be selected ran- domly. For good performance, Gl (D) and G2(D) forpa- rallel, and Gi(D ) for serial, turbo codes must be recursive encoders. Then, as has been shown by Benedetto et al [2], for parallel concatenated codes, since that the overall code is systematic (information bits transmitted unco- ded), the ensemble average IOWEF is given by K B (t) (Z) B~ 2) (Z) (6) T/,(W,Z) = ~ WkZ k where the degree of the polynomial in Z is k k and the code rate R = K/N. The form of (6) follows from the fact that for each output generated by GI(D), after permutation the second encoder G2(D ) can generate any one of k outputs, corresponding to one of as many per- mutations of k input ones among K input symbols. For the serial concatenated codes [3], the interleaver ensemble average IOWEF is given by 175 L A~)(W)B~)(Z) (7) T s(W,Z) = ~' where L is the size of the interleaver, dmin is the mini- mum weight of the outer code, K/L is the rate of the outer code, L/N the rate of the inner code, and the overall rate is again R = KIN. The form of (7) follows from the fact that if f is the weight of the outer code output, which after permutation is also the inner code input, tor each such output there will be (~) possible permutations for the inner code input sequence. In [4] we employed (5) and (7) to obtain the union- Chernoff bounds for serially concatenated convolutional codes by computing the functions Ae(W) and Be(Z). (We show the recursion equations, which we developed from the convolutional code state transition matrix, in Appendix I for the simple codes of Figures 2a and 2b.) Eneoder a) Nonreeursive [G0(D)] 7---- @--" b) Recursive [Gi(D)] State Transition Matrix [C(W,Z)] [-I o z~ o i w o I z 0 z wz o wz ! ~ 1 0 WZ 2 0 I IWZ2 0 t 0 I 0 WZ 0 Z z o wz l FIG. 2. -- Component convolutional codes Codes convolutifs dl&nentaires We were able to obtain results in [4] for large values of L because W and Z took on numerical values as indicated by (5). The drawback was that the union bound only converges for Eb/N o above the value which corresponds to the cutoff rate. To go beyond this, it is necessary to use more refined bounds to be described in Section I[I, which require the determination of the output weight enumera- tion polynomial in Z, T(W-- 1, Z). Then for serially concatenated codes it follows from (7) that AC(1) can again be computed numerically,* but Be(Z) is a polyno- mial. Though it can still be computed recursively, the * Note that we could equally handle Pb by replacing A t (1) in (8) by [A t (I + E) - At(1 - E)]/2(cid:127). However, we shall deal only with block error probability PE throughout, because data transmission is becoming mainly oriented toward packet networks with the option to repeat incorrect packets. 3/10 ANN, TELI~;COMMUN,, 54, n ~ 3-4, 1999
`
`Hughes, Exh. 1031, p. 3
`
`

`
`176 recursion is among polynomials, which imposes a sto- rage requirement proportional to L 2, hence limiting the interleaver size for which the output WEF can be practi- cally computed to no greater than L --< 512. Then L A e (1) Be, (Z) N (s) r(l,Z)=2 __ Zc. z" Note that the coefficients C, which denote the number of codewords of output weight n, grow exponentially with N. We define, therefore, a logarithmic measure which we call the rate-weight distribution (9) rna-_ In (Cn)/N which is the rate of the subcode of codewords of weight n. Figure 3 shows the rate-weight distribution for several -- K=256 I ..... K=128 .......... K=64 [ -- entropy bound 0,2 035 }... .... ! ...... .. 0,05 ~ : o ~/...535. -0.05 i (cid:12)9 0 0,2 0.4 n/N 0,6 0,8 1 FIG. 3. -- Rate-weight distribution for 4-state inner and outer codes of Figure 2 Rendement-distribution de poids pour les codes intdrieurs et extgrieurs b 4 dtats A. VITERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE values of K for a serially concatenated code of rate 1/4 with component codes which are rate 1/2 convolutional codes, respectively the outer code of Figure 2a and the inner code of Figure 2b. Also shown for comparison is the rate-weight distribution for the ensemble average of single randomly selected (N, K) codes ; this is simply 7"=Nln t 2K\ n/ 2 Nj = -~ In -(1-R)ln2 H (n/N) - (1 - R) fn 2 where H(.) is the entropy function to the base e. Note the close convergence, for large N, of the serially concatenated code to the random code rate- weight distribution for mid level values of n, but the considerable divergence at low and high n. ties. Several variants of Gallager's exponential bounds [7, 8] have been applied to turbo codes, with mediocre improvements over the union bound. Given that, as was shown by Benedetto et al [2] [3], the error probability of turbo codes decreases only as a power of the interleaver (and hence block) size, these exponential bounds are not particularly suited to turbo code performance. Instead, as was first noted by Sason and Shamai [9], a more recent bound due to Poltyrev [10] yields far superior results. This so called tangential-sphere bound (TSB) is a refinement on the union bound which isolates those received signal-plus- noise vectors which fall outside a cone of angle 0 from the correct transmitted signal vector. Denoting this N-dimensio- nal cone C(0), we have the bound on block error probability (10) Pc< Pr(E;zEC(O) + Pr (zr where E denotes error and z is the received N-dimensio- nal noise vector. Using simple geometric constructions it is shown that if the code's output WEF is III. THE TANGENTIAL-SPHERE IMPROVED UNION BOUND N T(Z)=~_. C Z ",then n= I PE < min f As noted in Section I, traditional error probability bounds have generally concentrated on determining the exponent of the block or convolutional code error probabili- e-Z12/2 n <-- Nr2/S--------~2 1 + r2/S 2 - 1 r2 (S- Zl)2t/ (11) +~,~.N[ , ~--2- ]/dzl + Q(s) / where r is the radius* of the cone measured along the u~ tangent to the signal sphere of radius S = /2E~N E is the signal energy of each of the N binary symbols and N 0 f e -z2/2 is the one-sided AWGN density, Q(x) = 4- ~ dz is 1 tk the complementary error function, y(k, x) =~ 0 e -t dt is the incomplete 7-function, and ?'(k, x) = 1 - Y (k, x). Because this bound in this form is not particularly well documented, we provide the derivation in Appendix II. Suffice it to note that the 7 term outside the summa- tion and Q(S) correspond to signal-plus-noise vectors outside the cone, the second term of (10). Also, if we let r ~ and eliminate the cone, then lim ~e z'2/2 C ( N~-nn ) r---~ PE (r)< f ~/~ ,, ~<~ N ''Q (S-z,) dz, = 2 Cn Pr z2> (S-z 1) p(zl)dz I n = dmi n -~ * For a given N, the minimizing value of r/S remains constant for all values of S. Note also that for virtually all cases of possible interest, S being pro- portional to ~ renders Q(S) absolutely neglible. ANN. TI~LECOMMUN., 54, n ~ 3-4, 1999 4/10
`
`Hughes, Exh. 1031, p. 4
`
`

`
`A. VITERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE 177 where z I and z, are independent unit variance zero mean Gaussian varial~les. We may express this as lira --->~ N ( N~_n S) PE(r)< E C nPr Z> dZ f n = dmi n z 1 whereZ = z 2 + N- n for which E(Z) = O, Var (Z) = 1 + -- so that N lim (12) r-->~ Pc(r)< E n = dmi n C,, n N N-n N-n e - Z2(N-n)I2N dZ ~ %/2IIN/(N - n) N : 2 C,,Q(~/---n-~) whereS= V~s/No n = d min which is the traditional union bound. (Note that the union-Chernoff bound of (5) replaces Q(x) by e- ~2/2.) While Poltyrev's TSB bound appears to be somewhat more complex than the union bound, it is easily compu- table numerically. Figure 4 shows the TSB and union IV. ACCUMULATED CONVOLUTIONAL CODES We now consider a very simply described class of binary codes inspired by the interesting and surprisingly good results obtained by Divsalar et al [5] for the class of repetition-accumulator (RA) codes. These involved merely repeating each input information bit k times and, after interleaving, passing the output to an accumulator whose transfer function is 1/(1 (9 D). We generalize from the tri- vial repetition code to an arbitrary rate R convolutional code as the outer code of a serially concatenated turbo code, but employing the accumulator as the inner code of unity rate, as shown in Figure 5. K inputs N N outputs ! I L -- 3 Gi(D) = I/(1 @ D FIG. 5. -- Accumulated-convolutional code Codes convolutifs avec accwnulation First, following [5], we show that for this inner code, (13) Be(Z) = Z 2/2 2/2]- 1 n = Fe/2l thus avoiding the necessity to compute the inner code polynomial recursively. Consider first the case when 2, the number of input ones to the inner code, is even. The first, third and all odd input ones will start a sequence of ones at the code output and the second, fourth and all even input ones will end it, as shown in Figure 6. Thus ! Input 0 0 I 0 0 I 0 0 .... I) 1 l) 0 0 0 I .... [ Output o o I I I o o o .... o I I I I I o .... / 3 FIG. 4. -- Error probability bounds for K = 256, R = 1/4 concatenated code with 4-state inner codes Bornes de la probabilitd d'erreur pour un code concatdnd avec K = 256, R = 1/4 et des codes intdrieurs ?t 4 dtats bounds for K = 256, N = 1024, for the 4-state outer, 4-state recursive inner, serial concatenated code of ove- rall rate 1/4 whose rate-weight distribution is shown in Figure 3. For comparison, the results are also shown in Figure 4 when the outer 4-state code is replaced with a 16-state nonrecursive rate 1/2 code whose tap generator polynomials are 1 (9 D 2 (9 D 3 (9 D 4 and 1 (9 D (9 D 4. The computational memory burden in computing the polynomials B(,(Z) make it difficult to go to higher K and N. In the next section, we consider an inner code for which the Be(Z) polynomial can be expressed in closed form so that much higher values of K can be considered. FIG. 6. -- Typical input and resulting output of accumulator (1/( 1 @ D) Entrde typique et sortie associde d'un accumulateur 1/(1 + D) there are U2 runs of output ones with as many starting input ones and ending input ones. Now if the total num- ber of output ones (the codeword weight) is n, the num- ber of ways that these can be distributed among the . N-n totalityofoutputsymbols, N, ls( 2/2 )(n-I k2/2 - I ]' since the first binomial represents the number of ways the 2/2 starting ones can be placed, while the second binomial is the number of ways the 2/2 ending ones can be placed, the last one being fixed by the totality of output ones. On the other hand, if 2 is odd, the number of starting ones which we are free to choose is Lg/2J, the integer value of 2/2, because the last starting one is fixed by the number of output ones, n, which must end at the end of the block 5/10 ANN. TI~L~COMMUN., 54, n o 3-4, 1999
`
`Hughes, Exh. 1031, p. 5
`
`

`
`178 of N symbols. The number of free ending ones is the same, but we write this as I-g/2] -1 in (13) to preserve the same notation for both even and odd cases. Inserting (13) in (7), we obtain after interchanging order of sum- mation, and noting that L = N, the overall WEF L (14) Ts(I'Z) = Z Ae(1) Be(Z)/(NI) e=df N = Z CnZ" n = [dj./2~ N ii- where C,, ~-_'@.ae(1)(~Ne/2])(~f/2] 1 l)/(~) and where d/is the free distance of the outer convolutio- hal code. Note that this shows that for the concatenated code dram = Fdf/2]. We also find that the first term of the WEF is proportional to Ad/(1)[N-~df/2?] [dJ2?-I / N [_dl./2J]( [4,/2~- ' ] (dj)-Adf (1)N-Fdfl2q But Adj. (1), the number of inputs which generate a codeword of weight df, is also on the order of N, so that the dominant term for large EJN o is proportional to N I~U21 +~, which agrees with the more general result for serial turbo codes of Benedetto et al [3] and esta- blishes the error floor for such codes. Figures 7 and 8 show the rate-weight distribution for A. vrI'ERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE the numerator remain nearly unchanged (except for the negative unity) when n is replaced by N-n. This is in marked distinction to the rate-weight distribution for the codes considered in Section II. Note that even though the expression (14) is explicit, the binomial coefficients must be computed recursively and the numbers become very large. Since ultimately we seek the logarithm of the sum of terms, we may deal with logarithms throughout so as to keep the terms within rea- sonable limits. Logarithms of products of terms are, of course, sums of logarithms of the terms, but logarithlns of sums are less natural. Note, however that if A and B are large numbers and we have computed a =lnA and = lnB, which are manageable, then gn(A + B) = (e a + e/~) = max (ot,[3) + In(1 +e [c, ~1) all of which operations are quite well bounded. The error probability TSB and union bounds for these rate 1/2 accumulated-convolutional codes are shown in Figures 9 and 10 for 4-state and 16-state outer codes. FJG. 7. -- 4-state outer, accumulated-convolutional code Code convolutif extdrieur gt 4 dtats avec accumulation FIG. 9. -- Error bounds for 4-state outer, rate 1/2 accumulated-convolutional code Bornes de la probabilitd d'erreur pour des codes com,ohmf~ extd- rieurs & 4 dtats avec accumulation, de rendement 1/2. Fro. 8.- 16-state outer, accumulated-convolutional code Code convolutifextdrieur d 16 dtats avec accumulation rate 1/2 accumulated-convolutional codes with 4-state and 16-state outer codes (the same as considered in Sec- tions II and III) for K = 256, 1024 and 4096. The distri- butions are nearly symmetrical in n/N as a consequence of the form of (14), where the binomial coefficients in ANN. TELECOMMUN,, 54, n ~ 3-4, 1999 FIG. 10. -- Error bounds for 16-state outer, rate 1/2 accunmlated-convolutional code Bornes de la probabilitd d'erreur pour des codes convoltmf~ extdrieurs gt 4 dtats avec accumulation, de rendement 1/2. 6/10
`
`Hughes, Exh. 1031, p. 6
`
`

`
`A. VITERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE 179 These were computed using (11 ) with the C n coefficients of (14). Note that the term multiplying each C,, may be very small and hence subject to computation underflow, while C may be very large and subject to overflow; however, by again computing logarithms both can be dealt with accurately. For a proper comparison with the rate 1/4 serial turbo codes considered in Section III, with the error probabi- lity bounds shown in Figure 4, we also consider rate 1/4 accumulated-convolutional codes. We construct these from the rate 1/2 codes of Figures 9 and 10 by repeating each outer code symbol twice before interleaving. The rate-weight distributions for K = 1024 are shown in Figure 11, and the error bounds for K = 256 and 1024 I- I 0,15 I ! 0A/ " I / 0.05 0,00 ,~..~. I" [ _ 0,00 0,20 / 0,40 -- K=1024, 4-State ~. ...... K=256, 16-Slate "~ ...... K=1024, 4-State "~ ...... K=256.16-Stale I ~-- Entropy Bound / ,i 0,60 0,80 1,00 n/N FIG. 11. -- Rate-weight distribution for rate 1/4 accumulated-convolutional code Rendement-distribution de poids pour des codes convoluttf~ avec accumulation, de rendement 1/4 are shown in Figure 12. For comparison, the concatenated rate 1/4 codes of Section III are also shown for K = 256. FIG. 12. -- Error bounds for rate I/4 serial turbo and accumulated-convolutional code Bornes de la probabilitd d'erreur pour des turbo codes sdrie de rendement I/4 utilisant des codes convolutifs avec accumulation V. CONCLUSIONS Performance of the accumulated-convolutional codes considered, assuming maximum likelihood decoding, is surprisingly close to capacity. For rate 1/2, 4-state convolu- tional codes at block error probability of .01, the bounds are less than 0.7 dB from capacity* for a block length of 1 K bits, and 0.4 dB from capacity for a block length of 4 K bits (with interleaver sizes 2 K and 8 K, respectively). Using 16- state convolutional codes reduces these values by less than 0. ldB, but it brings down the error floor by orders of magnitude, since this is proportional to N 2 for the 4-state but N 3 for the 16-state, where N is the interleaver size. For the rate 1/4 accumulated-convolutional codes considered, which are the same codes as for rate 1/2 but with each symbol repeated twice before interleaving and accumulating, performance at block error probability of .01 is again between 0. 6 and 0.7 dB from capacity for block lengths of 1K bits. Here the difference between 4-state and 16-state code is negligible, except for the error floor. What is more surprising is that for block length 256, where we have a comparison with the more conventional serial turbo codes, the simpler accumulated-convolutional codes out- perform the former by 0.2 to 0.4 dB at an error probability of .01, and have much lower error floors. The improvement at low Eb/N o may be explained by the symmetry of the rate-weight distribution which reduces the relative rates for low weights (comparing Figure 11 with Figure 3). The much lower error floor is easily explained by the fact that this floor is approximately proportional to N af/2 where d/ is the free distance of the outer code. For the rate 1/4 serial- turbo codes considered, the outer code had rate 1/2, while for the accumulated-convolutional codes it had rate 1/4, since the accumulator has rate 1 ; hence the outer free dis- tance is at least doubled, explaining the lower error floor. The overall impression left from these results is that provided the block length of the concatenated code and the associated interleaver is sufficiently large, the structure of the component codes may be extremely simple and yet, among the ensemble of interleaver permutations, nume- rous choices will lead to low maximum likelihood decoder error probabilities at EJN o values very near the Shannon limit for AWGN channels. One final caution, however; all these results pertain to maximum likelihood decoding of the composite code. A practical decoder employing iterative a posteriori probability soft decision decoding of each component code can at best approach this performance. Considerable empirical (simulation) evidence has demonstrated that iterative decoders are effective for conventional parallel and serial concatenated turbo codes. There is far less corroboration of such itera- rive performance for accumulated-convolutional codes. Nevertheless the superior error bound results and the grea- ter simplicity of this code class codes warrants further study of their performance with iterative turbo decoding. o * For rate 1/. codes, capacity of the binary-input AWON channel corresponds to EJN o = 0.2 dB ; for rate 1/4 codes it corresponds to -0.8 dB. 7/10 ANN. TELI~COMMUN., 54, n ~ 3-4, 1999
`
`Hughes, Exh. 1031, p. 7
`
`

`
`180 Appendix I. Recursion relations for A e (W) and B((Z) A. VITERBI - NEW RESULTS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PERFORMANCE Appendix II. Poltryev's tangential sphere bound We illustrate the calculations by means of the exam- ples of the convolutional codes of Figures 2a and 2 b, for which we have the state transition equations from node t- 1 to node t, S (~176 1 ) s(Ol)(t- 1) C(W, Z) s(lO)(t_ 1) s(ll)(t- 1) S(~176 s(O')(t) s(lO)(/) = s(ll)(t) Then referring to Figure 2a we may obtain A e (W) the input WEF when the output has weight 2, for this nonre- cursive convolutional code from the recursion relations : A(~176 = A?~ A~'~ (t-l) A(~Ol)(t) = wa(00) WA(IO)(t_I) .... ~_2 (t- 1) + A(em)(t) = a(~ (t-1) + a(ll) (t--1) A(]l) WA (01) (t-l) + wa(ll) (t-l) e (n)= e-1 .... e 1 with initial conditions Ae(OO)(o) = 1, A~ sl (0) = 0 for all (s) :~ (00) A{.,) (0) = 0, for all (s) when ~ < 0 ,(, Then for an L-symbol interleaver, the desired input WEF is A e (W) ~ A~ ~176 (t = L), which assumes termination in the state (00). Similarly referring to Figure 2b we may obtain B e (Z) the output WEF when the input has weight o for this recur- sive convolutional code from the recursion relations : 8:'(,) = z2 BL~ 1) B~0I)(/) = g 2 B~~176 l ) -I- S~ 10, (t-i) B(IO) ZB~~ ) Jr- ZB~ ll) (t-l) e (t) = - B(~) _ ~(ol) (i1) e (t)=zt~ c (t-1)+ZBe_l(t-1) with initial conditions Bg ~176 = l, B~ s) (0) = 0 for all (s) ~ (00) BI: ) (0) = 0 for all (s) when ~ < 0. Then for an L-symbol interleaver, the desired output WEF iS Be(Z) = B~~176 (t = L), which assumes termination in the state (00). These expressions are used to obtain Figures 3 and 4. Let x 0 be the N-dimensional transmitted vector of normalized length* S = ~v/NEs/(No/2). Let x be any other signal vector (of the same length) which differs from x 0 in n symbols and let z = (z l, z 2 "'" ZN) be the noise vec- tor each of whose components has zero mean and unit variance. The component z] is taken to be along vector x 0 (shown in Figure A1 with the convention that z I is positive r x """"',\\ Dr I~ Zl \ r, i, o Xo , \ \ 0 N\ 0 FIG. A1. -- Plane projection of signal and noise vectors Projection sur un plan des vecteurs de signal et de bruit when it is pointing toward the origin). The three points x o, x,, and the origin define a plane. Ois the cone angle, z 2 is the other noise component in the plane and all other noise components are orthogonal to the plane, r is the radius of the cone C(O) measured on the hyperplane tangent to the signal hypersphere at x o. M is the midpoint of the distance from x 0 to x and D is half the distance from x 0 to x. Now suppose we fix r and the value of z:. Then conditio- ning PE on these values and using (10), we have (A. 1) PE(r, zl) < Pr(E; zEC(O) Ir, Zl)+Pr(z ~C(O)]r, zl). (A. 2) Letting ~ = z , we may interpret Y2 to be the length of the noise vector orthogonal to z 1 and Y3 = ~ - "22 be the length of the noise vector orthogonal to the plane containing z I and z 2. From these definitions and Figure A1, it follows that for the second term of (A. 1) Pr(z ~ C(O)[r, Zl) = Pr(Y 2 > r 1 [r,z 1) (a. 3) = - 1 , q>S '~ Wc normalize by ~v/No/2 so as to deal with unit variance noise vectors. ANN. Tf~L~COMMUN., 54, n ~ 3-4, 1999 8/10
`
`Hughes, Exh. 1031, p. 8
`
`

`
`A. VITERBI - NEW RESUUFS ON SERIAL CONCATENATED AND ACCUMULATED-CONVOLUTIONAL TURBO CODE PREFORMANCE where r I depends on r and z l, as we shall show below, and Y2 is an N-1 dimensional chi-squared variable. For the first term of (A. 1), we have the union bound Pr(E:z E C(O)]r, zt) < ~', Cn Pr (E,,[z I, r; Y2 < rl) I1 = 2 CnPr(rl>z2>fln(Zl); n:[Sn(z 1) < r I < 2 Cn Pr (rl >Z2>fln(Zl ); n : ]3 n (z(cid:1)91 < r I Y3 < "~v/r] - fl~2 (Zl)) r I (a. 4): 52 C,, f Pz2 (z)dz n : ,~n (Zl) < rl fln(Zl) i ~/r12- fin2 (Zl) PY3 (y) d y where r 1 and fl~ (zl) are shown graphically in Figure A1 and will be determined below. Now "-.2 is a single zero mean unit variance Gaussian variable while Y/is the square root of a sum of squares of Gaussians and hence I) 2 is a chi-square variable. It fol- lows that the integrals in (A. 4) and (A. 3) are 'i (A. 5) J P= (z)dz=Q(fl,(Zl))-Q(r 1) 2 '[3n(Z I ) ~ e -y 2/2 where Q (x) = J ~ d y while (A. 6) and (A. 7) qq2 fl,,2 (Z~)py 3 0') d y r 2 --/~