第6章 有噪信道编码定理12

第6章有噪信道编码定理在无噪无损信道上，只要对信源的输出进行适当的编码，总能以最大信息传输率C（信道容量）无差错地传输信息。但一般信道中总存在噪声或干扰，信息传输会造成损失，那么在有噪信道中怎么能使消息通过传输后发生的错误最少？在有噪信道中无错误传输的可达的最大信息传输率是什么？这就是本章所要研究的内容，即研究通信的可靠性问题。这时香农在1948年的文章中提出并证明了的信道编码定理，也称香农第二定理。6.1错误概率和译码规则在有噪信道中传输消息时会发生错误的。为了减少错误，提高可靠性，首先就要分析错误概率与哪些因素有关，有没有办法加以控制，能控制到什么程度等问题。错误概率与信道统计特性有关。信道的统计特性可由信道的传递矩阵来描述。当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确传递概率，哪些是错误传递概率。但通信过程一般并不是在信道输出端就结束了，还要经过译码过程（或判决过程）才到达消息的终端（收信者）。因此译码过程和译码规则对系统的错误概率影响很大。错误概率既与信道的统计特性有关，也与译码的规则有关。定义译码规则：设离散单符号信道的输入符号集为A={ai}，i=1,2,…,r；输出符号集为B={bj}，j=1,2,…,s。制定译码规则就是设计一个函数F(bj)，它对于每一个输出符号bj确定一个唯一的输入符号ai与其对应（单值函数）。即F(bj)=ai（i=1,2,…,r）（j=1,2,…,s）译码规则的选择应该根据什么准则？一个很自然的准则当然就是要使平均错误概率为最小。为了选择译码规则，首先必须计算平均错误概率。平均错误概率PE表示经过译码后平均接收到一个符号所产生的错误大小。应是条件错误概率P(e|bj)对Y空间取平均值，e表示除了F(bj)=ai以外的所有输入符号的集合。PE=E[p(e|bj)]=收到符号bj条件下译码的正确概率为P[F(bj)|bj)]=P(ai|bj)P(e|bj)=1-P(ai|bj)=1-P[F(bj)|bj)]s1jjjbepbp如何设计译码规则F(bj)=ai，使PE最小PE=E[p(e|bj)]=由于上式PE的表达式中右边是非负项之和，可以选择译码规则使每一项为最小，即得PE最小。因为p(bj)与译码规则无关，所以只要设计译码规则F(bj)=ai，使条件错误概率P(e|bj)为最小。s1jjjbepbp最大后验概率准则如果采用一种译码函数，对于每一个输出符号均已成具有最大后验概率的那个输入符号，则信道错误概率就能最小。P(e|bj)最小，就是P[F(bj)|bj)]为最大，即选择译码函数：F(bj)=a*，a*∈A，bj∈B并使之满足条件P(a*|bj)≧P(ai|bj)，ai∈Aai≠a*这种译码规则称为“最大后验概率准则”或“最小错误概率准则”。最大后验概率准则利用贝叶斯定律就可以表示为选择译码函数F(bj)=a*，a*∈A，bj∈B，使满足P(bj|a*)p(a*)≧P(bj|ai)p(ai)，ai∈Aai≠a*jiijjjbPaPabPbPaPabP最大似然译码准则若最大后验概率准则中输入符号的先验概率p(ai)均相等，则上式(6.7)可写成选择译码函数F(bj)=a*，a*∈A，bj∈B，并满足P(bj|a*)≧P(bj|ai)，ai∈Aai≠a*这样定义的译码规则称为最大似然译码准则。在输入符号等概率时，这两个译码准则是等价的。根据最大似然译码准则可以直接从信道矩阵的传递概率中去选定译码函数。就是说，收到bj后，译成信道矩阵P的第j列中最大那个元素所对应的信源符号。最大似然译码准则本身不再依赖于先验概率p(ai)。但是当先验概率为等概率分布时，它使错误概率PE最小（如果先验概率不相等或不知道时，仍可以采用这个准则，但不一定能使PE最小）。平均错误概率PE根据译码准则，可以进一步推得平均错误概率PE=平均正确概率为经过简化YaX,Yjij*Y,XjijYj*bapbapbapbepbpYj*YjjEE_bapbbFpp1p*aX,YiijEapabppieXiY*jijXiijXbaYiEpapabFabpapabpappj*对应的平均错误概率PE令，就是某个输入符号ai传输所引起的错误概率。如果先验概率均相等，p(ai)=1/r，则得Y*jijieabFabppiepXieaX,YijEpr1abpr1p*在等先验概率分布情况下，译码错误概率可用信道矩阵中的元素P(bj|ai)求和表示。式(6.15)求和是除去每列对应于F(bj)=a*的那一项后，先对列求和，然后求各列之和。而式(6.16)是先对行求和，然后求各行之和。采用最小错误概率准则*,*,,11aXYjiYjYXjiYjjYXjiYjjjYjjjYjEbaPbaPbaPbbFPbaPbbFPbPbbFPbePbPP例题已知信道矩阵译码函数B译码函数A4.03.03.05.03.02.02.03.05.0P233211abFabFabF332211abFabFabF例题2.015.015.0125.0075.005.005.0075.0125.0jibaP333231abFabFabFjijbaPbaP译码函数CjjijjbPbaPbaPbP例题6.2可知输入不是等概率分布时最大似然译码准则的平均错误概率不是最小。费诺不等式平均错误概率PE与译码规则（译码函数）有关。而译码规则又由信道特性来决定。由于信道中存在噪声，导致输出端发生错误，并使接收到输出符号后，对发送的是什么符号还存在不确定性。可见，PE与信道疑义度H(X│Y)是有一定关系的，因此可得H(X│Y)≤H(PE)+PElog(r-1)虽然PE与译码规则有关，但是不管采用什么译码规则该不等式都是成立的。H(PE)是错误概率PE的熵，表示产生错误概率PE的不确定性。费诺不等式（说明）接收到Y后关于X的平均不确定性可分为两部分，第一部分是指接收到Y后是否产生PE错误的不确定性H(PE)。第二部分表示当错误PE发生后，到底是哪个输入符号发送而造成错误的最大不确定性，为PElog(r-1)（其中r是输入符号集的个数）。若以H(X│Y)为纵坐标，PE为横坐标，函数H(PE)+PElog(r-1)随PE变化的曲线如图6.2。从图中可知当信源、信道给定，信道疑义度H(X│Y)就给定了译码错误概率的下限。6.2错误概率与编码方法消息通过有噪信道传输时会发生错误，而错误概率与译码规则有关。但当一般信道给定即信道矩阵给定，不论采用什么译码规则，PE总不会等于或趋于零（除特殊信道外）。一般要求系统的错误概率在的10-6～10-9范围内，有的甚至要求更低的错误概率。例题一个二元对称信道选用最佳译码规则99.001.001.099.011002211abFabF输入等概率21001.0EP实际经验说明：只要在发送端把消息重复发几遍，也就是增加消息的传输时间，就可使接收端接收消息使错误减小，从而提高了通信的可靠性。这是一种最简单的重复编码，这种信道可以看作是N次无记忆扩展信道。简单重复编码方法可以纠正一位码元的错误，译错的可能性变小了，因此错误概率降低。也可以采用“择多译码”的译码规则，即根据输出端接收序列中0多还是1多。如果有二个以上是0，则译码器就判决为0，如果有两个以上是1则判决为1。例题重复编码将长度n=1的两个二元序列变成长度n=3的二元序列，信道输入端有两个码字000和111。输出端，由于信道干扰，可能发生错误，8个可能的输出。这样的信道看成三次无记忆扩展信道。其输入是在8个可能出现长度为3的二元序列中选取两个作为消息（许用码字）续信道矩阵为33222222222222338765432121ppppppppppppppppppppppppppppP8887861584131211FFFFFFFF最大似然译码准则平均错误概率)01.0(10332114233222222333ppppppppppppppppppPMPaPPaCYijaCYijiE)01.0(1033ppCpC234232-23333ppppPE个码元的概率错个码元的概率错择多译码准则8887861584131211FFFFFFFF发现10875105111091047105EEEEPnPnPnPn当n（重复次数）很大时，PE很小是可能的。但是一个新问题出现了，n很大时，信息传输率就会降低。信息传输率编码后信道的信息传输率（也称码率）表示为（比特/码符号）若传输每个码符号平均需要t秒钟，则编码后单位时间传输的信息量（比特/秒）此时，M是输入消息（许用码字）的个数。logM表示消息集在等概率条件下每个消息（码字）携带的平均信息量（比特）。N是编码后码字的长度（码元的个数）。nlogMRntlogMRt运用重复编码方法可计算得出PE和R的关系。表明：尽管可使PE降低很多，但同时也使传输率降得很低。11111121151512531312311log1ttttRRMnRRMnRRMnRnMRn思考N增大，PE降低，R降低能不能有好办法？从理论上，根据香农第二定理，就是有噪信道编码定理可知，能找到一种更好的编码方法，使得PE相当低，而R却保持在一定水平。例题通过例子可以看出错误概率与编码方法有很大关系。采用增大n，并适当增大M和合适的编码方法，既能使PE降低，又能使信息传输率不减少。0111011100000010101000002102EP21028.2EP为什么为什么上述编码的平均错误概率不同呢？引入码字距离码字距离长度为n的两个符号序列（码字）αi和βj之间的距离是指αi和βj之间对应位置上不同码元的个数，用符号D(αi,βj)表示。这种码字距离通常称为汉明距离。一般在信道编码中码字常用C=(cn-1cn-2…c0)表示。对于二元信道，即对于二元码，汉明距离可表达成下述关系式：若令∈{0,1}∈{0,1}则Ci和Cj的汉明距离为D(Ci,Cj)=（式中为模二和运算）0n2n1niiiiiccccCkic0n2n1njjjjjccccCkjcn1kjikkcc最小距离在某一码C中，任意两个码字的汉明距离的最小值称为该码C的最小距离，即dmin=min{D(Ci,Cj)}Ci≠CjCi,Cj∈C在任一码C中，码的最小距离dmin与该码的译码错误概率有关。上述距离定义是适合任意多元信道和多元码的，但一般常用的是二元离散对称信道和二元码。表6.1码A码B码C码D码E码字000111000，011101，110000,001100,01000000011011011111010000,001,010011,100,101110,111消息数M24448码的最小距离dmin32131信息传输率R