信息论与编码第六章PPT讲稿.ppt

《信息论与编码第六章PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第六章PPT讲稿.ppt（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码第六章第1页，共25页，编辑于2022年，星期四信源编码之后的码字序列抗干扰能力很脆弱，信源编码之后的码字序列抗干扰能力很脆弱，在信道噪声的影响下容易产生差错，为了提高在信道噪声的影响下容易产生差错，为了提高通信系统的有效性和可靠性，要在信源编码器通信系统的有效性和可靠性，要在信源编码器和信道之间加上一个信道编码器。和信道之间加上一个信道编码器。有噪声信道编码的主要目的是提高传输可靠有噪声信道编码的主要目的是提高传输可靠性，增加抗干扰能力，因此也称为纠错编码或性，增加抗干扰能力，因此也称为纠错编码或抗干扰编码。抗干扰编码。第2页，共25页，编辑于2022年，星期四6.1 6.1 错

2、误概率和译码规则错误概率和译码规则我们已经知道错误概率与信道统计特性有关。信道的我们已经知道错误概率与信道统计特性有关。信道的统计特性可由信道的传递矩阵来描述。当确定了输入和统计特性可由信道的传递矩阵来描述。当确定了输入和输出对应关系后，也就确定了信道矩阵中哪些是正确传输出对应关系后，也就确定了信道矩阵中哪些是正确传递概率，哪些是错误传递概率。例如在二元对称信道中，递概率，哪些是错误传递概率。例如在二元对称信道中，单个符号的错误传递概率是单个符号的错误传递概率是p，正确传递的概率是，正确传递的概率是但通信过程一般并不是在信道输出端就结束了，还要但通信过程一般并不是在信道输出端就结束了，还要经过

3、译码过程（或判决过程）才到达消息的终端（收经过译码过程（或判决过程）才到达消息的终端（收信者）。因此译码过程和译码规则对系统的错误概率信者）。因此译码过程和译码规则对系统的错误概率影响很大。影响很大。第3页，共25页，编辑于2022年，星期四例：影响通信系统可靠性的一个重要问题是译码方式，例：影响通信系统可靠性的一个重要问题是译码方式，可以通过一个例子看一下，设一个二元对称信道，其可以通过一个例子看一下，设一个二元对称信道，其传输特性如图所示传输特性如图所示（2 2）采用收）采用收0 0判判1 1，收收1 1判判0 0；则系统正确的译码概率为则系统正确的译码概率为0.9，错错误译码概率为误译码

4、概率为0.1，通信的可靠性提高了。通信的可靠性提高了。（1 1）采用收采用收0判判0，收，收1判判1；当信源先验概率的等概时当信源先验概率的等概时p(0)=p(1)=1/2；这时收到；这时收到Y判判X的后的后验概率等于信道转移概率，系统验概率等于信道转移概率，系统正确的译码概率为正确的译码概率为0.1，错误译码，错误译码概率为概率为0.9。第4页，共25页，编辑于2022年，星期四设信道设信道输入符号集输入符号集X=xi,i=1,2,r,输符号集为输符号集为Y=yj,j=1,2,s,F(yj)=xi (i=1,2,r;j=1,2,s)对于有对于有r个输入，个输入，s个输出的信道来说，可以有个输

5、出的信道来说，可以有rs个不同个不同的译码准则。的译码准则。若对每一个输出符号若对每一个输出符号yj都有一个确定的函数都有一个确定的函数 F(yj j)，使，使yj j对应于惟一的一个输入符号对应于惟一的一个输入符号xi i，则这样的函数为译码规，则这样的函数为译码规则。则。第5页，共25页，编辑于2022年，星期四【例【例6.16.1】有一离散单符号信道，信道矩阵为】有一离散单符号信道，信道矩阵为根据这样一个信道矩阵，设计一个译码规则根据这样一个信道矩阵，设计一个译码规则 ，即即设计另外一个译码规则，如设计另外一个译码规则，如 ，即，即第6页，共25页，编辑于2022年，星期四译码规则的选择

6、应该使平均错误概率为最小。译码规则的选择应该使平均错误概率为最小。为了选择译码规则，首先必须计算平均错误概率。为了选择译码规则，首先必须计算平均错误概率。1 1、错误概率、错误概率译码准则确定之后，当接收端收到一译码准则确定之后，当接收端收到一个个bj后，则按译码后，则按译码准则译成准则译成F(bj)=ai，这时如果发送的为，这时如果发送的为ai则为正确译码，则为正确译码，如果发送的不是如果发送的不是ai则为错误译码。所以接收到则为错误译码。所以接收到bj后正确译后正确译码的概率就是接收端收到码的概率就是接收端收到bj后，推测发送端发出后，推测发送端发出ai的正的正确译码概率：确译码概率：错误

7、译码的概率为错误译码的概率为：第7页，共25页，编辑于2022年，星期四平均错误译码概率为：平均错误译码概率为：它表示经过译码后平均接收到一个符号所产生的错它表示经过译码后平均接收到一个符号所产生的错误大小，也称平均错误概率。误大小，也称平均错误概率。只要设计译码规则只要设计译码规则，使条件错误译码概率，使条件错误译码概率为最小。就应选择为最大。即选择译码函数：为最小。就应选择为最大。即选择译码函数：并使之满足条件并使之满足条件第8页，共25页，编辑于2022年，星期四这就是说，如果采用这样一种译码函数，它对于每一这就是说，如果采用这样一种译码函数，它对于每一个输出符号均译成具有最大后验概率的

8、那个输入符号，个输出符号均译成具有最大后验概率的那个输入符号，则先信道错误概率就能最小。这种译码规则称为则先信道错误概率就能最小。这种译码规则称为“最最大后验概率译码准则大后验概率译码准则”或或“最小错误概率译码准则最小错误概率译码准则”。已知信道的传递概率已知信道的传递概率 与输入符号的先验概率与输入符号的先验概率，根据贝叶斯定律，根据贝叶斯定律选择译码函数选择译码函数并满足并满足第9页，共25页，编辑于2022年，星期四这样定义的译码规则称为最大似然译码准则。这样定义的译码规则称为最大似然译码准则。平均正确概率为平均正确概率为也可以写成也可以写成如果先验概率如果先验概率 是等概率的是等概率

9、的第10页，共25页，编辑于2022年，星期四【例【例6.2】已知信道矩阵已知信道矩阵根据最大似然译码准则可选择码函数为根据最大似然译码准则可选择码函数为第一列中第一列中，第三列中第三列中第二列中第二列中第11页，共25页，编辑于2022年，星期四若选用前述译码函数若选用前述译码函数得平均错误概率得平均错误概率若输入不是等概率分布，其概率分布为若输入不是等概率分布，其概率分布为根据最大似然译码准则仍可选择译码函数为根据最大似然译码准则仍可选择译码函数为计算其平均错误概率。计算其平均错误概率。第12页，共25页，编辑于2022年，星期四采用最小错误概率译码准则：采用最小错误概率译码准则：联合概率

10、矩阵联合概率矩阵译码函数为译码函数为输入不是等概率分布时最大似然译码输入不是等概率分布时最大似然译码准则的平均错误概率不是最小。准则的平均错误概率不是最小。第13页，共25页，编辑于2022年，星期四错误概率错误概率 与信道疑义度与信道疑义度 满足以下关系满足以下关系这个不等式称为费诺不等式。这个不等式称为费诺不等式。6.2 6.2 错误概率与编码方法错误概率与编码方法1 1、简单重复编码、简单重复编码一个一个BSCBSC信道，输入为信道，输入为X=0X=0，11，且为等概分布，信道模且为等概分布，信道模型为：型为：按最大似然译码准则为：按最大似然译码准则为：（输入等概率）（输入等概率）第14

11、页，共25页，编辑于2022年，星期四将将0 0编为编为000000，1 1编为编为111111。这时的可用码字为这时的可用码字为8 8；分别为：；分别为：X1=000 X2=001 X3=010 X4=100X1=000 X2=001 X3=010 X4=100X5=011 X6=110 X7=101 X8=111X5=011 X6=110 X7=101 X8=111而许用码字为而许用码字为000000和和111111，相当于信道输入为相当于信道输入为X1=000X1=000，X2=111X2=111，而信道输出端为：，而信道输出端为：Y1=000Y1=000；Y2=001Y2=001；Y3

12、=010Y3=010；Y4=100Y4=100Y5=011Y5=011；Y6=110Y6=110；Y7=101Y7=101；Y8=111Y8=111这时的信道转移矩阵为：这时的信道转移矩阵为：这时如果按最大似然法则译码，将为：这时如果按最大似然法则译码，将为：F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y1)=F(Y2)=F(Y3)=F(Y4)=X1=000F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111F(Y5)=F(Y6)=F(Y7)=F(Y8)=X2=111错误译码概率为：错误译码概率为：Pe 310Pe 310-4-4第15页，共25页，编辑于2022年

13、，星期四显然，若重复更多次显然，若重复更多次 一定可以进一步降低错一定可以进一步降低错误概率。可计算得误概率。可计算得但这里带来了一个新问题，当但这里带来了一个新问题，当 很大时，信息传输率就很大时，信息传输率就会降低很多。会降低很多。我们把编码后信道的我们把编码后信道的信息传输率信息传输率（也称码率）表示为（也称码率）表示为（比特（比特/码符号）码符号）若传输每个码符号平均需要若传输每个码符号平均需要 秒钟，则编码后每秒钟秒钟，则编码后每秒钟传输的信息量传输的信息量（比特（比特/秒）秒）第16页，共25页，编辑于2022年，星期四2 2、消息符号数、消息符号数在一个二元信道的在一个二元信道的

14、n次无记忆扩展信道中，输入端共有次无记忆扩展信道中，输入端共有2n个符号序列可能作为消息符号，现仅选其中个符号序列可能作为消息符号，现仅选其中M个做为个做为消息符号传递。当消息符号传递。当M选大些，选大些，pE也跟着大，也跟着大，R也大；也大；M选取小些，选取小些，pE就降低，而就降低，而R也要降低些。也要降低些。例：若信源例：若信源3 3次扩展后有次扩展后有8 8个消息符号数，如果选择其个消息符号数，如果选择其中中M个做为输入消息符号传递，则信道输出端将会个做为输入消息符号传递，则信道输出端将会收到收到8 8个输出符号，然后要从这个输出符号，然后要从这8 8个输出符号中译出个输出符号中译出M

15、个消息符号个消息符号从个符号序列中取个作为消息可以有从个符号序列中取个作为消息可以有7070种选取方法。种选取方法。选取的方法选取的方法(编码的方法编码的方法)不同，错误概率是不同的，不同，错误概率是不同的，现在我们来比较下面两种取法：现在我们来比较下面两种取法：第17页，共25页，编辑于2022年，星期四当当n=3，M=2 有有PE 310-4 R=1/3当当n=3，M=8 有有PE 310-2 R=1当当n=3，M=4 有有PE 310-2 R=2/3第第1 1种选法种选法第第2 2种选法种选法用最大似然译码规则计算用最大似然译码规则计算第18页，共25页，编辑于2022年，星期四3 3、

16、(5.2)(5.2)线性码线性码设取设取M=4,n=5，这时信息传输率这时信息传输率R=2/5 bit/码符号而输码符号而输入符号的入符号的4 4个个（M=4）个码字采用下述编码方法：个码字采用下述编码方法：设输入序列设输入序列 ，其中其中 为为 序列中第序列中第 个分量，若个分量，若 中各分量满足方中各分量满足方程程第19页，共25页，编辑于2022年，星期四正确译码概率正确译码概率错误译码概率错误译码概率第20页，共25页，编辑于2022年，星期四4 4、汉明距离、汉明距离设设 为两个为两个n长的二元码字，则码字长的二元码字，则码字 和和 之间的汉明距离定义为之间的汉明距离定义为其中，其中

17、，表模二和运算。表模二和运算。在一个码组（码字集合）中，任意两个等长码字之间，如果有在一个码组（码字集合）中，任意两个等长码字之间，如果有d个相对应的码元不同，则称个相对应的码元不同，则称d为这两个码字的汉明距离。为这两个码字的汉明距离。性质性质：1 1、非负性非负性D(X,Y)00 2 2、对称性对称性D(X,Y)=D(Y,X)3 3、三角不等式三角不等式D(X,Z)+D(Y,Z)D(X,Y)第21页，共25页，编辑于2022年，星期四在二元码在二元码C中，任意两个码字的汉明距离的最小值，称为中，任意两个码字的汉明距离的最小值，称为码码C的最小码距，即的最小码距，即5 5、用汉明距离来表示极

18、大似然译码规则、用汉明距离来表示极大似然译码规则极大似然译码准则极大似然译码准则码字码字码字码字当信道是无记忆时，则编码后信道的传递概率为当信道是无记忆时，则编码后信道的传递概率为第22页，共25页，编辑于2022年，星期四上式又称为最小距离译码准则。在二元对称信道中最小距离上式又称为最小距离译码准则。在二元对称信道中最小距离译码准则等于最大似然译码准则。在任意信道中也可采用最译码准则等于最大似然译码准则。在任意信道中也可采用最小距离译码准则，但它不一定等于最大似然译码准则。小距离译码准则，但它不一定等于最大似然译码准则。6 6、平均译码错误概率也可用汉明距离来表示、平均译码错误概率也可用汉明

19、距离来表示若设输入码字数为若设输入码字数为M(并设输入等概率分布并设输入等概率分布)，平均译，平均译码错误概率码错误概率或或第23页，共25页，编辑于2022年，星期四6.3 6.3 有噪信道编码定理有噪信道编码定理定理定理6.1 6.1 有噪信道编码定理：设离散无记忆信道有噪信道编码定理：设离散无记忆信道 为信道传递概率，其信道容量为为信道传递概率，其信道容量为 。当信息传输率。当信息传输率 时，只要码长时，只要码长 足够长，总可以在输入足够长，总可以在输入 符号集符号集中找到中找到M 2 2n n(C+)(C+)个码字组成的一组码和相应的译码规个码字组成的一组码和相应的译码规则，使译码的平

20、均错误概率任意小（则，使译码的平均错误概率任意小（）。）。定理定理6.26.2有噪信道编码逆定理（定理有噪信道编码逆定理（定理6.16.1的逆定）：设的逆定）：设离散无记忆信道离散无记忆信道 ，其信道容量为，其信道容量为 。当信息。当信息传输率传输率 则无论码长则无论码长n多长，总也找不到一种编多长，总也找不到一种编码码 ，使译码的错误概率任意小。证明略。，使译码的错误概率任意小。证明略。第24页，共25页，编辑于2022年，星期四1 1）若若M22n n(C-)(C-)，则则存存在在这这样样的的码码及及相相应应的的译译码码规规则则，当当n足足够够大大时时，使使信信道道输输出出的的错错误误概概率率PE任任意意小小；2 2）若若M=2=2n n(C+)(C+)则则无无论论n n多多大大，也也找找不不到到一一种种编编码码，使译码错误概率使译码错误概率PE任意小任意小。某某离离散散无无记记忆忆信信道道有有r个个输输入入，s个个输输出出，信信道道容容量量为为C，在在输输入入rn个个符符号号中中选选出出M个个码码字字组组成成一一种种码，设码，设是任意小的正数，是任意小的正数，第25页，共25页，编辑于2022年，星期四