信息论第六章有噪声编码

1、第第6章章有噪信道编码有噪信道编码 第第6章章 有噪信道编码有噪信道编码 内容提要本章介绍了信道编码和译码的基本概念，介绍了两种常用的译码准则：最大后验概率译码准则和极大似然译码准则,还介绍了在这两种译码准则下错误概率的计算方法。本章还介绍了信道编码定理及信道编码逆定理，以及信息论中的一个重要不等式Fnao不等式。 6 61 1 信道编码的基本概念信道编码的基本概念 将信道用图将信道用图6-1所示的模型表示。所示的模型表示。信道编码器信道编码器信道信道信道译码器信道译码器uxyX X图图6-1 6-1 信道模型信道模型 信源输出序列信源输出序列u，经信道编码器编成码字经信道编码器编成码字x =

2、 f (u) 并输入信道，由于干扰，信道输出并输入信道，由于干扰，信道输出y，信道译码器对信道译码器对y估值得估值得 = F (y) 。 X X信源编码以提高信源编码以提高传输效率传输效率作为主要考虑因素，信作为主要考虑因素，信道编码以提高道编码以提高传输可靠性传输可靠性作为主要考虑因素。作为主要考虑因素。【例【例6.3】 逆重复码逆重复码 离散无记忆二进制对称信道，固离散无记忆二进制对称信道，固有误码率为有误码率为p (p0.5)，信源输出序列为三位二进制数字。信源输出序列为三位二进制数字。编码规则编码规则：为提高传输效率，仅向信道发送一位，预先：为提高传输效率，仅向信道发送一位，预先将信源

3、输出序列进行择多编码将信源输出序列进行择多编码: :00000000011101010011101111001110判决输出接收发送原序列pp图图6-3 6-3 逆重复编码传输示意图逆重复编码传输示意图 译码规则：将接收的译码规则：将接收的一位符号重复三次译出，一位符号重复三次译出，即若接收到即若接收到1就译码为就译码为111，即若接收到，即若接收到0就译就译码为码为000。信源输出的三位符号中有两位或信源输出的三位符号中有两位或3位是位是1，信源序列编码为，信源序列编码为1，若三位符号中有两位或若三位符号中有两位或3位是位是0，就将此信源序列编码为，就将此信源序列编码为0。计算差错概率计算差

4、错概率pe ：（1）先设先设p = 0，计算这种编码方法带来的固有错误计算这种编码方法带来的固有错误p1信信道输入符号集道输入符号集 X = 000,001,010,011,100,101,110,111判决输出符号集判决输出符号集Y = 000,111译码规则译码规则因为后验概率因为后验概率 则出错概率则出错概率 111)111110101011(000)100010001000(，FF41)111111()41)000000()y yx xy yx x（43411)111()(43411)000()(epyepepyep 两个估值序列也是等概分布的，则每个序列的两个估值序列也是等概分布的，

5、则每个序列的平均错误概率为平均错误概率为误比特率误比特率 （2）再设）再设p0，计算由于信道噪声引起的错误概计算由于信道噪声引起的错误概率率p2。因为每个序列有三位二进制数字，但只发送因为每个序列有三位二进制数字，但只发送一位，这一位的出错概率为一位，这一位的出错概率为p，故序列差错概率为故序列差错概率为p，误比特率误比特率（3 3）总差错概率（误比特率）：）总差错概率（误比特率）：43)111(5 . 0)000(5 . 0epep4143311ppp312ppppe3141216 62 2 译码规则及错误概率译码规则及错误概率 信道总不可避免会搀杂噪声，所以信息在信道传输过程信道总不可避免

6、会搀杂噪声，所以信息在信道传输过程中，差错是不可避免的。选择合适的译码规则可以弥补信中，差错是不可避免的。选择合适的译码规则可以弥补信道的不足。道的不足。1最大后验概率译码准则最大后验概率译码准则发送码矢发送码矢x xk k ，其发送概率为其发送概率为q q( (x xk k) ) ，通过信道转移概率为通过信道转移概率为p p( (y yx xk k) )的信道传输，接收到矢量的信道传输，接收到矢量y y，信道译码器输出信道译码器输出 通信过程可用图通信过程可用图65所示框图表示。所示框图表示。,kx x下面介绍两种典型的译码规则下面介绍两种典型的译码规则：图图6 65 5 通信过程框图通信过

7、程框图 当估值当估值 xk 时，就产生了误码，用时，就产生了误码，用 （xy）表示后表示后验概率，则收到验概率，则收到y估错的概率为估错的概率为 （6-26-2） kx x kikikkepy yx xy yx xy yx xx xy y1通信总希望错误概率最小，由式通信总希望错误概率最小，由式(6-2)可看出错误概率可看出错误概率pe (xk ) 最小等同于后验概率最小等同于后验概率 （xk ky）最大，这就是最大，这就是最大后验概率译码准则最大后验概率译码准则。 kx xxky信源信源信道编码器信道编码器信道信道信道译码器信道译码器信宿信宿干扰干扰根据概率关系式根据概率关系式 （6-36-

8、3） )()()(y yxyxyy yx xp根据式（根据式（6-3）后验概率）后验概率 （xy）最大的就意味最大的就意味着着p（x y）全概率最大，因此最大后验概率译码全概率最大，因此最大后验概率译码准则也称为准则也称为最大联合概率译码准则最大联合概率译码准则。【例【例6.5】 信源分布信源分布 ，信道，信道转移概率矩阵转移概率矩阵 ， 信道输出符号信道输出符号Y = y1, y2, y3，按最大后验概率准则译码。按最大后验概率准则译码。4 . 01 . 05 . 0)(321xxxXqX4 . 03 . 03 . 02 . 07 . 01 . 02 . 03 . 05 . 0P P(1)(

9、1)根据根据p (xy) = p (yx) q(x) 算出全概率，用矩阵表示算出全概率，用矩阵表示 16. 012. 012. 002. 007. 001. 010. 015. 025. 0)(xyp (2)(2)根据根据 ，算出，算出 （y） = 0.38 0.34 0.28 ijijyxpy)()( (3)(3)再由再由 算出后验概率，用矩阵表示算出后验概率，用矩阵表示 )()(yxypyx28. 016. 034. 012. 038. 012. 028. 002. 034. 007. 038. 001. 028. 010. 034. 015. 038. 025. 0)( yx (4) (

10、4)按按最大后验概率准则最大后验概率准则译码，在后验译码，在后验概率矩阵中，每列选一最大值（矩阵中概率矩阵中，每列选一最大值（矩阵中带下划线的值），译为带下划线的值），译为 331211xyxyxy(5)(5)若按若按最大联合概率译码准则最大联合概率译码准则译码，在全译码，在全概率矩阵概率矩阵 p(xy) 中每列选一最大值（矩阵中每列选一最大值（矩阵中带下划线的值），也可译出中带下划线的值），也可译出 。331211xyxyxy 在实际应用中，一般最大信道转移概率来确定估值在实际应用中，一般最大信道转移概率来确定估值 ，即在收到矢量即在收到矢量y后，在所有的后，在所有的xm (m =1, 2,

11、 , M) 中中,选一个选一个转移概率转移概率p(yxm)最大的最大的xm值，作为对值，作为对y的估值的估值 = xk ，这一译码规则称为这一译码规则称为极大似然译码规则极大似然译码规则。 x kx 2极大似然译码准则极大似然译码准则 3平均错误概率平均错误概率y yx xy yy yx xx xy y)()(kppkpx x- -x xy yx xy y)(MjkMiMjjipp111)()(y yx xy yx xMjkj1)(1y yx xy y)(1)(yxypke由下式是信道输出由下式是信道输出y二信道译码器估错的概率，二信道译码器估错的概率，对上式求统计平均对上式求统计平均Mjje

12、jepp1)(y yy yMjkj11)(y yx xy ykpPex x- -x xy yx xy y)(（6-4） （1）求求平均错误概率平均错误概率pe 根据式（根据式（6-4）得）得 = 0.01+0.12+0.07+0.12+0.1+0.02 = 0.44 kppex x- -x xy yxyxy)(【例【例6.6】 计算计算 例例6.5 的平均错误概率，若信的平均错误概率，若信源等概分布，对其译码，并求平均错误概率。源等概分布，对其译码，并求平均错误概率。 16. 012. 012. 002. 007. 001. 010. 015. 025. 0)(xyp 例例6.56.5已经已经

13、根据根据p (xy) = p (yx) q(x) 算出全概率，算出全概率，用矩阵表示用矩阵表示 解：解：(2)(2)当信源等概分布，按当信源等概分布，按最大似然函数译码准则最大似然函数译码准则译码，译码， 例例6.5 已给出信道转移概率矩阵已给出信道转移概率矩阵 在矩阵的每在矩阵的每列中选一最大值列中选一最大值( (矩阵中带下划线的值矩阵中带下划线的值) )，译码为，译码为平均错误概率平均错误概率 4 . 03 . 03 . 02 . 07 . 01 . 02 . 03 . 05 . 0P P332211xyxyxy467. 02 . 02 . 03 . 03 . 03 . 01 . 031e

14、p6 63 3 信道编码定理信道编码定理定理定理6.1 对于任何离散无记忆信道对于任何离散无记忆信道DMC，存在信存在信息传输率为息传输率为R，长为长为n的码，当的码，当n 时，平均差错时，平均差错概率概率 pe exp- nE (R)0，式中式中E (R) 为可靠性函为可靠性函数，数，E ( R )在在0 R C的范围内为正。的范围内为正。 上述定理也称有噪上述定理也称有噪信道编码定理信道编码定理，即，即ShannonShannon第二定第二定理。理。 一一 随机编码方法随机编码方法 选用长为选用长为n的定长码，共可构成的定长码，共可构成kn个矢量，设有个矢量，设有M个个消息待传（消息待传（

15、M kn），），每次随机地从每次随机地从kn个矢量中抽出个矢量中抽出M个矢量构成一个码个矢量构成一个码字字集合集合C（允许重复取）允许重复取）C = x1 , , x m , , x M共可构成共可构成knM个这样的码个这样的码字字集合。集合。由随机编码的构造方法，得到任何一个码字的概率相由随机编码的构造方法，得到任何一个码字的概率相同，且相互独立。同，且相互独立。 式中式中0 , 1，因为，因为 , 都是任意数，可取都是任意数，可取 11二二Gallager上界上界 GallagerGallager上界：上界： （6-86-8）kmmkkeppp1111x xy yx xy yx x三三 随

16、机编码错误概率上界随机编码错误概率上界 Gallager限仅给出发送码矢限仅给出发送码矢xk时的错误概率上界，时的错误概率上界，通过对上述的随机编码集合求平均，可得到通过对上述的随机编码集合求平均，可得到随机编码随机编码错误概率的上界：错误概率的上界： y yx xx xy yx x111) 1(pqMPe（6-12） （6-12）平均错误概率的上界，它虽然是针对离散无）平均错误概率的上界，它虽然是针对离散无记忆信道推出的，但对有记忆的离散输入、输出及连续记忆信道推出的，但对有记忆的离散输入、输出及连续输出都适用，只不过在连续情况下，输出都适用，只不过在连续情况下， 表示概率密度。表示概率密度

17、。 )( xyp四四离散无记忆信道离散无记忆信道DMC的错误概率上界的错误概率上界 nyxexypxqMP 111)()(在在0 R C的范围内，的范围内，E (R )是下降的、下凹的正值函数，是下降的、下凹的正值函数，说明说明E (R )有界，这样，当有界，这样，当 时，时，有有exp - -nE (R ) 0，从而从而pe C，不可能存在任何方法使差错概率任意不可能存在任何方法使差错概率任意小。小。本本 章章 小小 结结 信道输入码矢xk x1, x2, , xM ，通过信道转移概率为p(yxk)的信道传输，输出矢量y，信道译码器估值为 F(y)， x1, x2, , xM 。 kx xkx xkx x最大后验概率译码准则最大后验概率译码准则 （ y） （xm