武汉理工信息理论与编码chapter5

1第5章有噪信道编码——差错控制编码2问题的提出愿望：信息传输多快好省。现实：（1）速度：受信道容量的限制，不可能无限大；（第3章）（2）质量：受信道噪声的干扰，传输错误不可避免。衡量信息传输可靠性的指标：平均差错率Pe。Pe与信道的统计特性有关，不可能为零，有时甚至很大。降低Pe的方法：先对消息进行编码再送入信道传送，这种为降低平均差错率而进行的编码称为信道编码；在信道输出端加信道译码器进行信息还原。香农第二编码定理所给出的结论：只要信道编码和译码的方法得当，就可使平均差错率趋于零。编码信道XN信道编码器fUˆUY信道信道译码器F3各节内容5.1译码规则与错误概率5.2两种典型的译码规则5.3平均差错率与信道编码5.4汉明距离5.5有噪信道编码定理与逆定理5.6线性分组码45.1译码规则与错误概率信道编码是一个一一对应的变换或函数，称为编码函数f；信道译码也是一个函数，称为译码函数F。编码信道XN信道编码器fUˆUY信道信道译码器F由于f是一一对应变换，其反变换f-1唯一确定。因此，讨论译码函数F时，只考虑从Y中还原出X就可以了。XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaN51、译码规则译码规则是由人为制订的；对于同一个信道可制订出多种译码规则；“好”的译码规则：平均差错率小。XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaN信道译码函数F，又称译码规则，是从信道输出符号集合B到信道输入符号集合A的映射：12*:(),,,...,jjFBAFbaAjs62、错误概率平均差错率Pe与译码规则F有关。XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaN*(),1,2,...,jjFbaAjs译码规则：bj的译码正确概率是后验概率：jjjjPXaYbPFbb*(|)()|bj的译码错误概率：1jjjjjPPXFbYbPFbebb(|()|())|平均差错率Pe:ssejjjjjjjPPbPbPFbPebb11()()1((|))|7平均差错率Pe的计算公式XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaNjjFbaAjs*(),1,2,...,译码规则：平均差错率Pe:ssejjjjjjjPPbPbPFbPebb11()()1((|))|ssejjjjjjjPPFbbPFbPbFb111(),1()|()eijijiYXaYXaPPabPaPba**,,(,)()(|)当输入等概时：sejjjijYXaPPbFbPbarr*1,111|()(|)换一种表达式：或者8例：译码规则与平均差错率0.80.90.20.12b1b1a2a3113322():()FbaFFba1()0.4Pa(1)找出所有可能的译码规则；(2)求出各个译码规则对应的平均差错率。1111121():()FbaFFba4124421():()FbaFFba2122222():()FbaFFba4种译码规则：XP[]0.40.6YXbbaaP2|1120.80.2[]0.10.9XYPaabb21120.320.08[]0.060.541111121()1(),1(,)(,)1(0.320.08)0.6sejjjPFPFbbPabPab2221221()1(),1(,)(,)1(0.060.54)0.4sejjjPFPFbbPabPab33112210.()1(),1(,)(,)1(0.320.514)4sejjjPFPFbbPabPab44211210.()1(),1(,)(,)1(0.080.086)6sejjjPFPFbbPabPabF3最好F4最差95.2两种典型的译码规则两种典型的译码规则：最佳译码规则、极大似然译码规则1、最佳译码规则：平均差错率最小的译码规则。XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaN1()1()|sejjjjPPbPFbb**(|)()|)(,:,jjjjiijjPabPaFbaAbBFaAb*(,(,)jjijPabPab*(|))((|)()jjijjjPbPPbPabab**(,(,))(,:,jjijjjjiPabPaFbaAbBFabA按“后验概率最大”原则定出，又称最大后验概率译码规则按“联合概率最大”原则定出，又称最大联合概率译码规则10例：求最佳译码规则0.80.90.20.12b1b1a2a1()0.4Pa求出最佳译码规则及平均差错率。[]0.40.6XP1122|0.80.2[]0.10.9YXaPbba12120.08[]00.320.54.06XYbbaaP3113322():()FbaFFba1111121():()FbaFFba4124421():()FbaFFba2122222():()FbaFFba已知的结论：1()0.6ePF2()0.4ePF3()0.14ePF4()0.86ePF1212|0.1290[]0.15790.84210.8710XYbPbaa[]0.380.62YP1122():()FbaFFba1122():()FbaFFba33111220.()1(),1(,)(,)1(0.320.514)4sejjjPFPFbbPabPab112、极大似然译码规则XYDMC12{,,,}rAaaa12{,,,}sBbbb信道译码FˆX12{,,,}rAaaaN按“转移概率最大”原则定出，称为极大似然译码规则。实际应用中，经常只知道信道的统计特性(转移概率)，而不知道信源的统计特性(输入概率)，这时求不出联合概率和后验概率，因此无法确定最佳译码规则。既然只知道转移概率，就只能按转移概率的某种约束条件制订译码规则。按最大转移概率条件来确定的译码规则，称为极大似然译码规则。**(),:(|)(|),jjjjjjiiFbaAbBFPbaPbaaA12例：极大似然译码规则已知信道转移矩阵，确定译码规则。|0.50.30.2[]0.20.30.50.30.30.4YXP只已知转移概率，无法找出最佳译码规则，只能采用极大似然译码规则。将转移矩阵各列最大的转移概率标出，重写转移矩阵如下：1231|230.50.300.2[]0.20.30.30.30.4.5YXbbbaPaa11212332():()(or,)()FbaFFbaaaFba按“转移概率最大”原则确定极大似然译码规则：注：无法求出平均差错率。13极大似然译码规则与最佳译码规则等价的条件**(|)(|)(),:,jjjjjjiiPbaPbFbaAbaAaBF**(,(,))(,:,jjijjjjiPabPaFbaAbBFabA极大似然译码规则最佳译码规则结论：信道输入等概时，极大似然译码规则与最佳译码规则等价*(|)(|)jjjiPbaPba*(,(,)jjijPabPab证明：输入等概*()()jiPaPa**(|)()((|))jjjiijPaPaPbaPba（1）信道输入是近似等概的：因为信道前级有信源编码器存在。（2）极大似然译码规则近似最佳，可以放心使用。注145.3平均差错率与信道编码Pe与译码规则有关，即使选择最佳译码规则，也只能使Pe有限地减小，难以满足信息传递系统的高可靠性要求。要进一步降低Pe，必须在传送之前进行信道编码。0.99p0.99p0.01p0.01p10a21a10b21bXYDMC12{,}aa12{,}bbUDMS12{,}uu11010.50.5UUuuP二元信源的消息个数：M=2熵：H(U)=logM=1bit/符号由于信道输入等概，这时极大似然译码规则是最佳的。12120.990.01[]0.010.99XYbbaPa1122():()FbaFFba21111|()1(0.990.99)102sejjjPPbFbr无信道编码时：例：151、“简单重复”编码信道译码F3ˆX3X3Y信道编码f128{,,,}128{,,,}U12{,}uu12{,}uu33|YXP112345672800000010100111001011101111ffuu12354678000001010100011101110111331234567832222223132222223|8[]YXppppppppppppppPpppppppppppppp1121314851687888()()()()()()()()FFFFFFFF83222222341111|()1()3102elllPPFppppppppppppppr18000111FF信道编码之后的信息率：()loglog2133HUMRNNbit/符号16信道编码前后比较无编码N=1Pe=10-2bit/符号loglog211MRN“重复2次”编码N=3Pe=3×10-4bit/符号loglog2133MRN结论：随着“重复”次数的增加，Pe下降，R也跟着下降。“重复”编码的其它结果N=5,Pe=10-5,N=7,Pe=4×10-7,N=9,Pe=10-9,15Rbit/符号19Rbit/符号bit/符号17R172、对符号串编码信道译码F3ˆX3X3Y信道编码f128{,,,}128{,,,}2U{00,01,10,11}12{,}uu33|YXP1111111212342156227800000001010100111010010111110111ffffuuuuuuuu123456780000010100111001011101111000F331234567832222223122322322322233222|5232222327[]YXppppppppppppppppppppppppppppPpppppppppppppppppppppppppppp1121334355657787()()()()()()()()FFFFFFFF8132211|()11(44)1.99104elllPPFMppp3010F5100F7110Floglog4233MRNbit/符号结论：增多消息个数M会提高R，但会使Pe增大