第5章有噪信道编码5.1基本要求通过本章学习，了解信道编码的目的、译码规则对错误概率的影响，掌握两种典型的译码规则：最佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系、最小汉明距离译码规则、有噪信道编码定理（香农第二定理）的基本思想，了解典型序列的概念、定理的证明方法。掌握线性分组码的生成和校验。学习要点5.25.2.1信道译码函数与平均差错率5.2.1.1信道译码模型从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为F。信道译码模型如图5.1所示。XXY信道译码DMCFA=(a,a2,,a,)A=(a,a2,,a,)B= {br,b2,"",b,)N图5.1信道译码模型5.2.1.2信道译码函数信道译码函数F是从输出符号集合B到输入符号集合A的映射：F(b,)=a,eA, j=l,2,...S其含义是：将接收符号b,EB译为某个输入符号a,EA。译码函数又称译码规则。5.2.1.3平均差错率在信道输出端接收到符号b,时，按译码规则F(b,)=a,eA将b,译为a，，若此时信道输入刚好是a，，则译码正确，否则译码错误。b，的译码正确概率是后验概率：(5.1)P(X =a,[Y = b,)= P(X =F(b,)/Y = b,)= P[F(b,)|b,]b,的译码错误概率：163
163 第 5 章 有噪信道编码 5.1 基本要求 通过本章学习，了解信道编码的目的、译码规则对错误概率的影响，掌握两种典型的译码规则：最 佳译码规则和极大似然译码规则。掌握信息率与平均差错率的关系、最小汉明距离译码规则、有噪信道 编码定理（香农第二定理）的基本思想，了解典型序列的概念、定理的证明方法。掌握线性分组码的生 成和校验。 5.2 学习要点 5.2.1 信道译码函数与平均差错率 5.2.1.1 信道译码模型 从数学角度讲，信道译码是一个变换或函数，称为译码函数，记为 F。信道译码模型如图 5.1 所示。 5.2.1.2 信道译码函数 信道译码函数 F 是从输出符号集合 B 到输入符号集合 A 的映射： * ( ) Fb a A j j ， j 1, 2,.s 其含义是：将接收符号 j b B 译为某个输入符号 * j a A 。译码函数又称译码规则。 5.2.1.3 平均差错率 在信道输出端接收到符号 j b 时，按译码规则 * ( ) Fb a A j j 将 j b 译为 * j a ，若此时信道输入刚好是 * j a ，则译码正确，否则译码错误。 j b 的译码正确概率是后验概率： * ( | ) ( ( )| ) [ ( )| ] PX a Y b PX Fb Y b PFb b j j j j jj （5.1） j b 的译码错误概率： 图 5.1 信道译码模型 X Y DMC 1 2 {, , , } A r aa a 1 2 {, , , } B bb b s 信道译码 F Xˆ 1 2 {, , , } A r aa a N
P(e|b,)= P[X + F(b,)/Y =b,]=1-P[F(b,)|b,](5.2)平均差错率是译码错误概率的统计平均，记为P：P,=Z P(b,)P(elb,)=2 P(b,)(1-P[F(b,)1b,])j=l(5.3)=1-ZP[F(b,),b,]=1-ZP[F(b,)]P[b,|F(b,)]5.2.2两种典型的译码规则两种典型的译码规则是最佳译码规则和极大似然译码规则。5.2.2.1最佳译码规则使P达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的，所以又称最大后验概率译码规则。F(b,)=a,eA,b,B(5.4)H:P(a,[b,)≥P(a,1b,), a, E A将P(a,Ib,)≥P(a,Ib,)两边乘以P(b,)，变换为P(a,b,)≥P(a,b,)。因此，最佳译码规则又可表示成：[F(b,)=a, eA, b, EB(5.5)HP(a,b,)≥P(a,b,), a, E A因为使用最大联合概率条件，所以又称为最大联合概率译码规则，该规则和最大后验概率规则等价。5.2.2.2极大似然译码规则按最大转移概率条件来确定的译码规则，称为极大似然译码规则：F(b,)=a,eA, b,eBF:(5.6)P(b,la,)≥P(b,la),a,EA虽然极大似然译码规则的平均差错率不一定最小，即不一定最佳，但最易找出。可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译码规则也是最佳的。5.2.3信道编码对平均差错率和信息率的影响信道编码（或称纠错编码）是靠增加穴余码元来克服或减轻噪声影响的。穴余是相对于信息的表示而言，但是对提高传送可靠性来说，穴余码元却提供了极宝贵的可靠性信息。以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响。164
164 ( | ) ( )| 1 ( )| Pe b P X Fb Y b P Fb b j j j jj （5.2） 平均差错率是译码错误概率的统计平均，记为 Pe ： 1 1 1 1 ( ) ( | ) ( ) 1 ( )| 1 ( ), 1 ( ) | ( ) s s e j j j jj j j s s jj j j j j j P Pb Pe b Pb P Fb b P Fb b P Fb P b Fb （5.3） 5.2.2 两种典型的译码规则 两种典型的译码规则是最佳译码规则和极大似然译码规则。 5.2.2.1 最佳译码规则 使 Pe 达到最小的译码规则称为最佳译码规则。这种规则是按后验概率最大原则定出的，所以又称最 大后验概率译码规则。 * * () , : ( | ) ( | ), jj j jj ij i Fb a A b B F Pa b Pa b a A （5.4） 将 * ( |) (|) Pa b Pa b jj ij 两边乘以 ( ) P bj ，变换为 * ( , (, ) Pa b Pa b jj ij 。 因此，最佳译码规则又可表示成： * * () , : ( , ) ( , ), jj j jj ij i Fb a A b B F Pa b Pa b a A （5.5） 因为使用最大联合概率条件，所以又称为最大联合概率译码规则，该规则和最大后验概率规则等价。 5.2.2.2 极大似然译码规则 按最大转移概率条件来确定的译码规则，称为极大似然译码规则： * * () , : ( | ) ( | ), jj j j j ji i Fb a A b B F Pb a Pb a a A （5.6） 虽然极大似然译码规则的平均差错率不一定最小，即不一定最佳，但最易找出。 可以证明，当信道输入等概时，极大似然译码规则与最大联合概率译码规则等价，此时极大似然译 码规则也是最佳的。 5.2.3 信道编码对平均差错率和信息率的影响 信道编码（或称纠错编码）是靠增加冗余码元来克服或减轻噪声影响的。冗余是相对于信息的表示 而言，但是对提高传送可靠性来说，冗余码元却提供了极宝贵的可靠性信息。 以下以两种简单信道编码方法来说明信道编码对平均差错率和信息率的影响
5.2.3.1“简单重复”编码日常中人们可以通过重复某句话使别人听得更清楚。数字通信中，将符号重复传几次，也会提高传送可靠性。例如，错误概率为p（p<1/2）的二进制对称信道的“重复2次”编码，如图5.2所示。y3x3X3U信道编码信道译码P'irs了F(ar,as)(B,B2,.)(u,uz)(ar,az,",ag)4=0-α,=000000=Bα,=001001=β2α,=010010=β3α,=011α=000011=β2g=111α,=100100 = β,αg =101101= β6α, =110110 = β,111 u, =1-111=β>αg =图5.2重复2次"编码编码规则为[0→0001→111扩展信道的转移矩阵为β,β4β,β2β,βaβ,β[巴Pp2P'pPp2Pp2p'pPpQ[Prura] =Pp?Pp2P'ppp2p'pD3p'pP3α按极大似然译码规则得译码函数：F(β)=α,F(β,)=α,F(β,)=α,F(β)=αF(β,)=α)F(β)=αsF(β,)=αgF(β,)=αg即165
165 5.2.3.1 “简单重复”编码 日常中人们可以通过重复某句话使别人听得更清楚。数字通信中，将符号重复传几次，也会提高传 送可靠性。例如，错误概率为 p （ p 1/2 ）的二进制对称信道的“重复 2 次”编码，如图 5.2 所示。 编码规则为 0 000 : 1 111 f 扩展信道的转移矩阵为 3 3 12345678 32 2 22 2 23 1 | 3 2 22 22 2 3 8 [ ] Y X p p p p p pp p p pp pp p P p pp pp p p pp p p p p p 按极大似然译码规则得译码函数： 11 21 31 4 8 51 68 78 88 () () () () () () () () FFFF FFFF 即 图 5.2 “重复 2 次”编码 1 1 2 3 4 5 6 7 2 8 0 000 001 010 011 100 101 110 1 111 f f u u 1 2 3 4 5 6 7 8 000 001 010 011 100 101 110 111 F 1 8 000 111 1 8 {, } 信道译码 F 3 Xˆ 3 X 3 Y 3 3 Y X| P 信道编码 f 12 8 {, , , } 12 8 {, , , } U 1 2 {, } u u
β, = 000β4 =011β, = 001β=101α=000>αg=111β, =010β, =110β,=111β, =100信道编码之后的信息率为H(U)R=bit/码元(5.7)N若信源等概率分布，则log MR :bit/码元(5.8)N其中M代表信源消息（符号）个数。log2P, =10-2R=N=1bit/码元无编码11log2,1R=P,=3×10-4N=3bit/码元“重复2次”编码33R=!P, =10-5“重复4次”编码N=5bit/码元51P, = 4x10-7R=“重复6次”编码N=7bit/码元7随着“重复”次数的增加，P下降，但R也跟着下降。即信息传输的有效性和可靠性是矛盾的。5.2.3.2对符号串编码对信源的符号串进行编码，即增多消息个数M，同时增大码长N，有可能使平均差错率P降低到要求的范围以内，同时使信息率R不至于降低太多。例如，取M=4（2次扩展信源）、N=5。4个消息记为S,=00,s,=01,S,=10,S4=11编码函数为i= 1,2,3,4f:s,=m,m,→α,=a,a,a,a,a[a, =m,a,=m,a,=m@m,a,=m,a,=m④m译码采用极大似然规则。编译码示意图见图5.3所示。166
166 1 4 2 6 1 8 3 7 5 8 000 011 001 101 000 111 010 110 100 111 F F 信道编码之后的信息率为 H U( ) R N bit /码元 （5.7） 若信源等概率分布，则 log M R N bit /码元 （5.8） 其中 M 代表信源消息（符号）个数。 无编码 log 2 1 1 1 N R bit /码元 2 10 Pe “重复 2 次”编码 log 2 1 3 3 3 N R bit /码元 4 3 10 Pe “重复 4 次”编码 1 5 5 N R bit /码元 5 10 Pe “重复 6 次”编码 1 7 7 N R bit /码元 7 4 10 Pe 随着“重复”次数的增加， Pe 下降，但 R 也跟着下降。即信息传输的有效性和可靠性是矛盾的。 5.2.3.2 对符号串编码 对信源的符号串进行编码，即增多消息个数 M ，同时增大码长 N ，有可能使平均差错率 Pe 降低到 要求的范围以内，同时使信息率 R 不至于降低太多。 例如，取 M 4 （2 次扩展信源）、 N 5。4 个消息记为 1234 ssss 00, 01, 10, 11 编码函数为 1 2 123 4 5 : 1,2,3,4 i i i i iii i i f s mm aaaa a i 1 1 2 2 31 2 4 1 11 2 i i i i iii i i iii a m a m amm a m amm 译码采用极大似然规则。编译码示意图见图 5.3 所示
0000000001A0001000100000000100010000100010001101101111701111010010000000011015次扩展信道001011110101>01101111000111010→101111011110110La101011001110111001111111111→1101000110101001101011011F11110110001101010010010100101111001图5.3M=4、N=5的编译码示意图编码后的信息率R和平均差错率P分别为R=log4_2bit/码元55P, =1--=(4p+20p*p+8pp)=7.86×10-44与“重复2次”编码相比，R略有增加，P处在同一数量级。因此，增大码长N和适当增多消息个数M，对兼顾P（可靠性）和R（有效性）的要求是有效的。5.2.4最小汉明距离译码规则5.2.4.1汉明距离两个等长符号序列和之间的汉明距离，记为D(，），是与之间对应位置上不同符号的个数，用来定量描述符号序列之间的“相似”程度。5.2.4.2汉明距离与信道编码性能的关系码是码字的集合，码字则是由码元组成的符号序列。假如C=(ci,C2"",C)是等长码，则C中任意两个不同码字之间的汉明距离或码间距离为D(c,c) , c,+cj, C,c,EC码C的最小码间距离定义为167
167 编码后的信息率 R 和平均差错率 Pe 分别为 log 4 2 5 5 R bit /码元 1 5 4 32 4 1 (4 20 8 ) 7.86 10 4 P p pp pp e 与“重复 2 次”编码相比， R 略有增加， Pe 处在同一数量级。因此，增大码长 N 和适当增多消息 个数 M ，对兼顾 Pe （可靠性）和 R （有效性）的要求是有效的。 5.2.4 最小汉明距离译码规则 5.2.4.1 汉明距离 两个等长符号序列 x 和 y 之间的汉明距离，记为 D(, ) x y ，是 x 与 y 之间对应位置上不同符号的个 数，用来定量描述符号序列之间的“相似”程度。 5.2.4.2 汉明距离与信道编码性能的关系 码是码字的集合，码字则是由码元组成的符号序列。假如 1 2 {, , , } C cc c q 是等长码，则C 中任 意两个不同码字之间的汉明距离或码间距离为 (, ) , , , D ij i j ij cc c c cc C 码C 的最小码间距离定义为 图 5.3 M 4 、 N 5 的编译码示意图 00 00000 01 01101 10 10111 11 11010 f f f f 00000 00001 00010 00100 01000 10000 10001 00011 01101 01100 01111 01001 00101 11101 11100 01110 10111 10110 10101 10011 11111 00111 00110 10100 11010 11011 11000 11110 10010 01010 01011 11001 F F F F 00000 01101 10111 11010 5 次扩展信道