TURBO-CODES AND HIGH SPECTRAL EFFICIENCY MODULATION
`
`Stéphane Le Goff, Alain Glavieux and Claude Berrou
`
`Stéphane Le Goff and Claude Berrou, Integrated Circuits for Telecommunications Laboratory
`
`Alain Glavieux, Digital Communication Laboratory
`
`TELECOM BRETAGNE, FRANCE TELECOM UNIVERSITY
`
`BP 832 — 29285 BREST, FRANCE
`
`ABSTRACT This paper presents a new coding scheme based
`on the association of a turbo-code [1] with a bandwith-
`efficient modulation. It is shown that the new coding scheme
`provides a substantial coding gain both on Gaussian channels
`and Rayleigh channels. On a Gaussian channel, it outperforms
`64-state trellis-coded modulation (TCM) by 2.5 dB at the bit
`error rate (BER) of 10'6. On a Rayleigh fading channel, it
`outperforms 64-state TCM optimized for that environment.
`
`1 - INTRODUCTION
`
`Turbo-codes, newly introduced by Berrou et al [1],
`are binary error—correcting codes built from the parallel
`concatenation of two recursive systematic convolutional codes
`and using a feedback decoder. Simulations over a Gaussian
`channel, using binary modulations (2—PSK or 4-PSK), have
`shown that turbo-codes possess an error-correcting capability
`unmatched at the present time.
`In order to improve the transmission spectral
`efficiency, it is interesting to combine turbo-codes with a
`bandwith-efficient modulation. In this paper, we investigate in
`particular combining a turbo-code of rate R with QAM
`constellations, over Gaussian and Rayleigh channels. This
`approach can be considered as an alternative to the
`conventional Trellis Coded Modulation (TCM). It is generally
`simpler to implement and moreover results in better
`performance than TCM, on both Gaussian and Rayleigh
`channels.
`
`2 - TURBO-CODES PRINCIPLE
`
`Turbo—codes result from concatenation of two
`recursive systematic convolutional (RSC) codes. In Fig. 1, an
`example of a rate R =1/3 standard turbo-encoder is shown.
`Two RSC elementary encoders C1 and C2, with the same
`constraint length K =5 and the same polynomial generators
`(23, 35) are used. Both elementary encoder C1 and C2 receive
`
`the same information string {dk} but arranged in a different
`sequence due to the presence of an interleaver 11 and a delay
`line L1. Given an input bit dk , the encoder outputs at time k
`are equal to dk
`itself since encoding is systematic, and the
`
`outputs c: and c; of the elementary encoders C1 and C2.
`
`0-7803-1825-0/94 $4.00 © 1994 IEEE
`
`645
`
`
`Cl
`
`
`Recursive
`
`Systematic
`
`Code (23,35)
`
`dk
`
`
`
`
`Recursive
`
`Systematic
`Code (2335)
`
`Figure 1 Rate R=ll3 standard turbo-encoder
`
`The turbo-decoder is made up of P pipelined idenn'cal modules
`as depicted in Fig. 2 and thus the turbo decoder structure is
`modular [1]. The pth module input at time k is made up of
`demodulator outputs (Xk)p-l and (Yk )p_I
`through a delay
`line and of extrinsic information (Zk )p-l provided by the
`(p-l)th module. Extrinsic information (Zk)p_l
`is new
`information concerning bit dk but affected by a noise weakly
`correlated with the noise that perturbs the observations
`(Xk )p_1 and (Y,( )p_l. Therefore extrinsic information and
`observations provided by the demodulator can be used jointly
`by the (p-1)th module for carrying out a new decoding of bit
`dk. The extrinsic information acts as a diversity effect and can
`therefore improve the decoder performance. Each module
`consists of two elementary decoders (DEC1 and DECz) in a
`serial concatenation scheme. Both elementary decoders
`provide a soft decision and use a low complexity soft output
`Viterbi algorithm [2].
`
` From
`
`demodulator
`
`Figure 2 Turbo-decoder with P pipelined identical modules
`
`ERICSSON EXHIBIT 1006
`
`

`

`
`
`to
`
`have
`notations
`According
`.
`_
`.
`_ l
`'_
`_
`.
`uk‘i—dk_,,t—2,3,4,
`uk‘l—cu and then uk+l.1_dk+l,i’
`-_
`_ 2
`and so on.
`i—2,3,4 ”k+l.| —Ck+1,i
`
`of Fig.
`
`3,
`
`we
`
`4 - RECEIVER AND TURBO-DECODER STRUCTURE
`
`the in—phase and
`Consider a coherent receiver,
`quadrature demodulator outputs Xk and Yk are equal to :
`Xk = akAk + 1k
`_
`Yk " ak Bk + Qk
`where ak is a Rayleigh random variable for a Rayleigh
`channel and a constant equal to 1 for a Gaussian channel, and
`[lqu are two uncorrelated gaussian noises, with zero mean,
`
`(2)
`
`variance 0%, and independantof variable oak.
`We assume that a pragmatic approach [3] is taken, so that the
`input turbo-decoder is made up of soft decisions associated to
`each turbo-encoder output bit. From observation of {Xk, Yk },
`the Logarithm of Likelihood Ratio (LLR) associated with each
`bit ”km i=1....m can be determined and used as a relevant
`soft decision by the turbo-decoder as depicted in Fig. 5.
`P,{uk,,. =1/ X,,Y,}
`P,{u,m- = 0/ Xk,Yk}’
`where K is a constant.
`
`A(uk,i)=KLOg
`
`i=1....m
`
`men—v—IH—=BGU
`
`computation
`
`module
`
`Demodulator
`
`decoder
`
`(ct)
`
`Figure 5 Pragmatic decoder structure
`
`Unfortunately, the computation of m quantities A(uk,i) leads
`to relatively complicated expressions which depend on signal-
`to—noise ratio (SNR) and channel characteristics (Gaussian or
`Rayleigh channel). Nevertheless it is possible to approximate
`these expressions by simpler relations. For example consider
`the case of square M-QAM constellations with M = 2'" and
`m = 2p.
`
`4 - 1 Gaussian channel
`
`By taking into account the fact that the observation
`{Xk, Yk} is affected by two independant gaussian noises with
`
`identical variance 6%,, and using Bayes' rule, the LLR Aw“)
`associated to hit u“, i=1....p depends only on observation
`Xk.
`
`3 - ASSOCIATION OF A TURBO-CODE WITH A
`MULTILEVEL MODULATION
`
`We now consider the association of M-state QAM or
`PSK (M = 2’") modulation and rate R: (m — rh)/ m encoder
`built from a standard turbo-encoder by using puncturing
`technique as depicted in Fig. 3.
`
` anxn_.°_v~—:Emg
`
`Figure 3 Asociation of a turbo-code with a multilevel
`modulation
`
`The puncturing function is inserted at the standard turbo-
`encoder output and thus it is possible to obtain a large code
`family, with various rates R. In order to obtain symbols
`affected with uncorrelated noises at the turbo—decoder input,
`an interleaver 12 has to be inserted between the puncturing
`function and the modulator. With this approach,
`the
`transmission spectral efficiency 7]
`is equal to :
`(1)
`11 = RLogzM
`Each point of the QAM (or PSK) constellation is represented
`by a couple of real-valued symbols {Ak,Bk} at time k coded
`by a set {um}, i= 1,...m of m bits according to a Gray code.
`The redundant bits provided by the punctured turbo-encoder
`are associated to the highest protected bit “k,i-
`For example, for a 16—QAM constellation with Gray coding
`depicted on Fig. 4, and for a rate R=3/4 turbo-encoder,
`parameters m and r7: are respectively equal to 4 and l.
`
`uk'3
`
`o 1
`
`/”k,4
`
`O
`
`1
`
`o
`
`O F
`
`igure 4 lG—QAM constellation with GRAY coding
`
`646
`
`

`

`21H
`
`2exp{-21N—T(Xk _ “11)2}
`A041:l=) KLogZ:1
`gal—3:7, M}
`
`,i=l....p (4)
`
`where a” and “0,1‘ respectively represent the realization of
`symbols Ak conditionally on "Li =1 and “kJ =0. In the
`same way, the LLR associated to bit u,“ 1‘+p,
`i = l. . .. p depends
`only on observation Yk and has the same expression as
`A(ukq,~) but with Yk substituted for Xk, and b” and bar for
`a” and “0,1' respectively.
`
`A good approximation of the LLR A(u,M-) for K = 0'12»! / 2
`can be achieved using the following expressions :
`
`A(uk'1)=|Xk|— 2P—1
`
`Mum) = |A(u,,',_1 )| — 21“",
`A(uk,p) = Xk
`
`and :
`
`A(uk‘1+p)=lYk|— 21"1
`
`i = 2 ...(p — 1)
`
`(5-a)
`
`(s-b)
`
`Am...) = |A<uk,,--1.,,>l— 21*", i= 2....(p — 1)
`(Hump) = Yk
`In Fig 6, the LLR Mu“) associated to bit “ka 1': 1,2 is
`plotted for a 16-QAM constellation and for a Eb / N0 = 4 118,
`where E, is the energy received per information bit and N0
`the one-sided noisebpower spectral density.
`M —1
`1
`__(___)_
`N0
`3Log2M a},
`Fig. 6 shows that relations (5--a, 5-b) appear to be good
`approximations to the LLR even for rather low SNR values.
`
`(6)
`
`2
`
`A
`1
`a
`3
`a
`.J
`
`A
`N.
`M
`3
`as
`.J
`
`
`
`
`0
`
`accounts for the interleaver inserted after the puncturing
`function (Fig.3). Moreover, in the general case, for a given
`couple (Ak,Bk), the Mu“) variables are not gaussian except
`for
`i=p and i=2p and thus the soft-output Viterbi
`algorithm used in each elementary decoderDECl and DECg is
`no longer optimal. Nevertheless for large SNR values, the
`Aw,“1') variables are close to gaussian variables with the same
`variance, and therefore the turbo—decoder performance is still
`quite attractive with the pragmatic approach.
`
`4 -2 Rayleigh channel
`
`We assume a memoryless Rayleigh fading channel
`whose a,‘ is known by the receiver. Under this asumption,
`relations (2) can be normalized by ak. That is :
`xk = Ak + ik
`
`(7)
`
`where:
`
`yk=Bk+qk
`
`Qk
`lk
`-
`Yk
`XI:
`=— 8
`=—and1=——,
`x =—,
`0‘1:
`()
`05k
`k W 4k
`Yk
`05k
`k
`Relations (7) are similar to those obtained over a Gaussian
`channel, but ik and qk are now nonstationary noises whose
`variance depends on time k through variable (2k.
`2
`2
`2
`O'
`2
`0'
`2
`9
`E11 }=—~, E1
`1——~
`(‘11:)
`( )
`a, (k)
`a:
`a,
`ak
`If we use relations (5-a) and (5-b) to determine simpler
`expressions for the LLR, we have now to take into account the
`variance of noises it and qk for the metric computation Mi”.
`in the low complexity soft-output Viterbi algorithm.
`a_k
`M,{-=jA(uk,- —2
`ON
`With the pragmatic approach, the turbo—decoder structure is
`optimized for binary transmission (2-PSK or QPSK) over a
`Gaussian channel. Thus the metrics used in the turbo-decoder
`are independant of the noise variance and are equal to :
`M,{’1=jA(uk,,-)
`‘=—1,1
`By using the following notations :
`
`j=-—l,1;i=1....p
`
`(10)
`
`(11)
`
`Mu .)=a2A(u .)
`hi
`I:
`1m
`i = 1.... p
`Mum?) = afAmmp)
`the metric (10) can be evaluated from relation (11) by
`
`i=1....p
`
`(12)
`
`substituting M.) for A(.). Thus the turbo decoder optimized
`for a Gaussian channel, is also optimal for a Rayleigh channel
`
`if [\(“kfl is used as the LLR expression.
`
`5 - RESULTS
`
`Figure 6 Logarithm of the Likelihood ratio corresponding to
`bit ukj, i=l,2 for a 16-QAM modulation at Ebflv0=4dB
`(Full line LLR from relation 4; dashed line LLRfrom
`relations S-a. 5-b)
`Unfortunately, with the pragmatic approach, the LLRs A04“)
`associated to bits uk‘i,i=l....p (respectively bits
`uk,i+p’ i=1....p ) are affected by correlated noises, which
`
`A rate R =1/3 standard turbo-encoder, made up of two
`elementary encoders with the same constraint length K =5 and
`the same polynomial generators (23,35) is considered in the
`following simulations. For different spectral efficiencies
`obtained by puncturing redundant bits at the standard turbo-
`encoder output, we have computed the Bit Error Rate (BER)
`using the Monte Carlo method as a function of Eb / No. In
`order to compare the performance of this new coded scheme
`
`647
`
`

`

`with conventional TCM, we have also plotted the BER of the
`64-state TCM and of the equivalent uncoded modulation
`(providing the same spectral efficiency).
`
`coding gain equal to 2.5 dB compared to a 64-state TC 8-PSK
`at a BER equal to 105.
`
`5 - 1 Gaussian channel
`
`is composed of a
`The nonuniform interleaver 11
`(64x64) matrix whereas the uniform interleaver 12 uses a
`smaller matrix, with p rows and a number of columns equal to
`several times the encoder constraint length K. Turbo decoding
`is performed in 3 iterations and the BER curves, for a spectral
`efficiency of 2, 3, 4 bit/s/Hz, are plotted in Figs. 7 to 9.
`
`TEB
`
`4" Unmded 4PSK
`
`* ‘
`64 state TC-BPSK
`'1 7 SPSK o Tumnoua 03:21.?)
`
`-
`- 160m 4, Tutbo—code(R=1/2)
`
`
`
`
`——-— Unconscisom
`B‘sma rc—azom
`
`5.. —- — mm + rumma (Rd/3)
`
`
`
`9.5
`
`
`
`6.5
`
`6
`5.5
`EblNo (dB)
`
`Figure 7 BER of a rate R=l/2 turbo-code associated with a
`16—QAM versus Eb/No overa Gaussien channel
`(2bit/s/Hzpectral efficiency)
`
`
`
`
`64 state TC‘lSQAM
`i‘ A 160AM o Tummode (Rim)
`
`10‘
`TEB
`
`102
`
`
`
`106
`5.5
`
`6
`
`65
`
`75
`
`8.5
`8
`Eb/No (dB)
`
`Figure 8 BER of a rate R=3/4 turbo-code associated with a
`l6-QAM versus Eb/NO over a Gaussien channel (3bir/s/Hz
`spectral efi‘iciency)
`We can notice that for both spectral efficiencies considered
`and for a BER less than 10'3. the turbo code performance is
`always better than the 64-state TCM. The main results
`obtained,
`in terms of coding gain (expressed in dB) are
`indicated in the table 1. Thus, for a 3bit/s/Hz spectral
`efficiency and a 16—QAM constellation, the turbo code gives a
`
`Figure 9 BER ofa rate R=2/3 turbo-code associated with a
`64-QAM versus Eb/NO over a Gaussian channel (4bifls/Hz
`spectral efi‘iciency)
`
`For higher spectral efficiencies (>3bit/s/Hz) the coding gain is
`weaker, but we can see that the BER slope is still larger with a
`turbo-code than with 64- state TCM.
`We have also evaluated the performance of a rate R =2/3
`turbo-code associated with a 8-PSK (2 bit/s/Hz spectral
`efficiency). The coding gain is smaller than with the rate
`R =l/2 turbo—code associated with l6-QAM. However the
`turbo-code solution always gives a better performance than the
`conventional 64-state TC 8-PSK.
`Finally, we have checked the usefulness of interleaver 12 over
`a gaussian channel. Indeed without the interleaver 12,
`the
`AM“) at the DEC] input are just correlated over p values
`and thanks to interleaver I], the samples at the DEC2 input are
`almost uncorrelated. Therefore, it is possible to drop the
`interleaver 12 over a gaussian channel.
`
`Turbo code rate
`
`Modulation
`
`J—
`
`
`
`
`
`Spectral efficiency
`
`-6
`
`Coding gain at 10
`over uncoded
`modulation
`
`Coding gain at 10-6
`over 64 state TCM
`
`Table I Coding gain at 0 BER equal to 10’6f0r a turbo-code
`over a Gaussian channel
`
`648
`
`

`

`5 - 2 Rayleigh channel
`
`The curves of BER for a spectral efficiency equal to
`2, 3 and 4 bit/s/Hz, are plotted in Figs. 10 to 12 as a function
`of E /No where:
`(13)
`E, = 2025,, with E{a,3} = 20'2 =1
`We have also plotted in Fig. 11 the BER of a 64-state TC 16-
`QAM [4], and respectively in Figs. 10 and 12 the BER of a
`trellis-coded 4-ASK and 8-ASK multilevel modulation with 64
`states [5].
`The turbo decoding is performed in 4 iterations and the
`uniform interleaver 12 is now made up with a matrix having 2p
`rows (the same number of columns as for the Gaussian
`channel) in order to obtain uncorrelated Rayleigh variables at
`at the decoder DECl input. We can see that over a Rayleigh
`channel, the interleaver 12 is necessary to achieve the best
`performance.
`
`
`——+— W arsx
`
`--------- 64 sm- to-apsx
`
`
` _ _. ~ 2 sum TC-MSK
`-- »~- 1m + Tumours (rel/2)
`
`
`10‘
`BER
`
`
`
`9
`
`11
`
`13
`EblNo (am
`
`15
`
`Figure 10 BER of a rate R=1/2 turbo—code associated with a
`16-QAM versus Eb/No over a Rayleigh channel (2bit/s/Hz
`spectral efficiency)
`
`—0— Um BPSK
`~ '- 64 state TC—tfiQAM
`
`- 150m + Turbo-code (333/4)
`
`10‘
`
`'
`
`10'
`
`9
`
`11
`
`13
`
`15
`
`19
`
`11
`Eb/No (as)
`
`Figure 11 BER ofa rate R=3/4 turbo—code associated with a
`16—QAM versus Eb/No over a Rayleigh channel (3bit/s/Hz
`spectral efliciency)
`
`__._ um 1m
`
`. 2 54“me
`... - mm + Tumom (Fl-2(3)
`
` 10'5
`
`a
`
`10
`
`12
`
`14
`
`18
`
`1G
`Ell/No (d8)
`
`Figure 12 BER ofa rate R=2l3 turbo-code associated with a
`64-QAM versus Eb/No over a Rayleigh channel (4bit/s/Hz
`spectral efliciency)
`
`the turbo-codes provide a better
`In all considered cases,
`performance than the 64-state TCM, when the BER is less
`than 10'3. For example for a spectral efficiency of 3 bit/s/Hz,
`the coding gain compared to 64-state TCM (codes of DU and
`VUCETI [4]) is equal to 9.5 dB!
`
`6 - CONCLUSIONS
`
`In this paper we have presented a new coding scheme
`using the association of a turbo-code with a quadrature
`amplitude modulation. For both Gausssian and Rayleigh
`channels, the performance of this new error correcting scheme
`is always better than the 64-state TCM, at BER values less
`than to 10‘3. The high performance of this new error
`correcting scheme is essentilly due to the good distance
`properties of the turbo-code which are obtained using a
`nonuniform interleaver II. Moreover, with a pragmatic
`approach, the turbo-decoder structure depends neither on the
`M parameter nor on channel type, and therefore, a single VLSI
`decoder can be suitable for both spectral efficiencies. Finally a
`turbo-code associated to M—QAM also makes high speed links
`possible since a turbo—decoder with 16-state trellis, is much
`simpler to implement than a 64 state TCM.
`REFERENCES
`[1] C. Berrou, A. Glavieux and P. Thitimajshima, "Near
`Shannon limit error-correcting coding and decoding : Turbo-
`codes", ICC’93, Conf. Rec. pp.1064—1070, Geneva, May 1993.
`[2] C. Berrou, P. Adde, E. Angui and S. Faudeil, "A low
`complexity soft-output Viterbi decoder architecture", ICC’93
`Conf. Rea, pp. 737- 740, Geneva, May 1993.
`[3] AJ. Viterbi, E. Zehavi, R. Padovani and J.K. Wolf, "A
`pragmatic approach to treillis-coded modulation", IEEE
`Commun. Mag, Vol. 27, N°7, pp. 11-19, July 1989.
`[4] J. Du and B. Vucetic "New 16-QAM trellis codes for
`fading channels", Electronics letters. Vol 26, N °l6, pp. 1267-
`1269, August 1990.
`[5] J.F. Hélard, "Modulations codées en treillis associées a un
`multiplex de porteuses orthogonales en presence de canaux
`affectés de trajets multiples", Thése de doctorat de l'Université
`de Rennes 1, N° d‘ordre : 776, pp. 5-12, Mai 1992.
`
`
`
`649
`
`