信息论与编码纠错第5章

1、信息论与编码信息论与编码第第5 5章章 有噪信道编码有噪信道编码 信息论与编码信息论与编码内容提要内容提要本章介绍了信道编码和译码的基本概念，介绍了两种常本章介绍了信道编码和译码的基本概念，介绍了两种常用的译码准则：最大后验概率译码准则和极大似然译码准则用的译码准则：最大后验概率译码准则和极大似然译码准则,还介绍了在这两种译码准则下错误概率的计算方法。还介绍了在这两种译码准则下错误概率的计算方法。本章还介绍了信道编码定理及信道编码逆定理，以及信本章还介绍了信道编码定理及信道编码逆定理，以及信息论中的一个重要不等式息论中的一个重要不等式fnao不等式。不等式。信息论与编码信息论与编码我们要尽可能

2、的提高信息传输率，并控制传输误差。信源编码以提我们要尽可能的提高信息传输率，并控制传输误差。信源编码以提高传输效率作为主要考虑因素，信道编码以提高传输可靠性作为主要考高传输效率作为主要考虑因素，信道编码以提高传输可靠性作为主要考虑因素。虑因素。 信道有多种形式，如电视、广播、微波、电话、计算机局域网和宽信道有多种形式，如电视、广播、微波、电话、计算机局域网和宽带网等，对于所有的信道可用下图所示的模型来表示带网等，对于所有的信道可用下图所示的模型来表示 ：信息论与编码信息论与编码衡量信道传输快慢的指标是信息传输率，而衡量信息传输可靠性的指衡量信道传输快慢的指标是信息传输率，而衡量信息传输可靠性的

3、指标是平均错误概率，平均错误概率与信道的统计特性有关。标是平均错误概率，平均错误概率与信道的统计特性有关。要改变信道统计特性成本太大，所以可事先对信源编码器输出的符号要改变信道统计特性成本太大，所以可事先对信源编码器输出的符号序列按照某种规则进行编码，一般的方法是给信源序列加上一定的冗余度，序列按照某种规则进行编码，一般的方法是给信源序列加上一定的冗余度，这种编码称为这种编码称为信道编码信道编码，编好的代码称为，编好的代码称为码字码字，将码字送入信道传输，在，将码字送入信道传输，在信道的输出端，信道译码器根据编码规则对信道输出符号进行估值，尽量信道的输出端，信道译码器根据编码规则对信道输出符号

4、进行估值，尽量使这种估值接近输入码字。使这种估值接近输入码字。 信源输出序列信源输出序列 ，经信道编码器编成码字，经信道编码器编成码字 并输入信并输入信道，由于干扰，信道输出道，由于干扰，信道输出 ，信道译码器对估值得，信道译码器对估值得 。 u( )xf uy( )xf y信息论与编码信息论与编码【例】给定二元对称信道，信道固有错误概率为【例】给定二元对称信道，信道固有错误概率为p（p 0.5）01011 - p1 - ppp编码规则：为提高可靠性，每个信道符号重复三次发送。编码规则：为提高可靠性，每个信道符号重复三次发送。译码规则：择多译码，即信宿方收到的三个符号中有两个或三个为译码规则：

5、择多译码，即信宿方收到的三个符号中有两个或三个为1，就将此，就将此次接收符号判决为次接收符号判决为1；若三个符号中有两个或三个为；若三个符号中有两个或三个为0，就将此次接，就将此次接收符号判决为收符号判决为0。下面为重复编码传输示意图，计算错误概率下面为重复编码传输示意图，计算错误概率pe。信息论与编码信息论与编码信源输出序列为：信源输出序列为：1, 0, 1, 1u 信道输入序列为：信道输入序列为：111, 000, 111, 111x 由于由于p的存在，使得传输出错，故信道输出为：的存在，使得传输出错，故信道输出为：111, 001, 001, 000y 根据译码规则，信道估值输出：根据译

6、码规则，信道估值输出：1, 0, 0, 0y 信道错误概率：假设信道离散无记忆，即信道错误概率：假设信道离散无记忆，即31( / )(/)iiip y xp yx 错误概率为：错误概率为：22332333(1)32epc ppc pppp重复编码的结果使错误概率下降。重复编码的结果使错误概率下降。信息论与编码信息论与编码【例】例】 逆重复码逆重复码离散无记忆二进制对称信道，固有误码率为离散无记忆二进制对称信道，固有误码率为p (p0.5)，信源输出序列为三，信源输出序列为三位二进制数字。位二进制数字。 编码规则：为提高传输效率，仅向信道发送一位，预先将信源输出序列进行择编码规则：为提高传输效率

7、，仅向信道发送一位，预先将信源输出序列进行择多编码：信源输出的三位符号中有两位或多编码：信源输出的三位符号中有两位或3位是位是1，信源序列编码为，信源序列编码为1，若三位符号中有两位或若三位符号中有两位或3位是位是0，就将此信源序列编码为，就将此信源序列编码为0。 译码规则：将接收的一位符号重复三次译出，即若接收到译码规则：将接收的一位符号重复三次译出，即若接收到1就译码为就译码为111，即若，即若接收到接收到0就译码为就译码为000。 下面为重复编码传输示意图，计算错误概率下面为重复编码传输示意图，计算错误概率pe。信息论与编码信息论与编码（1）先设）先设p = 0，计算这种编码方法带，计算

8、这种编码方法带 来的固有错误来的固有错误p1。信道输入符号集信道输入符号集x = 000，001，010，011，100，101，110，111判决输出符号集判决输出符号集y = 000，111译码规则：译码规则：(000001010100)000(011101110111)111ff，因为后验概率：因为后验概率：( / )(000/000)1/4( / )(111/111)1/4p x ypp x yp 则出错概率：则出错概率：( / )( /000)3/4( / )( /111)3/4p e yp ep e yp e信息论与编码信息论与编码假设假设8组输入序列是等概发送的，由于信道的对称性

9、，两个估值序列组输入序列是等概发送的，由于信道的对称性，两个估值序列也是等概分布的，则每个序列的平均错误概率为也是等概分布的，则每个序列的平均错误概率为:30.5 ( /000)0.5 ( /111)4p ep e误比特率误比特率1131344p （2）再设）再设p0，计算由于信道噪声引起的错误概率，计算由于信道噪声引起的错误概率p2。因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率为为p，故序列差错概率为，故序列差错概率为p，误比特率，误比特率 213pp（3）总差错概率（误比特率）：）总差错概率（误比特率）：12114

10、3epppp信息论与编码信息论与编码【例】例】 奇偶校验码奇偶校验码在信息序列后面加上一位校验位，使之模在信息序列后面加上一位校验位，使之模2和等于和等于1，这样的编码称，这样的编码称为奇校验码；若使模为奇校验码；若使模2和等于和等于0，这样的编码就称为偶校验码，即每个码，这样的编码就称为偶校验码，即每个码矢中矢中1的个数固定为奇数或偶数。的个数固定为奇数或偶数。 奇偶校验码能检测出奇数位错误，但无法判断错的是哪一位，故没奇偶校验码能检测出奇数位错误，但无法判断错的是哪一位，故没有纠错能力。这种编码方式可用在反馈信道场合，如计算机通信串口通有纠错能力。这种编码方式可用在反馈信道场合，如计算机通

11、信串口通信。信。 信息论与编码信息论与编码信道总不可避免会搀杂噪声，所以信息在信道传输过程中，差错是不信道总不可避免会搀杂噪声，所以信息在信道传输过程中，差错是不可避免的。选择合适的译码规则可以弥补信道的不足。可避免的。选择合适的译码规则可以弥补信道的不足。 【例】【例】 bsc信道的转移概率如下信道的转移概率如下11p1时，这是一种强噪声信道，在这种情况下，若按常规译码，肯定出时，这是一种强噪声信道，在这种情况下，若按常规译码，肯定出错，但可将判决取反，收到错，但可将判决取反，收到0判为判为1，收到，收到1判为判为0，反而正确。，反而正确。 可见译码规则对传输系统错误概率的影响是很大的。可见

12、译码规则对传输系统错误概率的影响是很大的。信息论与编码信息论与编码设信源有设信源有m个消息，信道编码器已用个消息，信道编码器已用m个码矢个码矢1 ,mmxxx对它进行了最佳编码。对它进行了最佳编码。编码后发送码矢量编码后发送码矢量 ，其发送概率为，其发送概率为 ，通过信道转移概率为，通过信道转移概率为 的信道传输，接收矢量为的信道传输，接收矢量为 ，信道译码器输出，信道译码器输出 。kx()kp x( /)kp y x ykx通信过程框图如下：通信过程框图如下：信息论与编码信息论与编码当估值当估值 时，就产生了误码，用时，就产生了误码，用 表示后验概率，则表示后验概率，则收到收到 估错的错误概

13、率为：估错的错误概率为： kkxx( / )p x y y( )(/ )(/ )1(/ )ekkiki kpyp xxyp xyp xy 通信总希望错误概率最小，由上式可看出错误概率通信总希望错误概率最小，由上式可看出错误概率 最小等同最小等同于后验概率于后验概率 最大，这就是最大，这就是最大后验概率译码准则最大后验概率译码准则。( )epy(/ )kp xy信息论与编码信息论与编码根据概率关系式根据概率关系式()( / )( )p x yp x yp y 根据最大后验概率译码准则，收到矢量根据最大后验概率译码准则，收到矢量y后，在所有后，在所有(1, 2,)mxmm中，中，选一个后验概率选一

14、个后验概率(/ )mp xy最大的最大的mx值，作为对值，作为对y的估值的估值kkxx，那么对这，那么对这m个个mx说，概率说，概率 是同一值，根据上式后验概率是同一值，根据上式后验概率值来值来( )p y( / )p x y 就意味着全概率就意味着全概率 最大，因此最大后验概率译码准则也称为最大，因此最大后验概率译码准则也称为最大联合概率译码准则最大联合概率译码准则。最大最大()p x y 信息论与编码信息论与编码【例】信源分布【例】信源分布123()0.50.10.4xxxxp x信道转移概率矩阵信道转移概率矩阵0.50.30.20.10.70.20.30.30.4p p信道输出符号信道输

15、出符号y = y1，y2，y3，按最大后验概率准则译码。，按最大后验概率准则译码。(1) 根据根据p (xy) = p (y/x) p (x) 算出全概率，用矩阵表示算出全概率，用矩阵表示0.250.150.10()0.010.070.020.120.120.16p xy(2) 根据根据()()jijip yp x y，算出，算出p(y) = 0.38 0.34 0.28信息论与编码信息论与编码(3) 再由再由()( / )( )p xyp x yp y算出后验概率，用矩阵表示算出后验概率，用矩阵表示0.25 0.380.15 0.340.10 0.28( / )0.01 0.380.07 0

16、.340.02 0.280.12 0.380.12 0.340.16 0.28p x y(4) 按最大后验概率准则译码，在后验概率矩阵中，每列选一最大值（矩按最大后验概率准则译码，在后验概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为阵中带下划线的值），译为112133yxyxyx信息论与编码信息论与编码(5) 若按最大联合概率译码准则译码，在全概率矩阵若按最大联合概率译码准则译码，在全概率矩阵 p(xy)中每列选一最中每列选一最大值（矩阵中带下划线的值），也可译出大值（矩阵中带下划线的值），也可译出 0.250.150.10()0.010.070.020.120.120.16p xy1

17、12133yxyxyx信息论与编码信息论与编码前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从前面介绍的最大后验概率译码准则等同于最小传输错误概率准则，从错误概率最小角度，该译码准则是最好的。错误概率最小角度，该译码准则是最好的。在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道在实际应用中，通常用同一信道去传输各种不同的信源，只知道信道的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大的转移概率，而不知道信源的分布，故无法计算全概率，故无法采用最大后验概率译码准则进行译码。后验概率译码准则进行译码。 在这种情况下，一般采用最大信道转移概率来确定估值，即在收

18、到矢量在这种情况下，一般采用最大信道转移概率来确定估值，即在收到矢量y后，在所有的后，在所有的(1, 2,)mx mm中，选一个转移概率中，选一个转移概率( /)mp y x 最大的最大的mx值，作为对值，作为对的估值的估值ykkxx译码规则。译码规则。， 这一译码规则称为这一译码规则称为极大似然极大似然信息论与编码信息论与编码实际上，在信道输入等概率条件下，极大似然译码规则也是最佳的。实际上，在信道输入等概率条件下，极大似然译码规则也是最佳的。( /)( /)kmp y xp y x 输入等概率时，有输入等概率时，有()()kmp xp x，故，故() ( /)() ( /)kkmmp xp

19、 y xp xp y x 则有则有()()kmp x yp x y 信息论与编码信息论与编码对信道译码器估错概率关于输出求统计平均值：对信道译码器估错概率关于输出求统计平均值：111111()()() 1(/)1() (/)()()()()()kmmejejjkjjjmmmmjkjijkjjijjkxyyx xypp ypyp yp xyp yp xyp x yp x yp x yp x yp x y 信息论与编码信息论与编码【例】信源分布【例】信源分布123()0.50.10.4xxxxp x信道转移概率矩阵信道转移概率矩阵0.50.30.20.10.70.20.30.30.4p p，信道输

20、出符号，信道输出符号y = y1，y2，y3。（1）计算按最大后验概率准则译码的平均错误概率；）计算按最大后验概率准则译码的平均错误概率；（2）若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率。）若信源等概分布，对其按极大似然译码准则译码，并求平均错误概率。【解】（【解】（1）最大后验概率准则译码）最大后验概率准则译码0.250.150.10()0.010.070.020.120.120.16p xy信息论与编码信息论与编码平均错误概率：平均错误概率：112133yxyxyx0.250.150.10()0.010.070.020.120.120.16p xy()0.1 0.1 0.

21、4 0.30.1 0.70.4 0.30.5 0.20.1 0.20.44kex xypp x y 信息论与编码信息论与编码（2）当信源等概分布，按最大似然函数译码准则译码，已给出信道转移概）当信源等概分布，按最大似然函数译码准则译码，已给出信道转移概率矩阵为率矩阵为0.50.30.20.10.70.20.30.30.4p p在矩阵的每列中选一最大值在矩阵的每列中选一最大值(矩阵中带下划线的值矩阵中带下划线的值)，译码为，译码为112233yxyxyx平均错误概率：平均错误概率：10.10.30.30.30.20.20.4673ep 信息论与编码信息论与编码【例】考虑重复码，信源等概率分布，采

22、用极大似然译码规则进行译码，并例】考虑重复码，信源等概率分布，采用极大似然译码规则进行译码，并计算平均错误概率。计算平均错误概率。根据编码规则：根据编码规则：( )xf u重复重复3次编码，即次编码，即12(0)000(1)111xfxf原信道的固有错误概率为原信道的固有错误概率为p（p 0.5）的二进制对称信道，其信道转）的二进制对称信道，其信道转移概率矩阵为：移概率矩阵为：11ppppp经编码后得到的码字是码长为经编码后得到的码字是码长为3的码矢量，的码矢量， 送入送入3次次扩展信道传输，信道离散无记忆，扩展信道的信道转移概率矩阵为：扩展信道传输，信道离散无记忆，扩展信道的信道转移概率矩阵

23、为：000, 111x 32222223(3)32222223(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)pp pp pp pp pp pp ppppp pp pp pp pp pp pp信息论与编码信息论与编码32222223(3)32222223(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)(1)pp pp pp pp pp pp ppppp pp pp pp pp pp pp按极大似然译码准则译码，在矩阵的每列中选一最大值（带下划线按极大似然译码准则译码，在矩阵的每列中选一最大值（带下划线的值），译码为：的值），译码

24、为：(000)000(001)000(010)000(100)000(011)111(101)111(110)111(111)111ffffffff计算平均错误概率，信源等概率分布计算平均错误概率，信源等概率分布12( )()1/2p xp x3223()( ) ( / )1126(1)3222kkex xyx xypp x yp x p y xpp ppp 信息论与编码信息论与编码由于信道在传输过程中不可避免地拾取干扰，以致产生错误，选择合由于信道在传输过程中不可避免地拾取干扰，以致产生错误，选择合适的编译规则可以使错误概率尽可能小，信道编码定理（香农第二定理）适的编译规则可以使错误概率尽可能小，信道编码定理（香农第二定理）指出：信道容量指出：信道容量c是在满足错误概率是在满足错误概率pe0时，信道所能容纳的信息传输率时，信道所能容纳的信息传输率的极限值。的极限值。【定理】有噪信道编码定理（香农第二定理）【定理】有噪信道编码定理（香农第二定理）对于任何离散无记忆信道对于任何离散无记忆信道dmc，存在信息传输率为，存在信息传输率为rc，长为，长为n的的码，当码，当n 时，平均差错概率时，平均差错概率 pe e