2022年信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考试知识点复习

1、学习必备精品知识点第五章无失真信源编码定理与编码511 信源编码和码的类型1信源编码2码的类型若码符号集中符号数r=2 称为二元码， r=3 称为三元码， r 元码。若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。若每个码符号 xix 的传输时间都相同则称为同价码，否则称为非同价码。若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码，否则称为非唯一可译码。若分组码中，没有任何完整的码字是其他码字的前缀，则称为即时码(又称非延长码或前缀条件码 )，否则称为延长码。本章主要研究的是同价唯一可译码

2、。512 即时码及其树图构造法即时码 (非延长码或前缀条件码 )是唯一可译码的一类子码。即时码可用树图法来构造。构造的要点是：(1)最上端为树根 a，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 12 页 - - - - - - - - -学习必备精品知识点为节点。(2)从每个节点再伸出r 枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。一直继续进行，直至都不能伸枝为止。(3)每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。即时码

3、可用树图法来进行编码和译码。从树图可知，即时码可以即时进行译码。当码字长度给定，即时码不是唯一的。可以认为等长唯一可译码是即时码的一类子码。513 唯一可译码存在的充要条件(1)对含有 q 个信源符号的信源用含r 个符号的码符号集进行编码， 各码字的码长为 l1，l2， lq的唯一可译码存在的充要条件是，满足kraft 不等式514 唯一可译码的判断法唯一可译码的判断步骤：首先，观察是否是非奇异码。若是奇异码则一定不是唯一可译码。其次，计算是否满足kraft 不等式。若不满足一定不是唯一可译码。再次，将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是唯一可译码。或用 sardinas

4、和 patterson设计的判断方法：计算出分组码中所有可能的尾精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 12 页 - - - - - - - - -学习必备精品知识点随后缀集合 f，观察 f 中有没有包含任一码字，若无则为唯一可译码；若有则一定不是唯一可译码。上述判断步骤中sardinas和 patterson设计的判断方法是能确切地判断出是否是唯一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。515 渐近等分割性和 典型序列则称此 n 长序列 i 为非典型序列。(2)典型序列集精品学习资料 可选择p d f - - -

5、- - - - - - - - - - - 第 3 页，共 12 页 - - - - - - - - -学习必备精品知识点516 无失真等长信源编码定理离散信源 s，其信息熵为 h，用含 r 个字母的码符号集对n 长信源符号序列进行等长编码，若满足 l/nh/logr+(0 的任意小数 )， 则当 n 足够大时，可实现几乎无失真编码。其中，当 s 为离散无记忆信源时， h=h(s)；当 s为离散平稳信源， h为信源的极限熵；当 s为马尔可夫信源， h为马尔可夫信源的极限熵。517 无失真变长信源编码定理(香农第一定理 ) 用含 r 个字母的码符号集对n 长信源符号序列进行变长编码， 总能找到一

6、种无失真的唯一可译码，使信源符号所需平均码长满足：精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 12 页 - - - - - - - - -学习必备精品知识点518 无失真信源编码定理和数据压缩1无失真数据压缩的极限值无失真信源编码定理(无论等长码还是变长码)在理论上指出离散信源的信息熵是信源无失真数据压缩的极限值。在实际应用上，变长码与等长码相比较，当n 不很大时，变长码能更快地接近这极限值，更快地获得较好的压缩效果。无失真的信源数据压缩是实现减少或消除信源的剩余度，所以在工程实用中又称为冗余度压缩编码。通过无失真数据压缩编码可使信道

7、的信息传输率提高，(提高了信息传输系统的有效性)达到信源与信道的匹配，使信道得到充分利用。2编码后信源信息率、码率和编码效率(1)编码后信源信息率信源编码后平均每个信源符号能载荷的最大信息量，即精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 12 页 - - - - - - - - -学习必备精品知识点519 最佳二元码平均码长为最短的即时码称为最佳码(又称紧致码 )。对于某个给定分布的离散信源，存在一个二元最佳码，此码满足如下性质：(1)概率大的信源符号所对应的码长不大于概率小的信源符号所对应的码长。(2)两个最小概率的信源符号所对应的

8、码字必具有相同码长。(3)两个最小概率的信源符号所对应的码字的差别，必与最后一位码元不同。对每一种信源编码需掌握其编码方法及其平均码长的极限值范围。所讨论的信源编码方法都是针对离散无记忆信源的。对于离散平稳信源只需将。 n 重概率空间看成无记忆信源进行编码即可。对于马尔可夫信源，可考虑不同状态下进行信源符号编码，压缩效果可得到改善。5110 香农(shannon)码精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 12 页 - - - - - - - - -学习必备精品知识点1编码方法5111 费诺(fano)码1编码方法 (r 元费诺码

9、) (1)将信源符号以概率递减的次序排列。(2)将它们划分成 r 个组，使每组的概率和接近相同，并各赋予一位码元。(3)再将每一组按同样原则划分，重复步骤(2)，直至各组不再可分为止。这样，所对应的码符号序列则为所编码字。2平均码长的极限5112 霍夫曼(huffman)码1编码方法 (r 元霍夫曼码 ) (1)信源符号个数 q 必须满足 q=(r-1)+r(表示缩减次数 )。不满足时，设一些概率为零的虚假符号，使其满足。当r=2 时，任意整数 q 一定满足。(2)将信源符号以概率递减的次序排列。(3)给 r 个概率最小的信源符号各分配一位码元，并将它们合并成一个新符号，r 个最小的概率之和作

10、为新符号的概率，从而得到只包含q-(r-1)个信源符号的新缩减信源 s1。(4)把缩减信源 s1重新按概率递减的次序排列(若此时把所得的新符号尽可能排列在靠前位置上，所得码的方差最小)，重复步骤 (3)，得只含 q-2(r-1)个信源符精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 12 页 - - - - - - - - -学习必备精品知识点号的缩减信源 s2。(5)以此继续， 直至缩减信源只剩r 个符号为止。 然后，从最后一级缩减信源起，依编码路径向前返回，所得码符号序列就是所对应的码字。2平均码长的极限信源给定情况下， 霍夫曼码是最

11、佳即时码。其各码字的码长是唯一的，但具体码字不是唯一的。平均码长的界限为5113 香农-费诺-埃利斯码1编码方法(1)将信源符号 x=a1，a2， aq)依次排列 (不要求以概率大小排序 )。5114 游程编码和 mh 编码1游程编码 (rlc) 游程编码是一种针对相关信源的有效编码方法，尤其适用于二元相关信源。有时实际工程技术中常将游程编码和其他编码方法混合使用，能获得更好的压缩效果。信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串，称这种字符串的长度为游程， 又称游长。游程编码就是将信源字符序列映射成串精品学习资料 可选择p d f - - - - - - - - - -

12、- - - - 第 8 页，共 12 页 - - - - - - - - -学习必备精品知识点的字符、串的长度和串的位置的标志序列。(1)二元信源游程编码编码方法：将一维二元序列中，分出一段一段的“0”符号串和“ 1”符号串，对应段中的符号个数标记为“ 0”游程长度 l(0)和“1”游程长度 l(1)。对串的长度即游程长度用自然数标记，并一般规定信源序列从“0”游程起始，所以二元信源序列总是“0”游程和“ 1”游程交替出现。将二元信源序列映射成交替出现的表示游程长度的自然数序列(即为对应的游程长度的标志序列 )。一般情况，对“ 0”游程长度和“ 1”游程长度也可分别编码，建立各自的码字和码表

13、(如霍夫曼编码 )。编码效率 (游程编码和霍夫曼编码 ) 其中 p0，p1为“0”和“1”符号的概率。 0和1为游程长度为“ 0”和“1”霍夫曼编码效率。(2)多元信源游程编码将多元信源输出的多元序列映射成一一对应的标志序列。一维多元信源序列需选用表示串的字符、串的长度的两个标志参量。二维多元信源序列需选用表示串的字符、串的长度及串的位置三个标志参量。2mh 编码精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 9 页，共 12 页 - - - - - - - - -学习必备精品知识点mh 编码是用于黑白二值文件传真的数据压缩码。它是一维编码方案。它是

14、游程编码和霍夫曼码相结合的一种标准的改进霍夫曼码。根据“黑” 、 “白”的不同游程长度有两张结尾码(终端码 )表和两张组合码 (形成码)表。(1)编码方法游程长度在 063 时，直接查表用相应的结尾码为码字。游程长度在 641728时，用组合码加上结尾码为相应码字。规定每行从白游程开始，每行结束用结束码(eol)。用于传输时， 每页文件开始第一数据前加一结束码，每页结尾连续用 6 个结束码。为了传输还要考虑实现同步的操作。5115 算术编码算术编码是非分组码， 它从全信源序列出发， 考虑符号之间的依赖关系直接对信源符号序列进行的编码。算术编码的主要概念是将信源符号序列的累积分布函数和0，1)区

15、间中的一个数 c 联系起来，不同的信源符号序列对应于不同的无重叠小区间中的数。所以，这个码是即时码。1编码方法(1)用递推公式计算信源序列的累积分布函数f(s)和所对应区间的宽度a(s)：精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 10 页，共 12 页 - - - - - - - - -学习必备精品知识点5116 字典码字典码又称 lz 码，是一种通用编码方法，无需知道信源的统计特性，而且编码效率很高。基本算法是，将长度不同的符号串编成一个个新的短语(符号串 )，形成短语词典的索引表，进行编译码。1lz-77 编码编码算法的主要思想是设一个滑动窗口，将已输入的数据流存储起来， 作为字典使用。然后用三元标识(k，l，d)即(移位数，匹配串长度，首字符)，对数据流编码，形成标识符序列。此编码字典不用传送，可以边译码，边建立译码字典。2lz-78 编码精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 11 页，共 12 页 - - - - - - - - -学习必备精品知识点lz-78 是一种分段编码算法。 他的短语词典是由前面已见到的文本