`CODING AND DECODING : TURBO-CODES (1)
`
`Claude Berrou, Alain Glavieux and Punya Thitimajshima
`
`Claude Berrou, Integrated Circuits for Telecommunication Laboratory
`
`Alain Glavieux and Punya Thitimajshima, Digital Communication Laboratory
`
`Ecole Nationale Superieure des Telecommunications de Bretagne, France
`
`(1) Patents N° 9105279 (France), N° 9246001 1.7 (Europe), N° O7/870,483 (USA)
`
`Abstract - This paper deals with a new class of convolutlonal
`codes called Turbo-codes, whose performances in terms of
`Bit Error Rate (BER) are close to the SHANNON limit The
`Turbo—Code encoder is built using a parallel concatenation of
`two Recursive Systematic Convolutional codes and the
`associated decoder, using a feedback decoding rule,
`is
`implemented as P pipelined identical elementary decoders.
`
`I - INTRODUCTION
`Consider a binary rate R=l/2 convolutional encoder with
`constraint length K and memory M=K-1. The input to the
`encoder at time k is a bit dk and the corresponding codeword
`Ck is the binary couple (Xk, Yk) with
`K-l
`
`Xk Z Eglidk—i
`i=0
`K-1
`
`m0d.2 g1,-=0,l
`
`(111)
`
`Y1: = Eg2idk—i
`i=0
`
`mod.2 gm =0,1
`
`(lb)
`
`where G1: {g1,-}, G2: {ggg } are the two encoder generators,
`generally expressed in octal form.
`It is well known, that the BER of a classical Non
`Systematic Convolutional (NSC) code is lower than that of a
`classical Systematic code with the same memory M at large
`SNR. At low SNR, it is in general the other way round. The
`new class of Recursive Systematic Convolutional (RSC)
`codes, proposed in this paper, can be better than the best NSC
`code at any SNR for high code rates.
`A binary rate R=1/2 RSC code is obtained from a
`NSC code by using a feedback loop and setting one of the
`two outputs Xk or Yk equal to the input bit dk. For an RSC
`code, the shift register (memory) input is no longer the bit dk
`but is a new binary variable ak. If Xk=dk (respectively
`Yk=dk), the output Yk (resp. Xk) is equal to equation (lb)
`(resp. la) by substituting ak for dk and the variable ak is
`recursively calculated asK-1
`ak =dk + ):y,-ak_,
`mad.2
`(2)
`r"-l
`where 7; is respectively equal to g1,- if Xk=dk and to gg; if
`Yk=dk. Equation (2) can be rewritten as
`[(-1
`
`dk = Z7iak—i
`;=o
`
`mod.2.
`
`(3)
`
`One RSC encoder with memory M=4 obtained from an NSC
`encoder defined by generators G1=37, G2=21 is depicted in
`Fig.1.
`
`Generally, we assume that the input bit dk takes
`values 0 or 1 with the same probability. From equation (2),
`we can show that variable ak exhibits the same statistical
`property
`
`07803-09503/93/$3.00©l993IEEE
`
`P,{a,, =0/a,=e,,..a,,_,=e,,_,}=11{d,, =2} =1/2 (4)
`with e is equal toK-
`e=Zly,e,.
`I=l
`
`mod.2
`
`e=0,1.
`
`(5)
`
`Thus the trellis structure is identical for the RSC
`code and the NSC code and these two codes have the same
`free distance df. However, the two output sequences {Xk} and
`{Yk } do not correspond to the same input sequence [dkl for
`RSC and NSC codes. This is the main difference between the
`two codes.
`
`When punctured code is considered, some output
`bits Xk or Yk are deleted according to a chosen puncturing
`pattern defined by a matrix P. For instance, starting from a
`rate R=l/2 code, the matrix P of rate 2/3 punctured code is
`11
`
`Fig. 1b Recursive Systematic code.
`
`Apple 1008
`
`
`
`ll - PARALLEL CONCATENATION OF RSC CODES
`With RSC codes, a new concatenation scheme,
`called parallel concatenation can be used. In Fig. 2, an
`example of two identical RSC codes with parallel
`concatenation is shown. Both elementary encoder (C; and
`C;) inputs use the same bit dk but according to a different
`sequence due to the presence of an interleaver. For an input
`bit sequence {dk}, encoder outputs X); and Yk at time k are
`respectively equal to dk (systematic encoder) and to encoder
`C1 output Y 1),, or to encoder C; output Y;k. If the coded
`outputs (Y1k, Yzk) of encoders C1 and C ; are used
`respectively n; times and n; times and so on. the encoder C1
`rate R1 and encoder C; rate R; are equal to
`
`R1 =_"lfl2_
`2n1+rt2
`
`R2 =_"lfl2__
`2n-2 +71,
`
`(5)
`
`given encoder (C1 or C;) is not emitted, the corresponding
`decoder input is set to zero. This is perfonned by the
`DEMUX/INSERTION block.
`It is well known that soft decoding is better than
`hard decoding, therefore the first decoder DEC; must deliver
`to the second decoder DEC; a weighted (soft) decision. The
`Logarithm of Likelihood Ratio (LLR), A1(dk ) associated
`with each decoded bit d), by the first decoder DEC1 is a
`relevant piece of information for the second decoder DEC;
`P, {d,, =1/observation}
`(8)
`P, {dk = O/observation
`where P,-{dk =i /observation}, i = 0, 1 is the a posteriori
`probability (APP) of the data bit dk.
`
`Al(dk) = L08
`
`ykgi
`
`INSEFITION
`
`Fig. 3a Principle of the decoder according to
`a serial concatenation scheme.
`
`III - OPTIMAL DECODING OF RSC CODES WITH
`WEIGHTED DECISION
`
`The VITERBI algorithm is an optimal decoding
`method which minimizes the probability of sequence error
`for convolutional codes. Unfortunately this algorithm is not
`able to yield the APP for each decoded bit. A relevant
`algorithm for this purpose has been proposed by BAHL er al.
`[1]. This algorithm minimizes the bit error probability in
`decoding linear block and convolutional codes and yields the
`APP for each decoded bit. For RSC codes, the BAHL et al.
`algorithm must be modified in order to take into account their
`recursive character.
`
`III - 1 Modified BAHL et al. algorithm for RSC codes
`Consider a RSC code with constraint length K; at
`time k the encoder state Sk is represented by a K-uple
`
`(9)
`S; = {ak,a,‘_, ..... ..a,,_K+1).
`Also suppose that the information bit sequence {dk} is made
`up of N independent hits dk. taking values 0 and l with equal
`probability and that the encoder initial state So and final state
`SN are both equal to zero, Le
`(10)
`S0 = SN: (0, O......0) = 0.
`encoder output
`codeword sequence, noted
`The
`C1” = {C1 ..... "Ck...... ..C,.,}is
`the input
`to a discrete
`gaussian memoryless channel whose output is the sequence
`R1” ={R, ...... ..R,, ...... ..RN} where Rk=(xk,yk) is defined by
`relations (7a) and (7b).
`
`Fig. 2 Recursive Systematic codes
`with parallel concatenation.
`
`The decoder DEC depicted in Fig. 3a, is made up of two
`elementary decoders (DEC1 and DEC;)
`in a serial
`concatenation scheme. The first elementary decoder DEC1 is
`associated with the lower rate R1 encoder C1 and yields a
`soft (weighted) decision. The error bursts at the decoder
`DEC1 output are scattered by the interleaver and the encoder
`delay L1 is inserted to take the decoder DEC1 delay into
`account. Parallel concatenation is a very attractive scheme
`because both elementary encoder and decoder use a single
`frequency clock.
`For a discrete memoryless gaussian channel and a
`binary modulation, the decoder DEC input
`is made up of a
`couple R], of two random variables xk and yk, at time k
`x,,=(2d,,—1)+i,,
`(7a)
`y,,=(2Y,‘ —1)+qk,
`(7b)
`where 1'}, and qk are two independent noises with the same
`variance G2. The redundant information yk is demultiplexed
`and sent to decoder DEC1 when Yk =Y1k and toward decoder
`DEC; when Yk =Y;k. When the redundant information of a
`
`
`
`The APP of a decoded data bit dk can be derived
`
`from the joint probability 2",(m) defined by
`(11)
`;(m)=P,{d, =i,s,,=m/121"}
`and thus, the APP of a decoded data bit dk is equal to
`P,{d,, =1/1t,”} =9; 2';,(m), i=o,1 (12)
`From relations (8) and (12), the LLR A(d,,) associated with
`a decoded bit dk can be written as
`
`Z/1'1.(m)
`"“’*"“’gim'
`
`Finally the decoder can make a decision by comparing
`A (d,,)
`to a threshold equal to zero
`
`(ilk =1
`
`if A(d,,)>0
`
`(14)
`if A(d,,) <0.
`(2,, =0
`In order to compute the probability ,1;( m), let us introduce
`
`the probability functions a,';(m), mm) and y,.(R,,, m’, m)
`P,{d,, = 1,5,, = m,R,"}
`P,{Rr*}
`
`P,{d, =1, S, =m/Rf} (15)
`
`a;’,(m)=
`
`fik(m)=
`P,{Rr”,i/Rf}
`(17)
`y,.(R,,,m',m)=P,{d, =1,R,,,s) =m/s,,_, =m’)}.
`The joint probability 2,‘), (m) can be rewritten using BAYES
`rule
`
`(16)
`
`,t"k(m) =
`
`Thus we obtain
`
`P,{d,,=i,s,,=m,R{‘,1e,f’,,}
`Pr{Rlk'RlIrv-kl}
`
`. (18)
`
`”"('"):
`
`1>,{d,, =1,s,, =m,R1"} p,{1e,§,,/(1,, =i,s,, =m,R,"}
`P,{Rf}
`P,{R£ir/Rf}
`
`Taking into account
`
`(19)
`that events after time k are not
`
`influenced by observation R{‘ and bit dk if state sk is known,
`
`the probability 2.; (m) is equal
`
`l'),(m)=a,';(m)fi,,(m).
`
`(20)
`
`The probabilities a;;(m) and mm) can be recursively
`calculated from probability ‘y,-(Rk,m’, m). From annex I, we
`obtain
`1
`.
`
`Z7.-(Rt.m’,m)a)£_1(m’)
`V
`(1; (m) = . (21)
`22 Z EYi(Rl-1'”/» m)‘7‘i-10"’)
`m m’i=0j=0
`
`and
`
`l’i(R1r+l» m»m,)Bk+l(m,)
`(mm)= (22)
`EX:%)fiOyi(Rk+l*m,'m)aIi(m’).
`m m K= 1=
`The probability y,-(R,c,m’, m)
`can be determined from
`transition probabilities of the discrete gaussian memoryless
`
`channel and transition probabilities of the encoder trellis.
`From relation (17),
`')(,.(R,‘, m’, m) is given by
`
`y,-(R,‘,m’,m)=p(R,, /dk =l',S,‘ = m,S,,_1 =m’)
`
`(23)
`q(d,, =i/S,, =m,S,,_1=m’)2z(S,, =m/S,(_1=m')
`where p(./.) is the transition probability of the discrete
`gaussian memoryless
`channel. Conditionally to
`(dk = 1', S1,, = m, S“ = m’), xk and yk are two uncorrelated
`gaussian variables and thus we obtain
`p(Rk /dk = 1', Sk = m,Sk_1= m’) =
`
`p(x,, /d,, = L5,, = m,S,,_1=m’)
`
`(24)
`p(y* /d,, =i,S,, :m,Sk_, =m’).
`Since the convolutional encoder is a deterministic machine,
`q(d, =1‘/S,, =m,S,_, =m’)
`is equal
`to 0 or 1. The
`transition state probabilities 1r(S,, = m/S,‘_1 = m’) of the
`trellis are defined by the encoder
`input statistic.
`Generally,P,{d, =1} = P, {d,, = 0} =1/2 and since there
`are
`two
`possible
`transitions
`from each
`state,7r(Sk =m/S,(_1=m’)=l/2
`for
`each of
`these
`transitions.
`
`Different steps of modified BAHL et al. algorithm
`—Step 0 : Probabilities af,(m) and [3N(m) are
`initialized according to relation (12)
`a;;(o)=1 ag(m)=o Vm¢0, 1=0,1
`
`(25a)
`
`(2512)
`[3N(0)=1 /3,,,(m)=0 Vm:=0.
`-Step 1 : For each observation Rk, the probabilities
`oz,",(nl) and 7,-(R,z,m’, m) are computed using relations (21)
`and (23) respectively.
`
`-Step 2 : When the sequence R," has been
`completely received, probabilities Bk (m) are computed using
`
`relation (22), and probabilities a},(m) and fik(m) are
`multiplied in order to obtain /t;,(m). Finally the LLR
`associated with each decoded bit dk is computed from
`relation (13).
`
`IV- THE EXTRINSIC INFORMATION OF THE RSC
`DECODER
`
`In this chapter, we will show that the LLR A(dk)
`associated with each decoded bit dk , is the sum of the LLR
`of dk at the decoder input and of another information called
`extrinsic information, generated by the decoder.
`Using the LLR A(d)(-) definition (13) and relations (20) and
`(21), we obtain
`22: i7t(R),.m’,m)a,{_((m’)B),(m)
`/l(r1,,)=mg . (26)
`E2 Ey0(Rk1m’-m)ai-l(m’)flk(m)
`m m’j=0
`
`the transition
`Since the encoder is systematic (Xk = dk),
`probability p(x,‘ /d,‘ = L5,‘ = m,Sk_1 = m’) in expression
`y,.(Rk,m’,m) is independent of state values Sk and Sk.1.
`Therefore we can factotize this transition probability in the
`numerator and in the denominator of relation (26)
`
`
`
`feedback loo -
`
`16-STATE
`DECODER
`DEC 1
`
`inter-
`
`leaving
`
`16-STATE
`DECODEFI
`
`DEC?
`
`deinter-
`
`deinter
`
`2?
`
`DEMUXI
`INSERTION
`
`Fig. 3b Feedback decoder (under 0 internal delay assumptlon).
`
`decoded output
`A
`
`d k
`
`A(dk):L0g
`1
`
`p(xk /d,, =1) +
`p(x,, /d,‘ =0)
`.
`
`E2: Z71()’k~’"’»”‘)‘1I£—1(m')Bk(’")
`mg . (27)
`E; _Z:070(ykrm,vm)aI:-l(m’)fik(m')
`III m /=
`Conditionally to dk=1 (resp. dk =0), variables xk are
`gaussian with mean 1 (resp. -1) and variance 02, thus the
`LLR A (dk) is still equal to
`A(d,,)=;21-x,‘+VV,‘
`
`(28)
`
`where
`
`W): ‘_"A(dI:) l,,-,, =
`2; Emi.m'.m2a.i-i(m'2/arm)
`mg . (29)
`E: ETo()’k»'"’- m)ai—1(m')l6k('")
`m nz’j=0
`Wk is a function of the redundant information introduced by
`the encoder. In general Wk has the same sign as (11,; therefore
`Wk may improve the LLR associated with each decoded data
`bit dk. This quantity represents the extrinsic information
`supplied by the decoder and does not depend on decoder
`input xk. This property will be used for decoding the two
`parallel concatenated encoders.
`
`V - DECODING SCHEME OF PARALLEL
`CONCATENATION CODES
`
`In the decoding scheme represented in Fig. 3a,
`decoder DEC; computes ‘LLR A1(dk) for each transmitted
`bit dk from sequences {xk} and {y;.,}, then the decoder DEC;
`performs the decoding of sequence{dk} from sequences
`{A1(dk)} and {yk}. Decoder DEC1 uses the modified BAHL
`et al. algorithm and decoder DEC; may use the VITERBI
`algorithm. The global decoding rule is not optimal because
`the first decoder uses only a fraction of the available
`redundant information. Therefore it is possible to improve the
`performance of this serial decoder by using a feedback loop.
`
`V-1 Decoding with a feedback loop
`We consider now that both decoders DEC1 and
`DEC; use the modified BAHL et al. algorithm. We have
`seen in section IV that the LLR at the decoder output can be
`expressed as a sum of two terms if the decoder inputs were
`independent. Hence if the decoder DEC; inputs A1(dk) and
`ygk are independent, the LLR A;(dk) at the decoder DEC;
`output can be written as
`A;(di)=f(A,(d,,))+Vé,,
`
`(30)
`
`with
`
`2
`A1(d,,)=?xk+-W/1;,
`From relation (29), we can see that the decoder DEC;
`extrinsic information W;k is a function of the sequence
`{A1(d,,)}n¢k. Since A 1(d,,) depends on observationR1N ,
`extrinsic information W;k is correlated with observations xk
`and y1k. Nevertheless from relation (29), the greater In-k I is,
`the less correlated are A; (d,.) and observations xk, yk. Thus,
`due to the presence of interleaving between decoders DEC1
`and DEC;, extrinsic information W;k and observations xk,
`y“, are weakly correlated. Therefore extrinsic information
`W;k and observations xk. y“, can be jointly used for carrying
`out a new decoding of bit dk. the extrinsic information
`zk = W;k acting as a diversity effect in an iterative process.
`In Fig. 3b, we have depicted a new decoding scheme
`using the extrinsic information Wzk generated by decoder
`DEC; in a feedback loop. This decoder does not take into
`account the different delays introduced by decoder DEC1
`and DEC; and a more realistic decoding structure will be
`presented later.
`The first decoder DEC; now has three data inputs,
`
`and/31,(m) are
`(xk, ylk, gig and probabilities a;',,(m)
`computed in substituting Rk ={xk, y1k] by Rk =(xk, ylk, zk) in
`relations (21) and (22). Taking into account that zk is weakly
`correlated with xk and y1k and supposing that zk can be
`
`approximated by a gaussian variable with variance of :9 0'2,
`the transition probability of the discrete gaussian memoryless
`channel can be now factored in three terms
`
`
`
`p(R,, /d, =i,S,, =m,S,,_, =m’) = p(x,,/.)p(y,,/.)p(z,,/.) (32)
`The encoder C1 with initial rate R1, through the feedback
`loop, is now equivalent to a rate R'1 encoder with
`
`«
`
`1
`1 =
`
`R1
`1 + R,
`The first decoder obtains an additional redundant information
`with zk that may significantly improve its performances; the
`term Turbo-codes is given for this iterative decoder scheme
`with reference to the turbo engine principle.
`With the feedback decoder, the LLR A1(dk) generated by
`decoder DEC; is now equal
`to
`2
`2
`(34)
`Al(dk) -‘-371:; +?Zk + “it
`Z
`where Wlk depends on sequence [Zn]n¢k. As indicated
`above, information zk has been built by decoder DEC; at the
`previous decoding step. Therefore zk must not be used as
`input information for decoder DEC2. Thus decoder DEC;
`input sequences at step p (p22) will be sequences
`{zi.td.)}ana {ml with
`(35)
`./i1(d,,)=A1(d,,),n=0.
`extrinsic
`Finally from relation (30), decoder DEC;
`information zk = Wgk, after deinterleaving, can be written as
`
`From
`demodulator
`
`Fig. 4a Modular pipelined decoder, oorresponding to an
`iterative processus at the feedback decoding.
`
`(1) pt
`
`(36)
`
`,i,(d,)=o
`3k = Wu = A2(dk )|
`and the decision at the decoder DEC output is
`3,, = sign[A,(d,)].
`(37)
`The decoding delays
`introduced by decoder D E C
`(DEC=DEC1+DEC2), the interleaver and the deinterleaver
`imply that the feedback information zk must be used through
`an iterative process as represented in Fig. 4a, 4b. In fact, the
`global decoder circuit is composed of P pipelined identical
`elementary decoders (Fig. 4a). The pth decoder DEC
`(Fig. 4b) input, is made up of demodulator output sequences
`(.01, and 01),, through a delay line and of extrinsic infomiation
`(2),, generated by the (p-1)th decoder DEC. Note that the
`variance of of the extrinsic information and the variance of
`/l1(d,, ) must be estimated at each decoding step p.
`
`V-2 Interleaving
`The interleaver uses a square matrix and bits {dk}
`are written row by row and read pseudo-randomly. This non—
`uniform reading rule is able to spread the residual error
`blocks of rectangular form, that may set up in the interleaver
`located behind the first decoder DEC1, and to give the
`greater free distance as possible to the concatenated (parallel)
`eode.
`
`VI - RESULTS
`
`For a rate R=l/2 encoder with constraint length K=5,
`generators G1=37, G2=21 and parallel concatenation
`(R1=R;=2/3), we have computed the Bit Error Rate (BER)
`after each decoding step using the Monte Carlo method, as a
`function of signal to noise ratio Eb/N0 where Eb is the
`energy received per information bit dk and N9 is the noise
`monolateral power spectral density. The interleaver consists
`of a 256x256 matrix and the modified BAHL et al. algorithm
`has been used with length data block of N=65536 bits. In
`
`Fig. 4b Decoding module (level p).
`
`order to evaluate a BER equal to 10'5, we have considered
`128 data blocks i.e. approximatively 8 X106 bits dk. The BER
`versus Eb/N0, for different values of p is plotted in Fig. 5.
`For any given signal to noise ratio greater than 0 dB, the BER
`decreases as a function of the decoding step p. The coding
`gain is fairly high for the first values of p (p=1,2,3) and
`carries on increasing for the subsequent values of p. For p=18
`for instance, the BER is lower than l()'5 at Eb/N0= 0,7 dB.
`Remember that the Shannon limit for a binary modulation
`with R=1/2, is P5 = 0 (several authors take Pg =10'5 as a
`reference) for E1,/Ng= 0 dB. With parallel concatenation of
`RSC convolutional codes and feedback decoding,
`the
`performances are at 0,7 dB from Shannon's limit.
`The influence of the constraint length on the BER
`has also been examined. For K greater
`than 5, at
`Eb/N0: 0,7 dB, the BER is slightly worst at the first (p=1)
`decoding step and the feedback decoding is inefficient to
`improve the final BER. For X smaller
`than 5, at
`E),/N0: 0,7 dB,
`the BER is slightly better at the first
`decoding step than for K equal to 5, but the correction
`capacity of encoders C1 and C2 is too weak to improve the
`BER with
`feedback decoding. For K=4 (i.e. 8-state
`elementary decoders) and after iteration 18, a BER of 10'5 is
`achieved at Eb/N0 = 0,9 dB. For K equal to 5, we have tested
`several generators (G1, G2 ) and the best results were
`achieved with G1=37, G2=21.
`
`
`
`uncodad
`
`Iteration #1
`
`5 Eb/No (dB)
`
`Ot
`
`heoretical
`limit
`
`Fig. 5 Blnary error rate given by Iterative decoding (p=1,....18)
`of code of Hg. 2 (rate:1/2); interleaving 256x256.
`
`For low signal to noise ratios, we have sometimes noticed
`that BER could increase during the iterative decoding
`process. In order to overcome this effect, we have divided the
`extrinsic information 2;, by [ 1 + 9|/i1(d,‘)i ]with 8 = 0,15.
`
`In Fig. 6, the histogram of extrinsic infomration (z)p
`has been drawn for several values of iteration p, with all data
`bits equal tol and for a low signal
`to noise ratio
`(Eb/No: 0,8 dB). For p=l
`(first
`iteration), extrinsic
`information (zlp is very poor about bit dk. furthermore the
`gaussian hypothesis made above for extrinsic information
`(z)p, is not satisfied! Nevertheless when iteration p increases,
`the histogram merges towards a gaussian law with a mean
`equal to 1. For instance, for p=13, extrinsic information (zlp
`becomes relevant information concerning data bits.
`
`VII CONCLUSION
`
`In this paper, we have presented a new class of
`convolutional codes called Turbo-codes whose performances
`in terms of BER are very close to SHANNONS limit. The
`decoder is made up of P pipelined identical elementary
`modules and rank p elementary module uses the data
`information coming from the demodulator and the extrinsic
`information generated by the rank (p-1) module. Each
`elementary module uses a modified BAHL er al. algorithm
`which is rather complex. A much simpler algorithm yielding
`weighted (soft) decisions has also been investigated for
`Turbo-codes decoding [2], whose complexity is only twice
`the complexity of the VITERBI algorithm, and with
`performances which are very close to those of the BAHL et
`al. algorithm. This new algorithm will enable encoders and
`
`
`
`decoders to be integrated in silicon with error correcting
`performances unmatched at the present time.
`
`,‘_1
`Pr{R,/R,
`
`I
`.
`I
`1
`1
`}=_>:z 2 ):y,.(R,,m m)a,{_,(m ). (A6)
`(=0 j=0
`In m’
`
`Finally probability (1,: (m) can be expressed from probability
`
`0:}, ,1 (m) by the following relation
`.: iy.-rRt.m'm)ai.1tm')
` _ (A7)
`Z2 2 Zr.-(R,..m’m)a,{_1(m')
`m m’
`i=0 j=0
`
`a;;(m)=
`
`In the same way, probability |3k(m) can be recursively
`calculated from probability Bk“ (m). From relation (16), we
`have
`
`_P.{Rt"+./s..=m} _
`fik(m)- —
`Z Z1:Pr{dIz+t '-"'»St+1 =m>’RI:v+2rRk+1/SI: '-'m}
`
`(A8)
`
`By using BAYES rule, the numerator is equal to
`.
`N
`1
`N
`P:-{Rim /51: = m} =2 zP.{Rm /SI.-+1: m}
`m'i=0
`
`(A9)
`P,{d,+,=i,S,H1=m,'R,‘,,/S,‘ =m}.
`By taking into account expressions of 1,-(Rk+1,m,m') and
`Bk“ (m’), we can write
`.5: )l:}’.'(Rk+1vm-m')»3k+1(m')
`P,{1e,+./Rf‘}
`
`‘**"“"
`
`(A10)
`
`In substituting k by (k+I) in relation (A6), the denominator
`of (A10) is equal to
`Pr{R,..1/Rf} :2); f E y,.(R,.,,.m'm)a{(m'). (A11)
`in m’
`i=0 j=0
`Finally probability Bk (m)can be expressed from probability
`Bk...1 (m'), by the following relation
`2:
`7’i(Rk+t»m» '71’ ).Bk+t(m')
`i=0
`:1:
`:2 5 $:r.(R,.+1.m'm)a.£(m')
`m m’
`i=0 j=0
`REFERENCES
`
`fik(m):
`
`. (A12)
`
`[1] L.R. Bahl, J. Cocke, F. Jeinek and J. Raviv,
`"Optimal decoding of linear codes for minimizing symbol
`error rate", IEEE Trans. Inform Theory, vol. IT-20, pp. 248-
`287, March 1974.
`
`[2] C. Berrou, P. Adde, E. Angui and S. Faudeil, "A
`low complexity soft-output Viterbi decoder architecture", to
`appear at ICC’ 93.
`
`5 __....~«v~
`0%
`NORMALIZED
`.1
`SAMPLES
`
`_]J ‘"3
`
`0
`
`Fig. 6 Histograms of extrinsic information z after
`iterations it 1.4.13 at Eb/No = 0.8 dB;
`all information bits d=1.
`
`ANNEX I : EVALUATION OF PROBABILITIES 05,‘; (m)
`AND fi,,(m) .
`
`From relation (15) probability 01;; (m) is equal to
`Pr{d,, =1‘, 5,, =m.R,"“,R,,}
`Pr{R1"",R,,}
`
`aztm) =
`
`(A1)
`
`Pr{d,, = i,S,, = m,Rk/R1"'1}
`'
`Pr{R,,/R{‘"}
`The numerator of a,i( m) can be expressed from state Sk_1
`and bit dk .1.
`Pr{d,, =1‘, s,, = m,R,./R,"“} =
`1
`2 zP,{d,, = i,d,,_, =1, s,, = m. s,,_1= m',R,, /RIM} (A2)
`m‘ ,'=o
`By using BAYES rule, we can write
`Pr{dk = z,s,, = m,Rk/RF‘) =
`
`1 Pr{d,,_1=j,S,H= m‘,R1""}
`1.3:’,-{:0
`P,{R1"_'}
`P,{d,, =1, s,, =m,R,,/d,,_1 = j,S,,_1 = m',R{‘-1}. (A3)
`By taking into account that events after time (k—1) are not
`
`influenced by observation Rf“ and bit dk_1 if state SM is
`known and from relation (17) we obtain
`Pr{d,, = as,‘ = m, R,, /R1"“} =
`1
`
`.
`
`(A4)
`Z207,-(R,.,m‘m)a,{_.(m’).
`m’ j=
`The denominator can be also expressed from bit dk and state
`St:
`
`1
`P,{R,,/R,""} =):_z0 Pr{d,, =i,S,, =m,R,,/R{"‘} (A5)
`HI l=
`and from relation (A4), we can write :