信息论课件信道编码

1、第六章第六章 信道编码信道编码6.1 译码规则与错误概率译码规则与错误概率6.2 典型的译码规则典型的译码规则6.3 平均差错率与信道编码平均差错率与信道编码引言引言 信道编码的目的是改善通信系统的传输质量。由于实信道编码的目的是改善通信系统的传输质量。由于实际信道存在噪声干扰，使发送的码字与信道传输后接收的际信道存在噪声干扰，使发送的码字与信道传输后接收的码字之间存在差异，这种差异称为差错。一般情况下，信码字之间存在差异，这种差异称为差错。一般情况下，信道噪声干扰越大，码字产生差错的概率也就越大。在无记道噪声干扰越大，码字产生差错的概率也就越大。在无记忆信道中，噪声独立随机地影响每个传输码元

2、，因此接收忆信道中，噪声独立随机地影响每个传输码元，因此接收的码元序列中的错误是独立随机出现的。太空信道、卫星的码元序列中的错误是独立随机出现的。太空信道、卫星信道、同轴电缆、光缆信道以及大多数视距微波接力信道信道、同轴电缆、光缆信道以及大多数视距微波接力信道均属于这一类型信道。均属于这一类型信道。引言引言 在有记忆信道中，噪声干扰的影响往往是前后相关的，在有记忆信道中，噪声干扰的影响往往是前后相关的，错误会成串出现。通常称这类信道为突发差错信道。典型的错误会成串出现。通常称这类信道为突发差错信道。典型的有短波信道、移动通信信道、散射信道以及受大的脉冲干扰有短波信道、移动通信信道、散射信道以及

3、受大的脉冲干扰和串话影响的明线和电缆信道，甚至还包括在磁记录中，划和串话影响的明线和电缆信道，甚至还包括在磁记录中，划痕、涂层缺损将造成成串的差错。有些实际信道既有独立随痕、涂层缺损将造成成串的差错。有些实际信道既有独立随机差错也有突发性成串差错，称它为混合信道。机差错也有突发性成串差错，称它为混合信道。 为降低平均差错率，可先对消息进行编码再送入信道传为降低平均差错率，可先对消息进行编码再送入信道传送，这种为降低平均差错率进行的编码称为信道编码。送，这种为降低平均差错率进行的编码称为信道编码。引言引言 其基本思想是根据一定的规律在待发送的信息码中加入其基本思想是根据一定的规律在待发送的信息码

4、中加入一些多余的码元，以保证传输过程的可靠性。信道编码的任一些多余的码元，以保证传输过程的可靠性。信道编码的任务就是构造出以最小多余度代价换取最大抗干扰性能的务就是构造出以最小多余度代价换取最大抗干扰性能的“好好码码”。总之，信道编码和译码就是为了消除噪声的影响，提。总之，信道编码和译码就是为了消除噪声的影响，提高传送可靠性。高传送可靠性。6.1 译码规则与错误概率译码规则与错误概率信信道道信道编码译码示意图信道编码译码示意图UXYU 译码规则译码规则 信道编码实际上就是一个一一变换信道编码实际上就是一个一一变换f f，信道译，信道译码就是一个反变换码就是一个反变换F F = =f f -1-

5、1，也称为译码函数，也称为译码函数( (译码译码规则规则) )。6.1 译码规则与错误概率译码规则与错误概率定义：信道译码函数定义：信道译码函数F是从信道输出符号集是从信道输出符号集B到信道到信道输入符号集输入符号集A的映射：的映射： F(bj)=ai A ( i =1, 2, r, j =1, 2, s )即将接收符号即将接收符号bj译为某个输入符号译为某个输入符号ai。YB=b1,b2,bs信道译码信道译码Fa1a2 arX 信道译码器模型信道译码器模型X信道信道a1a2 arAA6.1 译码规则与错误概率译码规则与错误概率同一个信道，可有多种译码规则。同一个信道，可有多种译码规则。译码规

6、则：译码规则：raaabF211)( rsaaabF21)( 共有共有r s种译码规则。种译码规则。raaabF212)( 6.1 译码规则与错误概率译码规则与错误概率 0)1(0)0(:111FFF 1)1(0)0(:222FFF 0)1(1)0(:333FFF 1)1(1)0(:444FFF422 sr译码规则共译码规则共4种种01011- -pp1- -pp例例5.1 5.1 对二进制对称信道对二进制对称信道6.1 译码规则与错误概率译码规则与错误概率 在所有的译码规则中，选择一个能使平均差错率最小的作在所有的译码规则中，选择一个能使平均差错率最小的作为译码规则。为译码规则。2. 2.平

7、均错误译码概率平均错误译码概率ijabF )(输入输入 ai译码正确译码正确输入为除输入为除ai以外的符号以外的符号译码错误译码错误译码正确的概率：译码正确的概率： p(ai | bj)=p F(bj) | bj 6.1 译码规则与错误概率译码规则与错误概率译码错误的概率：译码错误的概率： p( e | bj)= p(X F(bj)| bj)=1- - p(F(bj)| bj)平均译码正确概率：平均译码正确概率： sjjjjrbbFpbpP1)| )()(平均译码错误概率平均译码错误概率(平均差错率平均差错率)：) )| )(1)()|()(11sjjjjsjjjebbFpbpbepbpP6.

8、1 译码规则与错误概率译码规则与错误概率) )(|()( 1 ),( 1 )| )()(1 ) )| )(1)(1111 sjjjjsjjjsjjjjsjjjjebFbpbFpbbFpbbFpbpbbFpbpP当输入是等概率时：当输入是等概率时： pF(bj)= p(ai)=1/r，则，则6.1 译码规则与错误概率译码规则与错误概率) )(|(11 ) )(|()( 111 sjjjsjjjjebFbprbFbpbFpP例例5.2 5.2 对二进制对称信道对二进制对称信道01010.90.90.10.1若若P(0)=0.4，求四种译码规则所对应的平均差错率。，求四种译码规则所对应的平均差错率。

9、6.1 译码规则与错误概率译码规则与错误概率解：信道输入概率矩阵和信道转移概率矩阵为：解：信道输入概率矩阵和信道转移概率矩阵为： 9 . 01 . 01 . 09 . 0 6 . 0 , 4 . 0|XYXPP联合概率矩阵：联合概率矩阵： 54. 006. 004. 036. 0 XYP对于编码规则对于编码规则F1： 0)1(0)0(:111FFF6.1 译码规则与错误概率译码规则与错误概率6 . 0)04. 036. 0(1)1 , 0()0 , 0(1 )1),1()0),0(1),(1)(211 ppFpFpbbFpFPjjje 1)1(0)0(:222FFF对于编码规则对于编码规则F2

10、：1 . 0)54. 036. 0(1)1 , 1()0 , 0(1 )1),1()0),0(1),(1)(212 ppFpFpbbFpFPjjje6.1 译码规则与错误概率译码规则与错误概率 0)1(1)0(:333FFF对于编码规则对于编码规则F3： 1)1(1)0(:444FFF对于编码规则对于编码规则F4：9 . 0)04. 006. 0(1)1 , 0()0 , 1(1 )1),1()0),0(1),(1)(213 ppFpFpbbFpFPjjje6.1 译码规则与错误概率译码规则与错误概率4 . 0)54. 006. 0(1)1 , 1()0 , 1(1 )1),1()0),0(1

11、),(1)(214 ppFpFpbbFpFPjjje显然，译码规则显然，译码规则F2最好，最好， F3最差。最差。 采用穷举法可以构造给定信道的所有译码规则，从采用穷举法可以构造给定信道的所有译码规则，从中可通过计算平均差错率求出平均差错率最小的译码中可通过计算平均差错率求出平均差错率最小的译码规则，这就是最好的译码规则，但这样的工作量很大，规则，这就是最好的译码规则，但这样的工作量很大，下面介绍求好的译码规则的简单方法。下面介绍求好的译码规则的简单方法。6.2 典型的译码规则典型的译码规则最佳译码规则：使平均差错率最佳译码规则：使平均差错率Pe达到最小的译码规则称为最达到最小的译码规则称为最

12、佳译码规则。由平均差错率定义佳译码规则。由平均差错率定义) )| )(1)()|()(11sjjjjsjjjebbFpbpbepbpP可知，要是可知，要是Pe达到最小，应使每个达到最小，应使每个p(e|bj)都最小，或使都最小，或使 p(F(bj)| bj )( j=1,2,s )达到最大，即在后验概率集中达到最大，即在后验概率集中 p(a1|bj) , p(a2|bj) , , p(ar|bj) 选取一个最大值，它所对应的输入符号选取一个最大值，它所对应的输入符号a*就作为就作为bj的译码结果，的译码结果，即即F(bj)= a*。6.2 典型的译码规则典型的译码规则即最佳译码规则为：即最佳译

13、码规则为： )|()|( )(:* AabapbapB bAabFFijijjj),(),( )|()()|()( )|()|( *jijjijjjjijbapbapbapbpbapbpbapbap 由于由于也称最大后验概率译码规则。也称最大后验概率译码规则。6.2 典型的译码规则典型的译码规则也称最大联合概率译码规则。也称最大联合概率译码规则。故最佳译码也可写成：故最佳译码也可写成： ),(),( )(:* AabapbapB bAabFFijijjj6.2 典型的译码规则典型的译码规则 YaXijiYaXjisjjsjrijisjjjsjjsjjjeabpapbapbapbapbapbpb

14、pbapbpP* 1*111*11*min)|()( ),( ),(),( )|()()( )|(1)(此时此时Pe Pe min，由于，由于6.2 典型的译码规则典型的译码规则例例5.3 5.3 对二进制信道对二进制信道01010.80.90.20.1若若P(0)=0.4，求最佳译码规则所对应的平均差错率。，求最佳译码规则所对应的平均差错率。解：信道输入概率矩阵和信道转移概率矩阵为：解：信道输入概率矩阵和信道转移概率矩阵为： 9 . 01 . 02 . 08 . 0 6 . 0 , 4 . 0|XYXPP6.2 典型的译码规则典型的译码规则联合概率矩阵：联合概率矩阵： 54. 006. 00

15、8. 032. 0 XYP 可以看出，与输入符号对应的各列最大联合概率为可以看出，与输入符号对应的各列最大联合概率为0.32和和0.54，因此最大联合概率译码规则为：，因此最大联合概率译码规则为： 1)1(0)0(:FFF即最佳译码规则。即最佳译码规则。6.2 典型的译码规则典型的译码规则14. 0)54. 032. 0(1)1 , 1()0 , 0(1 )0),1()0),0(1),(1)(21 ppFpFpbbFpFPjjje译码差错率为：译码差错率为：同样，可采用最大后验概率译码规则：同样，可采用最大后验概率译码规则： 62. 038. 09 . 01 . 02 . 08 . 0 6 .

16、 0 , 4 . 0 YP 8710. 01579. 01290. 08421. 0|YXP6.2 典型的译码规则典型的译码规则 1)1(0)0(:FFF最大后验概率译码规则：最大后验概率译码规则：两种方法得到相同的结果。两种方法得到相同的结果。 最大后验概率译码规则又称为理想观测者规则。最大后验概率译码规则又称为理想观测者规则。它是选择这样一种译码函数，对于每一个输出符号它是选择这样一种译码函数，对于每一个输出符号bj，j1，2，s均译成具有最大后验概率的那个输均译成具有最大后验概率的那个输入符号入符号a*，则信道译码错误概率会最小。，则信道译码错误概率会最小。6.2 典型的译码规则典型的译

17、码规则一般来说，后验概率是难以确定的，所以应用起来并一般来说，后验概率是难以确定的，所以应用起来并不方便。所以当我们仅知道信道的统计特性而不知道不方便。所以当我们仅知道信道的统计特性而不知道信源的统计特性时，可只按最大转移概率来确定译码信源的统计特性时，可只按最大转移概率来确定译码规则，称为极大似然译码规则。规则，称为极大似然译码规则。 )|()|( )(:* AaabpabpB bAabFFiijjjj6.2 典型的译码规则典型的译码规则 极大似然译码规则的平均差错率不一定是最小，因极大似然译码规则的平均差错率不一定是最小，因此不一定是最佳码，但容易找到，只要知道信道的统此不一定是最佳码，但

18、容易找到，只要知道信道的统计特性即可。计特性即可。例例5.4 5.4 已知信道的转移概率矩阵如下，试用已知信道的转移概率矩阵如下，试用极大似然极大似然译码规则确定译码规则。译码规则确定译码规则。 4 . 03 . 03 . 05 . 03 . 02 . 02 . 03 . 05 . 0 321|321aaaPbbbXY31)()()(321 apapap6.2 典型的译码规则典型的译码规则解：在信道的转移概率矩阵每一列中选取一个最大值，解：在信道的转移概率矩阵每一列中选取一个最大值，确定译码规则。确定译码规则。 5 . 03 . 02 . 04 . 03 . 03 . 02 . 03 . 05

19、 . 0|XYP译码规则：译码规则： 33312211)(), ( )()(:abFaaabFabFF或或6.2 典型的译码规则典型的译码规则 由于已知条件中仅给出了转移概率矩阵，因此无法由于已知条件中仅给出了转移概率矩阵，因此无法求出对应的平均差错率。求出对应的平均差错率。 但由于信源输出序列在进入信道前已进行了信源编但由于信源输出序列在进入信道前已进行了信源编码码(主要作用之一是使输出符号概率均匀化主要作用之一是使输出符号概率均匀化)，经过有，经过有效的信源编码，信源编码器的输出码元概率分布已经效的信源编码，信源编码器的输出码元概率分布已经均匀化，因此信道的输入分布近似为等概率分布。可均匀

20、化，因此信道的输入分布近似为等概率分布。可以证明当输入等概率分布时，极大似然译码规则是最以证明当输入等概率分布时，极大似然译码规则是最佳译码规则。因为对于极大似然译码规则，要求佳译码规则。因为对于极大似然译码规则，要求 )|()|( )(:* AaabpabpB bAabFFiijjjj6.2 典型的译码规则典型的译码规则 当信道输入为等概率时，有当信道输入为等概率时，有p(a*)=p(ai)，因此，因此 p(a*) p( bj | a*) p(ai) p( bj | aj) p(a*, bj ) p(ai, bj ) 这就是最大联合概率条件。所以，当输入等概率时，这就是最大联合概率条件。所以

21、，当输入等概率时，极大似然译码规则与最大联合概率译码规则等价，因极大似然译码规则与最大联合概率译码规则等价，因此是最佳码。平均差错率：此是最佳码。平均差错率： YaXijYaXijieabprabpapP* min)|(1 )|()(*6.2 典型的译码规则典型的译码规则对上例，可求出平均差错率：对上例，可求出平均差错率：)4 . 02 . 0()3 . 03 . 0()2 . 03 . 0(31 )|()(* min YaXijieabpapP6.3 平均差错率与信道编码平均差错率与信道编码 仅通过采用最佳译码规则来减小平均差错率是有限的，很难仅通过采用最佳译码规则来减小平均差错率是有限的，

22、很难满足信息通信系统的高可靠性要求。要进一步降低平均差错率满足信息通信系统的高可靠性要求。要进一步降低平均差错率必须对信道输入序列进行变换必须对信道输入序列进行变换 信道编码，然后送入信道传送。信道编码，然后送入信道传送。例如，对于如下的信源和信道例如，对于如下的信源和信道( (不考虑信源编码，将信源的输出不考虑信源编码，将信源的输出看作信道的输入看作信道的输入) )：01010.990.990.010.01 5 . 05 . 010XPX6.3 平均差错率与信道编码平均差错率与信道编码 显然，错误传送概率显然，错误传送概率p=0.01，正确传送概率，正确传送概率p=0.99，其信道容量为：其

23、信道容量为： C=log2- -H(0.99,0.01) 0.92 bit/符号符号就信道本身而言，这样的信道是很好的。就信道本身而言，这样的信道是很好的。 如果在信源和信道之间不加信道编码，由于信道是如果在信源和信道之间不加信道编码，由于信道是输入等概率的，可知其极大似然译码规则就是最佳译输入等概率的，可知其极大似然译码规则就是最佳译码规则，由转移概率矩阵码规则，由转移概率矩阵 99. 001. 001. 099. 0 |XYP6.3 平均差错率与信道编码平均差错率与信道编码则极大似然译码规则为：则极大似然译码规则为： 1)1(0)0(:FFF平均差错率：平均差错率：2212110)99.

24、099. 0(21-1 ) )(|(211 ) )(|()( 1 jjjjjjjebFbpbFbpbFpP 显然，差错率太高，一般平均差错率应控制在显然，差错率太高，一般平均差错率应控制在1010-6-6以下，因以下，因此必须使用信道编码降低平均差错率。此必须使用信道编码降低平均差错率。 简单重复就是采用对同一信源符号进行多次重复编简单重复就是采用对同一信源符号进行多次重复编码。例如，对二元信源和二进制对称信道，信道编码码。例如，对二元信源和二进制对称信道，信道编码采用对信源符号的采用对信源符号的2次重复。次重复。 5 . 05 . 010UPU0101=0.99=0.99P=0.01P= 0

25、.01pp信道编码信道编码fUu1=0u2=1X 3=X1X2X3 1=000 8=111扩展扩展信道信道Y 3=Y1Y2Y3 1=000 2=001 8=111信道译码信道译码F 1=000 8=1113213 XXXX3213XXXX 3213YYYY 11100021 0101=0.99=0.99P=0.01P= 0.01pp2次重复编码的编码规则为：次重复编码的编码规则为： 111)1(000)0(:fff 显然，这是码长显然，这是码长N=3的定长编码，信道的输入为的定长编码，信道的输入为 1, 8， 经过三次扩展信道的传送，在信道的输出端经过三次扩展信道的传送，在信道的输出端可能得到

26、可能得到8个接收符号个接收符号 1, 2, 8。信道的转移概率矩阵为：信道的转移概率矩阵为： )|()|()|()|()|()|( 88828118121181 ppppppP1 2 8 按极大似然译码规则得译码规则：按极大似然译码规则得译码规则： 2876415321)()()()()()()()( FFFFFFFF 111)111()110()101()011(000)100()010()001()000( FFFFFFFF即即 322222233222222381ppppppppppppppppppppppppppppP 1 2 8 3 4 5 6 7 pp 因为因为 这是一种择多译码方法，即比较接收序列中这是一种择多译码方法，即比较接收序列中0和和1的的