信息论与编码[第五章无失真信源编码定理与编码]山东大学期末考

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

2、码(非延长码或前缀条件码是唯一可译码的一类子码。即时码可用树图法来构造。构造的要点是：(1最上端为树根A，从根出发向下伸出树枝，树枝总数等于r，树枝的尽头为节点。(2从每个节点再伸出r枝树枝，当某节点被安排为码字后，就不再伸枝，这节点为终端节点。一直继续进行，直至都不能伸枝为止。(3每个节点所伸出的树枝标上码符号，从根出发到终端节点所走路径对应的码符号序列则为终端节点的码字。即时码可用树图法来进行编码和译码。从树图可知，即时码可以即时进行译码。当码字长度给定，即时码不是唯一的。可以认为等长唯一可译码是即时码的一类子码。513 唯一可译码存在的充要条件(1对含有q个信源符号的信源用含r个符号的码

3、符号集进行编码，各码字的码长为l1，l2，lq的唯一可译码存在的充要条件是，满足Kraft不等式514 唯一可译码的判断法唯一可译码的判断步骤：首先，观察是否是非奇异码。若是奇异码则一定不是唯一可译码。其次，计算是否满足Kraft不等式。若不满足一定不是唯一可译码。再次，将码画成一棵树图，观察是否满足即时码的树图的构造，若满足则是唯一可译码。或用Sardinas和Patterson设计的判断方法：计算出分组码中所有可能的尾随后缀集合F，观察F中有没有包含任一码字，若无则为唯一可译码；若有则一定不是唯一可译码。上述判断步骤中Sardinas和Patterson设计的判断方法是能确切地判断出是否是

4、唯一可译码的方法，所以可以跳过前三个步骤直接采用该判断法。515 渐近等分割性和典型序列则称此N长序列i为非典型序列。(2典型序列集516 无失真等长信源编码定理离散信源S，其信息熵为H，用含r个字母的码符号集对N长信源符号序列进行等长编码，若满足l/NH/logr+(>0的任意小数，则当N足够大时，可实现几乎无失真编码。其中，当S为离散无记忆信源时，H=H(S；当S为离散平稳信源，H为信源的极限熵；当S为马尔可夫信源，H为马尔可夫信源的极限熵。517 无失真变长信源编码定理(香农第一定理用含r个字母的码符号集对N长信源符号序列进行变长编码，总能找到一种无失真的唯一可译码，使信源符号所需

5、平均码长满足：518 无失真信源编码定理和数据压缩1无失真数据压缩的极限值无失真信源编码定理(无论等长码还是变长码在理论上指出离散信源的信息熵是信源无失真数据压缩的极限值。在实际应用上，变长码与等长码相比较，当N不很大时，变长码能更快地接近这极限值，更快地获得较好的压缩效果。无失真的信源数据压缩是实现减少或消除信源的剩余度，所以在工程实用中又称为冗余度压缩编码。通过无失真数据压缩编码可使信道的信息传输率提高，(提高了信息传输系统的有效性达到信源与信道的匹配，使信道得到充分利用。2编码后信源信息率、码率和编码效率(1编码后信源信息率信源编码后平均每个信源符号能载荷的最大信息量，即519 最佳二元

6、码平均码长为最短的即时码称为最佳码(又称紧致码。对于某个给定分布的离散信源，存在一个二元最佳码，此码满足如下性质：(1概率大的信源符号所对应的码长不大于概率小的信源符号所对应的码长。(2两个最小概率的信源符号所对应的码字必具有相同码长。(3两个最小概率的信源符号所对应的码字的差别，必与最后一位码元不同。·对每一种信源编码需掌握其编码方法及其平均码长的极限值范围。·所讨论的信源编码方法都是针对离散无记忆信源的。对于离散平稳信源只需将。N重概率空间看成无记忆信源进行编码即可。·对于马尔可夫信源，可考虑不同状态下进行信源符号编码，压缩效果可得到改善。5110 香农(Sh

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

8、的概率之和作为新符号的概率，从而得到只包含q-(r-1个信源符号的新缩减信源S1。(4把缩减信源S1重新按概率递减的次序排列(若此时把所得的新符号尽可能排列在靠前位置上，所得码的方差最小，重复步骤(3，得只含q-2(r-1个信源符号的缩减信源S2。(5以此继续，直至缩减信源只剩r个符号为止。然后，从最后一级缩减信源起，依编码路径向前返回，所得码符号序列就是所对应的码字。2平均码长的极限信源给定情况下，霍夫曼码是最佳即时码。其各码字的码长是唯一的，但具体码字不是唯一的。平均码长的界限为5113 香农-费诺-埃利斯码1编码方法(1将信源符号X=a1，a2，aq依次排列(不要求以概率大小排序。511

9、4 游程编码和MH编码1游程编码(RLC游程编码是一种针对相关信源的有效编码方法，尤其适用于二元相关信源。有时实际工程技术中常将游程编码和其他编码方法混合使用，能获得更好的压缩效果。信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串，称这种字符串的长度为游程，又称游长。游程编码就是将信源字符序列映射成串的字符、串的长度和串的位置的标志序列。(1二元信源游程编码编码方法：将一维二元序列中，分出一段一段的“0”符号串和“1”符号串，对应段中的符号个数标记为“0”游程长度L(0和“1”游程长度L(1。对串的长度即游程长度用自然数标记，并一般规定信源序列从“0”游程起始，所以二元信源序列

10、总是“0”游程和“1”游程交替出现。将二元信源序列映射成交替出现的表示游程长度的自然数序列(即为对应的游程长度的标志序列。一般情况，对“0”游程长度和“1”游程长度也可分别编码，建立各自的码字和码表(如霍夫曼编码。 编码效率(游程编码和霍夫曼编码其中p0，p1为“0”和“1”符号的概率。0和1为游程长度为“0”和“1”霍夫曼编码效率。(2多元信源游程编码将多元信源输出的多元序列映射成一一对应的标志序列。一维多元信源序列需选用表示串的字符、串的长度的两个标志参量。二维多元信源序列需选用表示串的字符、串的长度及串的位置三个标志参量。2MH编码MH编码是用于黑白二值文件传真的数据压缩码。它是一维编码

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

12、不同的信源符号序列对应于不同的无重叠小区间中的数。所以，这个码是即时码。1编码方法(1用递推公式计算信源序列的累积分布函数F(s和所对应区间的宽度A(s：5116 字典码字典码又称LZ码，是一种通用编码方法，无需知道信源的统计特性，而且编码效率很高。基本算法是，将长度不同的符号串编成一个个新的短语(符号串，形成短语词典的索引表，进行编译码。1LZ-77编码编码算法的主要思想是设一个滑动窗口，将已输入的数据流存储起来，作为字典使用。然后用三元标识(K，l，d即(移位数，匹配串长度，首字符，对数据流编码，形成标识符序列。此编码字典不用传送，可以边译码，边建立译码字典。2LZ-78编码LZ-78是一种分段编