北邮信通院信息论第七章剖析

第7章有噪信道编码信息与通信工程学院许文俊2/66第7章有噪信道编码本章主要内容：1.概述2.常用译码准则3.费诺(Fano)不等式4.序列的最佳译码准则5.有噪信道编码定理3/66§7.1概述为提高传输的可靠性，必须进行信道编码。信道编码就是按一定的规则给信源输出序列增加某些冗余符号，使其变成满足一定数学规律的码序列（或码字），再经信道进行传输。（注意：与信源编码比较）信道译码就是按与编码器同样的数学规律去掉接收序列中的冗余符号,恢复信源消息序列。一般地说，所加的冗余符号越多，纠错能力就越强，但传输效率降低。因此在信道编码中明显体现了传输有效性与可靠性的矛盾。在数据传输系统中译码过程总要比编码过程复杂,这样采用的译码算法对系统的性能影响很大。4/66本节主要内容：1.错误概率2.译码（判决）规则5/667.1.1错误概率●两种错误概率的描述：误码率和误字率。误码率是指传输码元出错概率（对二进制也称误比特率）.误字率是指码字出错概率。●一个码字一般由多个码元构成，任何一个或多个码元出错都使得码字出错。所以对同一通信系统，误字率总比误码率高。●错误概率的大小与信噪比大小有关。信噪比大，则错误概率小；反之信噪比小，则错误概率大。●错误概率还与译码规则的选择有关。适当地选择译码规则使平均错误概率最小是提高传输可靠性的重要措施之一。6/667.1.2译码（判决）规则1.单符号译码规则设信道的输入与输出分别为X和Y，，分别取自符号集A和B，且，定义译码（判决）规则为对于所有（7.1.1）含义：当接收到就判定发送符号是因此，每一个信道输出都必须有一个信道输入与之对应。所以译码（判决）规则是一个有唯一结果的函数。,xXyY12{,,,}rAaaa12{,,,}sBbbb(),jiFyba1,,,1,,irjsjbia7/662．错误概率的计算设信道的转移概率为，采用的译码规则为：对于所有（7.1.2）（7.1.2）式可简记为。在接收到的条件下，若实际上发送的是，则译码正确，反之就出现差错。因此满足译码规则（7.1.2）的条件错误率为：/(|)YXjiijPybxap*(),jFyba1,,,1,,irjs*()Fyxjb*a*/(|)iXYijaaPxayb8/66正确率为：所以平均错误率为：（7.1.3）（7.1.3）式的含义是，如果输出y与未被y作为译码结果的输入同时出现就属于译码错误。还可计算平均正确率为（7.1.4）*/(|)XYjPxayb*/()(|)iEYjXYijjaaPPybPxayb*()(/)yxxpypxy*1()ypxy)(1*yEEyxpPP9/66§7.2常用译码准则为提高可靠性，所采用的译码准则都应该使平均错误概率最小。最常用的就是最大后验概率译码准则和最大似然译码准则。本节主要内容：1.最大后验概率译码准则2.最大似然译码准则10/667.2.1最大后验概率译码准则对所有i，当满足（7.2.1）时，则选择译码函数为F(y)=a*，称此准则为最大后验概率(MAP，MaximumaPosteriori)准则。MAP准则就是将具有最大后验概率的信道输入符号作为译码输出。由（7.2.1）式，得)()|()()()|()(**ypaxypaxpypaxypaxpii*(|)(|)ipxaypxay11/66所以，对所有i，当（7.2.2）时，则选择译码函数为F(y)=a*。其中，为似然比，（7.2.2）式表示的是似然比检验。可见，MAP准则可归结为似然比检验。MAP准则是使平均错误最小的准则,原因：)()()|()|(**axpaxpaxypaxypii**(|)()(|)()iipyxapxapyxapxa*(,)(,)ipxaypxay*1()EyPpxy12/667.2.2最大似然译码准则若输入符号等概，即p(ai)=1/r时，（7.2.2）变为：对所有i,当（7.2.3）则选择译码函数为F(y)=a*，称此准则为最大似然译码准则。注：1）当输入符号等概或先验概率未知时，采用此准则。2）当输入符号等概时，最大似然准则等价于最大后验概率准则。)|()|(*iaxypaxyp13/66例7.2.1设信道输入X取值为(a1,a2,a3),信道输出Y取值为(b1,b2,b3)，转移概率矩阵如下求利用最大似然（ML）译码准则的判决函数。解:每个输出符号给定，当y=b1时，p(y/a1)=0.5,p(y/a2)=0.2,p(y/a3)=0.3，利用（7.2.3），得判决函数,F(b1)=a1，同理得其它最大似然判决函数：F(b2)=a3（或F(b2)=a1或F(b2)=a2），F(b3)=a2。0.50.30.20.20.30.50.30.30.414/66两种准则使用要点：1．MAP准则i）由转移概率矩阵的每行分别乘p(x)，得到联合概率矩阵；ii）对于每一列（相当于y固定）找一个最大的概率对应的x作为译码结果；iii）所有译码结果所对应的联合概率的和为正确概率,其他矩阵元素的和为错误概率。2．ML准则i）对转移概率矩阵中每列选择最大的一个元素对应的x作为译码结果；ii）输入符号等概时，所有译码结果所对应的转移概率的和再乘以1/r为正确概率，其他矩阵元素的和再乘以1/r为错误概率。15/66例7.2.1（续）求最大似然准则的错误率。解：错误率PE=1-(0.5+0.3+0.5)/3=0.5667。16/66例7.2.2已知信道的转移概率矩阵为现有两种译码规则：规则A：规则B：设输入等概，求两种译码规则的错误率。1/21/31/61/61/21/31/31/61/2111222333()()()FybaFybaFyba111223332()()()FybaFybaFyba17/66解：设判决函数为，根据（7.1.3），得*()Fya*()(|)/3EyaapApyxa3/)]3/16/1()6/13/1()3/16/1[(2/1*()(|)/3EyaapBpyxa3/)]2/16/1()2/13/1()3/16/1[(3/218/66§7.3费诺(Fano)不等式主要内容：1.信道疑义度2.费诺(Fano)不等式3.序列费诺(Fano)不等式19/667.3.1信道疑义度设信道的输入与输出分别为X、Y，定义条件熵H(X|Y)为信道疑义度。它包含如下含义：1）信道疑义度表示接收到Y条件下X的平均不确定性；2）根据I(X;Y)=H(X)-H(X|Y)，信道疑义度又表示X经信道传输信息量的损失；3）接收的不确定性由信道噪声引起，在无噪情况下，H(X|Y)=0。20/667.3.2费诺(Fano)不等式设信道的输入与输出分别为X、Y，输入符号的数目为r，那么信道疑义度满足（7．3．1）其中，为平均错误率。证：设译码规则由（7.1.2）确定，那么(|)()log(1)EEHXYHpprEp(|)()log(1)EEHXYHppr()log(|)log(1)log(1)(1)EEEEExypxypxyppppplogr21/66上式=yxxEyxxrpxypyxpxyp**1log)()|(log)(***()log(|)()log(1)Eyypxypxypxyp***1()log()log(1)(|)(|)EEyyxxpppxypxyrpxypxy***1{()[1]()[1]}(log)(1)(|)(|)EEyyxxpppxypxyerpxypxy***{()(,)(1)()()}(log)(1)EEyyyyxxxxppypxyppypxyer0)1()1(EEEEpppp22/66当下面两个条件同时成立时，等号成立：i）ii）上面条件表明，当y给定后判决错误的概率相等时，不等式取等号。证毕。10(|)(1)(|)1EExxpppxyrpxyrEEpyxpyxpp1)|(01)|(1**23/66注释：i）无论什么译码规则，费诺不等式成立；译码规则变化只会改变pE的值；ii）信道疑义度由信源、信道及译码规则所限定；因为信源决定p(x)，r，而p(x)，p(y|x)及译码规则决定pEiii）对不等式的含义的理解：当接收到Y后，关于X平均不确定性的解除可以分成两步来实现：第1步是确定传输是否有错，解除这种不确定性所需信息量为H(pE)；第2步是当确定传输出错后，究竟是哪一个错解除这种不确定性所需最大信息量是log(r-1)。24/66EPH(X|Y)1rr01()log(1)EEHPPrlogrlog(1)rH(X|Y)的允许区域图7.3.1费诺不等式示意图图7.3.1为费诺不等式示意图。图中，曲线下面的区域为信道疑义度被限定的区域。现求曲线的极大值。25/66仅当即时等式成立。由于当时，有。)1log()(rppHEEEEEEppprp11log)1(1logEEppr111rrpE11Ep1Ep()log(1)log(1)EEHpprr11log[(1)]log1EEEErpprpp26/667.3.3序列费诺(Fano)不等式(教材无)若信道的输入与输出为多维随机变量和，定义（7．3．2）其中，是第个符号出错的概率，则Fano不等式成立：（7．3．3）其中r为输入符号集中元素的个数。LXLYLlEElpLp11lEpl1(|)()log(1)LLEEHXYHpprL27/66证：利用引理4，有利用（7．3．1）式，有)1log()()|(rppHYXHllEEllLlELlELlllLLrpLpHLYXHLYXHLll111)1log(1)(1)|(1)|(1)1log(]1[1rppLHLlEEl)1log()(rppHEE1(|)(|)lLLLllHXYHXY28/66§7.4序列的最佳译码准则主要内容：1.汉明距离2.序列最大似然译码29/667.4.1汉明距离设两码字为，定义它们的汉明距离为（7.4.1）其中，为模二加运算。例如，码字和码字的汉明距离为6。一个码字集合中任意两码的汉明距离最小值，称为码的最小距离，用dmin来表示。],...,[],,...,[11nnyyyxxx1(,)nkkkdxyxy]1101110[x]1010001[y30/667.4.2序列最大似然译码设信道的输入与输出分别为多维随机矢量集合：，其中，序列；分别取自符号集A和B，且，，其中，，。1,,nnXXX1,,nnYYYnnXxxx],...,[1nnYyyy],...,[1,iiiixXyY12{,,,}rAaaa12{,,,}sBbbbnkAnlB1,,nkr1,,nls31/66如果对于所有k，满足（7.4.2）那么就选择译码函数为，称为序列的最大似然译码准则。转移概率称为似然函数。与单符号情况相同，当消息序列等概或概率未知时用最大似然译码准则。(|)pyx*(|)(|)kpyxpyx*)(yF32/66定理7.4.1对于无记忆二元对称信道，最大似然译码准则等价于最小汉明距离准则。证：设信道的输入与输出分别为序列，似然函数为（7.4.3）设的汉明距离为，如果出错，那么与不同，从而使汉明距离增加1。又根据二元对称信道的特性，有其中，所以（7.4.3）式变为],...,[1nxxx],...,[1nyyy1(|)(|)niiipyxpyxyx,d