《信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考试知识点复习_资格考试-报关员资格考试.pdf》由会员分享，可在线阅读，更多相关《信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考试知识点复习_资格考试-报关员资格考试.pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、学习必备 精品知识点 第五章 无失真信源编码定理与编码 511 信源编码和码的类型 1信源编码 2码的类型 若码符号集中符号数 r=2 称为二元码，r=3 称为三元码，r 元码。若分组码中所有码字的码长都相同则称为等长码，否则称为变长码。若分组码中所有码字都不相同则称为非奇异码，否则称为奇异码。若每个码符号 xiX 的传输时间都相同则称为同价码，否则称为非同价码。若分组码的任意一串有限长的码符号只能被唯一地译成所对应的信源符号序列则称为唯一可译码，否则称为非唯一可译码。若分组码中，没有任何完整的码字是其他码字的前缀，则称为即时码(又称非延长码或前缀条件码)，否则称为延长码。本章主要研究的是同价
2、唯一可译码。512 即时码及其树图构造法 即时码(非延长码或前缀条件码)是唯一可译码的一类子码。即时码可用树图法来构造。构造的要点是：(1)最上端为树根 A，从根出发向下伸出树枝，树枝总数等于 r，树枝的尽头学习必备 精品知识点 为节点。(2)从每个节点再伸出 r 枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。一直继续进行，直至都不能伸枝为止。(3)每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。即时码可用树图法来进行编码和译码。从树图可知，即时码可以即时进行译码。当码字长度给定，即时码不是唯一的。可以认为等长唯一可译码是即时码的一
3、类子码。513 唯一可译码存在的充要条件 (1)对含有 q 个信源符号的信源用含 r 个符号的码符号集进行编码，各码字的码长为 l1，l2，lq的唯一可译码存在的充要条件是，满足 Kraft 不等式 514 唯一可译码的判断法 唯一可译码的判断步骤：首先，观察是否是非奇异码。若是奇异码则一定不是唯一可译码。其次，计算是否满足 Kraft 不等式。若不满足一定不是唯一可译码。再次，将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是唯一可译码。或用 Sardinas 和 Patterson 设计的判断方法：计算出分组码中所有可能的尾数称为二元码称为三元码元码若分组码中所有码字的码长都相同
4、则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 随后缀集合 F，观察 F 中
5、有没有包含任一码字，若无则为唯一可译码；若有则一定不是唯一可译码。上述判断步骤中 Sardinas 和 Patterson 设计的判断方法是能确切地判断出是否是唯一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。515 渐近等分割性和典型序列 则称此 N 长序列i 为非典型序列。(2)典型序列集 数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章
6、主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 516 无失真等长信源编码定理 离散信源 S，其信息熵为 H，用含 r 个字母的码符号集对 N 长信源符号序列进行等长编码，若满足 l/NH/logr+(0 的任意小数)，则当 N 足够大时，可实现几乎无失真编码。其中，当 S 为离散无记忆信源时，H=H(S)；当 S
7、 为离散平稳信源，H为信源的极限熵；当 S 为马尔可夫信源，H为马尔可夫信源的极限熵。517 无失真变长信源编码定理(香农第一定理)用含 r 个字母的码符号集对 N 长信源符号序列进行变长编码，总能找到一种无失真的唯一可译码，使信源符号所需平均码长满足：数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时
8、码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 518 无失真信源编码定理和数据压缩 1无失真数据压缩的极限值 无失真信源编码定理(无论等长码还是变长码)在理论上指出离散信源的信息熵是信源无失真数据压缩的极限值。在实际应用上，变长码与等长码相比较，当N 不很大时，变长码能更快地接近这极限值，更快地获得较好的压缩效果。无失真的信源数据压缩是实现减少或消除信源的剩余度
9、，所以在工程实用中又称为冗余度压缩编码。通过无失真数据压缩编码可使信道的信息传输率提高，(提高了信息传输系统的有效性)达到信源与信道的匹配，使信道得到充分利用。2编码后信源信息率、码率和编码效率 (1)编码后信源信息率 信源编码后平均每个信源符号能载荷的最大信息量，即 数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及
10、其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 519 最佳二元码 平均码长为最短的即时码称为最佳码(又称紧致码)。对于某个给定分布的离散信源，存在一个二元最佳码，此码满足如下性质：(1)概率大的信源符号所对应的码长不大于概率小的信源符号所对应的码长。(2)两个最小概率的信源符号所对应的码字必具有相同码长。(3)两个最小概率的信源符号所对应的码字的
11、差别，必与最后一位码元不同。对每一种信源编码需掌握其编码方法及其平均码长的极限值范围。所讨论的信源编码方法都是针对离散无记忆信源的。对于离散平稳信源只需将。N 重概率空间看成无记忆信源进行编码即可。对于马尔可夫信源，可考虑不同状态下进行信源符号编码，压缩效果可得到改善。5110 香农(Shannon)码 数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本
12、章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 1编码方法 5111 费诺(Fano)码 1编码方法(r 元费诺码)(1)将信源符号以概率递减的次序排列。(2)将它们划分成 r 个组，使每组的概率和接近相同，并各赋予一位码元。(3)再将每一组按同样原则划分，重复步骤(2)，直至各组不再可分为止。这样，所对应的码符
13、号序列则为所编码字。2平均码长的极限 5112 霍夫曼(Huffman)码 1编码方法(r 元霍夫曼码)(1)信源符号个数 q 必须满足 q=(r-1)+r(表示缩减次数)。不满足时，设一些概率为零的虚假符号，使其满足。当 r=2 时，任意整数 q 一定满足。(2)将信源符号以概率递减的次序排列。(3)给 r 个概率最小的信源符号各分配一位码元，并将它们合并成一个新符号，r 个最小的概率之和作为新符号的概率，从而得到只包含 q-(r-1)个信源符号的新缩减信源 S1。(4)把缩减信源S1重新按概率递减的次序排列(若此时把所得的新符号尽可能排列在靠前位置上，所得码的方差最小)，重复步骤(3)，得
14、只含 q-2(r-1)个信源符数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号
15、序列则为终端节点的码字即时码可用树图学习必备 精品知识点 号的缩减信源 S2。(5)以此继续，直至缩减信源只剩 r 个符号为止。然后，从最后一级缩减信源起，依编码路径向前返回，所得码符号序列就是所对应的码字。2平均码长的极限 信源给定情况下，霍夫曼码是最佳即时码。其各码字的码长是唯一的，但具体码字不是唯一的。平均码长的界限为 5113 香农-费诺-埃利斯码 1编码方法 (1)将信源符号 X=a1，a2，aq)依次排列(不要求以概率大小排序)。5114 游程编码和 MH 编码 1游程编码(RLC)游程编码是一种针对相关信源的有效编码方法，尤其适用于二元相关信源。有时实际工程技术中常将游程编码和其
16、他编码方法混合使用，能获得更好的压缩效果。信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串，称这种字符串的长度为游程，又称游长。游程编码就是将信源字符序列映射成串数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树
17、枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 的字符、串的长度和串的位置的标志序列。(1)二元信源游程编码 编码方法：将一维二元序列中，分出一段一段的“0”符号串和“1”符号串，对应段中的符号个数标记为“0”游程长度 L(0)和“1”游程长度 L(1)。对串的长度即游程长度用自然数标记，并一般规定信源序列从“0”游程起始，所以二元信源序列总是“0”游程和“1”游程交替出现。将二元信源序列映射成交替出现的表示游程长度的自然数序列(即为对应
18、的游程长度的标志序列)。一般情况，对“0”游程长度和“1”游程长度也可分别编码，建立各自的码字和码表(如霍夫曼编码)。编码效率(游程编码和霍夫曼编码)其中 p0，p1为“0”和“1”符号的概率。0和1为游程长度为“0”和“1”霍夫曼编码效率。(2)多元信源游程编码 将多元信源输出的多元序列映射成一一对应的标志序列。一维多元信源序列需选用表示串的字符、串的长度的两个标志参量。二维多元信源序列需选用表示串的字符、串的长度及串的位置三个标志参量。2MH 编码 数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个
19、码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 MH 编码是用于黑白二值文件传真的数据压缩码。它是一维编码方案。它是游程编码和霍夫曼码相结合的一种标准的改进霍夫曼
20、码。根据“黑”、“白”的不同游程长度有两张结尾码(终端码)表和两张组合码(形成码)表。(1)编码方法 游程长度在 063 时，直接查表用相应的结尾码为码字。游程长度在 641728 时，用组合码加上结尾码为相应码字。规定每行从白游程开始，每行结束用结束码(EOL)。用于传输时，每页文件开始第一数据前加一结束码，每页结尾连续用 6 个结束码。为了传输还要考虑实现同步的操作。5115 算术编码 算术编码是非分组码，它从全信源序列出发，考虑符号之间的依赖关系直接对信源符号序列进行的编码。算术编码的主要概念是将信源符号序列的累积分布函数和0，1)区间中的一个数 C 联系起来，不同的信源符号序列对应于不
21、同的无重叠小区间中的数。所以，这个码是即时码。1编码方法 (1)用递推公式计算信源序列的累积分布函数F(s)和所对应区间的宽度 A(s)：数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点
22、为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图学习必备 精品知识点 5116 字典码 字典码又称 LZ 码，是一种通用编码方法，无需知道信源的统计特性，而且编码效率很高。基本算法是，将长度不同的符号串编成一个个新的短语(符号串)，形成短语词典的索引表，进行编译码。1LZ-77编码 编码算法的主要思想是设一个滑动窗口，将已输入的数据流存储起来，作为字典使用。然后用三元标识(K，l，d)即(移位数，匹配串长度，首字符)，对数据流编码，形成标识符序列。此编码字典不用传送，可以边译码，边建立译码字典。2L
23、Z-78编码 数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点
24、的码字即时码可用树图学习必备 精品知识点 LZ-78是一种分段编码算法。他的短语词典是由前面已见到的文本进行分段来定义的。因而可将标识改为二元标识的形式。同样可以边译码边建成字典表。3LZW 编码 LZW 编码是 LZ 系列码中应用最广，变形最多的码。编码算法则是先建立初始化字典，再分解输入数据为“短语词条”，形成新词条，构成编码器的字典表。编码时只需一项指向字典的指针标识符，实现简化标识。此编码译码时需首先建立初始化字典，然后边译码边重建字典表。数称为二元码称为三元码元码若分组码中所有码字的码长都相同则称为等长码否则称为变长码若分组码中所有码字都不相同则称为非奇异码否则称为奇异码若每个码符号的传输时间都相同则称为同价码否则称为非同价码若分组码的组码中没有任何完整的码字是其他码字的前缀则称为即时码又称非延长码或前缀条件码否则称为延长码本章主要研究的是同价唯一可译码即时码及其树图构造法即时码非延长码或前缀条件码是唯一可译码的一类子码即时码可用树图每个节点再伸出枝树枝当某节点被安排为码字后就不再伸枝这节点为终端节点一直继续进行直至都不能伸枝为止每个节点所伸出的树枝标上码符号从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字即时码可用树图