信息论与编码2011-总复习.ppt

《信息论与编码2011-总复习.ppt》由会员分享，可在线阅读，更多相关《信息论与编码2011-总复习.ppt（98页珍藏版）》请在装配图网上搜索。

1、2020/7/6,1,要记住：历史上所有伟大的成就，都是由于战胜了看来是不可能的事情而取得的。 卓别林,2020/7/6,2,课程类型：专业选修课 学 时： 54 教 材：信息论与编码基础,唐朝京, 雷 菁，电子工业出版社， 2010.2 参考教材： （Elements of Information Theory, 英文 影印）,Thomas M.Cover, Joy A.Thomas ,清华大学出版社，2003 (The Theory of Information and Coding,英文影印版)(第2版), Robert J.McEliece,电子工业出版社, 2005.3 考 核： 平

2、时成绩40（作业、考勤、期中测验） 期末考试60（闭卷） 作业：20（百分制：缺一次扣20分） 考勤：10（百分制：缺席一次扣10分） 期中测验：10（百分制：实际分数）,2020/7/6,3,信息与消息和信号的区别 消息：是指包含有信息的语言、文字和图像等，可表达客观物质运动和主观思维活动的状态。 信号：把消息变换成适合信道传输的物理量，这种物理量称为信号（如电信号、光信号、声音信号等）。,第一章 概 论,2020/7/6,4,信息 “本体论”层次定义：信息是该事物运动的状态和状态改变的方式。 认识论层次的信息是同时考虑语法信息、语义信息和语用信息的全信息。 全信息：同时考虑外在形式/语法信

3、息、内在含义/语义信息、效用价值/语用信息，称为全信息。 语法信息：事物运动状态和状态改变的方式； 语义信息：事物运动状态和方式的具体含义； 语用信息：事物运动状态和方式及其含义对观察者的效用。 研究信息论的目的：它的主要目的是提高信息系统的可靠性、有效性和安全性以便达到系统最优化。,第一章 概 论,2020/7/6,5,单符号离散信源 自信息量 用概率测度定义信息量 设离散信源 X，其概率空间为 如果知道事件 xi 已发生，则该事件所含有的自信息定义为 当事件 xi 发生以前：表示事件 xi 发生的不确定性。 当事件 xi 发生以后：表示事件 xi 所含有（或所提供）的信息量,第二章 信源熵

4、,2020/7/6,6,联合自信息量 当 X 和 Y 相互独立时，p(xiyj)=p(xi)p(yj),第二章 信源熵,2020/7/6,7,条件自信息量：已知 yj 的条件下 xi 仍然存在的不确定度。 自信息量、条件自信息量和联合自信息量之间的关系,第二章 信源熵,2020/7/6,8,互信息量： yj 对 xi 的互信息量定义为的后验概率与先验概率比值的对数。,第二章 信源熵,2020/7/6,9,观察者站在输出端：两个不确定度之差是不确定度被消除的部分，即等于自信息量减去条件自信息量。 观察者站在输入端： 观察者得知输入端发出 xi 前、后对输出端出现 yj 的不确定度的差。 观察者站

5、在通信系统总体立场上：通信后的互信息量，等于前后不确定度的差。,第二章 信源熵,2020/7/6,10,平均信息量信源熵：自信息的数学期望。也称为信源的信息熵/信源熵/香农熵/无条件熵/熵函数/熵。 信息熵的意义：信源的信息熵 H 是从整个信源的统计特性来考虑的。它是从平均意义上来表征信源的总体特性的。对于某特定的信源，其信息熵只有一个。不同的信源因统计特性不同，其熵也不同。 信源熵的三种物理含义 信源熵 H(X) 是表示信源输出后每个消息/符号所提供的平均信息量； 信源熵 H(X) 是表示信源输出前，信源的平均不确定性； 用信源熵 H(X) 来表征变量 X 的随机性。,第二章 信源熵,202

6、0/7/6,11,条件熵：是在联合符号集合 XY 上的条件自信息的数学期望。,第二章 信源熵,2020/7/6,12,信道疑义度H(X/Y)：表示信宿在收到 Y 后，信源 X 仍然存在的不确定度。是通过有噪信道传输后引起的信息量的损失，故也可称为损失熵。 噪声熵H(Y/X)：表示在已知 X 的条件下，对于符号集 Y 尚存在的不确定性（疑义），这完全是由于信道中噪声引起的。,第二章 信源熵,2020/7/6,13,联合熵 H(XY)：表示输入随机变量 X，经信道传输到达信宿，输出随机变量 Y。即收、发双方通信后，整个系统仍然存在的不确定度。,第二章 信源熵,2020/7/6,14,最大离散熵定理

7、 (极值性) ：离散无记忆信源输出 n 个不同的信息符号，当且仅当各个符号出现概率相等时 (即p(xi)=1/n)，熵最大。 Hp(x1),p(x2),p(xn) H(1/n,1/n,1/n)=log2n 出现任何符号的可能性相等时，不确定性最大。,第二章 信源熵,2020/7/6,15,二进制信源的熵函数 H(p) 为,第二章 信源熵,2020/7/6,16,平均互信息量定义：互信息量 I(xi;yj) 在联合概率空间 P(XY) 中的统计平均值。 从一个事件获得另一个事件的平均互信息需要消除不确定度，一旦消除了不确定度，就获得了信息。,第二章 信源熵,2020/7/6,17,站在输出端：I

8、(X;Y)收到 Y 前、后关于 X 的不确定度减少的量。从 Y 获得的关于 X 的平均信息量。 站在输入端：I(Y;X) 发出 X 前、后关于 Y 的先验不确定度减少的量。 站在总体：I(X;Y) 通信前、后整个系统不确定度减少量。,第二章 信源熵,2020/7/6,18,BSC信道的平均互信息量 设二进制对称信道的输入概率空间为 转移概率如图2.1.8所示。,第二章 信源熵,2020/7/6,19,平均互信息量 当 q 不变 (固定信道特性) 时，可得 I(X;Y) 随输入概率分布 p 变化的曲线，如图2.1.9所示；二进制对称信道特性固定后，输入呈等概率分布时，平均而言在接收端可获得最大信

9、息量。,第二章 信源熵,2020/7/6,20,当固定信源特性 p 时，I(X;Y) 就是信道特性 q 的函数，如图2.1.10所示；当二进制对称信道特性 q=/q=1/2时，信道输出端获得信息量最小，即等于0。说明信源的全部信息信息都损失在信道中了。这是一种最差的信道。,第二章 信源熵,2020/7/6,21,离散无记忆信源 X 的 N 次扩展信源的熵等于离散信源X 的熵的 N 倍，即 H(X)=H(XN)=NH(X) 离散平稳信源：各维联合概率均与时间起点无关的完全平稳信源称为离散平稳信源。二维离散平稳信源的熵为,第二章 信源熵,2020/7/6,22,平均符号熵：信源平均每发一个符号提供

10、的信息量为 离散平稳有记忆信源的极限熵：当 N 时，平均符号熵取极限值称之为极限熵或极限信息量。用 H表示，即 极限熵的存在性：当离散有记忆信源是平稳信源时，极限熵等于关联长度 N时，条件熵H(XN/X1X2XN-1)的极限值，即 极限熵的含义：代表了一般离散平稳有记忆信源平均每发一个符号提供的信息量。,第二章 信源熵,2020/7/6,23,信源熵的相对率 ：= H/H0 信源冗余度： =1=(H0H)/H0 信源的冗余度表示信源可压缩的程度。,第二章 信源熵,2020/7/6,24,数据处理定理,数据处理定理：当消息经过多级处理后，随着处理器数目的增多，输入消息与输出消息之间的平均互信息量

11、趋于变小。即 I(X;Z)I(X;Y) I(X;Z)I(Y;Z),2020/7/6,25,结论： 两级串联信道输入与输出消息之间的平均互信息量既不会超过第级信道输入与输出消息之间的平均互信息量，也不会超过第级信道输入与输出消息之间的平均互信息量。 当对信号/数据/消息进行多级处理时，每处理一次，就有可能损失一部分信息，也就是说数据处理会把信号/数据/消息变成更有用的形式，但是绝不会创造出新的信息。这就是所谓的信息不增原理。 当已用某种方式取得Y后，不管怎样对Y进行处理，所获得的信息不会超过I(X;Y)。每处理一次，只会使信息量减少，至多不变。也就是说在任何信息流通系统中，最后获得的信息量，至多

12、是信源提供的信息。一旦在某一过程中丢失了一些信息，以后的系统不管怎样处理，如果不能接触到丢失信息的输入端，就不能再恢复已丢失的信息。,2020/7/6,26,随机过程 x(t) 中某一样本函数 x(t)的时间平均值定义： 随机过程 x(t) 在某时刻 ti 所取的随机变量 的统计平均值/集平均定义： 遍历的随机过程：时间平均与统计平均相等，即,第二章 信源熵,2020/7/6,27,连续信源的熵为 上式定义的熵在形式上和离散信源相似，也满足离散熵的主要特性，如可加性，但在概念上与离散熵有差异因为它失去了离散熵的部分含义和性质。 三种限定条件下连续信源的最大熵定理,第二章 信源熵,2020/7/

13、6,28,连续信源熵有关问题说明 连续信源熵并不是实际信源输出的绝对熵； 连续信源的绝对熵还有一项正的无限大量，虽然 log2(ba) 小于0，但两项相加还是正值，且一般还是一个无限大量。因为连续信源的可能取值数有无限多，若假定等概率，确知其输出值后所得信息量也将为无限大； Hc(X) 已不能代表信源的平均不确定度，也不能代表连续信源输出的信息量。 连续信源熵的意义 这种定义可以与离散信源在形式上统一起来； 在实际问题中常常讨论的是熵之间的差值问题，如信息变差、平均互信息等。在讨论熵差时，两个无限大量互相抵消。所以熵差具有信息的特征； 连续信源的熵 Hc(X) 具有相对性，因此 Hc(X) 也

14、称为相对熵。,第二章 信源熵,2020/7/6,29,信道容量 C：在信道中最大的信息传输速率，单位是比特/信道符号。 单位时间的信道容量 Ct：若信道平均传输一个符号需要 t 秒钟，则单位时间的信道容量为 Ct 实际是信道的最大信息传输速率。,第三章 信道容量,2020/7/6,30,求信道容量的方法 当信道特性 p(yj /xi) 固定后，I(X;Y) 随信源概率分布 p(xi) 的变化而变化。 调整 p(xi)，在接收端就能获得不同的信息量。由平均互信息的性质已知，I(X;Y) 是 p(xi) 的上凸函数，因此总能找到一种概率分布 p(xi)（即某一种信源），使信道所能传送的信息率为最大

15、。 C 和 Ct 都是求平均互信息 I(X;Y) 的条件极大值问题，当输入信源概率分布 p(xi) 调整好以后， C 和 Ct 已与 p(xi) 无关，而仅仅是信道转移概率的函数，只与信道统计特性有关； 信道容量是完全描述信道特性的参量； 信道容量是信道能够传送的最大信息量。,第三章 信道容量,2020/7/6,31,当 n=2 时的强对称离散信道就是二进制均匀信道。 二进制均匀信道 的信道容量为： 二进制均匀信道容量 曲线如图3.2.5所示。,第三章 信道容量,2020/7/6,32,香农公式说明 当信道容量一定时，增大信道带宽，可以降低对信噪功率比的要求；反之，当信道频带较窄时，可以通过提

16、高信噪功率比来补偿。 当信道频带无限时，其信道容量与信号功率成正比。,第三章 信道容量,2020/7/6,33,信道编码定理：若有一离散无记忆平稳信道，其容量为 C，输入序列长度为 L，只要待传送的信息率 RC时，任何编码的 Pe 必大于零，当 L，Pe1。 信道编码定理说明：同无失真信源编码定理类似，信道编码定理也是一个理想编码的存在性定理。它指出信道容量是一个临界值，只要信息传输率不超过这个临界值，信道就可几乎无失真地把信息传送过去，否则就会产生失真。,第三章 信道容量,2020/7/6,34,失真度 设离散无记忆信源为,第四章 信息率失真函数,2020/7/6,35,对每一对 (xi,y

17、j)，指定一个非负函数 d(xi,yj)0 i=1,2,n j=1,2,m 称 d(xi,yj) 为单个符号的失真度/失真函数。表示信源发出一个符号 xi，在接收端再现 yj 所引起的误差或失真。,第四章 信息率失真函数,2020/7/6,36,平均失真度定义 d(xi,yj) 只能表示两个特定的具体符号 xi 和 yj 之间的失真。 平均失真度：平均失真度为失真度的数学期望，,第四章 信息率失真函数,2020/7/6,37,平均失真度意义 是在平均意义上，从总体上对整个系统失真情况的描述。它是信源统计特性 p(xi) 、信道统计特性 p(yj/xi ) 和失真度 d(xi,yj) 的函数 。

18、当 p(xi)，p(yj/xi)和 d(xi,yj) 给定后，平均失真度就不是一个随机变量了，而是一个确定的量。 如果信源和失真度一定， 就只是信道统计特性的函数。信道传递概率不同，平均失真度随之改变。,第四章 信息率失真函数,2020/7/6,38,允许平均失真度：率失真函数中的自变量 D，也就是人们规定的平均失真度 的上限值。 率失真函数的定义域问题就是在信源和失真函数已知的情况下，讨论允许平均失真度 D 的最小和最大值问题。 D 的选取必须根据固定信源 X 的统计特性 P(X) 和选定的失真函数 d(xi , yj)，在平均失真度 的可能取值范围内。,第四章 信息率失真函数,2020/7

19、/6,39,常用的失真函数 第一种 当a=1时称为汉明失真矩阵。 第二种/平方误差失真矩阵：d(xi,yj)=(yjxi)2,第四章 信息率失真函数,2020/7/6,40,单符号信源和单符号信道的信息率失真函数 在信源和失真度给定以后，PD 是满足保真度准则 的试验信道集合，平均互信息 I(X;Y) 是信道传递概率 p(yj /xi) 的下凸函数，所以在 PD 中一定可以找到某个试验信道，使 I(X;Y)达到最小，即 这个最小值 R(D) 称为信息率失真函数，简称率失真函数。 在信源给定以后，总希望在允许一定失真的情况下，传送信源所必须的信息率越小越好。从接收端来看，就是在满足保真度准则 的

20、条件下，寻找再现信源消息必须的最低平均信息量，即平均互信息的最小值。,第四章 信息率失真函数,2020/7/6,41,求信息率失真函数的方法 信息率失真函数 R(D) 是假定信源给定的情况下，在用户可以容忍的失真度内再现信源消息所必须获得的最小平均信息量。它反映的是信源可压缩程度。率失真函数一旦找到，就与求极值过程中选择的试验信道不再有关，而只是信源特性的参量。不同的信源，其 R(D)是不同的。,第四章 信息率失真函数,2020/7/6,42,对偶问题：信道容量和信息率失真函数的问题，都是求平均互信息极值问题。分三个方面说明： 求极值问题 平均互信息I(X;Y)是信源概率分布p(xi)(i=1

21、,2,n) 的上凸函数，信道容量就是在固定信道情况下，求平均互信息极大值的问题，即 I(X;Y) 又是信道转移概率分布 p(yj /xi)(i=1,2,n;j=1,2,m) 的下凸函数，信息率失真函数就是在试验信道（满足保真度准则的信道）中寻找平均互信息极小值的问题，即,第四章 信息率失真函数,2020/7/6,43,特 性 信道容量 C一旦求出后，就只与信道转移概率 p(yj /xi) 有关，反映信道特性，与信源特性无关； 信息率失真函数 R(D)一旦求出后，就只与信源概率分布 p(xi) 有关，反映信源特性，与信道特性无关。 解决的问题 信道容量是为了解决通信的可靠性问题，是信息传输的理论

22、基础，通过信道编码增加信息的冗余度来实现； 信息率失真函数是为了解决通信的有效性问题，是信源压缩的理论基础，通过信源编码减少信息的冗余度来实现。,第四章 信息率失真函数,2020/7/6,44,限失真信源编码定理：设一离散平稳无记忆信源的输出随机变量序列为 X=(X1,X2,XL)，若该信源的信息率失真函数是 R(D)，并选定有限的失真函数。对于任意允许平均失真度 D0，和任意小的0，当信息率 RR(D) ，只要信源序列长度 L 足够长，一定存在一种编码方式 C，使译码后的平均失真度 ；反之，若 RR(D)，则无论用什么编码方式，必有 ，即译码平均失真必大于允许失真。 信息率失真函数也是一个界

23、限。只要信息率大于这个界限，译码失真就可限制在给定的范围内。即通信的过程中虽然有失真，但仍能满足要求，否则就不能满足要求。,第四章 信息率失真函数,2020/7/6,45,研究信道编码和率失真函数的意义 研究信道容量的意义：在实际应用中，研究信道容量是为了解决在已知信道中传送最大信息率问题。目的是充分利用已给信道，使传输的信息量最大而发生错误的概率任意小，以提高通信的可靠性。这就是信道编码问题。 研究信息率失真函数的意义：研究信息率失真函数是为了解决在已知信源和允许失真度D 的条件下，使信源必须传送给信宿的信息率最小。即用尽可能少的码符号尽快地传送尽可能多的信源消息，以提高通信的有效性。这是信

24、源编码问题。,第四章 信息率失真函数,2020/7/6,46,香农编码 费诺编码 哈夫曼编码 M进制哈夫曼编码 编码效率的计算,第五章 信源编码,2020/7/6,47,信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息

25、论的观点出发，“加密”可视为增熵的过程，“解密”可视为减熵的过程。,第五章 信源编码,2020/7/6,48,香农编码,设离散无记忆信源 二进制香农码的编码步骤如下： 将信源符号按概率从大到小的顺序排列，为方便起见，令 p(x1) p(x2) p(xn) 令p(x0)=0，用pa(xj)，j=i+1表示第i个码字的累加概率，则,2020/7/6,49,确定满足下列不等式的整数ki ，并令ki为第i个码字的长度 log2 p(xi)ki1 log2 p(xi) 将pa(xj) 用二进制表示，并取小数点后ki 位作为符号xi的编码。,香农编码,2020/7/6,50,费诺编码,费诺编码也是一种常见

26、的信源编码方法。编码步骤如下： 将概率按从大到小的顺序排列，令 p(x1) p(x2) p(xn) 按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二进制码就分成两组，编m进制码就分成m组。 给每一组分配一位码元。 将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分为止。,2020/7/6,51,将信源符号按概率从大到小的顺序排列，令 p(x1) p(x2) p(xn) 给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信

27、源的第一次缩减信源，用S1表示。 将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n2)个符号的缩减信源S2。 重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。,二元哈夫曼编码,2020/7/6,52,在编m进制哈夫曼码时为了使平均码长最短，必须使最后一步缩减信源有m个信源符号。非全树时，有s个码字不用： 第一次对最小概率符号分配码元时就只取(ms)个，分别配以0,1,ms1，把这些符号的概率相加作为一个新符号的概率，与其它符号一起重新排列。 以后每次就可以取m个符号

28、，分别配以0,1,m1；如此下去，直至所有概率相加得1为止，即得到各符号的m进制码字。,M元哈夫曼编码,2020/7/6,53,香农码、费诺码、哈夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩； 香农码有系统的、惟一的编码方法，但在很多情况下编码效率不是很高； 费诺码和哈夫曼码的编码方法都不惟一； 费诺码比较适合于对分组概率相等或接近的信源编码，费诺码也可以编m进制码，但m越大，信源的符号数越多，可能的编码方案就越多，编码过程就越复杂，有时短码未必能得到充分利用； 哈夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的

29、要求也比较简单，因此综合性能优于香农码和费诺码。,第五章 信源编码,2020/7/6,54,差错控制的基本方式 前向纠错(FEC)：发送端的信道编码器将信息码组编成具有一定纠错能力的码。接收端信道译码器对接收码字进行译码，若传输中产生的差错数目在码的纠错能力之内时，译码器对差错进行定位并加以纠正。 自动请求重发(ARQ)：用于检测的纠错码在译码器输出端只给出当前码字传输是否可能出错的指示，当有错时按某种协议通过一个反向信道请求发送端重传已发送的码字全部或部分。,第六章 信道编码,2020/7/6,55,混合纠错(HEC)：是 FEC 与 ARQ 方式的结合。发端发送同时具有自动纠错和检测能力的

30、码组，收端收到码组后，检查差错情况，如果差错在码的纠错能力以内，则自动进行纠正。如果信道干扰很严重，错误很多，超过了码的纠错能力，但能检测出来，则经反馈信道请求发端重发这组数据。 信息反馈(IRQ)：也称回程校验方式。收端把收到的数据，原封不动地通过反馈信道送回到发端，发端比较发的数据与反馈来的数据，从而发现错误，并且把错误的消息再次传送，直到发端没有发现错误为止。,第六章 信道编码,2020/7/6,56,最佳译码准则（最大似然译码） 通信是一个统计过程，纠、检错能力最终要反映到差错概率上。 对于FEC方式，采用纠错码后的码字差错概率为pwe， p(C)：发送码字C 的先验概率 p(C/R)

31、：后验概率 若码字数为 2k，对充分随机的消息源有p(C)=1/ 2k，所以最小化的pwe等价为最小化p(CCR )，又等价为最大化p(C=CR)；,第六章 信道编码,2020/7/6,57,对于 BSC 信道：最大化的 p(C=CR) 等价于最大化的 p(RC) ，最大化的p(RC) 又等价于最小化 d(R,C)，所以使差错概率最小的译码是使接收向量 R 与输出码字 C 距离最小的译码。,第六章 信道编码,2020/7/6,58,线性分组码的编码：线性分组码的编码过程分为两步： 把信息序列按一定长度分成若干信息码组，每组由 k 位组成； 编码器按照预定的线性规则(可由线性方程组规定)，把信息

32、码组变换成 n 重 (nk) 码字，其中 (nk) 个附加码元是由信息码元的线性运算产生的。 信息码组长 k 位，有 2k 个不同的信息码组，则有 2k 个码字与它们一一对应。,6.2线性分组码,第六章 信道编码,2020/7/6,59,名词解释 线性分组码：通过预定的线性运算将长为 k 位的信息码组变换成 n 重的码字 (nk)。由 2k 个信息码组所编成的 2k个码字集合，称为线性分组码。 码矢：一个 n 重的码字可以用矢量来表示 C=(Cn1,Cn2,C1,C0 ) 所以码字又称为码矢。 (n,k) 线性码：信息位长为 k，码长为 n 的线性码。 编码效率/编码速率/码率/传信率：R=k

33、 /n。它说明了信道的利用效率，R是衡量码性能的一个重要参数。,6.2线性分组码,第六章 信道编码,2020/7/6,60,(1) 一致监督方程 编码就是给已知信息码组按预定规则添加监督码元，以构成码字。 在 k 个信息码元之后附加 r(r=nk) 个监督码元，使每个监督元是其中某些信息元的模2和。 举例：k=3, r=4，构成 (7,3) 线性分组码。设码字为 (C6,C5,C4,C3,C2,C1,C0) C6,C5,C4为信息元，C3,C2,C1,C0为监督元，每个码元取“0”或“1” 监督元可按下面方程组计算,6.2线性分组码,第六章 信道编码,2020/7/6,61,一致监督方程/一致

34、校验方程：确定由信息元得到监督元规则的一组方程称为监督方程/校验方程。由于所有码字都按同一规则确定，又称为一致监督方程/一致校验方程。 由于一致监督方程是线性的，即监督元和新信源之间是线性运算关系，所以由线性监督方程所确定的分组码是线性分组码。,6.2线性分组码,第六章 信道编码,2020/7/6,62,(2) 举例 信息码组 (101)，即C6=1, C5=0, C4=1 代入 (6.2.1) 得： C3=0, C2=0, C1=1, C0=1 由信息码组 (101) 编出的码字为 (1010011)。其它7个码字如表6.2.1。,6.2线性分组码,第六章 信道编码,2020/7/6,63,

35、(3) 一致监督矩阵 为了运算方便，将式(6.2.1)监督方程写成矩阵形式，得 式(6.2.2)可写成 H CT=0T或 C HT=0 CT、HT、0T分别表示C、H、0的转置矩阵。,6.2线性分组码,第六章 信道编码,2020/7/6,64,系数矩阵 H 的后四列组成一个 (44) 阶单位子阵，用 I4 表示，H 的其余部分用 P 表示,6.2线性分组码,第六章 信道编码,2020/7/6,65,推广到一般情况：对 (n,k) 线性分组码，每个码字中的 r(r=nk) 个监督元与信息元之间的关系可由下面的线性方程组确定,6.2线性分组码,第六章 信道编码,2020/7/6,66,令上式的系数

36、矩阵为 H，码字行阵列为 C,6.2线性分组码,第六章 信道编码,2020/7/6,67,(4) 一致监督矩阵特性 对H 各行实行初等变换，将后面 r 列化为单位子阵，于是得到下面矩阵，行变换所得方程组与原方程组同解。 监督矩阵H 的标准形式：后面 r 列是一单位子阵的监督矩阵H。 H 阵的每一行都代表一个监督方程，它表示与该行中“1”相对应的码元的模2和为0。,6.2线性分组码,第六章 信道编码,2020/7/6,68,H 的标准形式还说明了相应的监督元是由哪些信息元决定的。例如 (7,3) 码的H 阵的第一行为 (1011000)，说明此码的第一个监督元等于第一个和第三个信息元的模2和，依

37、此类推。 H 阵的 r 行代表了 r 个监督方程，也表示由H 所确定的码字有 r 个监督元。 为了得到确定的码，r 个监督方程（或H 阵的r 行）必须是线性独立的，这要求H 阵的秩为 r。 若把H 阵化成标准形式，只要检查单位子阵的秩，就能方便地确定H 阵本身的秩。,6.2线性分组码,第六章 信道编码,2020/7/6,69,(2) 线性分组码的生成矩阵 在由 (n,k) 线性码构成的线性空间 Vn 的 k 维子空间中，一定存在 k 个线性独立的码字：g1,g2, gk,。码 CI 中其它任何码字C都可以表示为这 k 个码字的一种线性组合，即,6.2线性分组码,第六章 信道编码,2020/7/

38、6,70,G中每一行 gi=(gi1,gi2, gin ) 都是一个码字； 对每一个信息组m，由矩阵G都可以求得 (n,k) 线性码对应的码字。 生成矩阵：由于矩阵 G 生成了 (n,k) 线性码，称矩阵 G 为 (n,k) 线性码的生成矩阵。 (n,k) 线性码的每一个码字都是生成矩阵 G 的行矢量的线性组合，所以它的 2k 个码字构成了由 G 的行张成的 n 维空间的一个 k 维子空间 Vk。,6.2线性分组码,第六章 信道编码,2020/7/6,71,线性系统分组码 通过行初等变换，将 G 化为前 k 列是单位子阵的标准形式,6.2线性分组码,第六章 信道编码,2020/7/6,72,线

39、性系统分组码：用标准生成矩阵 Gkn 编成的码字，前面 k 位为信息数字，后面 r=nk 位为校验字，这种信息数字在前校验数字在后的线性分组码称为线性系统分组码。 当生成矩阵 G 确定之后，(n,k) 线性码也就完全被确定了，只要找到码的生成矩阵，编码问题也同样被解决了。,6.2线性分组码,第六章 信道编码,2020/7/6,73,生成矩阵与一致监督矩阵的关系 由于生成矩阵G的每一行都是一个码字，所以G 的每行都满足HrnCTn1=0Tr1，则有 HrnGTnk=0Trk 或 GknHTnr=0kr 线性系统码的监督矩阵 H 和生成矩阵 G 之间可以直接互换。,线性分组码,第六章 信道编码,2

40、020/7/6,74,伴随式和错误检测 用监督矩阵编码，也用监督矩阵译码：接收到一个接收字 R 后，校验 HRT=0T 是否成立： 若关系成立，则认为 R 是一个码字； 否则判为码字在传输中发生了错误； HRT的值是否为0是校验码字出错与否的依据。 伴随式/监督子/校验子：S=RHT或ST=HRT。 如何纠错？ 设发送码矢 C=(Cn1,Cn2,C0) 信道错误图样为 E=(En1,En2,E0) ， 其中Ei=0，表示第i位无错； Ei=1，表示第i位有错。i=n1,n2,0。,第六章 信道编码,2020/7/6,75,接收字 R 为 R=(Rn1,Rn2,R0)=C+E =(Cn1+En1

41、,Cn2+En2,C0 +E0) 求接收字的伴随式（接收字用监督矩阵进行检验 ST=HRT=H(C+E)T=HCT+HET (6.2.25) 由于HCT=0T，所以 ST=HET 设H=(h1,h2,hn)，其中hi表示H的列。代入式(6.2.25)得到,第六章 信道编码,2020/7/6,76, 总结 伴随式仅与错误图样有关，而与发送的具体码字无关，即伴随式仅由错误图样决定； 伴随式是错误的判别式： 若S=0，则判为没有出错，接收字是一个码字； 若S0，则判为有错。 不同的错误图样具有不同的伴随式，它们是一一对应的。对二元码，伴随式是 H 阵中与错误码元对应列之和。,第六章 信道编码,202

42、0/7/6,77,(1) 汉明距离、汉明重量和汉明球 汉明距离/距离：在 (n,k)线性码中，两个码字 U、V 之间对应码元位上符号取值不同的个数，称为码字 U、V 之间的汉明距离。 例如：(7,3) 码的两个码字 U=0011101,V=0100111，它们之间第2、3、4和6位不同。因此，码字 U 和 V 的距离为4。 线性分组码的一个码字对应于 n 维线性空间中的一点，码字间的距离即为空间中两对应点的距离。因此，码字间的距离满足一般距离公理：,6.2线性分组码,第六章 信道编码,2020/7/6,78,.,最小距离/dmin：在 (n,k) 线性码的码字集合中，任意两个码字间距离最小值，

43、叫做码的最小距离。若C(i)和C(j) 是任意两个码字，则码的最小距离表示为 码的最小距离是衡量码的抗干扰能力（检、纠错能力）的重要参数。码的最小距离越大，码的抗干扰能力就越强。 汉明球：以码字C为中心，半径为 t 的汉明球是与 C 的汉明距离 t 的向量全体 SC(t) 任意两个汉明球不相交最大程度取决于任意两个码字之间的最小汉明距离dmin。,6.2线性分组码,第六章 信道编码,2020/7/6,79,汉明重量/码字重量/W：码字中非0码元符号的个数，称为该码字的汉明重量。 在二元线性码中，码字重量就是码字中含“1”的个数。 最小重量/Wmin ：线性分组码CI中，非0码字重量最小值，叫做

44、码CI的最小重量： Wmin =minW(V),VCI ,V0 最小距离与最小重量的关系：线性分组码的最小距离等于它的最小重量。 证明：设线性码CI，且UCI, VCI，又设UV= Z ，由线性码的封闭性知，ZCI 。因此，d(U,V)=W(Z)，由此可推知，线性分组码的最小距离必等于非0码字的最小重量。,6.2线性分组码,第六章 信道编码,2020/7/6,80,(2) 最小距离与检、纠错能力 一般地说，线性码的最小距离越大，意味着任意码字间的差别越大，则码的检、纠错能力越强。 检错能力：如果一个线性码能检出长度l 个码元的任何错误图样，称码的检错能力为 l。 纠错能力：如果线性码能纠正长度

45、t 个码元的任意错误图样，称码的纠错能力为 t。,6.2.5 线性分组码的最小距离、检错和纠错能力,6.2线性分组码,2020/7/6,81,最小距离与纠错能力：(n,k) 线性码能纠 t 个错误的充要条件是码的最小距离为 证明： 设：发送的码字为V；接收的码字为R；U为任意其它码字； 则：矢量V、R、U间满足距离的三角不等式， d(R,V)+d(R,U)d(U,V) (6.2.16) 设：信道干扰使码字中码元发生错误的实际个数为 t，且t t d(R,V)t t (6.2.17) 由于d(U,V)dmin=2t+1，代入式(6.2.16)得 d(R,U) d(U,V)d(R,V)= 2t+1

46、tt (6.2.18),6.2.5 线性分组码的最小距离、检错和纠错能力,6.2线性分组码,2020/7/6,82,上式表明：如果接收字 R 中错误个数 tt，那么接收字 R 和发送字 V 间距离t ，而与其它任何码字间距离都大于 t，按最小距离译码把R译为V。此时译码正确，码字中的错误被纠正。 几何意义：,6.2.5 线性分组码的最小距离、检错和纠错能力,6.2线性分组码,2020/7/6,83,最小距离与检错能力：(n,k) 线性码能够发现 l 个错误的充要条件是码的最小距离为 dmin=l+1 或 l=dmin1 (6.2.19) 证明： 设：发送的码字为 V；接收的码字为 R；U 为任

47、意其它码字； 则：矢量V、R、U间满足距离的三角不等式， d(R,V)+d(R,U)d(U,V) (6.2.20) 设：信道干扰使码字中码元发生错误的实际个数为 l，且l l d(R,V)l l (6.2.21) 由于d(U,V)dmin=l+1，代入式(6.2.20)得 d(R,U) d(U,V)d(R,V)=l+1l0 (6.2.22),6.2线性分组码,第六章 信道编码,2020/7/6,84,上式表明：由于接收字 R 与其它任何码字 U 的距离都大于0，则说明接收字 R 不会因发生 l 个错误变为其它码字，因而必能发现错误。 几何意义：,6.2线性分组码,第六章 信道编码,2020/7

48、/6,85,最小距离与检、纠错能力：(n,k) 线性码能纠 t 个错误，并能发现 l 个错误 (l t) 的充要条件是码的最小距离为 dmin=t+l+1 或 t+l=dmin1 (6.2.23) 证明：因为dmin2t+1，根据最小距离与纠错能力定理，该码可纠 t 个错误。 因为dminl+1，根据最小距离与检错能力定理，该码有检 l 个错误的能力。 纠错和检错不会发生混淆：设发送码字为 V，接收字为 R，实际错误数为 l，且 tt+1t (6.2.24) 因而不会把 R 误纠为 U。,第六章 信道编码,2020/7/6,86,几何意义：,第六章 信道编码,2020/7/6,87,(1) 循

49、环码的性质 循环码是线性分组码的一个重要子类； 循环码具有优良的代数结构。在结构上，它的循环性使得更容易用数学语言来描述；在性能上，具有明确的纠、检错能力，对于给定的码长n和信息位数k，已提出的各类循环码都有确定的纠、检错能力的理论计算值；在实现上，编码和译码都可以通过简单的反馈移位寄存器来完成,并可使用多种简单而有效的译码方法。 循环码是研究最深入、理论最成熟、应用最广泛的一类线性分组码。,6.3循环码,第六章 信道编码,2020/7/6,88,(2) 循环码的定义 循环码：如果 (n,k) 线性分组码的任意码矢 C=(Cn1,Cn2,C0) 的 i 次循环移位，所得矢量 C(i)=(Cn1

50、i,Cn2i,C0,Cn1,Cni) 仍是一个码矢，则称此线性码为 (n,k) 循环码。,6.3循环码,第六章 信道编码,2020/7/6,89,循环码的码矢的 i 次循环移位与码多项式的关系 上式表明：码矢循环一次的码多项式 C(1)(x) 是原码多项式 C(x)乘以 x 除以 (xn+1) 的余式。写作 因此， C(x) 的 i 次循环移位 C(i)(x) 是 C(x) 乘以 xi 除以 (xn+1) 的余式，即 结论：循环码的码矢的 i 次循环移位等效于将码多项式乘 xi 后再模 (xn+1)。,第六章 信道编码,2020/7/6,90,接收字循环移位的伴随式与伴随式循环移位的关系 定理

51、6.3.7：设 S(x) 为接收矢量 R(x) 的伴随式，则 R(x) 的循环移位 xR(x) (mod (xn+1) ) 的伴随式 S(1)(x) 等于伴随式 S(x) 的循环移位 xS(x) (mod g(x) )，即 S(1)(x)xS(x) (mod g(x) ) 证明： 由伴随式计算式(6.3.4)知 S(x)R(x) (mod g(x) ) 对上式两边作同余运算得 xS(x)xR(x) (mod g(x) ) (6.3.5) 令 R(1)(x)xR(x) (mod (xn+1) ) (6.3.6) 即用 R(1)(x) 表示 R(x) 循环移位一次 (mod (xn+1) ) 的码

52、多项式。,第六章 信道编码,2020/7/6,91,对式 (6.3.6) 进行模 g(x) 运算，得到 R(x) 循环移位 xR(x) 的伴随式 S(1)(x)xR(x) (mod g(x) ) 考虑到式(6.3.5)，则有 S(1)(x)xS(x) (mod g(x) ) 上式说明：接收矢量的循环移位（mod (xn+1) 运算下）与伴随式在模 g(x) 运算下（即在除以 g(x) 的伴随式计算电路中）的循环移位是一一对应的。,第六章 信道编码,2020/7/6,92,已知 (7,3) 循环码的全部码字 0000000 0011101 0111010 1101001 1010011 0100

53、111 1001110 (1) 写出该循环码的生成多项式 g(x) 和生成矩阵 G； (2) 写出一致监督矩阵 H； (3) 画出 k 级编码电路； (4) 画出译码电路。,课堂练习题,2020/7/6,93,x7+1=(x+1)(x3+x2+1)(x3+x+1) g(x)=(x+1)(x3+x+1)=x4+x3+x2+1 h(x)=(x3+x2+1),第六章 信道编码,2020/7/6,94,第六章 信道编码,2020/7/6,95,第六章 信道编码,2020/7/6,96,时间：2011年12月31日 7-9节 14：05-16：30 地点：3区2-101 考试形式：闭卷 考试题型：简答题(30分)，计算题(70分) 带计算器，计算题精确到小数点后2位 认真答题，字迹清楚，计算题须有中间过程,考试要求,2020/7/6,97,Let the end try the man！ -Shakespeare, Henry IV让最终的结局检验世人。 -莎士比亚，亨利四世,2020/7/6,98,再见,