信息论-基础理论与应用第三版-第六章-讲义(课堂PPT)课件.ppt

1、第第6 6章章 有噪信道编码定理有噪信道编码定理 6.1 6.1 错误概率与译码规则错误概率与译码规则6.2 6.2 错误概率与编码方法错误概率与编码方法6.4 6.4 有噪信道编码定理有噪信道编码定理6.5 6.5 联合信源信道编码定理联合信源信道编码定理1 前面已经从理论上讨论了，对于无噪无损信道前面已经从理论上讨论了，对于无噪无损信道只要对信源进行适当的编码，总能以只要对信源进行适当的编码，总能以信道容量信道容量无差无差错的传递信息。但是一般信道总会存在噪声和干扰，错的传递信息。但是一般信道总会存在噪声和干扰，信息传输会造成损失。信息传输会造成损失。 那么在那么在有噪信道中有噪信道中怎样

2、能使消息传输发生的错误怎样能使消息传输发生的错误最少？进行无错传输的可达的最少？进行无错传输的可达的最大信息传输率最大信息传输率是多是多少呢？少呢？ 这就是本章所要讨论的问题。本章的核心是香农这就是本章所要讨论的问题。本章的核心是香农第二定理。第二定理。26.1 6.1 错误概率与译码规则错误概率与译码规则 为了减少传输错误，提高通信的可靠性，就必须分为了减少传输错误，提高通信的可靠性，就必须分析析错误概率错误概率与哪些因素有关，有没有办法控制？能控制与哪些因素有关，有没有办法控制？能控制到什么程度？到什么程度？ 一般地，错误概率与如下因素相关：一般地，错误概率与如下因素相关：信道的统计特性信

3、道的统计特性译码规则译码规则3例例：有一个：有一个BSCBSC信道，如图所示信道，如图所示 若收到若收到“0”0”译作译作“0”0”，收到，收到“1”1”译作译作“1”1”，则，则平均错误概率平均错误概率为：为：反之，若收到反之，若收到“0”0”译作译作“1”1”，收到，收到“1”1”译作译作“0”0”，则平均错误概率为，则平均错误概率为可见错误概率与可见错误概率与译码规则译码规则有关。有关。01011/31/32/32/301译码译码信源信源P(0)P(1)3/1)1 ()0(311) 1 (1)0()1()0(PPPPPPPeeE3/2)1 ()0(32) 1 ()0()1()0(PPPP

4、PPPeeE4译码规则译码规则： 输入符号集输入符号集 输出符号集输出符号集 译码规则译码规则()jiF ba例：例：某信道转移矩阵某信道转移矩阵0.50.30.20.20.30.50.30.30.4PriaAi,.2 , 1,sjbBj,.2 , 1,可以设计译码准则：可以设计译码准则： A A： 和和 B B：11()F ba22()F ba33()F ba11()F ba23()F ba32()F ba5总的译码规则数目总的译码规则数目 信道的信道的s s个输出符号的每一个译码输出有个输出符号的每一个译码输出有 r r 种选择，因此，总的种选择，因此，总的 译码规则总数为译码规则总数为译

5、码规则的选择依据译码规则的选择依据 一个自然的依据就是使一个自然的依据就是使平均错误概率最小平均错误概率最小。 为了选择译码规则，需要计算为了选择译码规则，需要计算平均错误概率平均错误概率。 srsr平均错误概率分析：平均错误概率分析： 译码规则确定后，设信道输出端收到译码规则确定后，设信道输出端收到 时一定译为时一定译为 。如果发送端刚好发送的就是如果发送端刚好发送的就是 ，则为，则为正确译码正确译码，译码的，译码的条件正条件正确概率确概率为：为：jb( ()/)(/)jjijP F bbP abiaia6而错误译码的概率为收到而错误译码的概率为收到 后翻译为后翻译为 ，但发送端实际上，但发

6、送端实际上发送的却不是发送的却不是 ，则为，则为错误译码，错误译码，其其条件条件错误概率错误概率为：为： jbia( /)1(/)jijP e bP ab e e表示：除了表示：除了 以外的所有以外的所有输入符号输入符号的集合。的集合。()jiF ba则可得则可得平均错误译码概率平均错误译码概率： 它表示经过它表示经过译码后译码后平均每收到一个符号所产生错误的大小，平均每收到一个符号所产生错误的大小，也称也称平均错误概率平均错误概率。sjjjjEbePbPbePEP1)/()()/(ia7条件正确概率条件正确概率 如何设计译码规则如何设计译码规则 ，使平均错误概率最小？，使平均错误概率最小？s

7、jjijsjjijsjjjEbaPbPbaPbPbePbPP111)/(max1)()/(1min()()/(min)(min()jiF ba最小错误概率准则（最大后验概率准则）最小错误概率准则（最大后验概率准则）sjjjjEbePbPbePEP1)/()()/(条件错误概率条件错误概率*()jF ba*(/)(/)jijiP abP abaa满足关系：满足关系：BbAaaji ,*因此因此应选择译码规则应选择译码规则 也即收到一个符号以后译成具有也即收到一个符号以后译成具有最大后验概率最大后验概率的那个输入符号。的那个输入符号。决定于译码规则决定于译码规则i i为待定为待定8根据贝叶斯定理，

8、上式可写成根据贝叶斯定理，上式可写成*(/) ()(/) ( )()()jjiijjP ba P aP ba P aP bP b*(/) ()(/) ()jjiiP baP aP ba P a当信源等概分布时，则最小错误概率准则变为当信源等概分布时，则最小错误概率准则变为*(/)(/)jjiP baP ba 这称为这称为最大似然译码准则最大似然译码准则，方法是收到一个，方法是收到一个 后，在信道矩后，在信道矩阵的第阵的第j j列元素中选择最大的值所对应的输入符号作为译码输出。列元素中选择最大的值所对应的输入符号作为译码输出。jb最大似然译码准则最大似然译码准则)()(*jijbaPbaP即即9

9、当译码规则确定后，可进一步计算当译码规则确定后，可进一步计算平均错误概率平均错误概率：() ( /)1()/ ()EjjjjjYYPP bP e bP F bbP b,() ()ijjjX YYp abP F b b1 ()jjYP F b b *,()ijjX YYp abP a b*,)|()()(aXYijiaXYjiabPaPbaP平均错误概率的计算平均错误概率的计算信道传递概率信道传递概率平均正确概率平均正确概率上式中，平均错误概率计算是在上式中，平均错误概率计算是在联合概率矩阵联合概率矩阵P(aP(ai i)P(b)P(bj j|a|ai i) )中：中： 1 1）先求）先求每一列

10、每一列除去除去F(bF(bj j)=a)=a* *所对应的所对应的P(aP(a* *b bj j) )以外的元素之和；以外的元素之和； 2 2）然后，对所有列求和。）然后，对所有列求和。10（选讲选讲）当然，也可以对）当然，也可以对联合概率矩阵联合概率矩阵P(aP(ai i)P(b)P(bj j/a/ai i) )中：中：1 1）先求）先求每一行每一行中除去中除去F(bF(bj j)=a)=ai i* *所对应的所对应的P(aP(ai ib bj j) )以外的元素之和以外的元素之和; ; 2 2）然后，对各行的和求和。）然后，对各行的和求和。 ()(/)()EijijXYPP aP baF

11、ba( )( )iieXP a P如果先验概率相等，则：如果先验概率相等，则：( )1iEeXPPrXbaYijiaXYijiEjabPaPabPaPP)*(,)|()()|()(*对应的某个输入符号某个输入符号a ai i传输引起的传输引起的错误概率错误概率即：即：具体计算如下：具体计算如下：11例：例：某信道某信道0.50.30.20.20.30.50.30.30.4P1 1）若根据）若根据最大似然准则最大似然准则选择译码函数为选择译码函数为B B：112332( )()()F baF baF ba*,11( / )(0.20.3)(0.30.3)(0.20.4)0.56733EY XaP

12、P b a若输入等概率，则平均错误概率为若输入等概率，则平均错误概率为若输入若输入不等概分布不等概分布 ，则错误概率为：，则错误概率为：123111(), (), ()442P aP aP a6 . 0)5 . 02 . 0(2/1)3 . 03 . 0(4/1)2 . 03 . 0(4/1)|()(*, abPaPPaXYE122 2）采用）采用最小错误概率译码准则最小错误概率译码准则，则联合矩阵为：，则联合矩阵为：0.1250.0750.05()0.050.0750.1250.150.150.2ijP ab 所得译码函数为：所得译码函数为：C C：132333( )()()F baF ba

13、F ba)|()()(ijijiabPaPbaP *, 5 . 0)125. 005. 0()075. 0075. 0()05. 0125. 0()()|()(*EPbaPabPaPPjiaXYijaXYiE平均错误概率：平均错误概率：136.2 6.2 错误概率与编码方法错误概率与编码方法 一般信道传输时都会产生错误，而选择译码准则一般信道传输时都会产生错误，而选择译码准则并并不会消除错误不会消除错误，那么如何减少错误概率呢？下边讨论通，那么如何减少错误概率呢？下边讨论通过过编码方法编码方法来降低错误概率。来降低错误概率。例例：对于如下二元对称信道：对于如下二元对称信道01010.990.9

14、90.010.0120.0110EP按照最大似然准则译码，按照最大似然准则译码，14 如何提高信道传输的正确率呢？可用重复消息的方法，即尝试如何提高信道传输的正确率呢？可用重复消息的方法，即尝试扩展信道的方法。扩展信道的方法。未用的码字未用的码字（禁用码字）（禁用码字）001001010010011011100100101101110110用作消息的码字用作消息的码字（许用码字）（许用码字）000 000 （表示（表示0 0）111 111 （表示（表示1 1）输出端输出端接收序列接收序列000000001001010010011011100100101101110110111111二元对称信

15、二元对称信道的三次扩道的三次扩展信道展信道876543218765432115则信道矩阵为：则信道矩阵为：3222222332222223pp pp pppp ppppppPpppppp pppp pp pp根据根据最大似然译码准则，当最大似然译码准则，当p=0.01p=0.01，可得，可得译码函数译码函数为：为：F(000)=000 F(001)=000 F(010)=000F(000)=000 F(001)=000 F(010)=000 F(011)=111 F(011)=111F(100)=000F(100)=000 F(101)=111 F(110)=111 F(111)=111 F(

16、101)=111 F(110)=111 F(111)=111111110101100011010001000111000一位错误一位错误)01. 0(10332/1)|(1)|()(42332222223,*3*3ppppppppppppppppppPMPPPCYijijCYiE当当000000、111111等概时，平均错误概率变小了：等概时，平均错误概率变小了：20.0110EP16 现在码元个数现在码元个数n=3n=3，已经将错误概率降低了两个数量级；若重，已经将错误概率降低了两个数量级；若重复更多次，复更多次，n=5n=5，7 7，还可以进一步降低错误概率，上例中：，还可以进一步降低错误

17、概率，上例中：当当n=5n=5时时 当当n=7n=7时时 当当n=9n=9时时 当当n=11n=11时时 108751051010410EEEEPPPP 但是但是n n很大时，信道的很大时，信道的信息传输率信息传输率会降低很多：（会降低很多：（MM为为许用码许用码字字的个数，即输入消息个数，的个数，即输入消息个数，n n为编码后码字的长度）为编码后码字的长度）logMRn 在上例中：在上例中：M=2M=2当当n=1n=1时时 R=1R=1当当n=3n=3时时 R=1/3R=1/3当当n=5n=5时时 R=1/5R=1/5（比特（比特/ /码符号）码符号）（比特（比特/ /码符号）码符号）（比特

18、（比特/ /码符号）码符号）17 分析前边的例子，只用了扩展信源的两个字符，因此信息率降分析前边的例子，只用了扩展信源的两个字符，因此信息率降低了，如果把低了，如果把8 8个字符全用上，信息传输率就会回到个字符全用上，信息传输率就会回到1 1，但是此时，但是此时错误率更大了：错误率更大了：一般地，有如下规律：一般地，有如下规律： 在二元信道的在二元信道的n n次扩展信道中，选取其中的次扩展信道中，选取其中的MM个作为消息，则个作为消息，则MM大一些，大一些， 跟着大，跟着大，R R也大；也大；MM小一些，小一些， 跟着小，跟着小，R R也小。也小。EPEP),01. 0(10*31323位全正

19、确传输的概率位全正确传输的概率为为3pppPE 如果上例中，取如果上例中，取MM4 4，如：取，如：取000 011 101 110000 011 101 110为消息，则为消息，则 与与M=8M=8比较，错误率降低了，而信息率也降低了。比较，错误率降低了，而信息率也降低了。222*103EPR18另外一个问题，消息数固定而编码选取方法不同，错误率也不同。另外一个问题，消息数固定而编码选取方法不同，错误率也不同。比较两种选取方法：比较两种选取方法： 第一种：第一种： 000 011 101 110000 011 101 110 第二种：第二种： 000 001 010 100000 001 0

20、10 100 可以计算得第一种方法的错误率为可以计算得第一种方法的错误率为 第二种方法的错误率为第二种方法的错误率为22*1022.28*10 比较可知，第一种方法好。仔细观察发现：比较可知，第一种方法好。仔细观察发现： 在第一种方法中，如果在第一种方法中，如果 000 000 有一位出错，就可以判定出错了；有一位出错，就可以判定出错了； 而在第二种方法中，如果而在第二种方法中，如果000000中任何一位出错，就变成了中任何一位出错，就变成了其他的其他的合法的码字合法的码字，我们无法判断是否出错。，我们无法判断是否出错。 再仔细观察，发现第二种方法中，码字之间太相似。再仔细观察，发现第二种方法

21、中，码字之间太相似。19码字距离：码字距离： 长度为长度为n n的两个码字对应位置上不同码元的个数。通常称的两个码字对应位置上不同码元的个数。通常称为为汉明距离汉明距离： 在二元码中，码字的汉明距离：在二元码中，码字的汉明距离：1(,)nijikjkkD如：如：101111i111100j则则(,)3ijD 在某一码中，任意两个码字在某一码中，任意两个码字C Ci i、C Cj j的汉明距离的最小值称为该的汉明距离的最小值称为该码码C C的最小距离的最小距离。minmin (,)ijijdD C CCC20 码码A A码码B B码码C C码码D D消息数消息数MM2 24 44 48 8码字码

22、字000000111111000000011011101101110110000000001001010010100100000 001000 001010 011010 011100 101100 101100 111100 111最小距离最小距离dmindmin3 32 21 11 1信息传输率信息传输率R R1/31/32/32/32/32/31 1错误概率错误概率43*1022*1022.28*10210*3 很明显，很明显， 越大，越大， 越小，在越小，在MM相同时也如此。码相同时也如此。码C C中最小距离中最小距离越大，受到干扰后，越不容易成为另一码字，因而错误概率小；相反，越大，

23、受到干扰后，越不容易成为另一码字，因而错误概率小；相反，则容易干扰后变成另一码字。所以：则容易干扰后变成另一码字。所以：应尽量设法使选取的应尽量设法使选取的MM个码字中个码字中任意两两不同码字的距离尽量大。任意两两不同码字的距离尽量大。mindEP讨论讨论4 4种码的距离和错误概率（码长种码的距离和错误概率（码长=3=3）：）：21 二元信道的二元信道的译码规则译码规则可以如下规定：可以如下规定：选择选择 使之满足条件：使之满足条件：*(,)(,)jijiDD 它称为它称为最小距离译码准则最小距离译码准则，也就是，也就是收到一个码字后，把它译成与它距离收到一个码字后，把它译成与它距离（汉明距离

24、）（汉明距离）最近最近的输入码字。的输入码字。 这样这样可以使平均错误率较小。可以使平均错误率较小。最小距离译码准则最小距离译码准则njjYCF,)(*CDDiijij,),(),(*min*即：即：j*ijkijDjjDkjD最近码字最近码字接收序列接收序列D22最小距离译码准则与最大似然准则的关系最小距离译码准则与最大似然准则的关系 在在二元无记忆对称信道二元无记忆对称信道中，最小距离译码准则等于中，最小距离译码准则等于最最大似然译码准则大似然译码准则。 （略）（略）证明：证明：n n次扩展信道传递概率为：次扩展信道传递概率为：)()1 ()|().|()|()|(2211ijijnnDn

25、DijijijijppabPabPabPP大；小，小；大，若)|()|(, 2/1ijijijijPDPDp错误位数错误位数正确位数正确位数N N长接收序列长接收序列N N长发送序列长发送序列信道转移概率信道转移概率23 在任意信道中，也可以采用最小距离译码准则，但它不一在任意信道中，也可以采用最小距离译码准则，但它不一定等于最大似然准则。定等于最大似然准则。*(,)(,)jijiDDnjjYCF,)(*CDDiijij,),(),(*min*由此，按照由此，按照最大似然准则最大似然准则，应选择，应选择传递概率最大者传递概率最大者对应的输入对应的输入序列作为译码输出。序列作为译码输出。选择译码

26、函数：选择译码函数：使满足：使满足：即满足：即满足：24小小 结结 在消息数在消息数 MM和码长和码长 n n不变的时，信息传输率不变的时，信息传输率R=logM/nR=logM/n。采。采用不同的编码可获得的不同的码字距离和最小码字距离，并导致用不同的编码可获得的不同的码字距离和最小码字距离，并导致不同的平均错误概率。且不同的平均错误概率。且最小码字距离越大，平均错误概率越小。最小码字距离越大，平均错误概率越小。 因此：应尽量设法使选取的因此：应尽量设法使选取的MM个码字中任意两两不同个码字中任意两两不同码字的码字的距离距离dmindmin尽量大尽量大。 总之，在有噪信道中，除了信道本身的统

27、计特性外，传输的总之，在有噪信道中，除了信道本身的统计特性外，传输的平均错误概率与各种编译码方法相关。平均错误概率与各种编译码方法相关。编码：编码：可选择可选择MM个消息所对应得码字之间最小距离个消息所对应得码字之间最小距离d dminmin尽可能大尽可能大的编码方法。的编码方法。译码：译码：则将接收序列译成与之最近的那个码字。则将接收序列译成与之最近的那个码字。 只要码长只要码长n n足够大，合适地选择足够大，合适地选择MM个消息的对应码字，就可以个消息的对应码字，就可以使错误概率很小，而信息传输率保持一定。使错误概率很小，而信息传输率保持一定。256.3 6.3 有噪信道编码定理有噪信道编

28、码定理1 1、有噪信道编码定理、有噪信道编码定理（香农第二定理）（香农第二定理） 设一个离散无记忆信道设一个离散无记忆信道 ， 为信为信道传递概率，信道容量为道传递概率，信道容量为C C。当。当信息传输率信息传输率 R CRCRC时，则无论码长时，则无论码长n n多长，总找多长，总找不到一种编码不到一种编码 使信道输出端的平均错误译码使信道输出端的平均错误译码概率达到任意小。概率达到任意小。(2 , )nRnYxyPX),/(,logMRn26 这个定理是信道编码的理论依据，可以看出：这个定理是信道编码的理论依据，可以看出：信道信道容量容量是一个明确的分界点，当取分界点以下的信息传输是一个明确

29、的分界点，当取分界点以下的信息传输率时，率时， 以指数趋进于以指数趋进于0 0；当取分界点以下的信息传输；当取分界点以下的信息传输率时，率时， 以指数趋进于以指数趋进于1 1。 因此在任何信道中，信道容量都是可达的、最大的因此在任何信道中，信道容量都是可达的、最大的可靠信息传输率可靠信息传输率。 这个定理是一个这个定理是一个存在定理存在定理，它说明错误概率趋于，它说明错误概率趋于0 0的的好码是存在的。但它没有给出一个具体可构造的编码方好码是存在的。但它没有给出一个具体可构造的编码方法，在它的证明过程中，码是随机的选取的。然而，它法，在它的证明过程中，码是随机的选取的。然而，它有助于指导各种通

30、信系统的设计，有助于评价各种系统有助于指导各种通信系统的设计，有助于评价各种系统及编码的效率。及编码的效率。EPEP意意 义义27 从香农第一、第二定理可以看出，要做到有效和可靠从香农第一、第二定理可以看出，要做到有效和可靠的传输信息，可以将通信系统设计成两部分的组合，即的传输信息，可以将通信系统设计成两部分的组合，即信信源编码源编码和和信道编码信道编码两部分：两部分： 1 1）首先通过信源编码，用尽可能少的信道符号来表达）首先通过信源编码，用尽可能少的信道符号来表达信源，尽可能减少编码后信源的数据的剩余率；信源，尽可能减少编码后信源的数据的剩余率； 2 2）然后针对信道，对信源编码后的数据独

31、立的进行信）然后针对信道，对信源编码后的数据独立的进行信道编码，适当道编码，适当增加一些剩余度增加一些剩余度，使能纠正和克服信道中引，使能纠正和克服信道中引起的错误和干扰。起的错误和干扰。 理论分析表明，只要满足香农第一定理和第二定理，理论分析表明，只要满足香农第一定理和第二定理，用用两步编码两步编码的方法传输信息和的方法传输信息和一步编码一步编码的方法传输信息其的方法传输信息其效果是一样的。效果是一样的。（选讲）（选讲）6.5 6.5 联合信源信道编码定理联合信源信道编码定理28两步编码分析：两步编码分析：其信源压缩编码只与信源有关，不依赖于信道；其信源压缩编码只与信源有关，不依赖于信道；信

32、道编码只与信道有关，不依赖于信源。信道编码只与信道有关，不依赖于信源。如果信源编码是一一对应的无失真编码如果信源编码是一一对应的无失真编码 (RH)(RH)，则编，则编码、译码都是一一对应的映射，不会带来信息的损失；码、译码都是一一对应的映射，不会带来信息的损失；信道会导致信息有一些损失。但通过适当的信道编码信道会导致信息有一些损失。但通过适当的信道编码（RCRC），可使信道引起的损失或错误尽可能小。），可使信道引起的损失或错误尽可能小。 因此，两步处理不会带来信息的损失。因此，两步处理不会带来信息的损失。29若若 是有限符号集的随机序列，并满足是有限符号集的随机序列，并满足AEP(AEP(渐

33、进等分性渐进等分性) )，信源，信源S S的极限熵的极限熵 ，则存在，则存在信信源与信道编码源与信道编码，其，其 。反之，对于任意平稳随机序列，若极限熵反之，对于任意平稳随机序列，若极限熵 ，则，则错误概率远离错误概率远离0 0，即不可能以任意小的错误概率发送随机，即不可能以任意小的错误概率发送随机序列。序列。信源信源- -信道编码定理信道编码定理).(21nnSSSS CH0EPCH 因此，信源通过信道传输，有效和可靠地传输的因此，信源通过信道传输，有效和可靠地传输的充充要条件是要条件是 HCHC。30 可见，当且仅当可见，当且仅当信源极限熵信源极限熵HH信道容量信道容量C C，在信道上无错

34、，在信道上无错误地传输平稳信源。误地传输平稳信源。 由于两步编码方法中，数据压缩编码和数据传输编码，分由于两步编码方法中，数据压缩编码和数据传输编码，分别满足别满足HRHR和和RCRC，所以其与一步编码的效果一样。，所以其与一步编码的效果一样。 正因为通过分别进行信源的数据压缩编码和信道的数据传正因为通过分别进行信源的数据压缩编码和信道的数据传输编码，既能做到有效而可靠地传输信息，又能大大简化通信输编码，既能做到有效而可靠地传输信息，又能大大简化通信系统设计，因此在实际通信系统中得到广泛应用：系统设计，因此在实际通信系统中得到广泛应用： 针对不同的信源，如文本、图像、语音等数据压缩研究形成针对不同的信源，如文本、图像、语音等数据压缩研究形成了了数据压缩理论与技术数据压缩理论与技术； 而针对信道编码问题的研究又形成了另一独立分支而针对信道编码问题的研究又形成了另一独立分支-纠错编纠错编码理论和技术码理论和技术。316.16.36.9课后作业课后作业32