第五章-无失真信源编码课件.ppt

《第五章-无失真信源编码课件.ppt》由会员分享，可在线阅读，更多相关《第五章-无失真信源编码课件.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第五五章章 无失真信源编码无失真信源编码5.1 信源编码的相关概念信源编码的相关概念5.2 定长码及定长编码定理定长码及定长编码定理5.3 变长码及变长编码定理变长码及变长编码定理5.4 变长码的编码方法变长码的编码方法5.5 实用的无失真信源码方法实用的无失真信源码方法5.1 信源编码的相关概念信源编码的相关概念n5.1.1 编码器编码器n 信源输出的符号序列，需要变换成适合信道传输的符号序列，一般称为码序列码序列，对信源输出的原始符号按照一定的数学规则进行的这种变换称为编码编码，完成编码功能的器件，称为编码器编码器。接收端有一个译译码器码器完成相反的功能。n 信源编码器的输入是信源符号集

2、 ，共有q个信源符号。同时存在另一个符号集 ，称为码符号集，共有r个码符号，码符号集中的元素称为码元码元或码符号码符号，编码器的作用就是将信源符号集 Si 中的符号 变换成由 个码符号组成的一一对应的码符号序列。编码器输出的码符号序列称为码字码字，并用 来表示，它与信源符号 之间是一一对应的关系，如图5.1所示。n 码字的集合C称为码码，即 。信源符号 对应的码字 包含 个码符号，称为码字长度码字长度，简称码长码长。n 所以，信源编码就是把信源符号序列变换到码符号序列的一种映射。若要实现无失真编码无失真编码，那么这种映射必须是一一对应的、可逆的。一般来说，人们总是希望把信源所有的信息毫无保留地

3、传递到接收端，即实现无失真传递，所以首先要对信源实现无失真编码。图5.1 信源编码器5.1.2 码的分类码的分类n1.分组码和非分组码分组码和非分组码n 定义定义5.1 将信源符号集中的每个信源符号 固定地映射成一个码字 ，这样的码称为分组码。分组码。n 用分组码对信源符号进行编码时，为了使接收端能够迅速准确地将码译出，分组码必须具有一些直观属性。与分组码对应的是非分组码非分组码，又称为树码树码、树码编码器输出的码符号通常与编码器的所有信源符号都有关。n2.奇异码与非奇异码奇异码与非奇异码n 定义定义5.2 若一种分组码中的所有码字都不相同，则称此分组码为非非奇异码奇异码，否则称为奇异码奇异码

4、。n3.唯一可译码与非唯一可译码唯一可译码与非唯一可译码n 定义定义5.3 任意有限长的码元序列，如果只能唯一地分割成一个个码字，便称为唯一可译码唯一可译码。n 唯一可译码的物理含义是指不仅要求不同的码字表示不同的信源符号，而且还要求对由信源符号构成的符号序列进行编码时，在接收端仍能正确译码而不发生混淆。唯一可译码首先是非奇异码，且任意有限长的码字序列不会雷同。n4.即时码与非即时码即时码与非即时码n 定义定义5.4 无需考虑后续的码符号就可以从码符号序列中译出码字，这样的唯一可译码称为即时码即时码。n 下面讨论唯一可译码成为即时码的条件。n 定义定义5.5 设 为一码字，对于任意的 ，称码符

5、号序列的前j个元素 为码字的前缀。n 按照上述的前缀的定义，有下述结论：n n 定理定理5.1 一个唯一可译码成为即时码n 的充要条件是其中任何一个码字都不是n 其他码字的前缀。n 即时码可以用树图来构造图5.2是一个n 二元即时码的树图图5.2 二元即时码的树图n 树是没有回路的图，所以它也是由节点和弧构成的树中最顶部的节点称为根节点根节点，没有子节点的节点称为叶子节点叶子节点。n 所有根节点的子节点称为一阶节点一阶节点，所有一阶节点的子节点称为二二阶节点阶节点，依此类推。阶节点最多有 个。节点的阶次又称为节点的深度深度。n 综上所述，可将信源编码作如下分类：码非分组码（树码）分组码（块码）

6、奇异码非奇异码非唯一可译码唯一可译码即时码非即时码n 定长编码的信息传输效率是很低的。提高信息传输效率的方法有：n 方法方法1 考虑符号之间的依赖关系，对信源S的扩展信源进行编码。方法方法2对于概率等于0或非常小的符号序列不予编码。n 定理定理5.2 离散无记忆信源的熵为H(S)，若对信源长为N的序列进行定长编码，码符号集X中有r个码符号，码长为l，则对于任意 ，只要满足n 则当N足够大时，可实现几乎无失真编码，即译码错误概率任小；反之，如果n n 则不可能实现几乎无失真编码，即当N足够大时，译码错误概率为1。n 定义定义5.7 定义 为编码效率编码效率。n 由定理5.2可得最佳编码效率为 ，

7、所以n 在已知方差和信源熵的条件下，信源符号序列长度N与最佳编码效率和允许错误概率 的关系为：n n 当允许错误概率越小，编码效率又要高，那么信源符号序列长度N必须越长在实际情况下，要实现几乎无失真的定长编码，N需要的长度将会大到难以实现。n 对于唯一可译码，该不等式又称为McMillan不等式。n 定理定理5.4 唯一可译码存在的充要条件是n n r为码符号个数，为码字长度，q为信源符号个数。n 定理5.4指出了唯一可译码中r、q、之间的关系，如果满足这个不等式的条件，则一定能够构成至少一种唯一可译码，否则，无法构成唯一可译码它给出了唯一可译变长码的存在性。n 另外，从定理5.3和定理5.4

8、可以得到一个重要的结论，即任何一个唯一可译码均可用一个相同码长的即时码来代替，因为即时码很容易用树图法构造，因此要构造唯一可译码，只要构造即时码就可以了。(5.12)5.3.2 唯一可译码的判别准则唯一可译码的判别准则n A.A.Sardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性此算法的原理如下所示：n n n 其中 都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时 一定是 的前缀，而 的尾随后缀一定是另一码字 的前缀；而 的尾随后缀又是其他码字的前缀最后，码符号序列的尾部一定是一个码字。n 设C为码字

9、集合，按以下步骤构造此码的尾随后缀集合F：n (1)考查C中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中；n (2)考查C和 两个集合，若 是 的前缀或 是 的前缀，则将相应的后缀作为尾随后缀码放入集合 中；n (3)即为码C的尾随后缀集合；n (4)若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)；否则若F中没有出现新的元素，则返回真。n n 定理定理5.5 一个码是唯一可译码的充要条件是的 并集中没有C中的码字。5.3.3 无失真变长编码定理无失真变长编码定理n 定义定义5.8 设有信源nn 编码后的码字分别为 ，各码字相应的码长分别为 因为是唯一

10、可译码，信源符号 和码字 一一对应，则定义此码的平均码平均码长长为nn 其中，表示每个信源符号平均需用的码元数。n 当信源给定时，信源熵H(S)就确定了，而编码后每个信源符号平均用 个码元来变换，故平均每个码元载荷的信息量即编码后信源的信息传输率。码符号/信源符号(5.20)n 定义定义5.9 编码后信源的信息传输率为nn 如果传输一个码符号平均需要t秒时间，则编码后信源每秒钟提供的信息量为nn 可以看出，越小，则 越大，信息传输率就越高，因此我们感兴趣的码是使平均码长 最短的码。n 定义定义5.10 对于给定的信源和码符号集，若有一个唯一可译码，其平均码长 小于所有其他唯一可译码，则称这种码

11、为紧致码紧致码或最佳码最佳码。n 无失真信源编码的核心问题就是寻找紧致码比特/码符号(5.21)(5.22)5.3.4 香农第一编码定理香农第一编码定理n 定理定理5.7 设离散无记忆信源S的信源熵H(S)，它的N次扩展信源 ，其熵 。并用码符号 对信源 进行编码，总可以找到一种唯一可译码，使信源S中每个信源符号所需的平均码长满足nn 或者写成n n 定理5.6可以看作定理5.7在N=1时的特殊情况。n 定理5.7是香农信息论的主要定理之一。(5.34)(5.35)n 定义定义5.11 编码后信道的信息传输率信息传输率为nn n n 这里，所以n 无失真信源编码的实质就是对离散信源进行适当的变

12、换，使变换后新的码符号信源(信道的输入)尽可能为等概率分布，使新信源的每个码符号平均所含的信息量达到最大，从而使信道的信息传输率R达到信道容量，实现信源与信道理想的统计匹配。这就是香农第一定理的物理意义。比特/码符号(5.43)比特/信源符号码符号/信源符号n 另外，为了衡量各种编码与最佳码的差距，引入码的剩余度的概念。n 定义定义5.13 定义nn 为码的剩余度剩余度。n 在二元无噪无损信道中r=2，所以在二元无噪无损信道中信息传输率n n 注意它们数值相同，单位不同是个无单位的比值，而R的单位是比特/码符号。(5.45)5.4 变长码的编码方法变长码的编码方法n 本章介绍的变长码的常见编码

13、方法，如香农编码、香农-费诺-埃利斯编码、霍夫曼编码、费诺编码均为匹配编码，也称统计编码统计编码，都是通过使用较短的码字来给出现概率较高的信源符号编码。而出现概率较小的信源符号用较长的码字来编码，从而使平均码长最短，达到最佳编码的目的。下面介绍这几种方法：n5.4.1 香农编码香农编码n 香农码的方法是选择每个码字长度 满足n 按照香农编码方法构造的码，其平均码长 不超过上界，即5.4.2 香农香农-费诺费诺-埃利斯编码埃利斯编码n 将香农编码中的累加概率换成修正累加概率即可得到相应的香农-费诺-埃利斯编码：n (1)计算出各个信源符号的修正累加概率n n (2)按下式计算第i个消息的二元代码

14、组的码长n (3)将累加概率 (十进制小数)变换成二进制小数根据码长 取小数点后 个二进制符号作为第i个消息的码字5.4.3 霍夫曼编码霍夫曼编码n这是霍夫曼于1952年提出的一种构造紧致码的方法具体方法如下：n(1)q将个信源符号按概率大小递减排列 n(2)用“0，1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减信源 ；n(3)把缩减信源 的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的缩减信源 ；n(4)依次继续下去

15、，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；n(5)然后从最后一级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即相应的码字。n霍夫曼编码方法得到的码并非是唯一的。造成非唯一的原因有两个：n(1)每次对信源缩减时，赋予最后两个概率最小的信源符号的码符号“0”和“1”是可以互换的，所以可得到不同的霍夫曼码；n(2)对信源进行缩减时，如果两个概率最小的信源符号合并后的概率与其他信源符号的概率相同，则在进行概率排序时的次序可以是任意的，因此会得到不同的霍夫曼码。n霍夫曼码是用概率匹配的方法进行信源编码它有两个明显特点：n(1)霍夫曼码的

16、编码方法保证了概率大的信源符号对应的码长小，概率小的信源符号对应的码长大，充分利用了短码；n(2)每次缩减信源的最长两个码字有相同的码长，并且仅仅只有最后一位码符号不同。n定理定理5.8 霍夫曼码是紧致码。5.4.5 费诺编码费诺编码n费诺码编码过程如下：n(1)将信源符号 以概率递减次序排列，即n(2)将依次排列的信源符号以概率分为两组，使两个组的概率和基本相等，并对各组赋予二元码符号“0”和“1”；n(3)将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率和近于相等，又分别赋予各组二元码符号“0”和“1”；n(4)如此重复，直至每组只剩下一个信源符号为止；n(5)信源符号所对应的

17、码符号序列即为费诺码编码平均码长信息传输率R香农码霍夫曼费诺码3.142.722.740.8310.9590.953 以上讨论了霍夫曼码和其他一些编码方法，并且证明了霍夫曼码是最佳码，当N不很大时，它能使无失真编码的效率接近于1，但是在实际使用时设备较复杂。首先，每个信源符号所对应的码 长不同，一般情况下，信源符号 以匀速输出，信道也是匀速传输 的。其次，差错扩散的问题变长码 的一个码元的差错可能造成译码 错误，并且还会造成同步错误，结果后面一系列码字也会译错。最后，霍夫曼码的编译码需要用 查表的方法来进行。表5.15 三种编码方法的比较5.5 实用的无失真信源编码方法实用的无失真信源编码方法

18、n5.5.1 游程编码游程编码n 游程编码主要用于黑白二值文件、传真的数据压缩。由于传真文件中连“0”和连“1”较多这些连“0”或连“1”的字符串称为游程对游程长度进行霍夫曼编码或其他的编码处理就可以达到压缩数据的目的。n 图5.5是一幅1050黑白二值图像。图5.5 二值图像n n MH编码是一种实用的游程编码算法，应用于黑、白传真数据的压缩编码，根据不同的黑、白游程长度有两张结尾码表和两张组合码表其基本的编码规范为n (1)游程长度在063时，直接查表用相应的结尾码作为码字；n (2)游程长度在641728范围内时，用组合码加上结尾码作为相应的码字；n (3)每行的第一个游程规定为白游程(

19、长度可以为零)，每行用一个结束码(EOL)终止；n (4)在传输时，每页数据之前加一个结束码，每页尾部连续实用6个结束码。5.5.2 算术编码算术编码n 算术式编码是一种非分组码，无需计算出所有N长信源序列的概率分布及码表，可以直接对输入的信源符号序列编码输出。这种方法是由香农-费诺-埃利斯编码直接扩展得到的。n n 算术式编码算法的中心思想是高效地计算n长信源符号序列x的分布概率p(x)和累积概率F(x)，然后用区间F(x)-p(x),F(x)中的一个值来作为x的码字。n n 假定信源是二进制的，并且分组的长度n已知。n 定义定义5.14 两个n长信源符号序列x和y，定义x大于y，当第一个使

20、得 的i有 。5.5.3 LZW码码nLZW码也称基于字典的编码方法，它是定长码。n(1)基于字典编码的基本原理n 计算机文件是以字节为单位组成的。LZW码是一种自适应变码，它的字典是直接由被压缩文件在编码过程中生成的。n(2)字典的构成n 字典的容量为4096(04095),序号用12bit表示最后一个单词(第4095个单词)为空。n(3)算法n 字典初始化n 动态数据初始化：初始化新单词存放位置指针P，将它指向字典的第一个空位置。n 如果文件再没有字符了，输出当前单词W的序号。编码结束。如果文件中还有字符，把当前单词W作为前缀，再从被压缩文件中读入一个字符CH，把CH作为尾字符，得到一个单

21、词 。n 如果字典中已有 ，则将 看作当前单词W，返回。如果字典中没有 (发现一个新单词)，先将原单词W的序号输出，再加新单词 ，增加到字典中，然后把刚刚读入的字符CH作为当前单词W，返回。n(4)适用文件类型n 不适合小文件的压缩(因为压缩编码初期，由于字典中的单词很少，字典对压缩效果的贡献也很少，主要是进行字典的扩充)，也不适合太大的文件(因字典容量有限，文件太大时字典满了，效率将受到制约)适合内容有明显单词结构的文件(如文本文件、程序文件)。n(5)译码n 字典初始化n 动态数据初始化n 如果压缩中已经没有码字，解码结束。否则继续读入一个码字。n 如果读入的码字是无效码字FFF，则解码结束，否则下一步。n 如果在字典中已经有该码字对应的单词，则采用递归算法，输出该单词的内容。并将单词的第一个有效字符作为尾字符，将已经记忆的前一个码字作为前缀，组成一个新单词，写入字典中，然后将当前码字记忆下来，返回；否则，首先在字典中生成新的单词，然后再输出这个单词，将新单词的码字记忆下来，返回。这时的新单词一定是首尾相同的单词。n(6)LZW编码算法的优化