信息论部分课件第六章有噪信道编码

《信息论部分课件第六章有噪信道编码》由会员分享，可在线阅读，更多相关《信息论部分课件第六章有噪信道编码（47页珍藏版）》请在金锄头文库上搜索。

1、第六章 有噪信道编码定理,主 讲： 易 波 老 师 博一工作室2010年V.1版,主要内容,1、译码规则对错误概率的影响 2、两种典型的译码规则 3、信道编码对平均差错率和信息率的影响 4、汉明距离译码规则 5、有噪信道编码定理（香农第二定理） 6、有噪信道编码逆定理,实际信道由于信道噪声的干扰，传输错误不可避免。为了降低平均差错率，可先对消息进行编码信道编码，再送入信道传送。,6.1 译码规则对错误概率的影响,1、译码规则对错误概率的影响 译码是一种映射： ， 信道正好输入的是 =正确译码 信道输入的不是 =错误译码 译码正确概率： 译码错误概率：,平均差错率： 好的译码规则应使平均差错率小

2、。,例：信道如下，已知 四种译码规则如下,设输入概率 信道输转移概率矩阵为 将 乘以 的第i行得联合概率矩阵 译码规则F1所对应的平均差错率为,同理，其它几种译码规则对应的平均差错率分别为 4种规则相比，F3最好，F4最差。,2、两种典型的译码规则 （1）最佳译码规则 使 达到最小的译码规则最佳译码规则的 确定： 计算出所有以 为条件的输入符号的概率，即后验概率： 取最大后验概率所对应的输入符号 为译码输出。 又称最大后验概率译码规则。,最大后验概率条件可等价成最大联合概率条件 最佳译码规则又可表示成： 因此，该规则又称为最大联合概率译码规则。,2）最大似然译码规则 按最大转移概率条件来确定的

3、译码规则。 最大似然译码规则的平均差错率不是最小， 因此不是最佳的，但最易找出，只须已知 信道特性即可。,例 已知信道转移矩阵如下，试确定译码规则。 解 只知转移概率，无法找出最佳译码规则，只能采用最大似然译码规则。 将转移概率矩阵各列最大的值标出，重写转移矩阵如下：,按转移概率最大原则确定最大似然译码规则如下： 尽管一般情况下并不知道这样译码的差错率。但可以证明，当信道输入等概时，最大似然译码规则也是最佳的。,最大似然译码规则 是按最大转移概率条件确定的，即 如果输入等概，则 ，所以 得到了最大联合概率条件，由此说明， 输入等概时，最大似然译码规则与最大 联合概率译码规则等价，因此是最佳的。

4、,6.2 错误概率与编码方法,从式(5.10)可知,消息通过有噪信道传输时会发生错误,而错误概率与译码规则有关。但一般当信道给定即信道矩阵给定，不论采用什么译码规则，PE总不会等于或趋于零(除特殊信道外)。 例如，一个二元对称信道如图5.3所示 若选择最佳译码规则,则总的平均错误概率,图5.3二元对称信道,图5.4 简单的重复编码,输入是在8个可能出现的二元序列中选两个作为消息(符号),而 输出端这8个可能的输出符号都是接收序列。这时信道矩阵为,根据最大似然译码规则(假设输入是等概率的),可得简单重复编码的译码函数为,根据式(5.12)计算得译码后的错误概率为,我们也可以采用“择多译码”的译码

5、规则,即根据输出端接收序列中0多还是1多.如果有二个以上是0则译码器就判决为0,如果有二个以上是1则判决为1.根据择多译规则,同样可得到,可见择多译码准则与最大似然译码准则是一致的。 若重复更多次n=5,7,一定可以进一步降低错误概率。可算得,编码后的消息传输率(也称码率)表示为,若传输每个码符号平均需要t秒钟,则编码后每秒钟传输的信息量,此处M是输入消息(符号)的个数.logM表示消息集在等概率条件下每个消息(符号)携带的平均信息量(比特).n是编码后码字的长度(码元的个数). 根据式(5.20),对上述重复编码方法可计算得,当n=1(无重复),M=2,设t=1秒时,n=3(重复三次),M=

6、2时,n=5时,n=11时,图5 . 5 二元对称信道 中PE和R的关系,如何解决PE和R的矛盾问题呢？能否找到一种更好的编码方法，使PE相当低，而R却保持在一定水平上呢？仙侬有噪信道编码定理从理论上证明是可能的。,由此得到一个启发,如果在扩展信道的输入端把8个可能作为消息的二元序列取作为消息M=8,则每个消息携带的平均信息量就是logM=log8=3比特,而传递一个消息所需的符号数仍为三个二元码符,则R就是提高到1比特/码符.这时信道如图所示。,只有符号序列中每个符号都不发生错误才能正确传输。所以得到正确传输概率为 /P3，于是错误概率为：,若在三次无记忆扩展信道中，取M=4，取如下4个符号

7、序列作为消息,按照最大似然译码规则，可计算出错误概率为,与M=8的情况比较，错误概率降低了,而信息传输率与降低了,即,从2n=23=8个符号序列中取M=4个作为消息可能有70种选取方法.选取的方法(编码的方法)不同,错误概率是不同的,现在我们来比较下面两种取法:,已求得第I种选法的错误概率为 PE 2 10-2 用最大似然译码规则,计算出第II种选法的错误概率为 PE 2.28 10-2,比较这两种选法可知第II种码要差些(两者R相同).对于第I种码来说,当接收到发送的4个消息中只要任一位码元发生错误时,就可判断消息在传输中发生了错误,但无法判断由那个消息发生什么错误而来的.而对第II种码来说

8、,当发送消息“000”传输时其中任一位码元发生错误,就变成了其他三个可能发送的消息,根本无法判断传输时有无发生错误.可见,错误概率与编码方法有很大关系. 这时信息传输率为,3、信道编码对平均差错率和信息率的影响 仅仅依靠选择合适的译码规则，往往还不能满足通信质量的需要。为了进一步降低，还必须进行信道编码。一般有以下两种编码： 1）“简单重复”编码 2）对信源符号串编码,汉明距离 汉明距离（Hamming）用于定量描述符号序列之间的相似程度。 定义 两个等长符号序列 和 之间的汉明距离，是 与 之间对应位置上不同符号的个数，记为 ，例如 小意味着 与 的相似程度高，否则 与 的相似程度低。,汉明

9、距离 满足如下性质（公理）： （1）非负性： 当且仅当 时等号成立； （2）对称性： （3）三角不等式：,对于二元信道,即对于二元码,汉明距离可表达成下述关系式:,在任一码书中,码的最小距离dmin与该码的译码错误概率有关。,对于二元对称信道，可以根据汉明距离来决定译码规则。 最小汉明距离译码规则： 其含义是：将接收序列 译为与之 最相似的输入码字 。,设输入序列,中各分量满足方程,就选取此序列ai作为码字(其中 为模二和运算), 则得一种(5,2)线性码,如图所示。 译码仍采用最大似然后译码规则，如图5.7所示的译码规则.,从图可以看出,选用此码，接收端译码规则能纠正码字中所有发生一位码元的

10、错误,也能纠正其中二个二位码元的错误,所以可计算得：,(5,2汉明码）,最大似然译码准则为： 选择译码函数使满足,设二元对称信道的单个符传输错误概率为P,当信道是无记忆时,则编码后信道的传递概率为,如果P1/2(这是正常情况,例如P=10-2),可以看出Dij越大,P(j| ai)越小, Dij越小, P(j| ai)越大.根据上式最大似然译码准则可用汉明距离表示为,上式又称为最小距离译码准则.,在二元对称无记忆信道中,平均译码错误概率也可用汉明距离来表示。若设输入码字数为M(并设输入等概率分布), 平均译码错误概率为：,因此,在二元信道中最大似然译码准则可表达为:当收到j后,译成与之距离(汉

11、明距离)为最近的输入码字a*.也就是把j译成与它最邻近的那个发送码字a*,可使平均错误概率PE达到最小,如图所示。,综上所述,在有噪信道中,传输的平均错误概率PE与各种编、译码方法有关。编码可彩霞选择M个消息所对应的码字间最小距离dmin尽可能增大的编码方法，而译码彩将接收序列,j译成与之距离最近的那个码字a*的译码规则，则只要码长n足够长时，合适地选择M个消息所对应的码字，就可以使错误概率很小，而信息传输率保持一定。,6.有噪声信道编码定理,有噪声信道编码定理(即仙侬第二定理)的方法中包含的基本思路有 1)允许平均错误概率任意小而非零; 2)连续使用信道许多次,即在n次无记忆信道中讨论,以便

12、使大数定律有效; 3)随机选取码书,在随机选取编码的基础上计算码的平均错误概率;因为随机选取,所以使概率对称;并由此证明至少有一种好码存在。,有噪信道编码定理（仙侬第二定理） 定理（仙侬第二定理） 离散、无记忆、平稳信道，信道容量为C，只要待传送的信息率RC，就一定能找到一种信道编码方法，使得码长N足够大时，平均差错率Pe任意接近于零。 仙侬第二定理是存在性定理，它指出在RC时，肯定存在一种好的信道编码方法，使Pe逼近零。但仙侬并没有给出编码的具体方法。,有噪信道编码逆定理 定理 离散、无记忆、平稳信道，信道容量为C，如果信息率RC，则肯定找不到一种信道编码方法，使得码长N足够大时，平均差错率

13、任意接近于零。,研究信息论的目的,1、仙侬信息论对信道编码的指导意义,信道编码定理：每一个信道具有确定的信道容量C，对于任何小于C的信息传输率R，总存在一个码长为n，码率等于R的分组码，若采用最大似然译码，则其译码错误概率PE满足 PEAe-nE(R） 其中：A是常数，E（R)为误差函数 错误概率PE越小，传输可靠性越高。增大码长n也可提高传输可靠性,误差函数E（R)与信息传输率R的关系曲线： E（R)是关于R的单调递减函数，同样的R，信道容量C不同时，E（R）也不同，C越大，E（R)值也越大。,2、仙侬信息论对信源编码的指导意义,有效性是指在一定时间内如何传输尽可能多的信息量。或在每一个传送

14、符号内携带尽可能多的信息量。 对信源进行高效编码，去除信源中多余度。 信源多余度有：统计多余度、结构多余度、视觉多余度、时间多余度、空间多余度等，需要采用不同方法消除。 仙侬信息论讨论的是统计多余度。,统计多余度包括信源前后符号间相关性带来的多余度和信源符号分布不均匀导致的多余度。,仙侬第一定理和第三定理分别从理论上给出无失真信源编码与限失真信源编码的压缩极限。,仙侬的贡献,1948年发表“通信的数学理论”，标志着信息论的诞生； 1949年发表“保密通信的信息理论”，首先用信息论的观点对信息保密问题作了全面的论述； 1959年发表“保真度准则下的离散信源编码定理”-提出信息率失真理论，为信源压缩编码研究奠定理论基础； 1961年发表“双路通信信道”，开拓了多用户信息理论（网络信息论）的研究；,E N D,