《信息论基础 普通高等教育十一五 国家级规划教材 教学课件 ppt 作者 田宝玉 杨洁 贺志强 王晓湘 chapter7》由会员分享，可在线阅读，更多相关《信息论基础 普通高等教育十一五 国家级规划教材 教学课件 ppt 作者 田宝玉 杨洁 贺志强 王晓湘 chapter7（118页珍藏版）》请在金锄头文库上搜索。
1、第7章 有噪信道编码,本章主要内容： 1.概述 2.最佳判决与译码准则 3.信道编码与最佳译码 4.费诺（Fano）不等式 5.有噪信道编码定理 6.纠错编码技术简介 7.信道编码性能界限,7.1 概述,信道编码：就是按一定的规则给信源输出序列增加某些冗 余符号，使其变成满足一定数学规律的码序列（或码字） ，再经信道进行传输。（提高传输的可靠性） 信道译码：就是按与编码器同样的数学规律去掉接收序列 中的冗余符号, 恢复信源消息序列。 一般地说，所加的冗余符号越多，纠错能力就越强，但传 输效率降低。因此在信道编码中明显体现了传输有效性与可靠 性的矛盾。,本节主要内容： 1. 信道编码的基本概念
2、2. 判决与译码规则 3. 译码错误概率,7.1.1 信道编码的基本概念,简化的通信系统模型如图7.1.1所示。 图7.1.1 简化通信系统模型图,设信源输出或信道编码器的输入消息集合为U，信道编 码器采用分组编码，输出码字为 的一个子集，其中每个 码符号 取自符号集 ；码字通过 离散无记忆信道传输；信道输出或译码器的输入为 ，其 中每个符号 取自符号集 ；译码器输 出是被恢复的消息，其集合用V表示。,（1） 消息产生：由信源发出M个等概率消息：U = 1，2，M； （2） 信道编码：编码器将消息映射成码字，编码函 数f：1，2，MC= ，其为码 长为n的码字，码符号集A的大小为r； （3）
3、信道传输： 为n维矢量，取自码字集C，作为 n次扩展信道的输入， ， 是n维矢量 ，为信道输出， ； （4） 信道译码：译码器根据接收的 完成译码功能 ，译码函数 。,信息传送过程,衡量信道编码有效性的重要指标就是信息传输速率 （也称码率）。 对于离散信道，当离散信源的符号通过信道编码器 编成长度为n的码字通过信道传输时，那么信息传输速 率为 （7. 1. 1） 单位为：比特（或奈特）/信道符号，其中，H（X）为 信源的熵。 当信源符号等概率时，一个（M，n）码信息传输速 率R为 （7. 1. 2）,对于时间连续信道，信息传输速率表示单位时间所传送 的信息量，即信息传输速率为 单位为：比特（或
4、奈特）/秒，其中， 为传输一个码符号所 需时间。幻灯片 4,7.1.2 判决与译码准则,对于图7.1.1所示的模型，单符号判决规则为： （7.1.3） 其中， 。（7.1.3）的含义是，当接收到 就判定为 发送符号。因此，对每一个信道输出都必须有一个信道 输入与之对应。所以判决规则是一个有惟一结果的函数。 （7.1.3）式可简记为 ，称 为判决函数。 设信道的转移概率为 ，那么，在接 收到 的条件下，若实际上发送的是 ，则判决正确， 反之就出现差错。,在发送 条件下，利用判决规则（7.1.3） ，条件错误率定义为 （7.1.4） 平均错误率定义为 （7.1.5） 还可计算平均正确率为： （7.
5、1.6）,例7. 1. 1 一个二元对称信道输入和输出分别为X，Y ，其中 ，信道的转移概率为 ， ，分 别求下面两种判决函数所对应的平均错误率并比较两者的 大小： （1） ； （2） 。,解 （1） 平均错误率： （2） 平均错误率： 很明显，当 时， ；否则 。 此例说明，错误率和判决函数的选取有关。幻灯片 4,7.1.3 译码错误概率,如前所述，译码就是通过接收序列恢复消息序列。如果恢 复的消息序列与发送序列不同，则称译码差错。通常有两种错 误概率的描述：误码率和误字率。误码率是指传输码元出错概 率（对二进制也称误比特率）。误字率是指码字出错概率。本 章所研究的错误率就是误字率。 与单符
6、号判决情况类似，条件错误率为： （7.1.7） 平均错误率为： （7.1.8）,如果一个L长的二进码字的传输中至少出现一个比特差错 ，则码字就发生译码错误。而当发生一个码字差错时，其中多 个比特的传输可能是正确的。所以对同一通信系统，误码率总 比误字率低。 错误概率的大小首先与编码器的纠错性能有关，其次与译 码规则的选择有关也和接收信噪比大小有关。应选择纠错性能 好的编码，性能好的译码算法以使平均错误概率最小。幻灯片 2,本节主要内容： 1. 最大后验概率准则 2. 最大似然准则,7.2 最佳判决与译码准则,7.2.1 最大后验概率准则,为提高传输可靠性，除采用有效的 信道编码之外，还应 采用
7、适当的译码准则。本节介绍最大后验概率（MAP）准则 和最大似然（ML）准则。 根据（7.1.6）式，平均正确率可以写为 这样，为使判决正确率最大或使判决错误率最小，应使 得对于每一个输出y，都选择对应后验概率最大的x。,即对所有i，当满足 （7.2.1） 时，则选择判决函数为，称此准则为最大后验概率 (MAP, Maximum a Posteriori) 准则，可简写为： MAP准则： （7.2.2） MAP准则就是，对给定的信道输出将具有最大后验概率的输入符号作为判决结果。,由（7.2.1）式，得 所以 ，对所有i，当 （7.2.3） 时，则选择判决函数为g(y)=a*。其中，为似然比，（7
8、.2.3） 式表示的是似然比检验。 注：（1）MAP准则是使平均错误率最小的准则； （2）MAP准则可归结为似然比检验。,例7.2.1 设信道输入X等概率取值为+1，-1，通过一 个加性高斯信道传输，加性噪声Z是均值为零，方差为 的高斯随机变量，信道输出Y=X+Z，接收机用MAP准则接 收，试确定判决函数。 解 后验概率密度为,令 则 时， ； 时， ；而当 时，有 ； 时，有 ； 所以，判决函数为 7.2,7.2.2 最大似然准则,若输入符号等概，（7.2.3）变为： 对所有i, 当 （7.2.4） 则选择判决函数为g(y)=a*，称此准则为最大似然（Maximum Likelihood，M
9、L）准则，可简写为： ML准则： （7.2.5） 注：（1）当输入符号等概或先验概率未知时，采用 此准则。 （2）当输入符号等概时，最大似然准则等价于最大后验 概率准则。,例7.2.1（续）接收机用ML准则接收，试确 定判决函数。 解 似然函数为 令 类似于MAP判决情况，可得到与MAP相同的结果， 这是意料之中的，因为信道输入等概率。但当信道输入 概率不相等时，MAP和ML判决函数和平均错误率通常是 不同的，而MAP准则是使平均错误率最小的。,如果信道输入概率和转移概率矩阵给定，那么可对两种准 则使用要点总结如下： MAP准则 由转移概率矩阵的每行分别乘p(x)，得到联合概率矩阵； 对于每一
10、列（相当于y固定）找一个最大的概率对应的x作为判 决结果；所有判决结果所对应的联合概率的和为正确概率，其 他矩阵元素的和为错误概率。 ML准则 对转移概率矩阵中每列选择最大的一个元素对应的x作为 判决结果；所有信道输出和所对应判决结果的联合概率之和为 平均正确率，其他的联合概率之和为平均错误率。幻灯片 2,本节主要内容： 1. 线性分组码 2. 序列最大似然译码 3. 几种简单的分组码,7.3 信道编码与最佳译码,7.3.1 线性分组码,信道编码有很多种类，其中最重要的一类是线性分组 码，其冗余符号（也称校验位或监督位）和信息符号是线 性关系。本节利用简单的线性分组码的最佳译码说明如何 实现传
11、输可靠性。 一个二元（n，k）线性分组码有k个信息位，n-k个校 验位，根据某种确定的数学关系构成总长度为n的码字， 码率为k/n。在线性分组码中，校验位为信息位的线性组 合。如果码字的开头或结尾的k位是信息位，那么就称为 系统码，否则称非系统码。在（n，k）线性分组码中码字 的个数有 个。,例7. 3. 1 求一个二进（n，k）线性分组码 的信息传输速率。 解 （比特/符号） （7.3.1） R=k/n常称做码率或编码效率。,1. 汉明距离,设两个二元码字为 ，其中， 均取自符号0，1，定义它们的汉明距离为 （7.3.2） 其中， 为模二加运算。 例如，码字 和码字 的汉明 距离为6。,引理
12、7.3.1 设x、y、z是长度为n的二元矢量，那么 （1）d(x,y) 0 （非负性） （2）d(x,y) = d(y,x) （对称性） （3）d(x,z) d(x,y) +d(y,z) （三角不等式） （证明留做练习）,2. 码的最小距离,码的最小距离：一个码字集合中任意两码字的汉明距 离最小值。用 来表示。 一个（n，k）线性分组码的最小 距离定义为 （7.3.3） 其中， 表示码字 间的汉明距离。,由于线性分组码可看成n维空间的一个子空间，任何 两码字的和都是码字，所以 （7.3.4） 其中， ，w(.)表示某码字的重量，即该码字中不 为“0”的“1”的个数。 因此，线性分组码的最小距离
13、 就是其最小重量的非零 码字。 例7. 3. 2 一个线性分组码C=00000，01010，10101 ，11111，求该码的最小距离 。 解 = w(01010)=2 7.3,7.3.2 序列最大似然译码,设所有符号规定与图7.1.1所示的模型的说明相同。 如果对于所有k，满足 （7.3.5） 就选择译码函数为 ，则称为序列的最 大似然译码准则，其中， 表示码字 所对应的 消息。转移概率 称为似然函数。 可以简写为 ML译码： （7.3.6） 与单符号情况相同，当消息等概或概率未知时用最大 似然译码准则。,在通信系统中，设发送序列为 ，接收序列为 ，并且 和 来自同一个符号集，由于信道噪声的干扰 通常与 不 同。当接收到 后，计算所有可能的发送序列 与 之间的汉 明距离，将与 汉明距离最小的 作为译码输出，这种译码方 法称最小汉明距离准则。 定理7.3.1 对于无记忆二元对称信道（错误概率1/2）， 最大似然译码准则等价于最小汉明距离准则。,证 设信道
