(信息论)第6章有噪信道编码

第6章有噪信道编码6.1噪声信道的编码问题信道译码器编码器信源编码器信源译码器MXYMˆ编码信道M+多余码元码序列C(码序列中的信息序列的码元与多余码元之间具有相关性)译码端根据编码规则中的相关性检测和纠正传输过程中的差错6.1.1错误概率和译码规则01XY011.0p9.0ppp二元对称信道错误概率不仅与信道的统计特征有关，而且也与译码规则有关。如上例011110009.0Ep1.0Ep6.1.2译码规则定义6.1.1设信道输入符号集为，输出符号集为，若对每一个输出符号都有一个确定的函数，使对应唯一的一个输入符号，则称这样的函数为译码规则，记为rix,,2,1,1Xsjyj,,2,1,YjyjyFjyixsjrixyFij,,2,1;,,2,1显然，对于有r个输入、s个输出的信道而言，按上述定义得到的译码规则共有种。(6.1)sr1、错误概率在译码规则的情况下，得出条件正确概率和条件错误概率分别为sjrixyFij,,2,1;,,2,1,jjjijjijjyyFpyxpyepyxpyyFp|1|1|||因为译码过程有统计平均作用，经过译码后的平均错误概率为上式的含义是经过译码后，平均接收到一个符号所产生错误的大小。jsjjjEyepypyepEp||1Ep(6.2)(6.3)2、译码规则选择译码规则总的原则应是使平均错误概率最小。由于错误概率为非负项之和，欲使最小，那么应使每一项为最小，又由于式(6.3)中与译码规则无关，故欲使最小，从式(6.2)看出，亦即为使为最大，于是引出最大后验概率准则。定义6.1.2选择译码函数，使之满足条件则称为最大后验概率译码规则(理想观测者规则)。该规则的意义是选择这样一种译码函数，对于每一个输出符号均译成具有最大后验概率的那个输入符号，则信道译码错误概率会最小。一般说来，后验概率是难以实现的，所以应用起来并不方便。iyxpyxpjij对||EpEpEpjypjjyyFp|xyFjEpsjyj,,2,1,x(6.4)定义6.1.3选择译码函数，使之满足条件则称为极大似然译码规则。当输入符号为等概分布时则式(6.5)可改写成当信道输入符号为等概分布时，应用极大似然译码规则是很方便的，式(6.7)中的条件概率为信道矩阵中的元素。从最大后验概率译码规则可以导出极大似然译码规则。xyFjixpxypxpxypiijj对||rixpxpi,,2,1ixypxypijj对||(6.7)(6.6)(6.5)3、平均错误概率平均错误概率的推导过程：xXYYYXYYXYjjYXjiYjjjYjjYjjYjjjsjjEyxpyxpyxpyyFpyxpyyFpyxpyyFpypyyFpypypyyFpyepypp,1,,,1||1|(6.8)平均正确概率为若用条件概率表示，式(6.8)又可表示为若输入为等概分布，则式(6.11)意味着，在输入为等概分布的条件下，译码错误概率可用信源矩阵中的元素来表示。这种求和是除去信道矩阵中每列中对应于的那一项后，求矩阵中其余元素之和。YYEEyxpyyFppp,1xpxyppxXYE,|xXYExyprp,|1EpxyFj(6.9)(6.10)(6.11)例：已知信道矩阵设计如下两种译码规则：216131312161613121P233211332211::xyFxyFxyFBxyFxyFxyFA当输入为等概分布时，译码规则A就是极大似然译码规则。两种译码规则所对应的平均错误概率分别为32612316465213121612131316131|31212133131616131316131|31,,xXYExXYExypBpxypAp引理6.1.1错误概率与信道疑义度满足以下关系该不等式称为费诺不等式。EpYXH|1log|rppHYXHEE(6.12)上式的意义是：当作了一次译码判决后所保留的关于信源的不确定性可以分成两部分：第一部分是接收到Y后，判决是否发生错误的不确定性；第二部分是当判决是错误的，其错误概率为，确定由r-1个输入符号中哪一个引起错误的不确定性，它是(r-1)个符号不确定性的最大值与的乘积。EEppH1,Ep1logrEp的许用区域和YXHPE|1logrPPHEErlog1logrEPYXH|rr1Fano不等式的几何意义6.2错误概率与编码方法6.2.1简单重复编码01a02a01b02b01.0p99.0ppp二元对称信道信道矩阵为99.001.001.099.0P选择最佳译码规则为2211xyFxyF在输入分布为等概分布的条件下，总的平均错误概率为2,1001.001.021|1xyprpxXYE简单重复编码就是规定当信源符号为“0”(或“1”)时，则重复发送若干个“0”(或“1”)。这样规则构成的信道实际上就是二元对称信道的三次扩展信道。输入符号和输出符号的关系为：3BSC8877665544332211111111110110101101100100011011010101001001000000没有使用的码字发送端用作消息的码字输出端接收序列二元对称信道的三次扩展信道简单重复编码图则这时的信道矩阵为3222222332222223ppppppppppppppppppppppppppppP设输入符号为等概分布，采用极大似然译码规则，即取信道矩阵中每列数值最大的元素所对应的为，所以译码函数为i8884871386121511FFFFFFFF在输入为等概条件下，相应的平均错误概率为42332222223,,103321|1|ppppppppppppppppppMpppijxXYiijxXYE该方法采用的是“择多译码”的译码规则。得到的平均错误与最大似然译码规则是一致的。采用简单重复编码方法，如果进一步增大重复次数n，则会继续降低平均错误概率，Ep10875105111091047105EEEEpnpnpnpn虽然随着提高重复编码次数n，平均错误概率得到下降，但同时信息传输率也在减小，也就是说简单重复编码减少平均错误概率是以降低信息传输率为代价的。这是由于Ep符号比特/lognMLSHR秒比特秒比特秒比特秒比特/111112loglog,211/5152loglog,25/3132loglog,23/12loglog,21nMRMnnMRMnnMRMnnMRMn(无重复编码)6.2.2消息符号数Miiaaaaan221Miin221二元信道n次扩展发送端(发送消息)接收端(接收消息)n次扩展信道的消息符号在一个二元信道的n次无记忆扩展信道中，输入端共有个符号序列可能作为消息符号，仅选其中M个作为消息符号传递。则当M选取大些，也跟着增大，R也大；M选取小些，就降低些，而R也要降低。n2EpEp6.2.3(5.2)线性码(5.2)线性码，在适当增大n和M的情况下，得到比较低的平均错误概率和较好的信息传输率R。设取M=4,n=5，这时信息传输率码符号比特/5254loglog22nMR而输入符号的4(M=4)个码字采用下列编码方法4,3,2,154321iiiiiii其中，为中第k个分量，，且码字中个分量满足方程kii5,4,3,2,1ki(6.13)215142132211iiiiiiiiiiii000101011模二和运算(6.14)式可写成如下的形式0001100001000110001000001i(6.14)(6.15)采用上述编码方法则得到如下一种(5.2)线性码。0001110001100000100000000001000000000010000010000001110111001110100101011010100101101011110110001101输入端发送序列输出端接收序列译码规则扩展信道1010000110001111111110111100111011110101101101011111001010110101010010110101111011010110001101111010输入端发送序列输出端接收序列译码规则扩展信道续仍采用极大似然译码规则，可计算得正确译码概率为而平均错误译码概率为234525ppppppE)01.0(108.7825114232345ppppppppppEE当从该编码方法上看，与从二元信道经过n次扩展的得到的消息符号数中取同样的M个符号传递相比，虽然信息传输率R略有降低，但平均错误概率都要好得多。6.2.4汉明距离定义6.2.1设为两个n长的二元码字，则码字X和Y之间的汉明距离定义为knikyxYXD1,nnyyyYxxxX,,,,,,,2121其中，表示模二和运算上式的含义是两个码字之间的汉明距离就是它们在相同位上不同码符号的数目的总和。(6.16)汉明距离的性质非负性当且仅当X=Y时等号成立。0,YXD对称性XYDYXD,,三角不等式YXDZYDZXD,,,③①②定义6.2.2在二元码C中，任意两个码字的汉明距离的最小值，称为码C的最小距离，即CCCCCCCDDjijiji,,minmin(6.17)最小码间距离越大，则平均错误概率越小。在输入消息符号个数M相同的情况下，同样地越大，越小。概括地讲，码组中最小距离越大，受干扰后，越不容易把一个码字错误译成另一个码字，因而平均错误概率小。如果最小码间距离小，受干扰后很容易把一个码字错译成另一个码字，因而平均错误概率大。这意味着，在选择编码规则时，应使码字之间的距离越大越好。minDEpEpminDEpminD汉明距离对极大似然译码规则的表示极大似然译码规则为式中——信道输入端作为消息的码字，码长为n；——信道输出端接收到的可能有的码字，码长亦为n;——似然函数。ixypxyFxyFijjj对||ixjyijxyp|设码字与的距离为D，则表示在传输过程中有D的位置发生错误，n-D个位置没有发生错误。即ixjy(6.18)sjyyyyrixxxxnnjjjjiiii,,2,1,,2,12121当信道无记忆时，有从式(6.19)看出，当时，D越大，则越小；D越小，则越大。因此，极大似然译码规则式(6.18)就变成了这样一个含义：当接收到码字后，在输入码字集中寻找一个，使之与的汉明距离为最短，即选取译码函数使之满足DnDijijijijppxypxypxypxypnn||