西安电子科技大学：《现代数字通信与编码理论》课程教学资源（讲义）Chapter 04 Binary Capacity-Approaching Codes（4.1-4.5）

modulation.then we have and 1 where E,is the average transmitted energy per symbol,o2=N/2 is the variance of noise samples and a is the fading amplitude. Thus,with the channel model above,(4.5)can be written as E L(ylx)=In exp-2+a) ” =L.y where 4货 (4.6) is defined as the channel reliability vae,and depends only on the SNR and fading amplitude of the channel.Hence,for BPSK over a(possibly fading)Gaussian channel,the conditional LLR L(),which is referred to as the sofi ouput of the channel,is simply the matched filter outputy multiplied by the channel reliability valueLe 4.3.2 The Maximum A Posteriori Algorithm Having introduced log likelihood ratios,we now proceed to describe the operation of the Maximum A-Posteriori algorithm,which is one of the possible sof-in soft-out component decoders that can be used in an iterative turbo decode 4.3.2.1 Introduction In 1974 an algorithm,which is known as the Maximum A-Posteriori(MAP)algorithm, op.Cocke linck and Ravi for esimating the pos f a Markov source obse when Thisorit has beom nown本e PCmed西 o memoryles inventors.They showed,how the algorithm could be used for decoding both block and 4-16

4-16 modulation, then we have 2 2 1 ( | 1) exp ( ) 2 2 s kk k E p yx y a             and 2 2 1 ( | 1) exp ( ) 2 2 s kk k E p yx y a             where Es is the average transmitted energy per symbol, 2 0   N / 2 is the variance of noise samples and a is the fading amplitude. Thus, with the channel model above, (4.5) can be written as 2 2 2 2 exp ( ) 2 ( | ) ln exp ( ) 2 s k k k s k E y a Ly x E y a                          2 2 2 2 () () 2 2 s s k k E E ya ya       2 4 2 s k aE y    L yc k where 0 4 s c aE L N  (4.6) is defined as the channel reliability value, and depends only on the SNR and fading amplitude of the channel. Hence, for BPSK over a (possibly fading) Gaussian channel, the conditional LLR ( | ) Ly x k k , which is referred to as the soft output of the channel, is simply the matched filter output yk multiplied by the channel reliability value Lc. 4.3.2 The Maximum A Posteriori Algorithm Having introduced log likelihood ratios, we now proceed to describe the operation of the Maximum A-Posteriori algorithm, which is one of the possible soft-in soft-out component decoders that can be used in an iterative turbo decoder. 4.3.2.1 Introduction In 1974 an algorithm, which is known as the Maximum A-Posteriori (MAP) algorithm, was proposed by Bahl, Cocke, Jelinek and Raviv for estimating the a-posteriori probabilities of the states and the transitions of a Markov source observed, when subjected to memoryless noise. This algorithm has also become known as the BCJR algorithm, named after its inventors. They showed, how the algorithm could be used for decoding both block and

convolutional codes.When employed for decoding convolutional codes,the algorithm is optimal in terms of minimizing the decoded bit error rate,unlike the Viterbi algorithm,which minimizes the probability of an incorrect path through the trellis being selected by the decoder However the MAP algorithm provides not only the estimated bit sequence.but also the probabilities for each bit that it has been decoded correctly.This is essential for the iterative decoding of turbo codes. we often use Bayes"rule in this section.This rule may be briefly stated as P(u,v)=P(ulv)P(v) A usedul consequence of Bayes's rule is that P(u,vlw)=P(ulv,w)P(vlw) 4.3.2.2 Symbol-by-Symbol MAP decoding algorithm for a convolutional code Consider the system model shown in Fig.4.11.Letu=()be the input information sequence,which is encoded by a rate-1/2 (either systematic or non-systematic)convolutional encoder into a coded symbol sequence c=(c.). where c=(c,cf),l≤k≤N.The coded symbols,.c∈{o,I)and cf∈{0，l,are then modulated in BPSK format,producing the transmitted symbols,andx n 积 ⊕ n 图4.11信道模型 With the channel model shown in Fig.4.11,the received sequence y=y=y,y2.,ya,.,yw）consists of N symbol pairs y=Og,yW),where =+度=ag(2c-)NE+m (4.7) y=ax+=a成(2c-l)WE,+n 式中E是每发送符号的平均能量：a和a为信道衰落因子，对于AWGN信道， a=a{=l;对于Rayleigh衰落信道，a和af为两个Reyleigh随机变量。n和nf是两 417

4-17 convolutional codes. When employed for decoding convolutional codes, the algorithm is optimal in terms of minimizing the decoded bit error rate, unlike the Viterbi algorithm, which minimizes the probability of an incorrect path through the trellis being selected by the decoder. However the MAP algorithm provides not only the estimated bit sequence, but also the probabilities for each bit that it has been decoded correctly. This is essential for the iterative decoding of turbo codes. We often use Bayes’ rule in this section. This rule may be briefly stated as Puv Pu vPv (,) ( | ) ()  A usedul consequence of Bayes’s rule is that Puv w Pu vwPv w (, | ) ( |, ) (| )  4.3.2.2 Symbol-by-Symbol MAP decoding algorithm for a convolutional code Consider the system model shown in Fig. 4.11. Let 1 2 ( , ,., ), {0,1} N k u  uu u u  be the input information sequence, which is encoded by a rate-1/2 (either systematic or non-systematic) convolutional encoder into a coded symbol sequence   1 2 , ,.,  N c cc c , where   , ,1 s p k kk c   cc k N . The coded symbols, {0,1} s k c  and {0,1} p k c  , are then modulated in BPSK format, producing the transmitted symbols, and s p k k x x . 图 4.11 信道模型 With the channel model shown in Fig. 4.11, the received sequence y y   1 12 N k N (, , , ) yy y y   consists of N symbol pairs ( , ) s p k kk y  y y , where (2 1) s ss s s s s k kk k k k s k y     ax n a c E n (4.7) (2 1) p pp p p p p k kk k k k s k y     ax n a c E n 式中 Es 是每发送符号的平均能量； p k s ak和a 为信道衰落因子，对于 AWGN 信道，   1 p k s ak a ； 对于 Rayleigh 衰落信道， p k s ak和a 为两个 Reyleigh 随机变量。n n k s k 和 是两 p QPSK 调制器 s k y p k y s ak p ak s nk p nk s k c p k c s k x p k x 卷积 编码器 uk

个独立同分布的高斯噪声样值，它们的均值为0，方差σ=N。/2。 式(4.7)可以等效地写为： =a(2c-)+m y=ap(2cf -1)+n 式中，噪声and nf的方差成为o2=σ/E,=N。(2E,). Assume that the convolutional encoder used has v memory elements and a constraint length of K.Let S=(.)be the encoder state at time k.Denote by S the set of encoder states and by M=the number of states.In the following.we will consider the optimal decoding of ufrom y. 考虑图4.12所示的软输入软输出(SS0)译码器，它能为每一译码比特提供对数 似然比输出。 L(4) MAP 译码器 图4.12软输入软输出译码器框图 图中MAP译码器的输入序列为y=y=(2.,y,.,yx),其中y=(,)。 L(u)是关于的先验信息，L(u)是关于的对数APP(似然)比。它们的定义如下： L(u)=In P(u =1) P(u =0) Z:)=nP4,= P(4=y) (4.8) MAP译码器的任务就是求解式(4.8)，然后按照下列规则进行判决： 1.L(u)20 a={0,u,)<0 (4.9) 下面我们利用BCJR算法对式(4.8)的计算方法进行推导。 A branch at the kth section in the trellis diagram can be specified by b=(S.CS).where u and c are the information and coded symbols associated with the state transition SS Denote by B(s'.s)the set of all the parallel branches 4-18

4-18 个独立同分布的高斯噪声样值，它们的均值为 0，方差 2 0 / 2  n  N 。 式(4.7)可以等效地写为： (2 1) (2 1) s ss s k kk k p pp p k kk k y ac n y ac n      式中，噪声 and s p k k n n 的方差成为 2 2 0 / /(2 )    ns s EN E . Assume that the convolutional encoder used has v memory elements and a constraint length of K. Let S aa a k k k kv    (, , ) 1 1  be the encoder state at time k. Denote by  the set of encoder states and by M = || the number of states. In the following, we will consider the optimal decoding of u from y. 考虑图 4.12 所示的软输入软输出（SISO）译码器，它能为每一译码比特提供对数 似然比输出。 图 4.12 软输入软输出译码器框图 图中 MAP 译码器的输入序列为 1 12 (, , , , ) N   k N y y yy y y   ，其中 (, ) s p k kk y  y y 。 ( ) L u a k 是关于 uk的先验信息， L uk ( ) 是关于 uk的对数 APP(似然)比。它们的定义如下： ( 1) ( ) ln ( 0) k a k k P u L u P u    L u P u P u k k N k N ( ) ln ( |) ( |)    1 0 1 1 y y (4.8) MAP 译码器的任务就是求解式(4.8)，然后按照下列规则进行判决：  , () , () u L u L u k k k       1 0 0 0 (4.9) 下面我们利用 BCJR 算法对式(4.8)的计算方法进行推导。 A branch at the kth section in the trellis diagram can be specified by 1 ( ,) k k kk k b Su S   c , where uk and k c are the information and coded symbols associated with the state transition k k 1 S S   . Denote by ( ', ) Bk s s the set of all the parallel branches ( ) L u a k MAP 译码器 yk s yk p L uk ( )

connecting S=s'ES and S=sES. Using Bayes'rule,the aposteriori probability can be expressed as P(u =ily)=P(u =i,S=s',S=sly) =∑pw,=4S=sS=s,y (se成 p(y) where B is the set of transitions S that are caused by the input us=i.Thus (4.8) can be written as p(u =1.S=s'.S.=s.y )p(y) L(u)=In n三u=0=5S=7/p0 (4.10) The sequence y in p(u=i,S=s'.S=s.y)can be written as p(u.()y.yx))=p(uS-Syiye-yi) where y=(yy)represents the portion of the received sequence y in the time interval to / Applying Bayes'rule to this expression yields the following decomposition of p(u=i,S-=s',S:=s,y): p(u=1.S-=5'.S=5.y)=p(u =1.S.=5.S-=5'.yi.y.y) =p(yim lyeyiu=i.S=5.S-=s)p(yyu=i.S:=s.S=s) =p(yiu ls=s)p(y.yf,u=i.S=s,S=s) (4.1) p(yiIs=s)p(u=i.S.=5.yS=5'.y)p(S-=s'.y) =p(S=s',y）p(4=iS=sylS=s）pylS=s) =a4-(s')(s',sB(s) (4.12) where (s)=p(S=s.y),called the forward state metric,is the joint of the encoder state at time k being S=s and receiving the sequencey B (s)=p(yS=s)is the backward state metric;and 419

4-19 connecting 1 ' k S s    and k S s   . Using Bayes’ rule, the a posteriori probability can be expressed as 1 11 ( ', ) ( | ) ( , ', | ) i k N N k kk k ss B Pu i Pu iS s S s        y y  1 1 ( ', ) 1 ( , ', , ) i ( ) k N kk k N ss B pu iS s S s p        y y where i Bk is the set of transitions S S k k 1  that are caused by the input uk=i. Thus (4.8) can be written as 1 0 1 11 ( ', ) 1 11 ( ', ) ( 1, ', , ) / ( ) ( ) ln ( 0, ', , ) / ( ) k k N N kk k ss B k N N kk k ss B pu S s S s p L u pu S s S s p              y y y y (4.10) The sequence y in 1 1 ( , ', , ) N kk k pu iS s S s    y can be written as     1 1 1 1 1 11 1 , , ,( ,., ), ,( ,., ) , , , , , k N kk k k k k N kk k kk pu S S pu S S      y y y y y y yy  where 1 ( , ,., ) l t tt l   y yy y represents the portion of the received sequence y in the time interval t to l. Applying Bayes’ rule to this expression yields the following decomposition of 1 1 ( , ', , ) N kk k pu iS s S s    y :    1 1 1 11 1 , ', , , , ', , , N kN k k k k k k kk pu iS s S s pu iS sS s          y y yy     1 1 11 1 1 1 |, , , , , , , , ' Nk k kk k k k k k k k p u iS sS s p u iS sS s            y yy yy    1 11 1 | , , , ' N k kk k k k k p S s p u iS sS s         y yy (4.11)      1 1 1 11 11 | , , | ', ', N kk k k k k kk k p S s pu iS s S s p S s            y yy y       1 11 1 1 ', , , | ' | k N k k k kk k k p S s pu iS s S s p S s           y yy 1( ') ( ', ) ( ) i kk k   s ss s   (4.12) where  k k k () ( , ) s pS s   y1 , called the forward state metric, is the joint of the encoder state at time k being Sk=s and receiving the sequence 1 k y ; k k N k () ( | ) sp Ss   y 1 is the backward state metric; and