《编码理论第7章》由会员分享，可在线阅读，更多相关《编码理论第7章（24页珍藏版）》请在金锄头文库上搜索。
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)单位时间内所能传输的信息比特数尽量大(
3、即 有少的冗余度)。 7.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。 如二进制对称信道传递矩阵 采取译码规则(2)：则信道输出端出
4、现“0”和“1”的正确译码概率分 别是 在这种译码规则下，从统计的观点看，信道输出端出现四个符号 “0”(或“1”)，只能有一个“0”(或“l”)能得到正确译码。 采用译码规则(3)。信道输出端出现“0”和“1”的正确译码概率 分别是 在这种译码规则下，从统计的观点看，信道输出端出现四个 符号“0”(或“l”)，就有三个能得到正确译码。 可见不同的译码规则确实会引起不同的可靠程度。在一个完整的 信息传输过程中，译码规则对信息传输的可靠性有重大影响。因 此，有必要深入讨论译码规则与信息传输可靠性之间的关系。 在译码过程中，若确定了译码规则，那么当信道输出端出现某输出符 号，则一定按规定好的译码规
5、则译成相应的输入符号, 显然，这就是正确 译码；否则为错误译码。 信道输出端收到某符号后错误译码的概率 对于信息传输系统来说，人们的兴趣不仅仅停留在个别的输出符号 的正确或错误译码概率的表述上，更重要的是要描述在信道的输出端，每 收到一个符号的平均正确译码或平均错误译码的概率。也就是从平均的意 义上来说，在信道输出端每收到一个符号，发生正确译码或错误译码的可 能性的大小。 同样，由(7-4)式可知，在信道输出端，每收到输出Y中一个符号的平均 错误译码概率应该是(7-4)式所示后验概率在信道输出随机变量Y的概率空 间中的统计平均值，即 说明: (7-5)式所示的平均错误译码概率，表示在信道输出端
6、，平均 每收到一个符号，产生错误译码可能性的大小。平均错误译码概 率越大，表示在信道输出端平均每收到一个符号产生错误译码的 可能性越大；平均错误译码概率越小，表示在信道输出端平均每 收到一个符号产生错误译码的可能性越小。 显然，产生错误译码的可能性越大，意味着信息传输的可靠 性越差；产生错误译码的可能性越小，意味着信息传输的可靠性 较好。 所以，可把平均错误译码概率当作衡量信息传输的可靠 性的标准。 (7-5)式进一步指明了，平均错误译码概率，取决于信道输 出随机变量Y的概率空间、信道的后验概率分布以及人们规定好 的译码规则。 那么，对于传递概率固定的给定信道来说，当信道的输入符 号，即信源的
7、输出符号的概率分布确定后，不同的译码规则就有 不同的平均错误译码概率。 译码规则是人们根据一定的准则予以选择的，所以选择合适 的译码规则，就可成为降低平均错误译码概率，提高信息传输有 效性的一种可控制的手段。 7.1.3 费诺不等式 著名的费诺(Fano)不等式正确地描述了平均错误译码 概率与信道疑义度H(XY)的内在联系，即 费诺不等式并没有指定在什么样的准则下选择译码 规则,所以，虽然平均错误译码概率与选择的译码规则 有关，但不论采用什么准则选择译码规则，费诺不等式 (7-6)都是普遍成立的。 费诺不等式(7-6)表明，收到信道输出随机变量后， 对输入随机变量仍然存在的平均不确定性H(XY
8、)由二 部分组成： 第一部分是收到输出随机变量后，按选则的译码规 则译码时，是否产生错误译码的平均不确定性H()； 第二部分是当平均错误译码概率为时，到底是哪一 个信源符号被错误译码的最大平均不确定性1oga(r-1)。 7.2 译码准则7.2.1 最大后验概率译码准则 按什么准则来选择合适的译码规则，使其平均错误译码概率达到最小，是 提高由给定信源、给定信道组成的信息传输系统的可靠性的关键问题。 设基本离散信道传递矩阵为由可得 个确定的后验概率,同样把这确定的 后验概率排列成一个 后验概率矩阵后验概率矩阵 由给定的信源X的概率分布和信道的传递概率，可求得信道输出随机变量 Y的s个概率分量 再
9、把注意力回到(7-5)式所示的平均错误译码概率 上来，(7-5)式指明了，平均错误译码概率，取决于信道输出随机变量Y的概率 空间、信道的后验概率分布以及人们规定好的译码规则。 (7-8)和(7-10)表明，对于给定信源和给定信道来说，后验概率和信道输出 随机变量Y的概率分布也都是固定不变的。显然，要使平均错误译码概率最小 ，势必要使达到最大。势必要使 达到最大。 若把这个最大者所对应的信源符号记为 ，即有 因此必须选择译码规则 这就是最大后验概率译码准则。 由最大后验概率译码函数构成的译码规则，一定能使平均错误译码概率 达到最小值 由此可见， 采用最大后验概率准则选择译码规则，一定能使平均错误
10、译 码概率达到最小值。而最小平均错误译码概率取决于给定信源和给定信道的 统计特性。这就是说，当信源和信道给定后，信息传输的可靠性最高程度也 就确定了。而这个最高的可靠程度，必须用最大后验概率准则来选则译码规 则，才能得以实现。例7-1设某信道的信道矩阵及信道输入符号的概率分别为试选择译码规则，使其平均错误译码概率达到最小值,并计算其值? 解: 因信道输入符号非先验等概，故只能采用最大后验概率准则选择译码 规则。由(7-8)式和(7-9)式计算出后验概率矩阵考虑信道输出符号与信道输入符号 一一对应，选择译码译码规则采用最大后验概率准则选择译码规则的最小平均错误译码概率7.2.2 最大似然译码准则
11、 若要用最大后验概率准则选择译码规则,则首先要根据给定的信源统计特性 和给定的信道统计特性，由(7-8)式算出与有关的r个后验概率。显然，这会给 具体操作带来一些困难和不方便。在某些特定条件下，信源等概时,最大后验 概率准则能得到一定程度的简化，因为则可有选择译码规则 这种选择译码规则的准则，称之为最大似然译码准则。 显然，最大似然准则是在信道输入符号(信源输出符号)先验等概特定条件 下的最大后验概率准则，其平均错误译码概率同样达到最小值，由(7-16)和(7- 17)式，得例7-2设某信道的信道矩阵及信道输入符号的概率分别为试选择译码规则，使其平均错误译码概率达到最小值,并计算其值? 解:因
12、信道输入符号先验等概，故采用最大似然准则选择译码规则。按最 大似然准则得到译码规则,并考虑信道输出符号与信道输入符号 一一对应，选 择译码函数 所以，在采用最大似然准则选择译码规则时，就不必像一般的最大后验概 率准则那样，由给定信道矩阵中的信道传递概率(前向概率)换算成后验概率( 后向概率)，再比较后验概率的大小来选择译码规则了。这就是最大似然准则 比最大后验概率准则的方便之处。采用最大似然准则选择译码规则的最小平 均错误译码概率的具体计算值7.3 编码原则 7.3.1 编码的功能 下面以二元对称信道为例说明编码的作用。 例7-2二元对称离散无记忆信道的信道矩阵 设p=0.01,输入符号“0”
13、和“1”先验等慨，分析其直接传输 及编码传输的效果。 解：因为信源先验等慨，则采用最大似然准则选择译码 规则平均错误译码概率必定达到最小值0.01； 对信道输入符号“0”和“1”进行重复编码，把 “0”变成“000”，把“1”变成“111”。这时，采用最大 似然准则选择译码规则，最小平均错误译码概率 若选“000”代表信源符号“0”；选“001”代表信 源符号“1”，这种译码规则的最小平均错误译码 概率 0.01。 在随机编码中码字的不同选择，会导致不 同的最小平均错误译码概率，那么应遵循什么原 则挑选码字，才能得到尽可能小的最小平均错误 译码概率呢?下面讨论这个问题。 7.3.2 最小汉明距
14、离译码准则 简单重复编码减少平均错误译码概率是以 降低信息传输率R作为代价的。即 “牺牲有效性 ，换取可靠性”。 现在要讨论的问题是,在随机编码中，当消 息数M和码字长度N保持不变的条件下，即信道 信息传输率(码率)保持不变条件下，应遵循什么 原则挑选码字，才能得到尽可能小的最小平均错 误译码概率? 信道的输入端有M个长度为N的由“0”和“1”组 成的码符号序列(码字),信道的输出端有 个长 度为N的码符号序列。离散无记忆信道的N次扩 展信道有 个传递概率，它们是 (7-23)式可由汉明距离表示为 在M个消息先验等概的条件下，采用最大似然准则选择译码规则 。对 来说，若有 即 考虑到在一般情况下都有 ， 且 ，所以 (7-26)式又可改写为 则选择译码规则 (7-27)和(7-28)式就是用汉明
