编码理论第7章课件.ppt

1、7.1信道编码的基本概念 7.1.1基本概念 7.1.2平均错误概率 7.1.3费诺不等式7.2 译码准则 7.2.1 最大后验概率译码准则 7.2.2 最大似然译码准则7.3编码原则 7.3.1编码的功能 7.3.2最小汉明距离译码准则 7.3.3编码原则7.4抗干扰信道编码定理 7.4.1抗干扰信道编码定理 7.4.2抗干扰信道编码定理的逆定理第7章 纠错编码原理7.1 信道编码基本概念 7.1.1 基本概念 无失真信源编码是在无噪信道的背景下，用无噪信道的输入符号集当作码符号集，对信源符号或符号序列编出的惟一可译码，使信源符号适合信道的传输，以保证在无噪信道中无失真地传输信源发生的消息。

2、同时还要求编码是有效的，使每一信源符号所需的平均码符号数尽量的小。无噪信道问题，实质上是信源本身的问题。无失真信源编码，实际上只是用无噪信道的输入符号集作为码符号集，对信源符号的形式作一一对应的变换，并且充分而合理地利用和挖掘信源本身的统计特性，以期得到尽可能短的平均码长。无失真信源编码实质上是信源领域自身的问题。信道编码的任务就是构造出以最小多余度代价换取最大抗干扰性能的“好码”。一个好的错误控制编码方案的目标是:(1)用可以纠正的错误个数来衡量的纠错能力;(2)快速有效地对消息进行编码;(3)快速有效地对接收到的消息进行译码;(4)单位时间内所能传输的信息比特数尽量大(即有少的冗余度)。7

3、.1.2 平均错误概率 为了达到信息传输的目的，人们总是根据一定的判决准则，设计一个单值函数 使每一种可能的输出符号与一个唯一的输入符号一一对应，则函数就被称为译码函数或译码规则。译码函数或译码规则。若信道对输入符号集、输出符号集分别为 一共可构成种 不同的译码规则。例如二进制对称信道，输入符号集及输出符号集均为 则可构成种 译码规则。即 译码规则(1)：F(0)=0,F(1)=0;译码规则(2)：F(0)=0,F(1)=1;译码规则(3)：F(0)=1,F(1)=0；译码规则(4)：F(0)=1,F(1)=1。sjriabFij,.,2,1;,.,2,1,)(raaaX,.,21sbbbY,

4、.,21sr 1,0422sr 如二进制对称信道传递矩阵 采取译码规则(2)：则信道输出端出现“0”和“1”的正确译码概率分别是 在这种译码规则下，从统计的观点看，信道输出端出现四个符号“0”(或“1”)，只能有一个“0”(或“l”)能得到正确译码。采用译码规则(3)。信道输出端出现“0”和“1”的正确译码概率分别是 在这种译码规则下，从统计的观点看，信道输出端出现四个符号“0”(或“l”)，就有三个能得到正确译码。可见不同的译码规则确实会引起不同的可靠程度。在一个完整的信息传输过程中，译码规则对信息传输的可靠性有重大影响。因此，有必要深入讨论译码规则与信息传输可靠性之间的关系。4143143

5、41010P4100pYXp4111pYXp4301pYXp4310pYXp 在译码过程中，若确定了译码规则，那么当信道输出端出现某输出符号，则一定按规定好的译码规则译成相应的输入符号,显然，这就是正确译码；否则为错误译码。信道输出端收到某符号后错误译码的概率 对于信息传输系统来说，人们的兴趣不仅仅停留在个别的输出符号的正确或错误译码概率的表述上，更重要的是要描述在信道的输出端，每收到一个符号的平均正确译码或平均错误译码的概率。也就是从平均的意义上来说，在信道输出端每收到一个符号，发生正确译码或错误译码的可 能性的大小。同样，由(7-4)式可知，在信道输出端，每收到输出Y中一个符号的平均平均错

6、误译码概率错误译码概率应该是(7-4)式所示后验概率在信道输出随机变量Y的概率空间中的统计平均值，即)47()(11jijrjejbabFpppjijsjjejsjjebabFpbppbpP)(1)()(11jijsjjsjjbabFPbpbp)()()(11)57()()(11jijsjjbabFPbp 说明:(7-5)式所示的平均错误译码概率，表示在信道输出端，平均 每收到一个符号，产生错误译码可能性的大小。平均错误译码概 率越大，表示在信道输出端平均每收到一个符号产生错误译码的 可能性越大；平均错误译码概率越小，表示在信道输出端平均每 收到一个符号产生错误译码的可能性越小。显然，产生错误

7、译码的可能性越大，意味着信息传输的可靠 性越差；产生错误译码的可能性越小，意味着信息传输的可靠性 较好。所以，可把平均错误译码概率当作衡量信息传输的可靠性的标准。(7-5)式进一步指明了，平均错误译码概率，取决于信道输 出随机变量Y的概率空间、信道的后验概率分布以及人们规定好 的译码规则。那么，对于传递概率固定的给定信道来说，当信道的输入符 号，即信源的输出符号的概率分布确定后，不同的译码规则就有 不同的平均错误译码概率。译码规则是人们根据一定的准则予以选择的，所以选择合适 的译码规则，就可成为降低平均错误译码概率，提高信息传输有效性的一种可控制的手段。7.1.3 费诺不等式 著名的费诺(Fa

8、no)不等式正确地描述了平均错误译码概率与信道疑义度H(XY)的内在联系，即 费诺不等式并没有指定在什么样的准则下选择译码规则,所以，虽然平均错误译码概率与选择的译码规则有关，但不论采用什么准则选择译码规则，费诺不等式(7-6)都是普遍成立的。费诺不等式(7-6)表明，收到信道输出随机变量后，对输入随机变量仍然存在的平均不确定性H(XY)由二部分组成：第一部分是收到输出随机变量后，按选则的译码规则译码时，是否产生错误译码的平均不确定性H()；第二部分是当平均错误译码概率为时，到底是哪一个信源符号被错误译码的最大平均不确定性1oga(r-1)。)67)(1(log)()|(rPPHYXHaee7

9、.2 译码准则7.2.1 最大后验概率译码准则 按什么准则来选择合适的译码规则，使其平均错误译码概率达到最小，是提高由给定信源、给定信道组成的信息传输系统的可靠性的关键问题。设基本离散信道传递矩阵为由可得 个确定的后验概率,同样把这确定的 后验概率排列成一个后验概率矩阵)()()()()()()()()(2122221211211121rsrrrsssabpabpabpaabpabpabpaabpabpabpabbbPriijiijijijijiabpapabpapbpabpapbap1)()()()()()()()()87(,.,2,1;,.,2,1sjri)(sr)(sr 后验概率矩阵 由

10、给定的信源X的概率分布和信道的传递概率，可求得信道输出随机变量Y的s个概率分量 再把注意力回到(7-5)式所示的平均错误译码概率 上来，(7-5)式指明了，平均错误译码概率，取决于信道输出随机变量Y的概率空间、信道的后验概率分布以及人们规定好的译码规则。(7-8)和(7-10)表明，对于给定信源和给定信道来说，后验概率和信道输出随机变量Y的概率分布也都是固定不变的。显然，要使平均错误译码概率最小，势必要使达到最大。势必要使 达到最大。)97()()()()()()()()()(2122212212111121srrrrsssbapbapbapabapbapbapabapbapbapabbbP)

11、107(,.,2,1,)()()(1sjabpapbpriijijjijsjjebabFPbpP)()(11jijsjjbabFPbp)()(1jijbabFP)(sj,.,2,1 若把这个最大者所对应的信源符号记为 ，即有 因此必须选择译码规则 这就是最大后验概率译码准则。由最大后验概率译码函数构成的译码规则，一定能使平均错误译码概率达到最小值 由此可见，采用最大后验概率准则选择译码规则，一定能使平均错误译码概率达到最小值。而最小平均错误译码概率取决于给定信源和给定信道的统计特性。这就是说，当信源和信道给定后，信息传输的可靠性最高程度也就确定了。而这个最高的可靠程度，必须用最大后验概率准则来

12、选则译码规则，才能得以实现。)()(jijbapbap)137)(,.,2,1;,.,2,1(sjri abFj)(a)157(,.,2,1sj)167()()(1minsjiijieabpapP例7-1设某信道的信道矩阵及信道输入符号的概率分别为试选择译码规则，使其平均错误译码概率达到最小值,并计算其值?解:因信道输入符号非先验等概，故只能采用最大后验概率准则选择译码规则。由(7-8)式和(7-9)式计算出后验概率矩阵考虑信道输出符号与信道输入符号 一一对应，选择译码译码规则采用最大后验概率准则选择译码规则的最小平均错误译码概率4.03.03.05.03.02.02.03.05.032132

13、1aaabbbP 27.020.015.033.020.010.040.060.075.03213211aaabbbp51)()(,53)(321apapap233211)()()(abFabFabF54.0)()(31minjiijieabpapP7.2.2 最大似然译码准则 若要用最大后验概率准则选择译码规则,则首先要根据给定的信源统计特性和给定的信道统计特性，由(7-8)式算出与有关的r个后验概率。显然，这会给具体操作带来一些困难和不方便。在某些特定条件下，信源等概时,最大后验概率准则能得到一定程度的简化，因为则可有选择译码规则 这种选择译码规则的准则，称之为最大似然译码准则。显然，最大

14、似然准则是在信道输入符号(信源输出符号)先验等概特定条件下的最大后验概率准则，其平均错误译码概率同样达到最小值，由(7-16)和(7-17)式，得)()()()()()()()(jijijijjjbpabpapbapbpabpapbapsjiijabpr1)(1)()(ijjabpabp abFj)(sj,.,2,1),.,2,1;,.,2,1(sjrisjiijieabpapP1min)()(例7-2设某信道的信道矩阵及信道输入符号的概率分别为试选择译码规则，使其平均错误译码概率达到最小值,并计算其值?解:因信道输入符号先验等概，故采用最大似然准则选择译码规则。按最大似然准则得到译码规则,并

15、考虑信道输出符号与信道输入符号 一一对应，选择译码函数 所以，在采用最大似然准则选择译码规则时，就不必像一般的最大后验概率准则那样，由给定信道矩阵中的信道传递概率(前向概率)换算成后验概率(后向概率)，再比较后验概率的大小来选择译码规则了。这就是最大似然准则比最大后验概率准则的方便之处。采用最大似然准则选择译码规则的最小平均错误译码概率的具体计算值4.03.03.05.03.02.02.03.05.0321321aaabbbP 31)()()(321apapap233211)()()(abFabFabF31min)(1jiijeabprP5667.0)4.02.0()3.03.0()3.02.

16、0(317.3 编码原则 7.3.1 编码的功能 下面以二元对称信道为例说明编码的作用。例7-2二元对称离散无记忆信道的信道矩阵 设p=0.01,输入符号“0”和“1”先验等慨，分析其直接传输及编码传输的效果。解：因为信源先验等慨，则采用最大似然准则选择译码规则平均错误译码概率必定达到最小值0.01；99.001.0101.099.0010P 对信道输入符号“0”和“1”进行重复编码，把“0”变成“000”，把“1”变成“111”。这时，采用最大似然准则选择译码规则，最小平均错误译码概率 若选“000”代表信源符号“0”；选“001”代表信源符号“1”，这种译码规则的最小平均错误译码概率 0.

17、01。在随机编码中码字的不同选择，会导致不同的最小平均错误译码概率，那么应遵循什么原则挑选码字，才能得到尽可能小的最小平均错误译码概率呢?下面讨论这个问题。4103 7.3.2 最小汉明距离译码准则 简单重复编码减少平均错误译码概率是以降低信息传输率R作为代价的。即“牺牲有效性，换取可靠性”。现在要讨论的问题是,在随机编码中，当消息数M和码字长度N保持不变的条件下，即信道信息传输率(码率)保持不变条件下，应遵循什么原则挑选码字，才能得到尽可能小的最小平均错误译码概率?信道的输入端有M个长度为N的由“0”和“1”组成的码符号序列(码字),信道的输出端有 个长度为N的码符号序列。离散无记忆信道的N

18、次扩展信道有 个传递概率，它们是NM 2N2(7-23)式可由汉明距离表示为 在M个消息先验等概的条件下，采用最大似然准则选择译码规则。对 来说，若有 即)()(2121iNiijNjjijaaabbbPP)237)()()(2211iNjNijijabpabpabPNkikjkijabpp1)()(个个),(),(.jijidNdpppppp),(),(jijidNdpp)247(2,.,2,1;,.,2,1NjMi)257()()(),(),(),(),(*jjijjdNdijdNadjpppppp),(),(),(),(jjijjdNddNadpppp)267(2,.,2,1;,.,2,

19、1NjMij 考虑到在一般情况下都有 ，且 ，所以(7-26)式又可改写为 则选择译码规则 (7-27)和(7-28)式就是用汉明距离“语言”表述的最大似然准则。它表明，在信道M个输入消息先验等概的条件下，离散无记忆信道的N次扩展信道的某一输出序列，翻译成与的汉明距离中的最小者所对应的输入消息,则其平均错误译码概率达到最小值。(7-27)和式(7-28)意味着把翻译成与之最相似的输入消息。这就是为什么把这个准则称之为“最大似然”准则的由来。21ppp),(),(jijdd)277(2,.,2,1;,.,2,1,NjMiMjF,.,)(21)287(2,.,2,1Nj (7-21)式所示的采用最

20、大似然准则选择译码规则所得的最小平均错误译码概率，也可用汉明距离表示为 由(7-16)式可知，采用最大似然准则选择译码规则所得的最小平均错误译码概率还可表示为另一种形式)297(1)(11),(),(1minNjijiNrjidNdrjiijeppMPMP)307(11)(111),(),(1*minNjijNrjdNdrjjeppMPMP (7-29)和(7-30)式表明，采用最大似然准则选译码规则所得的最小平均错误译码概率取决于：(1)先验等概的消息数M；(2)随机编码的码字长度N；(3)离散无记忆信道N次扩展信道的输出序列与译码函数规定的翻译码字之间的汉明距离;(4)离散无记忆信道N次扩

21、展信道的输出序列与除了翻译码字以外的其它码字之间的汉明距离。那么，在保持一定的信道的信息率，即码率R的前提下(即保持先验等概的消息数M和码字长度N不变的前提下)，最小平均错误译码概率就取决于汉明距离。信道编码的任务就是保持码率R在一定水平(保持M和N不变)的前提下，采用正确的方法选择M个码字，使最小平均错误译码概率尽量小。(7-29)和(7-30)式就指出了正确选择M个码字，使平均错误译码概率达到最小所必须遵循的原则。那么应该道循什么样的原则，才能恰当选择M个码字呢?下面介绍这个问题。7.3.3 编码原则 假定二进制对称信道(BSC)的正确传递概率远大于 错误传递概率。在这样的假定下，由(7-

22、29)式可知，N次扩展离散无记亿信道的输出序列与除了译码函数规定的相应码字以外的(M一1)个码字的汉明距离 越大，其最小平均错误译码概率就越小。即与这(M1)个其它不对应的码字之间越不相似，其最小平均错误译码概率就可越小。另一方面，由(7-30)式可知，N次扩展离散无记忆信道的输出序列与译码函数规定的相应码字之间的汉明距离越小，其最小平均错误译码概率就越小。即与译码函数规定的码字之间越相似，其最小平均错误译码概率就越小。结论：如消息数M和码字长度N保持不变，信道信息传输率(码率)保持不变，同时又要使最小平均错误译码概率尽量小。一方面要尽量缩短N次扩展信道的输出序列与译码函数规定的翻译码字之间的汉明距离;另一方面又要尽量扩大N次扩展信道的输出序列与除了翻译码字以外的其它码字之间的汉明距离。那么，为了要同时满足这两方面的要求，在从 个长度为N的码符号序列中选择M个作为代表消息的码字的选择过程中，必须遵循这样的原则：M个码字中，任何两个不同的码字间的汉明距离要尽量大。换句话说，挑选出来的M个码字之间，越不相似越好。这就是随机编码必须遵循的原则。