Iterative correction of intersymbol interference:
`turbo-equalization
`Catherine Douillard, Michel Jezequel, Claude Berrou, Annie Picart, Pierre
`
`Didier
`
`To cite this version:
`
`Catherine Douillard, Michel Jezequel, Claude Berrou, Annie Picart, Pierre Didier. Iterative
`correction of intersymbol interference: turbo-equalization. European Transactions on Telecom-
`munications, Wiley, 1995, 6 (5), pp.507-512. <hal-00703645>
`
`HAL Id: hal-00703645
`
`https://hal.archives-ouvertes.fr/hal-00703645
`
`Submitted on 4 Jun 2012
`
`HAL is a multi-disciplinary open access
`archive for the deposit and dissemination of sci-
`entific research documents, whether they are pub-
`lished or not. The documents may come from
`teaching and research institutions in France or
`abroad, or from public or private research centers.
`
`L’archive ouverte pluridisciplinaire HAL, est
`destin´ee au d´epˆot et `a la diffusion de documents
`scientifiques de niveau recherche, publi´es ou non,
`´emanant des ´etablissements d’enseignement et de
`recherche fran¸cais ou ´etrangers, des laboratoires
`publics ou priv´es.
`
`Exhibit 1016
`U.S. Patent No. 6,108,388
`
`

`

`Iterative Correction of lntersymbol
`Interference: Thrbo-Equalization
`
`Catherine Douillard, Michel Jezequel, Claude Berrou
`Departement Electronique
`Annie Picart, Pierre Didier, Alain Glavieux
`Departement Signal et Communications
`ENST de Bretagne
`BP 832, 29285 Brest Cedex - France
`
`Abstract. This paper presents a receiving scheme intended to combat the detrimental effects of
`intersymbol interference for digital transmissions protected by convolutional codes. The receiver
`performs two successive soft-output decisions, achieved by a symbol detector and a channel de(cid:173)
`coder, through an iterative process. At each iteration, extrinsic information is extracted from the
`detection and decoding steps and is then used at the next iteration as in turbo-decoding. From the
`implementation point of view, the receiver can be structured in a modular way and its perfor(cid:173)
`mance, in bit error rate terms, is directly related to the number of modules used. Simulation results
`are presented for transmissions on Gauss and Rayleigh channels. The results obtained show that
`turbo-equalization manages to overcome multipath effects, totally on Gauss channels, and partial(cid:173)
`ly but still satisfactorily on Rayleigh channels.
`
`1. INTRODUCTION
`
`With the growth of mobile radio systems, digital
`communications have to deal with the problem of trans(cid:173)
`mitting messages over multipath channels. In such cas(cid:173)
`es, channels appear to be frequency-selective and give
`rise to Doppler effects. Several approaches may be em(cid:173)
`ployed in order to overcome channel selectivity. A first
`possibility consists in equalizing the channel so as to
`minimize InterSymbol Interference (lSI) at the receiv(cid:173)
`ing filter output. Another solution, which we have cho(cid:173)
`sen, takes the channel memory effect into account. In
`the latter approach, the modulator, the transmission
`channel and the demodulator are represented by an
`equivalent discrete-time model that behaves similarly to
`a convolutional encoder. Symbol detection is based on a
`Maximum-Likelihood Sequence Estimation (MLSE)
`and is achieved through the application of the Viterbi
`algorithm [1]. In the case where the transmission chan(cid:173)
`nel is protected by a convolutional encoder and a decod(cid:173)
`er using the Viterbi algorithm, the detection and decod(cid:173)
`ing modules may be associated in the same way as in
`turbo-decoding. In order to take the best advantage of
`the encoding function, the symbol detection has to pro(cid:173)
`vide soft outputs and the samples at the output of the
`equivalent discrete-time channel are processed in an it(cid:173)
`erative way. This approach is referred to as turbo-equal(cid:173)
`ization in what follows, by analogy with turbo-codes.
`
`2. PRESENTATION OF THE TRANSMISSION
`CHANNEL
`
`Let us suppose that the binary digits dk delivered by
`the source are encoded by a convolutional encoder. The
`encoded data ck are reordered by an interleaver, and ap(cid:173)
`plied at the input of a Binary Phase Shift Keying
`(BPSK) modulator. The transmitted signal e (t) is pro(cid:173)
`vided by the output of a filter whose impulse response is
`he(t). The signal emitted can be expressed in the form:
`
`e(t) =A ~>k he (t- kT)expj(2n fo t + tp0)
`
`k
`
`(1)
`
`where A denotes an amplitude, fo is the carrier frequen(cid:173)
`cy,% is a constant phase whose value is in [0, 2 tr], and
`ck are binary symbols(± 1) transmitted at the rate of one
`symbol every T seconds.
`In the case of a multipath channel, the received signal
`Y(t), can be written as follows:
`M-1
`Y(t) =LAm (t) :~>k he (t- 'l'm- kT) ·
`m=O
`
`(2)
`
`expj(2nf0 t + fJ'o) +B(t)
`where Am (t) are complex-valued independent multipli(cid:173)
`cative noise processes, gaussian in the case of a Ray(cid:173)
`leigh-type channel and constant in the case of a Gauss-
`
`Vol. 6, No. 5 September- October 1995
`
`507
`
`
`
`
`
`

`

`Catherine Douillard, Michel Jezequel, Claude Berrou, Annie Picart, Pierre Didier, Alain Glavieux
`
`type channel. The delays 't'm take into account the differ(cid:173)
`ent propagation delays on each of the M paths. B (t) is a
`complex-valued zero mean white gaussian noise with a
`power bilateral spectral density equal to 2 N0. After de(cid:173)
`modulation, the samples taken from the output of the re(cid:173)
`ceiving matched filter are expressed as:
`
`M-i
`Rn ~R(nT)= LAm(n)~>n-khs(kT--rm)+bn (3)
`m=O
`k
`
`where Am (n) equals Am (n T) by definition, bn denotes
`the response of the receiving matched filter to the noise
`B (t), sampled at time n T. h5 (t) is defined by hs(t) =
`he(t) x h; (- t) and satisfies the Nyquist criterion. Let:
`
`···········.·.·.:::::::::.-.-.-_:::::::. 00
`
`---Cn+1=1
`
`.................. Cn+1 = 0
`
`Sn-1
`
`00
`
`01
`
`10
`
`11
`
`___ _.__ ______ .L.. _ __ _ _ _.. Time
`
`(n-1)T
`
`nT
`
`M-i
`
`rk (n) =LAm (n)hs (kT- -rm)
`
`m=O
`
`Fig. 2 - Trellis diagram for L1 = ~ = I.
`
`(4)
`
`and let us suppose that the lSI is limited to (L1 + L2)
`symbols. Eq. (3) may be written in the form:
`
`can be modeled as a Markov chain and its behavior can
`be represented by a trellis diagram (Fig. 2).
`
`Ll
`Rn = L rk (n)cn-k + bn
`
`k=-~
`
`(5)
`
`3. PRINCIPLE OF TURBO-EQUALIZATION
`
`Quantities rk(n) are expressed as a linear combination
`of the multiplicative noises Am(n), therefore, they are
`gaussian in the case of a Rayleigh-type channel and con(cid:173)
`stant in the case of a Gauss-type channel. Consequently,
`the set of modules made up of the modulator, the trans(cid:173)
`mission channel and the demodulator can be represented
`by an equivalent discrete-time channel (Fig. 1).
`
`In order to use a soft-input channel decoder, the sym(cid:173)
`bol detector has to provide information about the reli(cid:173)
`ability of the symbols estimated. This information may
`be obtained by using a Soft-Output Viterbi Algorithm
`(SOV A) [2 - 4], that associates an estimation of the
`Logarithm of its Likelihood Ratio (LLR), A1 (en), to
`each symbol en detected:
`
`(7)
`
`where R denotes the vector of samples that constitutes
`the observation. After deinterleaving, the SOV A decod(cid:173)
`er provides a new LLR value of ck, A2 (ck), that may be
`derived by analogy with the calculations made in [5]
`and expressed in the form:
`
`(8)
`
`Fig. 1 - Equivalent discrete-time model of a channel with intersymbol
`interference.
`
`After a change of variable k, eq. (5) may also be ex(cid:173)
`pressed in the form:
`
`where zk is the extrinsic information associated with sym(cid:173)
`bol ck and provided by the channel decoder (Fig. 3). In
`fact, the extrinsic information zk is another estimation of
`the LLR of symbol ck conditioned on the decoding step:
`
`Ll+Lz
`Rn = Irk-~ (n)cn+~-k + bn
`
`k=O
`
`Pr{ck =+II decoding}
`zk =log
`{
`}
`Pr ck =-II decoding
`
`(6)
`
`(9)
`
`If We denote Sn = (en+£:!•· .. , Cn-LI+i) the State Of the
`equivalent discrete-time channel at time n T, sample Rn
`depends on the channel state sn-i and on the symbol
`cn+L
`• Therefore, the equivalent discrete-time channel
`
`2
`
`Hence, zk may be used through a feedback loop by
`the symbol detector, after interleaving. This is the basis
`of turbo-equalization principle.
`To evaluate the LLR of symbol cn-L
`, the Viterbi al(cid:173)
`1
`gorithm used in the detector has to calculate a metric at
`
`508
`
`ETT
`
`

`

`Interative Correction of lntersymbol Interference: Turbo-Equalization
`
`Soft-Output
`Symbol
`Detector
`
`f-----.1
`
`Soft-Output
`Channel
`Decoder
`
`Fig. 3 - Extrinsic information deriving scheme.
`
`time n T for every branch in the trellis. This metric may
`be written in the form [1]:
`
`where:
`
`Ll +Lz -I
`
`r~ = L fk-L2 (n)·en+L2 -k +f'L1 (n)·i
`
`A
`
`i=±l (10)
`
`i=±l (11)
`
`k=O
`and rk-Lz (n), 0 ~ k ~ L1 + ~. represents an estimation
`of quantity rk-L (n) and a; denotes the variance of
`noise bn, that is a1 = E [Ibn 12].
`
`= i} used in rela(cid:173)
`The a priori probabilities Pr { en-L
`1
`tion (10) may be estimated from the extrinsic informa(cid:173)
`, if we assume that
`tion Zn-L
`
`1
`
`Pr{en-L1 = + 1}
`"::log -T---'----+
`Pr{en-LI = -1}
`
`(12)
`
`Then, the following expressions can be derived from
`(12):
`
`expzn-LI
`Pr en-LJ = + 1 ""----'---
`}
`{
`1 + expzn-L1
`
`(13a)
`
`Pr{en-LJ = -1}""
`
`+112
`rn
`
`- r Zn-LI
`
`1
`1 + expzn-L1
`Using (13 a), (13 b) and (10), metrics ~are equal to:
`I R
`1+1
`J'l,n = n -
`
`(13b)
`
`(14a)
`
`(14b)
`
`Note that the common term log (1 + exp Zn-L
`) has
`1
`been suppressed in eqs. (14 a) and (14 b). Coefficient y
`is a weight introduced to take into account variance ai;
`and the fact that the extrinsic information is only an es(cid:173)
`timation of the a priori probability. Its value depends on
`the signal-to-noise ratio, that is to say the reliability of
`the extrinsic information.
`
`4. ITERATIVE IMPLEMENTATION
`OF TURBO-EQUALIZATION
`
`'
`
`only be implemented in an iterative way. At each itera(cid:173)
`tion, a new value of extrinsic information is calculated
`and used by the symbol detector at the next iteration.
`Therefore, the turbo-equalizer can be implemented in a 1 ~
`modular pipelined structure, where each module is asso- 1
`ciated with one iteration. Then, performance in Bit Error
`Rate (BER) terms is a function of the number of chained
`modules. An example of turbo-equalization implementa(cid:173)
`tion is illustrated in Fig. 4 in the case of a 4-stage pro(cid:173)
`cess. The rank q module, 1 ~ q ~ 4, has two inputs and
`three outputs. Input Rq receives the samples from the re(cid:173)
`ceiving matching filter after a delay equal to the latency
`of the (q- 1) previous modules. Input zQ represents the
`extrinsic information of the previous iteration provided
`by the rank (q- 1) module. Output Rq+I is equal to input
`Rq delayed of the latency of the module, and zQ+ I is the
`extrinsic information provided by the current iteration.
`These outputs are unused for the last module and do not
`appear on the figure. Output [)q provides the decoded
`data and is only used at the last module output.
`
`Decoded
`Data
`
`Fig. 4 - Modular pipelined structure of a turbo-equalizer for a 4-itera(cid:173)
`tion process.
`
`When extrinsic information is used by the symbol de(cid:173)
`tector, it can be proved that, at iteration q, the LLR of
`symbol en, A'{ (en), may be expressed as:
`
`(15)
`
`where A'{ is a term depending on the samples of obser(cid:173)
`vation R and on z~-I, k-:!- n, and z~-I denotes the extrin(cid:173)
`sic information of symbol en determined at iteration
`q - 1. If we apply the same approach as in turbo-decod(cid:173)
`ing, the quantity yq z~ 1 provided by the channel decod(cid:173)
`er at the previous iteration has to be subtracted from Ai
`(en), as illustrated in Fig. 5. Hence, after deinterleaving,
`the channel decoder input is in fact equal to:
`
`(16)
`
`At the channel decoder output, the extrinsic informa(cid:173)
`tion zZ may also be written as follows, using (8):
`
`The different processing stages in the turbo-equalizer
`present a non-zero internal delay, so turbo-equalizing can
`
`zf =A~ (ek )IA1{c,)=O
`
`Vol. 6, No.5 September- October 1995
`
`(17)
`
`509
`
`

`

`Catherine Douillard, Michel Jezequel, Claude Berrou, Annie Picart, Pierre Didier, Alain Glavieux
`
`Extrinsic Information
`
`Fig. 5 - Principle of turbo-equalization (under zero internal delay assumption) .
`
`. 5. SIMULATION RESULTS
`
`Performa,nce of this device has been evaluated for a
`rate R = 112 recursive systematic encoder with con(cid:173)
`straint length K = 5, and generators G1 = 23, G2 = 35.
`Bits were interleaved in a non uniform matrix whose di(cid:173)
`mensions are 64 by 64. The modulation used was a
`BPSK modulation, with a Nyquist filter whose transfer
`function H.(f) was a raised cosine with a rolloff a = 1,
`on both gaussian and Rayleigh channels.
`For both channels, M = 5 independent paths were con(cid:173)
`sidered, each with a mean power P m = E [ I Am (n) 1 2], so
`that the total mean power was normalized: ~~ P m = 1.
`The delays 't"m were chosen as multiples of T ( 't"m = mT,
`rk (n) = Ak (n) since h. [(k- m) T] = ok-m,o). The coeffi(cid:173)
`cients for the gaussian channel were chosen equal to:
`
`ro (n) = ~0.45 'rl (n) = .Jo.25, r2 (n) =
`.Jo.15,r3 (n) = .Jo.10,r4 (n) = .Jo.o5
`
`On the Rayleigh channel considered, the five paths
`had equal mean power (P; = liM, Vi E [1, M]). A pa(cid:173)
`rameter BT, which is the product of the Doppler band(cid:173)
`width and the symbol duration, fixes the variation veloc(cid:173)
`ity of the channel: the smaller BT is, the more slowly the
`channel parameters vary during a time interval symbol.
`The discrete-time equivalent channel was modeled by
`a 16-state trellis, and the symbole detector was working
`on the SOVA algorithm presented in [4]. The channel
`coefficients rk (n) were supposed perfectly known. Af(cid:173)
`ter deinterleaving, the soft estimations provided by the
`SOV A detector were used by the decoder which also
`worked on a 16-state trellis and the SOVA algorithm.
`The extrinsic information extracted from the decoder
`was used by the symbol detector according to the prin(cid:173)
`ciple depicted in Fig. 5.
`The BER was computed as a function of signal to
`noise ratio Eb/N0 , where Eb is the mean energy received
`per information bit dk and N0 is the noise power bilater(cid:173)
`al spectral density. The signal to noise ratio Eb/N0 may
`be expressed as:
`
`Results are presented in Figs. 6, 7 and 8. On a gaussian
`channel (Fig. 6), the gain at the first iteration, compared
`to the classical Viterbi detector which provides a binary
`decision, is 1.7 dB for a BER of 1Q-5• At the second itera(cid:173)
`tion, the gain is 2.2 dB better. After the fifth iteration, the
`total gain is 5.2 dB. Finally, the turbo-equalizer manages
`to completely compensate for the degradation due to the
`interference generated by the multipath effects after six
`iterations. Then, the BER is the same as on a non selec(cid:173)
`tive gaussian channel (without intersymbol interference).
`Two types of Rayleigh channels with BT = 0.1 (Fig. 7)
`and BT = 0.001 (Fig. 8) were examined. In both of these
`cases, the gain after the first iteration is about 2.2 dB, that
`is to say better than that on the gaussian channel. This can
`be explained by the fact that the system takes advantage
`of the diversity created by the multiple paths. The global
`gain after the third iteration remains inferior to that on the
`gaussian channel. The limit that has been considered is
`the BPSK modulation with encoding and without interfer(cid:173)
`ence on a gaussian channel. This limit is not completely
`achieved: the third iteration is 0.8 dB from this limit for
`BT= 0.1 and 2 dB for BT= 0.001. A degradation is noted
`in the case of BT = 0.001 compared to the case of BT =
`0.1, this is due to the use of the same 64 by 64 interleav(cid:173)
`ing matrix in both cases. Such dimensions were chosen to
`simulate a realistic receiver from the implementation
`point of view. When BT = 0.001, the channel parameters
`
`2
`
`3
`
`4
`
`9
`
`1 0 EtfN0 (dB)
`
`-
`
`#Turbo-Equalization
`
`- - - Binary (Hard) Output
`Detection and Encoding
`
`-- BPSK With Symbol Detection
`and Without Encoding
`-o- BPSK With Encoding and Without
`lSI on a Gaussian Channel
`
`(18)
`
`Fig. 6 - Performance of turbo-equalization over a gaussian channel
`(convolutional encoding with K = 5).
`
`510
`
`ETI
`
`

`

`Interative Correction of Intersymbol Interference: Turbo-Equalization
`
`receiving scheme has been called turbo-equalization.
`The receiver is made up of identical pipelined elemen(cid:173)
`tary modules, and the rank q elementary module uses
`data information coming from the demodulator and ex(cid:173)
`trinsic information provided by the rank (q- 1) module
`in order to take decisions. The performance of turbo(cid:173)
`equalizing is directly related to the number of iterations.
`The results presented in this paper have been obtained
`from simulations of Gauss and Rayleigh channels. In the
`case of a gaussian channel, the compensation for inter(cid:173)
`ference is complete and the behavior of a Gauss channel
`without multipath effects is reached after a few itera(cid:173)
`tions. In the case of a Rayleigh channel, compensation is
`only partially achieved. However, this is still satisfacto(cid:173)
`ry because the bit error rate is close to that obtained on a
`gaussian channel without intersymbol interference. It is
`to be noted that these results were obtained in the case
`where the channel coefficients are supposed known. In
`practice, these coefficients have to be estimated, and the
`bit error rate is therefore degraded. However, further
`simulations are currently being processed in these con(cid:173)
`ditions to show that the iterative process is also able to
`correct the degradation due to estimation, and turbo(cid:173)
`equalization seems to provide results of great interest.
`Finally, the results obtained clearly show that turbo(cid:173)
`equalization is an effective method of overcoming mul(cid:173)
`tipath effects in digital transmissions.
`
`Acknowledgment
`
`The authors would like to thank P. Combelles and D.
`Callonnec from the Centre Commun d'Etudes des
`Telecommunications (CCETT), and R. Schmitt from
`the University of Kaiserslautem, for their helpful col(cid:173)
`laboration.
`
`Manuscript received on January 10, 1995.
`
`REFERENCES
`
`[I] J. G. Proakis: Digital communications. McGraw-Hill Series in
`Electrical Engineering, 2nd Edition, 1989.
`
`[2] J. Hagenauer, P. Hoeher: A Viterbi algorithm with soft-decision
`outputs and its applications. In: Proc. IEEE Globecom' 89, Dal(cid:173)
`las, Texas, Nov 1989, p. 47.1.1-47.1.7.
`
`[3] G. Battail: Ponderation des symboles decodes par l'algorithme
`de Viterbi. (in French), "Ann. Telecomm.", No. 1-2, Jan-Fev.
`1987, p. 31-38.
`
`[4] C. Berrou, P. Adde, E. Angui, S. Faudeil: A low complexity soft(cid:173)
`output Viterbi decoder architecture. In: Proc. IEEE Int. Conf. on
`Comm., ICC' 93, Vol2/3, May 1993, p. 737-740.
`
`[5] C. Berrou, A. Glavieux, P. Thitimajshima: Near Shannon limit
`error-correcting coding and decoding: Turbo-codes. In: Proc.
`IEEE Int. Conf. on Comm., ICC' 93, Vol 2/3, May 1993, p.
`1064-1071.
`
`10-7
`0
`
`2
`
`3
`
`4
`
`5
`
`6
`
`7
`
`8
`
`9 EJN0 (dB}
`
`- - #Turbo-Equalization
`
`Binary (Hard} Output
`Detection and Encoding
`
`- - BPSK With Symbol Detection
`and Without Encoding
`-<>- BPSK With Encoding and Without
`lSI on a Gaussian Channel
`
`Fig. 7 - Performance of turbo-equalization over a Rayleigh channel
`with BT = 0.1 (convolutional encoding with K = 5).
`
`vary so slowly that, when fading occurs, it can last so
`long that it can affect a number of symbols which is ap(cid:173)
`proximately the size of the interleaving matrix. In such a
`case, a 64 by 64 interleaving is less effective. Therefore,
`it is necessary to adapt the interleaver dimensions accord(cid:173)
`ing to the variation speed of the channel.
`
`1Q-2
`
`10-3
`
`1Q-4
`
`1Q-5
`
`10-6
`
`10·7L_ __ L_~--~--_L __ _L __ J_ __ L_ __ L_~----
`o
`3
`5
`6
`2
`4
`7
`8
`9 EJN0 (dB}
`
`- - #Turbo-Equalization - - E3PSK With Symbol Detection
`and Without Encoding
`-<>- BPSK With Encoding and Without
`lSI on a Gaussian Channel
`
`-- - - Binary (Hard} Output
`Detection and Encoding
`
`Fig. 8 - Performance of turbo-equalization over a Rayleigh channel
`with BT = 0.001 (convolutional encoding with K = 5).
`
`6. CONCLUSION
`
`In this paper a new method of combating the detri(cid:173)
`mental effects of intersymbol interference on multipath
`channels has been presented. It is based on the associa(cid:173)
`tion of two successive soft-output decisions, achieved
`by a symbol detector and a channel decoder, in an itera(cid:173)
`tive process. At each iteration a new piece of informa(cid:173)
`tion, called extrinsic information, is calculated and used
`at the next iteration. By analogy with turbo-codes, this
`
`Vol. 6, No.5 September- October 1995
`
`511
`
`