Application of Distance Spectrum Analysis to Turbo
`
`Code Performance Improvement
`
`Mats Oberg and Paul H. Siegel
`Department of Electrical and Computer Engineering
`
`University of California, San Diego
`
`La Jolla, California  -
`
`E-mail: moberg@ucsd.edu, psiegel@ucsd.edu
`
`Abstract
`
`We present a simple method to improve the performance of turbo codes. Dis-
`tance spectrum analysis is used to identify information bit positions aected by
`low-distance error events, which are few in number due to the sparseness of the
`spectrum. A modied encoder inserts dummy bits in these positions, resulting in
`a lower and steeper error oor in the bit-error-rate BER performance curve. For
`suciently large interleaver size, the only cost is a very slight reduction in the code
`rate. We illustrate the method using a rate  turbo code, with interleaver length
`N = : The proposed method improves the BER by an order of magnitude at
`Eb=N = : dB, with a rate loss of only ..
`
` Introduction and Background
`
`Turbo codes  parallel concatenated convolutional codes connected by an interleaver 
`were rst introduced in by Berrou et. al  , and are now widely recognized as a
`landmark development in error control coding. Two characteristic features of turbo code
`performance are the small bit-error-rate BER achieved even at very low signal-to-noise
`ratio SNR and the attening of the error-rate curve  the so-called "error oor"  at
`moderate and high values of SNR.
`Recently Perez et. al.  analyzed the codeword weight distribution and multiplicity
` the distance spectrum  of turbo codes and oered an explanation for both of these
`phenomena. By considering input sequences of length equal to the interleaver size N ,
`they derived a maximum-likelihood ML bound for the BER performance of turbo codes,
`
`Nd ~!d
`
`Pb 
`
`+N 
`
`Xd=df ree
`
`

`

`memory of the constituent convolutional code. Although the iterative decoding procedure
`utilized in turbo codes is sub-optimal  , its performance has been found to be very close
`to that of an optimal ML decoder. Thus the bound in   can be used to evaluate turbo
`code performance.
`At moderate to high SNR, the BER bound is dominated by the free-distance term,
`and the performance approaches the free-distance asymptote, Pf ree, given by
`
`Nf ree ~!f ree
`
`Pf ree =
`
`

`

`positions in the decoded frame are discarded. This process eectively removes the con-
`tribution to the BER of the free-distance error events, resulting in a lowering of the error
`oor and a change in its slope. By determining bit positions that correspond to other
`low-weight codewords, we can further improve code performance by applying this same
`procedure to those frame positions. The small multiplicity of low-weight codewords in the
`turbo code implies that the rate loss incurred by this encoder modication is negligible
`for large interleaver size.
`The remainder of the paper is organized as follows. In Section , we discuss properties
`of the constituent convolutional encoders that play a role in the analysis of turbo code
`performance. In Section , we investigate the eect of the interleaver on the distance
`spectrum and, in particular, the set of low-weight codewords. Section  provides the
`details of the new method for improving the turbo code performance, as well as BER
`simulation results that conrm the expected gains. Section  summarizes our results.
`
` Properties of the Constituent Encoders
`
`A turbo encoder consists of two or more recursive systematic convolutional RSC en-
`coders in parallel concatenation, along with interleavers which permute the input bits of
`the rst encoder before applying them to the inputs of the other encoders. Input bits
`in a frame of length N are encoded by the rst RSC, producing what we call the rst
`dimension codeword. The same information frame is permuted by the interleaver and
`encoded by the second encoder, generating the second dimension sequence. A similar
`procedure is followed with any additional encoders. Since the constituent encoders are
`systematic, only the rst information frame need be transmitted, along with the parity
`bits from each encoder. In this paper, we will consider only the case of two identical,
`rate  RSC encoders. To increase the overall rate of the encoder from  to , we
`follow the usual practice of puncturing every other parity bit in each dimension.
`Berrou, et al.  proved a property of RSC encoders that plays an important role in
`the characterization of minimum-distance error events in turbo encoders. They showed
`that if hD is the feedback polynomial of a RSC encoder, and if hD is a divisor of
`L, then hD is also a divisor of + D
`pL for any integer p  . Let i denote a
` + D
`run of ’s of length i. The result implies that an input stream Lp(cid:0) , where the two
`ones are separated by pL (cid:0) zeros, for any integer p  , will generate a trellis path that
`diverges from the all-zero path and then remerges after pL + trellis steps. The encoder
`will leave the all-zero state in response to the rst , and then will return to that state
`in response to the second .
`
`Example Consider the memory-, RSC encoder with parity-check polynomials hD =
` + D
` + D
` octal   . The feedback poly-
` octal  and h D = + D
` + D + D
`. Therefore, any binary sequence p(cid:0) ; p  , will force
`nomial hD divides + D
`the encoder to leave the all-zero state at the appearance of the rst , and return to that
`state p + steps later, in response to the second . Fig. illustrates the codeword
`corresponding to the case p = . Note that the weight of the resulting codeword is .
`
`Example  For an encoder with the same feedback polynomial hD as in Example
` , any binary sequence hDr
`; r  , will force the encoder to leave the all-zero state at
`the rst , and return at the nal . When r = , one gets the length- sequence ,
`which generates a weight- codeword.
`
`0003
`
`

`

`Input weight 2 trellis diagram for a 37/21 constituent RSC encoder
`
`1111
`
`0111
`
`1011
`
`0011
`
`1101
`
`0101
`
`1001
`
`0001
`
`1110
`
`0110
`
`1010
`
`0010
`
`1100
`
`0100
`
`1000
`
`0000
`
`States
`
`00
`
`11
`
`01
`
`00
`Branch labels
`
`00
`
`01
`
`11
`
`00
`
`Figure : Response of a octal  ,  RSC encoder with input pattern .
`
`The linearity of RSC encoders permits the interpretation of these observations in terms
`of error events. In the case of the feedback polynomial in the preceding examples, any
`p
`pair of code sequences aD and bD that dier from another by eD = + D
`; p  ;
`or eD = hDr
`; r  ; will correspond to trellis paths whose state sequences are
`distinct during the course of an error event of length equal to the degree of eD.
`For a RSC encoder, one might expect that low-weight code sequences would be gen-
`erated in response to low-weight input sequences that correspond to short error events in
`the trellis. In particular, the weight- input sequences discussed in Example , in which
`the non-zero bits are separated by a small multiple of the code constraint length L = ,
`are good candidates for producing minimum-weight code sequences. For the rate ,
`octal  ,  code, the free distance is df ree = , and Fig. depicts a minimum distance
`code sequence that is generated in response to a weight- input sequence in which the
`non-zero bit separation is one constraint length.
`As discussed in , for the constituent convolutional code, the multiplicity of free-
`distance error events, Nf ree, will be roughly proportional to the frame length N , since
`there are few restrictions on the frame positions where the event may begin. In the next
`section, we will see that the introduction of an interleaver in a parallel concatenated RSC
`coding structure will dramatically restrict the possible starting positions of free-distance
`error events.
`
` The Eect of the Interleaver
`
`The remarkable power of turbo codes comes from the combination of the parallel con-
`catenated RSC codes and the permutation of the information frame by the interleaver.
`The interleaver permutes the frame of information bits in the rst dimension prior to
`their encoding by the encoder in the second dimension. Loosely speaking, the eect of
`this permutation is to ensure that low-weight error events occur in only one dimension.
`Depending on the choice of the permutation, the interleaver can aect both the distances
`and the multiplicities of error events.
`Low-weight turbo codewords arise when the interleaver maps low-weight information
`frames that produce low-weight parity in the rst dimension into frames that produce
`low-weight parity in the second dimension.
`In view of the discussion in the previous
`
`0004
`
`

`

`section, therefore, the interleaver should avoid certain permutations of bit positions as
`much as possible. Specically, dene the polynomial bD by
`
`bD =
`
`p
`
`Xn=
`
`bnD
`
`n = hDp
`
`;
`
`and let Mp denote the indices of non-zero coecients of bD,
`
`Mp = fnjbn = g:
`
` 
`
`
`
`Then, the interleaver should avoid the following mappings of subsets of bit positions:
`
`fi; i + Lpg (cid:0)! fj; j + Lrg
`
`fi; i + Lp; j; j + Lrg (cid:0)! fk; k + Lu; m; m + Lvg
`
`fi + Mpg (cid:0)! fj + Mrg
`
`
`
`
`
`
`
`where L is the parameter in the divisibility condition of the previous section; i; j; k and
`m are positive integers  N ;  is the memory length of the constituent RSC encoder;
`and r; s; u and v are integers small enough that the corresponding information sequences
`produce low parity weight at the encoder output. Note that, in the mappings in 
`above, we require that jMpj = jMrj:
`Remark: Permutations that map unions of the various subsets above to other unions
`of these subsets having equal information weight should also be avoided.
`Analysis of random interleavers shows that an average interleaver" can accomplish
`these desired objectives fairly well , and pseudo-randomly generated interleavers have
`been found to be generally superior to other structured interleavers. The superior per-
`formance does not typically arise from a large free distance, however. Rather, the best
`performing interleavers appear to gain their advantage through drastic reduction of the
`low-distance error event multiplicity. This spectral thinning" is the property demon-
`strated through example and analysis in , and lies at the heart of the technique for
`improving turbo code performance as described in the next section.
`We analyzed the distance spectrum of a turbo code based upon the aforementioned
`rate  constituent code and a particular pseudo-random interleaver of size N = .
`In the analysis, we assume that, at the end of the information frame, the encoders in
`both dimensions are driven to the all-zero state by appending appropriate tails of length
`. The free distance of the turbo code is df ree = ; with free-distance multiplicity
`Nf ree = . As was the case for the N =   turbo code discussed in , all of the free-
`distance codewords correspond to weight- information sequences. We also determined
`the codewords of weight  or less that are generated by weight- inputs where the
`non-zero information bit positions in both dimensions are separated by a small multiple
`of the constituent code constraint length.
`In our search for mappings of bit patterns
`corresponding to powers of the feedback polynomial that mapped into a bit pattern
`corresponding to a power of the feedback polynomial, we found none which would result
`in codeword weight  or less.
`Table describes in more detail the search results for codewords of weight or less.
`The table species the positions of the non-zero bits in information frames of weight 
`that generate code sequences with weight , , or . For each bit pair, the bit separation
`in the rst dimension and the bit separation in the second dimension after permutation
`by the interleaver are indicated in the column labeled Mapping". The bit separation is
`
`0005
`
`

`

`

`

`Turbo coding (37,21,10000), Simulated and Analytical
`Simulated BER
`Free Distance Asymptote
`Distance 8 Asymptote
`
`1
`
`1.5
`SNR /dB
`
`2
`
`2.5
`
`−2
`10
`
`−3
`10
`
`−4
`10
`
`−5
`10
`
`BER
`
`−6
`10
`
`−7
`10
`0.5
`
`Figure : Simulated BER and asymptotes for distances  and .
`
`1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
`
`250
`
`200
`
`150
`
`# Errors
`
`100
`
`50
`
`0
`
`0
`
`Figure : Cumulative bit errors per bit position in frame.
`
`The fact that the distance spectrum analysis pinpointed the non-zero information bit
`positions involved in all possible free-distance error events suggests a simple modication
`to the turbo encoder that will improve BER performance. Specically, the encoder is
`modied so that it does not write information in those bit positions, but inserts randomly
`chosen dummy bits.
`If a free-distance error event occurs during decoding, only these
`positions in the information frame will be aected, so the actual information bits remain
`uncorrupted.
`If we decompose the asymptotic performance bound into spectral lines as in , it is
`clear that the spectral line corresponding to df ree =  has the greatest impact on the
`performance. By avoiding the bit positions that can be aected by free-distance error
`events, the modied encoder eectively removes the contribution to the BER represented
`by the free-distance spectral line. The observed decoded BER should therefore be reduced
`by the amount reected in the asymptote.
`Fig.  compares the simulated BER curve of Fig.  to the BER curve obtained when
`the bit positions corresponding to free-distance codewords are ignored. The simulated
`BER is reduced by a factor of about  relative to the original BER. Also shown is the
`distance- asymptote reecting the weight- codewords listed in Table . The plot shows
`
`0007
`
`

`

`Turbo coding (37,21,10000), Simulated and Analytical
`Simulated BER
`Free Dist Errors removed
`Free Distance Asymptote
`Distance 8 Asymptote
`
`1
`
`1.5
`
`SNR /dB
`
`2
`
`2.5
`
`3
`
`−2
`10
`
`−3
`10
`
`−4
`10
`
`−5
`10
`
`BER
`
`−6
`10
`
`−7
`10
`0.5
`
`Figure : Simulated BER with distance- events removed.
`
`the expected changes to the error oor, namely a lowering and change in slope.
`The modied encoder incurs a rate loss through this introduction of dummy bit posi-
`tions. However, the impact is slight for large interleaver size. For the length N =
`interleaver studied in this paper, the loss is  information bits out of , implying
`a reduction in rate of approximately . percent.
`If applied to the N =   turbo
`code in , the modied encoding procedure would discard only  information bits out
`of  , causing a decrease in the code rate amounting to less than one hundredth of
`one percent.
`Given a characterization of bit positions aected by other low-distance error events,
`the encoder can be further modied to avoid writing information into those locations,
`thereby providing additional improvement to the BER performance. By referring to Table
` , we modied the encoder to avoid positions corresponding to error events of weight , in
`addition to those of weight . The performance improvement resulting from this further
`modication is shown in Fig. . The simulated BER is reduced by an additional factor
`of about , yielding a total reduction factor of approximately  relative to the original
`BER. The gure also shows the distance- asymptote reecting the contributions of the
`weight- codewords in Table . The rate loss incurred in achieving this reduced BER
`was slight, amounting to only  information bits per frame, or about .  percent.
`Finally, the encoder was modied to successively avoid all of the positions aected by
`the error events with distance  or less that we found in our search. Fig.  shows the
`progressive reduction in the error oor, culminating in a BER improvement that is about
`an order of magnitude at an SNR of . dB. Note that there is no signicant improvement
`after the removal of the bits corresponding to the distance- events. This is due to the
`existence of distance-  events not uncovered in the search. The rate penalty incurred by
`the removal of all of the events of distance or less amounts to only  information bits
`out of , or a reduction of about .  percent. The removal of all of the events of
`distance  or less uncovered in the search amounts to eliminating only  information
`bits out of , for a rate reduction of about . percent.
`We have investigated two variations of the performance improvement scheme proposed
`above. In the rst, we use dummy bits that are known to the decoder and therefore do
`not need to be transmitted. For example, the dummy bits may be chosen to be all
`’s, and the receiver then associates to their bit positions a strong indication that the
`
`0008
`
`

`

`Turbo coding (37,21,10000), Simulated and Analytical
`Simulated BER
`Dist 6 & 8 Errors removed
`Distance 8 Asymptote
`Distance 10 Asymptote
`
`1
`
`1.5
`
`SNR /dB
`
`2
`
`2.5
`
`3
`
`−2
`10
`
`−3
`10
`
`−4
`10
`
`−5
`10
`
`BER
`
`−6
`10
`
`−7
`10
`
`−8
`10
`0.5
`
`Figure : Simulated BER with distance- and distance- events removed.
`
`Turbo coding (37,21,10000), Simulated and Analytical
`Simulated BER
`Dist 6 Errors removed
`Dist <=8 Errors removed
`Dist <=10 Errors removed
`Dist <=12 Errors removed
`Dist <=14 Errors removed
`Dist <=16 Errors removed
`
`1
`
`1.5
`
`SNR /dB
`
`2
`
`2.5
`
`3
`
`−2
`10
`
`−3
`10
`
`−4
`10
`
`−5
`10
`
`BER
`
`−6
`10
`
`−7
`10
`
`−8
`10
`0.5
`
`Figure : Simulated BER with information weight  events of distance  or less removed.
`
`transmitted bits were all ’s. The simulation results for this enhanced decoder indicate
`some improvement in performance, but the gain, only about . dB, is slight. This
`approach can be further modied to require that only one information bit position from
`each information-weight  error event be treated as a known dummy bit position, thereby
`reducing the rate loss.
`In a second variation, we attempted to increase the minimum distance of the turbo
`code by designing an interleaver that avoids the permutations described in -. In
`, we applied this criterion in the design of an S-random" permutation, as introduced
`by Divsalar and Pollara . The BER results obtained with this constrained S-random"
`interleaver were comparable to those shown in Fig. . The implementation of this design
`strategy is straightforward for long interleavers, but for short interleavers, one might
`expect the constraint on the permutation to limit the randomness" of the interleaver
`and, therefore, negatively aect performance gains. It is possible that a combination of
`the constrained interleaver approach and the dummy bit insertion technique presented
`in this paper may further improve turbo code performance.
`
`0009
`
`

`

` Conclusions
`
`We have presented a new method to lower the error oor of turbo codes with sparse
`distance spectrum. The technique involves identication of the bit positions associated
`with low-weight codewords, and modifying the encoder to avoid writing information in
`those locations. Simulation results for a particular turbo code using a pseudo-random
`interleaver of length N = show an order of magnitude improvement in BER at
`SNR=. dB with a code rate penalty of less than . percent.
`Note: The unequal error protection characteristic of turbo codes was recognized in-
`dependently by Narayanan and Stuber . They lowered the error oor by protecting
`error prone bit positions with an outer double-error correcting BCH code, achieving
`performance improvements comparable to those presented in this paper.
`
`References
`
`  C. Berrou, A. Glavieux, and P. Thitimajshima, Near Shannon limit error-correcting
`coding and decoding: Turbo Codes," in Proc. IEEE International Conference
`on Communication ICC, Geneva, Switzerland, May , pp.  .
`
` L. Perez, J. Seghers, and D. J. Costello Jr., A distance spectrum interpretation of
`turbo codes," IEEE Transactions on Information Theory, vol. , no. , pp.  
`  , November .
`
`  R. J. McEliece, E. R. Rodemich, and J. Cheng, The turbo decision algorithm," in
`Proc. rd Annual Allerton Conference on Communication, Control, and Computing,
`October , p. .
`
` C. Berrou, S. Evano, and G. Battail, Turbo-block-codes," in Turbo coding seminar,
`Lund, Sweden, August , pp. , Lund University.
`
` S. Benedetto and G. Montorsi, Unveiling turbo codes: Some results on parallel
`concatenated coding schemes," IEEE Transactions on Information Theory, vol. ,
`no. , pp.  , March .
`
` M. Oberg, A. Vityaev, and P. H. Siegel, The eect of puncturing in turbo encoders,"
`in Proceedings of the International Symposium on Turbo Codes & Related Topics,
`Brest, France, September , pp.  , ENST de Bretagne.
`
` D. Divsalar and F. Pollara, Turbo codes for PCS applications," in Proc. 
`IEEE International Conference on Communication ICC, Seattle, WA, June ,
`pp.  .
`
` K. R. Narayanan and G. L. Stuber, Selective serial concatenation of turbo codes’,"
`IEEE Communications Letters, vol. , no. , pp.  , September .
`
`0010
`
`