信息论与编码技术：第五章 信源编码

《信息论与编码技术：第五章 信源编码》由会员分享，可在线阅读，更多相关《信息论与编码技术：第五章 信源编码（266页珍藏版）》请在金锄头文库上搜索。

1、1第五章第五章 信源编码信源编码5.1 编码器和相关概念编码器和相关概念5.2 变长编码变长编码 5.3 限失真信源编码限失真信源编码5.4 实用信源编码方法实用信源编码方法 信息由信源产生后通过信道传输到信宿的过程，即为通信。要做到既不失真又快速地通信，需要解决两个问题： 在不失真或允许一定失真条件下，如何提高信息传输速度(即如何用尽可能少的符号传送信源信息)这是本章要讨论的信源编码问题信源编码问题。 在信道受到干扰的情况下，如何增加信号的抗干扰能力，即尽量提高信息传输的可靠性，同时又使得信息传输率最大这是下章要讨论的信道编码问题信道编码问题。2 一般来说，抗干扰能力与信息传输率二者相互矛盾

2、。然而编码定理已从理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。 实际信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。 信信源源编编码码的的目目的的就就是是要要减减少少冗冗余余，提提高高编编码码效效率率针针对对信信源源输输出出符符号号序序列列的的统统计计特特性性，寻寻找找合合适适的的方方法法把把信信源源输出符号序列变换为最短的码字序列。输出符号序列变换为最短的码字序列。3信源编码的基本途径有两个信源编码的基本途径有两个: 一是编码后使序列中的各个符号之间尽可能地互相独立，即解除相关性。 去除信源符号之间冗

3、余度的有效方法包括预测编码和变换编码。 二是使编码后各个符号出现的概率尽可能相等，即均匀化分布。 去除信源符号概率分布冗余度的方法主要方法是统计编码。 上述方法已相当成熟，得到广泛应用，并被相应压缩编码的国际标准所采用。4 无失真信源编码无失真信源编码 (主要用于文字、数据信源的压缩)p 信源编码信源编码 限限失失真真信信源源编编码码 (主要用于图像、语音信源的压缩)p 本章重点内容： 信源编码的基本思路； 香农码、费诺码、霍夫曼码等变长编码方法； 限失真信源编码； 游程编码、算术编码、预测编码和变换编码等实用信源编码方法(其中以无失真、统计编码为主)。p 通过本章学习建立起信信源源压压缩缩编

4、编码码的的基基本本概概念念和掌握主主要的编码方法要的编码方法。55.1 编码器及相关概念器及相关概念 为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。6信源信源信源编码器信源编码器信道编码器信道编码器调调制制器器编码信道编码信道解解调调器器信宿信宿信源译码器信源译码器信道译码器信道译码器干扰干扰源源信道信道5.1.1 码的分的分类1.编码器模型编码器模型 由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。下图为一个编码器模型:7 编码器的输

5、入为信源符号集信源符号集S=s1,s2,sq。 X为 编 码 器 的 编编 码码 符符 号号 集集 X=x1,x2,xr， 其 中xi(i=1,r)为适合于信道传输的符号，称为码元码元(码符号码符号)。 由若干码元xi组成的对应信源符号si的输出序列Wi称为码码字字，Wi的长度li称为码码字字长长度度或码码长长，全体码字Wi的集合C称为码码或码书码书 。 编编码码器器将将信信源源符符号号集集中中的的信信源源符符号号si(或或长长为为N的的信信源源符符号号序序列列 )变变换换成成由由码码元元符符号号xi组组成成的的长长为为li的的与与信信源源符符号号si(或或信信源源符符号号序序列列 )一一一一

6、对对应应的的输输出出序序列列Wi(从从而而实实现现编编码码)。如如下图所示。下图所示。892.2.码的分类码的分类: : 根据编码器码符号集合X中码元的个数不同以及码字长度是否一致，有以下一些常用的编码形式：(1)二元码和二元码和r元码元码 若码符号集X=0,1 ，编码所得码字为一些适合在二元信道中传输的二元序列，则称二元码。二元码是数字通信与计算机系统中最常用的一种码。 若码符号集共有r个元素，X=0,1,r-1 ，则所得的码称为 r 元码。(2)等长码等长码 若一组码中所有码字Wi的长度都相同(即li=l, i=1, 2, ,q )，则称为等长码。10(3)(3)变长码变长码 若一组码中码

7、字Wi的码长各不相同(即码字长度li不等)，则称为变长码。 如表1中“编码1”为等长码，“编码2”为变长码。信源符号si符号出现概率p(si)编码1编码2s1p(s1)000s2p (s2)0101s3p (s3)10001s4p (s4)1110111(4)(4)分组码分组码 若每每个个信信源源符符号号si按按照照固固定定的的码码表表映映射射成成一一个个码码字字Wi，则称为分组码则称为分组码。否则就是非分组码非分组码。 如果采用分组编码方法，需要分组码具有某些属性，以保证在接收端能够迅速而准确地将接收到的码译成与信源符号对应的消息。分组码的直观属性分组码的直观属性:1)非奇异码和奇异码非奇异

8、码和奇异码 若一组码中所有码字Wi都不相同(即所有信源符号映射到不同的码符号序列)，则称为非非奇奇异异码码。反之，有相同码字Wi的一组码则为奇异码奇异码。1213信源符号概率p(ai) 编码1编码2编码3编码4编码5a11/2000001a21/401011001a31/810100100001a41/811101110000001表2中的“编码2”是奇异码，其他编码是非奇异码。2)同价码同价码 若码符号集X:x1,x2,xr中每个码符号所占的传输时间都相同，则所得的码为同价码同价码。 我们一般讨论同价码，对同价码来说等长码中每个码字的传输时间相同，而变长码中每个码字的传输时间就不一定相同。3

9、)码的码的N次扩展码次扩展码 假定某一码C，它把信源S=s1,s2,sq中的符号si一一变换成码C中的码字Wi，则码码C的的N次次扩扩展展码码是是长长度度为为N的的所所有有qN个码字组成的码字序列的集合个码字组成的码字序列的集合。14例如例如：若S=s1,s2,sq，C=W1,W2,Wq满足 则码C的N次扩展码集合 ,其中： 即码C的N次扩展码中，每个码字Bi与信源的N次扩展信源中的每个信源符号序列 是一一对应的：1516例例 设信源S的概率空间为 若把该信源的信号通过二元信道传输，就必须把信源变换成由0,1组成的码符号序列(二元序列)。 在诸多编码方法中，如采用上表“编码3”对信源进行编码，

10、当对“编码3”进行二次扩展时，得到“编码3的二次扩展编码”。 由于信源S的二次扩展信源为 17“编码3的二次扩展编码”如表3所示。(由编码3知：a10,a2 1,a3 00,a4 11)信源符号序列码 字信源符号序列码 字信源符号序列码 字00=B1=W1W1 10 11001=B2=W1W2 11 111000 100 1100011 11114)4)惟一可译码惟一可译码 若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟惟一一可可译译码码(或称单单义义可可译译码码)。否则就称为非惟一可译码非惟一可译码(非单义可译码非单义可译码) )。 若要使某一码为惟一可译码，

11、则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。例例如如：对于二元码C1=1,01,00，当任意给定一串码字序列，例如“10001101”，只可唯一地划分为1,00,01,1,01，因此C1是惟一可译码； 而 对 另 一 个 二 元 码 C2=0,10,01 ， 当 码 字 序 列 为“01001”时，可划分为0,10,01或01,0,01，所以C2是非惟一可译的。1819例例 设信源S的概率空间为 若把该信源的信号通过二元信道传输，就必须把信源变换成由0,1组成的二元序列。采用不同的二元序列与信源符号一一对应，可得到不同的二元码，如表4所示(取q=4)。 信源符号概率p(

12、ai) 编码1编码2a1p(ai)000a2p(a2)0101a3p(a3)10001a4p(a4)1111120信源符号概率p(ai) 编码1编码2a1p(ai)000a2p(a2)0101a3p(a3)10001a4p(a4)11111表4 上述两种码元中，“编码1”为非奇异码，唯一可译的等长码。 “编码2”为非奇异码、非唯一可译的变长码。对“编码2”，如果送入码符号序列0010，则可译成a1a2a1或a3a1，此时就产生了歧义，而非唯一可译。对惟一可译码的进一步说明：对惟一可译码的进一步说明： 惟一可译码又分为即时码即时码和非即时码非即时码： 如果在接收端收到一个完整的码字后，就能立即进

13、行译码，这样的码叫做即时码。 在接收端收到一个完整的码字后，还需等下一个码字(码符号)接收后才能判断是否可以译码，这样的码叫做非即时码。 即时码又称为非非延延长长码码，对即时码而言，在码书中任意一个码字都不是其它码字的前缀部分。 对非即时码来说，有的码是惟一可译的，有的码是非惟一可译的，主要取决于码的总体结构。 综上所述，惟一可译码不一定是即时码；即时码一定是惟一可译码；非即时码则不一定是惟一可译码。2122 信源符号概率p(ai) 编码1编码2编码3编码4编码5a11/2000001a21/401011001a31/810100100001a41/811101110000001 即时码与非即

14、时码举例 “编码1”和“编码5”是即时码；“编码4”是非即时码。 非奇异等长码一定是即时码，如“编码1”；而对“编码5”，只要收到符号1就表示该码字已完整，可以马上译码。23242526272829综上所述，可将码作如下分类：30注意注意：惟一可译码不一定是即时码； 即时码一定是惟一可译码； 非奇异等长码一定是即时码； 变长码不一定是即时码； 非即时码则不一定是惟一可译码。 313233n 首先，是否非奇异，奇异的一定不是唯一可译。n 如果是非奇异的，判断是否为唯一可译码可以借助Kraft不等式。n 这个不等式给出了唯一可译码的码长限制。n 如果码长符合kraft不等式，还可借助码数判断是否是

15、即时码判断变长码唯一可译的步骤：5.1.2 码树 对于给定码字C=W1,W2,Wq的全体集合，可以用码树表示码的构成和研究惟一可译码的判别。 对于r进制的码树，如码树图所示，其中图(a)为二元码树，图(b)为三元码树。5.1.2 码树树图树图中最顶部的节点称为根节点（树根）根节点（树根），没有子节点的节点称为叶子节点叶子节点。根节点的所有子节点称为一阶节点一阶节点，所有一阶节点的子节点称为二阶节点二阶节点，依此类推。n阶节点最多有rn个子节点。节点的阶次又称为节点的深度节点的深度。当码字长度给定后，用树图法安排的即时码不是惟一的。树没有回路树没有回路。如果指定某个n阶节点为叶子节点，用于表示一

16、个信源符号，则该节点就不再延伸，相应的码码字字即即为为从从树树根根到到此此端端点点的的分分枝枝标标号号序列，该序列长度为序列，该序列长度为n 用上述方法构造的码满足即时码的条件，因为从树根到每一个终端节点所走的路径均不相同，所以一定满足对即时码前缀的限制(每个码字都不是其他码字的前缀部分)。 【例】用树图法表示如下码。S:1,01,001,0001树根树根码字的起点码字的起点 分成分成r个树枝个树枝码的进码的进制数制数中间节点中间节点码字的一部分码字的一部分终端节点终端节点叶节点叶节点节数节数码长码长满树（整树）满树（整树）37 如果有q个信源符号，那么在码树上就要选择q个终端节点，用相应r的

17、元基本符号表示这些码字(即为从树根到此端点的分枝标号序列，该序列长度为n )。 若码树的各个分支都延伸到最后一级端点，此时将共有rn个码字，这样的码树称为整整树树，整树的码字为等长码，如图(a)所示。否则就称为非非整整树树，如图(b)所示，非整树的码字为非等长码。 因此，码树与码之间具有如下一一对应的关系： 树根树根码字起点；码字起点； 树枝数树枝数码的进制数；码的进制数； 节点节点码字或码字的一部分；码字或码字的一部分； 终端节点终端节点码字；码字； 阶数阶数码长；码长； 非整树非整树变长码；变长码； 整树整树等长码。等长码。3839例例 写出下图所示码树对应的码字，并判断这三棵码树所对应的

18、码的性质。40解解 对图(a)有 W1=0; W2=100; W3=111; W4=1010; W5= 1011 对图(b)有 W1=0; W2=10; W3=110; W4=1110 对图(c)有 W1=1; W2=10; W3=100; W4=1000码码性性质质分分析析：上述三个码都是变长码、非奇异码，其中(a)、(b)所有的码字都在终端节点上，所以是即时码；图(c)中码字有的落在终端节点上，有的落在非终端节点上，因而是非即时码。5.1.3 Kraft不等式不等式 利用码树可以判断给定的码是否为惟一可译码，但需要画出码树。 实际判断给定的码是否为惟一可译码时，可以利用克拉夫特(Kraft

19、)不等式，直接根据各码字的长度li来判断惟一可译码是否存在，即惟一可译码各码字的长度li应符合克拉夫特不等式：式中，r为进制数(即码符号的个数)，q为信源符号数。41 Kraft定理给出判断给定码字长度的编码是否为即时码的一个简单标准。定理定理(单义可可译定理定理) (1)如果C是一个码字长度分别为li(i=1,2,q)的r元(码字母表长度)即时码，则这些长度必须满足Kraft不等式：(2)如果数li(i=1,2,q)和r满足Kraft不等式，则存存在在一个码字长度分别为li(i=1,2,q)的r元即时码。42 该该定定理理说说明明必必存存在在某某些些即即时时码码，其其各各码码字字长长度度与与

20、一一组组编编码码C的的各各码码字字长长度度一一致致, ,且且C的的码码长长li(i=1,2,=1,2, ,q) )满满足足KraftKraft不不等等式式，这这样样的的即即时时码码可可通通过过码码树树构构造造出出来来。它它同同时时说说明明码码字字长长度度满满足足KraftKraft不等式时编码不等式时编码C未必是即时码。未必是即时码。例例 考虑二元编码C=0,11,100,110它们的码字长度分别为1,2,3,3，由于r=2，则满足Kraft不等式，但编码C不是即时码，因为码字11是码字110的前缀。 4344例例 设信源字符表X=x1,x2,x3,x4,x5,x6,做三元编码，则编码字符表A

21、=0,1,2,设n1=n2=1, n3=2, n4=n5=4, n6=5，由于则Kraft不等式成立，从而可以构造出一个以n1,n2,n6为码字长度的即时码。 首先选择最小的码字长度n1=n2=1编码 x1c1=0,x2c2=1 然后选择码字长度n3=2，由于编码是即时码，这个码字不能以0或1开头，所以它只能以2开头，编码 x3c3=2045 再选择码字长度n4=n5=4，这些码字不能以0或1开头，所以它必须以2开头，然而它们也不能以20开头，因为20是c3的码字，因此编码 x4c4=2100，x5c5=2101 最后选择码字长度5，以212开头，则 x6c6=21200这样码字符表为 C=0

22、,1,20,2100,2101,21200这一过程可由下图表示。46三元即时码的构造三元即时码的构造关于关于Kraft不等式的说明：不等式的说明： Kraft不等式是惟一可译码存在的充要条件，其必要性表现在如果码是惟一可译码，则必定满足Kraft不等式。如表2中，“编码1”、“编码4”和“编码5” 满足Kraft不等式。 充分性表现在如果满足Kraft不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可译码。 因此，Kraft不不等等式式是是惟惟一一可可译译码码存存在在的的充充要要条条件件，而而不是惟一可译码的充要条件不是惟一可译码的充要条件。4748例例

23、 判断前述表2所列5种编码是否满足Kraft不等式。解解 表2中所有码都是二元码，即r=2，有4个信源符号，即取 q=4，则 由计算结果可知，编码1、编码4和编码5满足Kraft不等式对应的码可能是唯一可译码，而编码2和编码3不满足Kraft不等式，对应的码一定不是唯一可译码。49例例 设二进制码树S:s1,s2,s3,s4，l1=1, l2=2, l3=2, l4=3, 用Kraft不等式判断 因此，不存在满足有这种li所确定的唯一可译码。 该结论也可用码树说明。如下图所示，要形成上述li限定的码，必须在中间节点设置码字：如果s1W1=0， s2W2=10，则由于l3=2，可取 s3W3=1

24、1(或其他取法)，则s4的编码只能取s3或 s2的延长码。50 如果将各码字的长度改为l1=1, l2=2, l3=3, l4=3，则此时满足Kraft不等式(见上例编码4)，因而满足这种li限定的唯一可译码是存在的。如上例中编码40,10,110,111即为一种唯一可译码。注意：注意： Kraft不不等等式式只只能能说说明明唯唯一一可可译译码码是是否否存存在在，并并不不能能作作为唯一可译码的判据。为唯一可译码的判据。 例如，码0,10,010,111也满足Kraft 不等式，但它不是唯一可译码。定义定义(异字头码异字头码|前缀码前缀码) 如果一个码的任何一个码字都不是另一个码字的前缀部分，则

25、称该码为前缀码。 前前缀码的判断方法：的判断方法： 只要把每个码字按其长度由小到大排列，再把每个码字与其后面的码字进行比较，看它与后面的码字的前边部分是否相同即可。只有要找到有一个是相同的，则这种码就不是前缀码，否则是前缀码。 如C1=0,01,001,0111不是前缀码；而C2=0, 10, 110, 1110是前缀码。 前前缀缀码码一一定定是是惟惟一一可可译译码码，是是即即时时码码；即即时时码码则则不不一一定定是前缀码是前缀码。 如C3=0,01,011,0111不是前缀码，但它是一个即时码(由收到的码序列每个0后边的1的个数可立即译码)。该码实际上是后缀码(略) 。51前前缀码的判断方法

26、：的判断方法： 只要把每个码字按其长度由小到大排列，再把每个码字与其后面的码字进行比较，看它与后面的码字的前边部分是否相同即可。只有要找到有一个是相同的，则这种码就不是前缀码，否则是前缀码。 如C1=0,01,001,0111不是前缀码；而C2=0, 10, 110, 1110是前缀码。 前前缀缀码码一一定定是是惟惟一一可可译译码码，是是即即时时码码；即即时时码码则则不不一一定定是前缀码是前缀码。 如C3=0,01,011,0111不是前缀码，但它是一个即时码(由收到的码序列每个0后边的1的个数可立即译码)。该码实际上是后缀码(略) 。5253唯一可译码的判别准则唯一可译码的判别准则A.A.S

27、ardinas和G.W.Patterson于1957年提出下述算法用于判断码C的唯一可译性此算法的原理如下所示： 其中 都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时 一定是 的前缀，而 的尾随后缀一定是另一码字 的前缀；而 的尾随后缀又是其他码字的前缀最后，码符号序列的尾部一定是一个码字。设C为码字集合，按以下步骤构造此码的尾随后缀集合F：(1) 考查C中所有的码字，若 是 的前缀，则将相应的后缀作为一个尾随后缀码放入集合 中；(2) 考查C和 两个集合，若 是 的前缀或 是 的 前缀，则将相应的后缀作为尾随后缀码放入集合 中；(3) 即为

28、码C的尾随后缀集合；(4) 若F中出现了C中的元素，则算法终止，返回假(C不是唯一可译码)； 否则若F中没有出现新的元素，则返回真。定理定理5.5 一个码是唯一可译码的充要条件是的 并集中没有C中的码字。2024/8/156惟一可译码判别准则惟一可译码判别准则例题例题u命题5.4.1 一种码是唯一可译码的充要条件是S1, S2,中没有一个含有S0中的码字。S0S1S2S3S4S50000010111011100011000111101111001111101110111101方法一方法一:根据异前缀码是唯一可译码来进行判断。其步骤如下: 首先,观察是否为非奇异码。若是奇异码,肯定不是唯一可译码

29、;其次,计算是否满足Kraft不等式。若不满足一定不是唯一可译码;最后,将码画成一棵码树图,观察是否满足异前缀码的码树图的构造,若满足则是唯一可译码。这种方法的理论基础是异前缀码一定是唯一可译码,通过经典的Kraft不等式及码树图进行判别。但它的缺点也是显而易见的,若不是异前缀码时,则此方法无法判断是否是唯一可译码。惟一可译码判别方法方法二:使用A.A. Sardinas和G.W. Patterson设计的判断法。其判断准则为:计算分组码C中所有可能的尾随后缀集合F,观察F中有没有包含任一码字,若无则为唯一可译码;若有则一定不是唯一可译码。算法中的关键为尾随后缀集合F的构造。惟一可译码判别方法

30、5960616263【例】1.英文电报有32个符号(26个英文字母加上6个标点)，即q=32。2.若r=2、N=1(即对信源S进行单符号二元编码)，由式得：3.这就是说，为了实现无失真信源编码，每个英文电报符号至少要用5位二元码符号编码。4.【深入讨论】实际英文电报符号信源在考虑了符号出现概率及符号之间的依赖性后，每个英文电报符号只携带了1.4bit的信息量，而5位二元码符号最大能载荷5bit的信息量。可见，这种编码方式的传输效率极低。【例】原因原因【原因】a)英文字母之间有很强的关联性，并不是所有的字母组合都是有意义的单字，也不是任意的单字组合都是有意义的句子。b)当N足够长时，英文字母序列

31、是无用和无意义的序列，即这些信源序列出现的概率等于零或任意小，因此可以不编码。c)在英文字母序列中去掉概率等于零或任意小序列，使扩展源中的符号总数小于qN，这样编码所需的码字个数将大大减少。【原因】d)因此，平均每个信源符号所需的码符号个数就可以大大减少，从而使传输效率提高。当然，这就会引入一定的误差。e)但是，当N足够长时，这种误差概率可以任意小，即可做到几乎无失真地编码。686970717273747576777879808182835.2 变长编码 变长码往往在码长li的平均值不很大时，就可编出效率很高而且无失真的码，其平均码长受香农第一定理所限定，即有如下定理：变长编码定定理理 若对离

32、散无记忆信源S的N次扩展信源SN进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：说明：说明： 为N次次扩扩展展信信源源的的平平均均码码长长，li为信源符号扩展序列 的码长。 为对扩展信源SN进行编码后，每每个个信信源源符符号号编编码码所所需需的的等等效的平均码长效的平均码长。 通过对扩展信源的变长编码，N时，平均码长Hr(S)，即表明实现无无失失真真信信源源编编码码，平平均均每每个个信信源源符符号号所所需需最最少少的的r r元元码码元元数数为为信信源源的的熵熵Hr(S)，即即Hr(S)是是无无失失真真信信源源压压缩缩的的极极限限值值；或或者说信源信

33、息熵是描述信源每个符号平均所需最少的比特数。者说信源信息熵是描述信源每个符号平均所需最少的比特数。8485 若编码的平均码长小于信源的熵值Hr(S) ，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。 无失真信源编码的实质：无失真信源编码的实质： 对离散信源进行适当的变换，使变换后形成的新的码符号信源(即信道的输入信源)尽可能为等概率分布，以使新信源的每个码符号平均所携带的信息量达到最大，使信道的信息传输率R达到信道容量C，实现信源与信道的统计匹配。这实际上就是香农第一定理的物理意义。 为了衡量各种编码是否达到极限情况，定义变长码的编编码码效率效率为： 常通过编码效率来衡量各种编码的

34、优劣。 为了衡量各种编码与最佳码的差距，定义码的剩余度剩余度为： 信息传输率信息传输率定义为： 注意注意: R与虽在数值上相同，但它们是不同的概念。编码效率没有单位，而信息传输率R的单位是“比特/码符号”。86 在二元无噪无损信道中，r=2，Hr(S)=H(S)， 在二元信道中，若编码效率=1，R=1比特/码符号，则达到信道的信道容量。此时编码效率最高，码的剩余度为零。 由前述知，对对于于某某一一个个信信源源和和某某一一符符号号集集来来说说，凡凡是是满满足足Kraft不不等等式式的的惟惟一一可可译译码码可可以以有有多多种种。在这些惟一可译码中，如果有一种(或几种)码，其平均编码长度小于所有其他

35、惟一可译码的平均编码长度，则该码称为最佳码最佳码(或紧致码紧致码)。 为为了了使使得得平平均均编编码码长长度度为为最最小小，必必须须将将概概率率大大的的信信息息符符号编以短的码字，概率小的符号编以长的码字号编以短的码字，概率小的符号编以长的码字。87 能获得最佳码(或次最佳码)的编码方法有很多，本节重点介 绍 ： 香香 农农 (shannon)编编 码码 、 费费 诺诺 (Fano)编编 码码 、 霍霍 夫夫 曼曼(Huffman)编码编码。5.2.1 香香农码 香农第一定理指出，可选择每个码字的长度li满足关系式 x表示不小于x的整数。按上述不等式选择的码长所构成的码称香农码。香农码满足Kr

36、aft不等式，所以一定存在对应码字长度的惟一可译码。 8889 一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，即不是紧致码(最佳码)。只有当信源符号的概率分布满足-logp(Si)=li，编码效率才达到最高。香农码的编码步骤如下：香农码的编码步骤如下： 1)将q个信源符号按概率递减的方式进行排列： p1p2pq 2)按 计算出每个信源符号的码长li； 3)为了编成惟一可译码，计算第i个信源符号的累加概率 4)将累加概率Pi用二进制数表示。 5)取Pi对应二进制数的小数点后li位构成该信源符号的二进 制码字。9091信源符号概率p(ai) 累加概率Gi对应的二进制数码长li码字a

37、10.200 0.0002.343 000a20.190.2 0.00112.413 001a30.180.39 0.01102.483 011a40.170.57 0.10012.563 100a50.150.74 0.10112.743 101a60.100.89 0.11103.344 1110a70.010.99 0.11111106.667 1111110例例1 1 设某信源共有七个信源符号，其概率分布如下表所示，试对该信源进行香农编码。解解(十进制整数化为二进制整数除二取余；十进制小数化为二进制小数乘二取整。)信源信源符号符号si符号符号概率概率p(si) 累加累加概率概率Gi-l

38、og p(si)码字码字长度长度li码字码字s10.20s20.19s30.18s40.17s50.15s60.10s70.01信源信源符号符号si符号符号概率概率p(si) 累加累加概率概率Gi-log p(si)码字码字长度长度li码字码字s10.200s20.190.2s30.180.39s40.170.57s50.150.74s60.100.89s70.010.99和为和为1，结果，结果正确正确信源信源符号符号si符号符号概率概率p(si) 累加累加概率概率Gi-log p(si)码字码字长度长度li码字码字s10.2002.34s20.190.22.41s30.180.392.45s

39、40.170.572.56s50.150.742.74s60.100.893.34s70.010.996.66取整取整信源信源符号符号si符号符号概率概率p(si) 累加累加概率概率Gi-log p(si)码字码字长度长度li码字码字s10.2002.343s20.190.22.413s30.180.392.453s40.170.572.563s50.150.742.743s60.100.893.344s70.010.996.667信源信源符号符号si符号符号概率概率p(si) 累加累加概率概率GiGi的的二进制数二进制数码字码字长度长度li码字码字s10.20003s20.190.20.00

40、1 100 13s30.180.390.011 000 13s40.170.570.100 100 03s50.150.740.101 111 03s60.100.890.111 000 14s70.010.990.111 111 07信源信源符号符号si符号符号概率概率p(si) 累加累加概率概率GiGi的的二进制数二进制数码字码字长度长度li码字码字s10.20003000s20.190.20.001 100 13001s30.180.390.011 000 13011s40.170.570.100 100 03100s50.150.740.101 111 03101s60.100.890

41、.111 000 141110s70.010.990.111 111 071111110取小数点后取小数点后三位三位取小数点后取小数点后四位四位取小数点后取小数点后七位七位*二进制与十进制小数基底转换关系20=12-1=0.52-2=0.252-3=0.1252-4=0.06252-5=0.031252-6=0.0156252-7=0.00781252-8=0.00390625除除2除除2除除2除除2除除2除除2除除2除除2例如：例如： 0.2=0.125+0.0625 +0.0078125+ =2-3+2-4+2-7 因此，因此，0.2=(0.0011001)22-1 2-2 2-3 2-4

42、 2-5 2-6 2-799例如：例如： 0.2=0.125+0.0625 +0.0078125+ =2-3+2-4+2-7 因此，因此，0.2=(0.0011001)2(十进制整数化为二进制整数除二取余；十进制小数化为二进制小数乘二取整。)0.2*2=0.40.4*2=0.80.8*2=1.60.6*2=1.20.2*2=0.40.4*2=0.8,.因此，因此，0.2=(0.0011001)2码的性能分析码的性能分析： 通过计算可得此信源的熵:100由图可知，这些码由图可知，这些码字字没有没有占占满满所有所有树树叶，所以是叶，所以是非最佳非最佳编码编码。AB为了提高编码为了提高编码效率，首先

43、应效率，首先应达到满树。达到满树。例如把例如把s6、s7换换成成A、B这些前这些前面的节点，就面的节点，就可减小平均码可减小平均码长。长。所以不应先规定码长，而是由码树来所以不应先规定码长，而是由码树来规定码字，可得更好的结果。规定码字，可得更好的结果。 例2 ：有一单符号离散无记忆信源：对该信源编二进制香农码。其编码过程如表5.2.1 所示。第104页例2 ：计算出给定信源香农码的平均码长：由离散无记忆信源熵定义，可计算出信源上熵为：对上述信源采用香农编码的编码效率为：可以看出，编码效率并不是很高。105例例3 设某信源有3个信源符号，其概率分布为(0.5, 0.4, 0.1)，按香农编码对

44、该信源进行编码所得的码长应为(1, 2, 4)，对应的码字为(0, 10, 1110)其平均码长为 ，信源熵 H(S)=1.36。因此该码的编码效率=0.8。 如果我们观察本例信源的概率分布，可以构造出一个码长更短的码(0, 10, 11)，显然它也是唯一可译码，其平均码长为 由此知，香农编码的剩余度较大，实用性不强。但香农编码是由香农第一定理得出的编码方法，具有重要的理论意义，它是算术编码的基础。5.2.2 费诺码 费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。二元费诺码的编码步骤：二元费诺码的编码步骤：1)1)将信

45、源符号按概率递减的次序排列。2)2)将排列好的信源符号按概率值划分成两大组，使每组的概率之和尽量接近，并对每组各赋予一个二元码符号0和1。3)3)将每一大组的信源符号再分成两组，使划分后的两个组的概率之和尽量接近，再分别赋予一个二元码符号。4)4)依次下去，直至每个小组只剩一个信源符号为止。5)5)信源符号对应的由分组符号序列组成的码字即为费诺码。106107例例4 4 将例1中的离散无记忆信源进行二元费诺编码。解解 其编码过程如下：信源符号概率p(ai) 第一次 分组第二次 分组第三次 分组第四次 分组码字码长lia10.2000 002a20.191 0 0103a30.181 0113a

46、40.1710 102a50.1510 1103a60.1010 11104a70.011 11114信源信源符号符号si符号符号概率概率p(si)码字字Wi码长lis10.20s20.19s30.18s40.17s50.15s60.10s70.01两组概率和尽两组概率和尽可能的接近可能的接近01信源信源符号符号si符号符号概率概率p(si)码字字Wi码长lis10.200s20.19s30.18s40.171s50.15s60.10s70.010101信源信源符号符号si符号符号概率概率p(si)码字字Wi码长lis10.200s20.19s30.18s40.171s50.15s60.10s

47、70.010101无分组，故无分组，故不需再编码不需再编码01001信源信源符号符号si符号符号概率概率p(si)码长lis10.200s20.19s30.18s40.171s50.15s60.10s70.010110100101信源信源符号符号si符号符号概率概率p(si)码字字Wi码长lis10.200s20.19s30.18s40.171s50.15s60.10s70.010110100101000100111011011101111正向读码字正向读码字信源信源符号符号si符号符号概率概率p(si)码字字Wi码长lis10.2002s20.193s30.183s40.1712s50.15

48、3s60.104s70.0140110100101000100111011011101111码的性能分析：码的性能分析： 此信源的熵 H(S)=2.61 (bit/符号) 平均码长 编码效率 =0.953 本例费诺编码的平均码长比香农编码的平均码长小，编码效率较高。114费诺码是从树根开始，把各节点分给某子集；若子集已是单点集，它就是一片叶而作为码字。116例例5 5 将下列消息按二元费诺码方法进行编码。解解 其编码过程如下：码的性能分析：码的性能分析： 此信源的熵 H(S)=2.75 (bit/符号) 平均码长 显然，该码是紧致码，编码效率 =1 该码之所以能达到最佳，是因为信源符号的概率分

49、布正好满足 ， 否则，在一般情况下是无法达到编码效率等于“1”的。 117费诺码具有如下的性质：费诺码具有如下的性质：费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用。当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。118 119r 元费诺码元费诺码 前面讨论的费诺码是二元费诺码(每次分组时将符号分成概率分布接近的2个

50、组，然后给每个组各赋予一个二元码符号0或1)。 编制r元费诺码时，每次分组应将信源符号分成概率分布接近的r个组，然后给每个组各赋予一个r元码符号0、1、r-1中的一个。 对r元费诺码，除分组与给各组赋予的符号不同之外，其余过程与二元费诺码编码方法相同。5.2.3 霍夫曼霍夫曼码 1952年，霍夫曼(Huffman)提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼霍夫曼码。1. 二元霍夫曼二元霍夫曼码 设信源S=s1,s2,sq，其对应的概率分布为 p(si)=p1,p2,pq 对二元霍夫曼码而言，其编码步骤如下：1) 将q个信源符号按概率递减的方式排列。2) 用0

51、、1码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为S信源的S1缩减信源。 1203) 将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用0、1码符号表示，这样又形成了由q-2个符号构成的缩减信源S2。4) 依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用0、1码符号表示。5) 从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。121【例】对信源S进行霍夫曼编码。符号符

52、号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四第四次次 si p(si) 编码编码 编码编码 编码编码 编编 s1 s2 s3 s4 s5 对原始概率排序0.40.2 0.20.1 0.1 符号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四第四次次 si p(si) 编码编码 编码编码 编码编码 编编 s1 s2 s3 s4 s5 从最小的两个概率开始分配码元0.40.2 0.20.1 0.1 0.40.2 0.20.201重新排序重新排序符号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四第四次次 si p(si) 编码编码 编码编码 编码编码 编

53、编 s1 s2 s3 s4 s5 重排后，再次取最小的两个概率编码0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 01符号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四第四次次 si p(si) 编码编码 编码编码 编码编码 编编 s1 s2 s3 s4 s5 重复步骤、0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 010.60.4 01符号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四次第四次 si p(si) 编码编码 编码编码 编码编码 编码编码 s1 s2 s3 s4

54、s5 直至最后两个符号为止0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 010.60.4 011.0 01 全部概率和为全部概率和为1后，编码结束，开后，编码结束，开始读码字始读码字符号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四次第四次 si p(si) 编码编码 编码编码 编码编码 编码编码s1 s2 s3 s4 s5 由后向前、逆序读出码字0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 010.60.4 011.0 011111符号符号 概率概率 第一次第一次 第二次第二次 第三次第三

55、次 第四次第四次 si p(si) 编码编码 编码编码 编码编码 编码编码s1 s2 s3 s4 s5 由后向前、逆序读出码字0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 010.60.4 011.0 0101010101符号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四次第四次 si p(si) 编码编码 编码编码 编码编码 编码编码s1 s2 s3 s4 s5 由后向前、逆序读出码字0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 010.60.4 011.0 01000000000101符

56、号符号 概率概率 第一次第一次 第二次第二次 第三次第三次 第四次第四次 si p(si) 编码编码 编码编码 编码编码 编码编码s1 s2 s3 s4 s5 由后向前、逆序读出码字0.40.2 0.20.1 0.1 0.40.2 0.20.2 010.40.4 0.2 010.60.4 011.0 0100001000010100100011【例】信源符号信源符号si概率概率p(si)码字字Wi码长lis10.411s20.2012s30.20003s40.100104s50.100114【例】信源熵：平均码长：编码效率： 霍夫曼编码是先给每一符号一片树叶，逐步合并成节点直到树根。例例 对离

57、散无记忆信源 进行霍夫曼编码。解解 编码过程如下表所示： 1)将信源符号按概率大小由大至小排序。 2)从概率最小的两个信源符号s4和s5开始编码，并按一定的规则赋予码符号，如下面的信源符号(小概率)为1，上面的信源符号(大概率)为0(本例中s4为0，s5为1)。若两支路概率相等，仍取下面的信源符号为1,上面的信源符号为0。 1351363)将已编码两个信源符号概率合并，重新排队，编码。4)重复步骤3)直至合并概率等于“1.0”为止。5)从概率等于“1.0”端沿合并路线逆行至对应消息编码。如s2对应码字为01，s4对应码字为0010。码的性能分析：码的性能分析： 信源的熵 H(S)=2.12 (

58、比特/符号) 编码效率为：137138例例 对离散无记忆信源 再做霍夫曼编码。139例例 设离散无记忆信源为做其霍夫曼编码。 下图左边一列是经Huffman编码后的相应码字，树枝上面的数字是每次概率最小的两个信息所标识的“0”和“1”，树枝下面的数字表示两个消息合并后的概率和。140141例例5 对例1所示的离散无记忆信源进行霍夫曼编码。3.霍夫曼编码中应注意的问题在霍夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得来的概率和尽量处于是高的位置。这样可使合并的元素重复编码次数减少，使短码得到充分利用。3.霍夫曼编码中应注意的问题霍夫曼编码方法得到的码并非惟一的。每次对信源缩减时，赋予

59、信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的霍夫曼码，但不会影响码字的长度。4.霍夫曼编码的三个特点霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码，即pipj有lilj，充分利用了短码。缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同(二元编码情况)，从而保证了霍夫曼是即时码 。4.霍夫曼编码的三个特点每次缩减信源的最长两个码字有相同的码长。 这三个特点保证了所得的霍夫曼码一定是最佳码。霍夫曼码的特征：霍夫曼码的特征：它它是是一一种种分分组组码码：各个信源符号都被映射成一组固定次序的码符号；它它是是一一种种惟惟一一可可译译的的码码：任

60、何码符号序列只能以一种方式译码；它它是是一一种种即即时时码码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其它终端节点对应的编码的前缀，霍夫曼编码所得的码字一定是即时码。所以一串码符号中的每个码字都可不考虑其后的符号直接译码出来。146说明：说明：霍夫曼码是一种即时码，可用码树形式来表示。每次对缩减信源最后两个概率最小的符号，用“0”和“1”码的位置是可以任意的，一般可得到不同的码，但码长li不变，平均码长 也不变。当缩减信源中缩减合并后得到的新符号的概率与其他信源符号概率相同时，从编码方法上来说，它们概率的排序是没有限制的，因此也可得到不同的码。147霍夫曼码的译码：霍夫曼码的译码

61、： 对接收到的霍夫曼码序列可通过从左到右检查各个符号进行译码。对于上例，若收到的霍夫曼码序列是00011011 0101011(由C=11,10,011,010,001,0001,0000)，则可译为a6a2a1a4a2a1。148例例 离散无记忆信源 可有两种霍夫曼码。第一种霍夫曼码为前例结果：平均码长 ，如码树图中(a)所示。信源符号概率p(si)码字码长lis10.4 1 1s20.2 01 2s30.2 000 3s40.1 0010 4s50.1 0011 4 对于给定信源，用霍夫曼编码方法得到的码并非唯一，对于给定信源，用霍夫曼编码方法得到的码并非唯一，但平均码长不变但平均码长不变

62、。 149 第二种霍夫曼码。在编码过程中，若缩减信源出现相同的概率，则把缩减合并后新出现的相同的概率排在上面。其编码过程如图所示。可算出其平均码长 ，对应的码树图如下图(b)所示。150上述两种霍夫曼码的码树151比较上述两种霍夫曼编码方法：比较上述两种霍夫曼编码方法： 两种编码方法的平均码长相同，因此编码效率相同。 但每个信源符号的码长li却不相同，由此导致两种编码的质量也不相同。 可可用用码码的的方方差差来来衡衡量量编编码码质质量量，并并以以此此作作为为选选择择编编码码方方法法的依据。的依据。 定义码长li与平均码长 差方的期望为码的方差： 2较较小小，则则编编码码所所得得的的码码序序列列

63、长长度度变变化化较较小小( (各各码码字字长长度度的的波波动动范范围围相相对对小小) )，是是一一种种质质量量较较好好的的编编码码。其其直直接接好好处处是是对对编编码码后后的的信信息息进进行行传传输输时时，每每个个信信源源符符号号所所需需的的传传输输时时间间基基本本相相等等( (相相差差较较小小) )(?)(?)。若2较大，则各码字的长度相差较大，每个信源符号的传输时间会长短不等。152153r 元霍夫曼码元霍夫曼码 二元霍夫曼码的编码方法可以推广到r元霍夫曼编码中。不同的只是每次把概率最小的r个符号合并成一个新的信源符号，并分别用0,1,r-1码元表示。 为了使短码得到充分利用，即使平均码长

64、为最短，必须使最后一步的缩减信源有r个信源符号。 因此对于r元编码，信源S的符号个数q必须满足 q=n(r-1)+r其中，n表示缩减的次数，r-1为每次缩减后的信源符号个数。 对于二元码(r=2)，信源符号个数q必定满足 q=n+2 因此q可取3的任意整正数(n为任意正整数)。154注意：注意： 对于r元码，不一定能找到一个n使式q=n(r-1)+r成立。在q不 满 足 上 式 时 ， 可 假 设 一 些 信 源 符 号 ： Sq+1,Sq+2,Sq+t 作为虚拟信源符号虚拟信源符号，并令它们对应的概率为零，即 pq+1=pq+2=pq+t=0而使 q+t=n(r-1)+r能成立，这样处理后得

65、到的r元霍夫曼码可充分利用短码，一定是紧致码。155例例 对下列信源进行四元霍夫曼码编码。下表列出了四元霍夫曼码的编码方法及其对应的码字。156157 上表中S9和S10是两个假设信源符号，这样q+t=10，可以找到n=2使q+t=n(r-1)+r成立。而且从上述编码过程可知，这样编码可使短码充分利用，使用平均码长最短。158 三种编码方法总结三种编码方法总结香浓码、费诺码和霍夫曼码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩； 由香农编码方法所求得的二进制码组集合是唯一的，即所有信源符号对应的码字是唯一的，但在很多情况下编码效率不是

66、很高；费诺码和霍夫曼码的编码方法都不是唯一的。因为当任意两个信源符号等概率时，它们的排序可以是任意的，所以通过编码，会由于不同的排序而得到不同的编码结果。159 费诺码费诺码比较适合于对分组概率相等或接近的信源编码 霍霍夫夫曼曼码码对信源的统计特性没有特殊要求，编码效率比较高， 对编码设备的要求也比较简单，因此综合性能能优于香农码和费诺码。 对对霍霍夫夫曼曼编编码码而言，只要方法正确，对同一个信源，无论如何排序，最终平均码长和编码效率不会改变最终平均码长和编码效率不会改变。 香香农农编编码码和和费费诺诺编编码码的的码码的的平平均均长长度度不不一一定定是是最最小小的的，因此它们是一种次最佳编码方

67、法因此它们是一种次最佳编码方法。 霍霍夫夫曼曼编编码码方方法法得得到到的的码码的的平平均均长长度度一一定定是是最最小小的的，所以它是一种最佳编码方法。所以它是一种最佳编码方法。160 变变长长编编码码在在理理想想条条件件下下可可以以无无失失真真地地译译码码，但是当变长码通过信道传输时，如果有某一个码元符号出现了传输错误，则因为一个码字中有某一个码元发生了变化，就可能误认为是另一个码字，结果会造成后面一系列的码字也译错称为差错的扩散差错的扩散。 当然也可以采用一定的措施，使错了一段以后，能恢复正确的码字分割和译码。所以，一一般般要要求求在在传传输输过过程程中中差差错错很很少少，或或者者添添加加纠

68、纠错错用用的的监监督督码码位位，但但这这样样一一来来会会降降低低编编码码效率。效率。161 另外，当信源有记忆时，用单符号进行编码不可能使编码效率接近于1，因为信息传输速率只能接近一维熵H1，而极限熵H一定小于H1。因此当当信信源源有有记记忆忆时时，需需要要把把多多个个符符号号一一起编码，即进行信源扩展，才能进一步提高编码效率起编码，即进行信源扩展，才能进一步提高编码效率。 以上讨论的编码定理都是针对离散平稳无记忆信源，也即仅考虑了信源符号分布的不均匀性，并没有考虑符号之间的相关性。相关性较复杂，难以定量描述，但可在一些具体方法中考虑相关性，如后述的预测编码、变换编码等方法。5.3 限失真信源

69、限失真信源编码 我们由实际生活经验知道，一般人们并不要求完全无失真地恢复消息。 对人的心理与视觉研究表明，人们在观察图像时主要是寻找某些比较明显的目标特征，而不是定量地分析图像中每个像素的亮度，或者至少不是对每个像素都等同地分析。 例如观看一段视频或观察一幅图像，人们可能会关注其主要情节，对视频或图像中的细节并不是那么注意，此时便允许视频或图像有一定程度的失真。162 由香农第一定理知，无论哪种信道，只要信息传输率R小于信道容量C，总能找到一种编码方法，使得在信道上能以任意小的错误概率，以任意接近C的传输率来传送信息。 实际信道中，信源输出的信息传输率R一般都会超过信道容量，因此也就不可能实现

70、完全无失真地传输信源的信息。 由香农第三定理知，在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，只要信息传输率R大于R(D)，一定能找到一种编码方法，使得译码后的失真小于D。香农第三定理从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。163 一般情况下信源编码可分为离散信源编码、连续信源编码和相关信源编码三类。 离散信源编码、连续信源编码方法主要讨论独立信源编码问题。 相关信源编码方法讨论非独立信源编码问题。 离离散散信信源源可可做做到到无无失失真真编编码码，而而连连续续信信源源则则

71、只只能能做到限失真编码做到限失真编码。1645.4 实用信源用信源编码方法方法 香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高； 香农编码、费诺编码、哈夫曼编码属于无失真信源编码； 本节介绍性能优良的一些实用的编码方法：游程编码，算术编码，预测编码和变换编码5.4.1 游程游程编码 游程编码对相关信源编码更有效； 游程编码属于限失真信源编码。 游游程程(Run-Length，简记RL)是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度游程长度或游长游长。 游游程程编编码码(Run-Length Coding，简记RLC)就是将这种符符号号序序

72、列列映映射射成成游游程程长长度度和和对对应应符符号号序序列列位位置置的的标标志志序序列列。译码时，如果知知道道了了游游程程长长度度和和对对应应符符号号序序列列位位置置的的标标志志序序列列，就可以完全恢复出原来的符号序列就可以完全恢复出原来的符号序列。166 游程编码特别适用于对相关信源的编码游程编码特别适用于对相关信源的编码。 对二元相关信源，其输出序列往往会出现多个连续的“0”或连续的“1”。在信源输出的二元序列中，连续出现的“0”符号称为“0游游程程”，连续出现的“1”符号称为“1游游程程”，对应连续同一符号的个数分别称为“0”游程长度和“1游程”长度，因为游程长度是随机的，其取值可以是1

73、，2，3，。 对二元序列，“0”游程和“1游程”总是交替出现的，如果规定二元序列是以“0”开始的，那么第一个游程是“0”游程，第二个游程必为“1”游程，第三个游程又是“0”游程等等。 将将任任何何二二元元序序列列变变换换成成游游程程长长度度序序列列，这这种种变变换换是是一一一一对应的，因此是可逆的、无失真的。对应的，因此是可逆的、无失真的。167168例例 有一个二元序列： 000 011 111 001 110 000 111 111 按游程编码，可得对应的游程序列 452346 若已规定二元序列是从0开始的，从上述游程序列就可以不失真地恢复出原来的二元序列。 因为游程长度是随机的、多值的，

74、所以游程序列本身是多元序列，对游程序列可以按霍夫曼编码或其他编码方法进行处理以达到压缩码率的目的。 对于r元序列也存在相应的游程序列。在r元序列中，可有r种游程。连续出现符号ai的游程，其长度L(i)就是“i游程”长度。用L(i)也可构成游程序列，但此时由于游程所对应的信源符号可有r种，因此，这种变换必须再加一些标志信源符号取值的识别符号，才能使编码以后的游程序列与原来的r元序列一一对应。所以把r元序列变换成游程序列再进行压缩编码通常效率不高。169 游程编码仍是变长码，有着变长码固有的缺点，即需要大量的缓冲和优质的通信信道。此外，由于游程长度可从“1”直到无穷大，这在码字的选择和码表的建立方

75、面都有困难，实际应用时尚需采取某些措施来改进。例如，通常长游程出现的概率较小，所以对于这类长游程所对应的小概率码字，在实际应用时采用截断处理的方法。 游程编码已在图文传真、图像传输等通信工程技术中得到应用。在实际中还常常将游程编码与其他编码方法综合起来使用，以期得到更好的压缩效果。 下面以三类传真机中使用的压缩编码的国际标准MH编码为例说明游程编码的实际应用。170171MH编码编码 文件传真是指一般文件、图纸、手写稿、表格、报纸等文件的传真，这种信源是黑白二值的，也即信源为二元信源(q=2)。 文件传真需要根据清晰度的要求决定空间扫描分辨率，将内容在空间离散化。例如，将一页文件离散化为nm个

76、像素。国际标准规定，一张A4幅面文件(210mm297mm)应该有1188(或2376) 1728个像素的扫描分辨率，将其离散化后将有约2.05MB像素/公文纸(或4.1MB像素/公文纸)的数据。从节省传送时间和存储空间方面考虑，进行数据压缩是十分必要的。 MH编码是一维编码方案，它是一行一行的对文件传真数据进行编码。编码将游程编码和霍夫曼码相结合，是一种改进的霍夫曼码。 对黑白二值文件传真，每一行由连续出现的“白(用码符号0表示)像素”或连续出现“黑(用码符号1表示)像素”组成。MH码分别对“黑”、“白”像素的不同游程长度进行霍夫曼编码，形成黑、白两张霍夫曼码表。MH码的编、译码都通过查表进

77、行。 MH码以国际电话电报咨询委员会(CCITT)确定的8幅标准文件样张为样本信源，对这8幅样张作统计，计算出“黑”、“白”各种游程长度的出现概率，然后根据这些概率分布，分别得出“黑”、“白”游程长度的霍夫曼码表，即MH码表码表：其中包括终端码终端码(结尾码结尾码)和形成码形成码(组合码组合码)两张表两张表。172MH码编码规则如下：码编码规则如下： 1) 游程长度在063时，码字直接用相应的终端码表示。 2) 游程长度在641728，用一个形成码再加上一个终端 码作为相应码字。 3) 规定每行都从白游程开始。若实际出现黑游程开始的 话，则在行首加上长度为零的白游程码字，每行结束 时用一个结束

78、码(EOL)作标记。 4) 每页文件开始第一个数据前加一个结束码，每页结尾 连续使用6个结束码表示结尾。173174MH码编码规则码编码规则(续续) 5) 为了在传输时可实现同步操作，规定T为每个编码行的 最小传输时间，一般规定T最小为20ms，最大为5s。若 编码行传输时间小于T，则在结束码之前填上足够的“0” 码元(称填充码)。 6) 译码时，每一行的码都应恢复出1728个像素，否则有错。 如果采用编码仅仅是用于存储，则可省去步骤中的4)至 6)步。例例 白游程长65。黑游程长856。某段文字有连续19个白色像素，紧接着为连续30个黑色像素，分别求其MH码字。解解 查表5.4.2，得白游程

79、长度为64的形成码字，再查表5.4.1，得白游程长度为1的终端码字，两者组成相应的码字，即 11011 000111因为856=832+24，查表5.4.2，得黑游程长度为832的形成码字，再查表5.4.1，得黑游程长度为24的终端码字，两者组成相应的码字，即 0000001001101 00000010111查表5.4.1，得白游程长度为19和黑游程长度为30的终端码字，两者组成相应的码字，即 0001100 000001101000175176例例 设某页传真文件中某一扫描行的像素点为： 17白 5黑 55白 10黑 l641白解解 通过查表可得该扫描行的码为： 17白 5黑 55白 10

80、黑 1600白（+） 41白 EOL 101011 0011 01011000 0000100 010011010 00101010 000000000001 该行经编码后只需用54位二元码元，而原来一行共有1728个像素，如用“0”表示白，用“l”表示黑，则共需1728位二元码元。可见，这一行数据的压缩比为1728:5432，因此压缩效率较高。5.4.2 算算术编码 无失真编码建立在信源符号与码字一一对应的基础上，这种编码方法通常称为块块码码或分分组组码码，此时信源符号一般应是多元的，而且不考虑信源符号之间的相关性。 如果要对最常见的二元序列进行编码，则需采用游程编码或合并信源符号等方法，把

81、二元序列转换成多值符号，转换后这些多值符号之间的相关性也是不予考虑的。这就使信源编码的匹配原则不能充分满足，编码效率一般不高。 为了克服这种局限性，需要跳出分组码的范畴，研究非分组码的编码方法。算术编码即为一种非分组码。在算术编码中，信源符号和码字间的一一对应关系并不存在，它是一种从整个符号序列出发，采用递推形式进行编码的方法。177算术编码的基本思路算术编码的基本思路 从整个符号序列出发，将各信源序列的概率映射到 0,1)区间上，使每个符号序列对应于区间内的一点，也就是一个二进制的小数。这些点把0,1)区间分成许多小段，每段的长度等于某一信源序列的概率。再在段内取一个二进制小数，其长度可与该

82、序列的概率匹配，达到高效率编码的目的。 这种方法与香农编码法有些类似，只是它们考虑的信源对象有所不同，香农编码考虑的是单个信源符号，而算术码考虑的是信源符号序列。178 如果信源符号集为A=a1,a2,an，信源序列 则总共有nL种可能的序列。 由于考虑的是整个符号序列，因而整页纸上的信息也许就是一个序列，所以序列长度L一般都很大。 在实际中很难得到对应信源序列的概率，一般从已知的信源符号概率P=p1,p2, ,pn递推得到。179定义各符号的累积概率为：那么可得 P1=0, P2=P1+p1, P3=p1+p2=P2+p2, , Pn=Pn-1+pn-1 由于Pi和Pi-1都是小于1的正数，

83、可用0，1)区间内的两个点来表示，而pi-1就是这两个点之间的长度，如图所示。 180信源符号累计概率示意图 不同的信源符号有不同的概率区间，它们互不重叠，因此可以用这个小区间中的任意一点的取值，作为该信源符号的代码。我们所需确定的是这个代码所对应的长度，应使这个长度与信源符号的概率相匹配。 同样对于整个信源符号序列而言，要把一个算术码字赋给它，则必须确定这个算术码字所对应的位于0，1)区间内的实数区间，即由整个信源符号序列的概率本身确定0和1之间的一个实数区间。随着符号序列中的符号数量的增加，用来代表它的区间减小，而用来表达区间所需的信息单位(如比特)的数量则增大。181182 每个符号序列

84、中随着符号数量的增加，即信源符号的不断输入，用于代表符号序列概率的区间将随之减小，区间减小的过程如图所示。183 随着对信源符号序列中逐个符号的输入，代表符号序列的概率区间将随之减小，为清晰地表示区间减小的过程，每次将选取的区间放大到原大，直到信源符号序列输入完毕，如图所示。184 若为二元信源，A=0,1，则得累积概率 P1=0，P2=p(0)记 P1=P(0)，P2=P(1)表示分别输入符号0和1的累积概率, P1=P(0)=0, P2=P(1)=p(0)。 上图中输入信源序列为 ，其累积概率值对应区间的减少过程如下：(1)输入第一个符号0，0,1)区间由P(1)划分成两个小区间0,P(1

85、)和P(1),1)，其中分割点为P(1)。 此时第一个小区间的宽度为A(0)=p(0)，它对应输入信源符号0。 第二个小区间的宽度为A(1)=p(1)，它对应输入信源符号1。185 P(0)=0是输入符号序列0区间的下界值，而且也是符号序列0的累积概率。(2)输入第二个符号1，这时将对应的区间0,P(1)继续进行分割成0,P(01)和P(01),P(1)两个小区间，其宽度为 A(00)=A(0)p(0)=p(0)p(0)=p(00) A(01)=A(0)p(1)=p(0)p(1)=p(01) 其中分割点 是输入符号序列01区间的下界值，而且 正是符号序列01的累积概率值。186(3)输入符号序

86、列中的第三个符号1时，将对应的区间P(01),P(1) 继 续 进 行 分 割 。 P(01),P(1)分 割 为P(01),P(011)和P(011),P(1)两个小区间。两个小区间的宽度分别为 A(010)=A(01)p(0)=p(01)p(0)=p(010) A(011)=A(01)p(1)=p(01)p(1)=p(011)其中分割点 是输入符号序列011区间的下界值，而且正是符号序列011的累积概率值。187(4)输入符号序列中的第四个符号1时，将对应的区间P(011),P(1)继续分割为P(011),P(0111)和P(0111),P(1)两个小区间，其宽度分别为 A(0110)=A

87、(011)p(0)=p(011)p(0)=p(0110) A(0111)=A(011)p(1)=p(011)p(1)=p(0111)其中分割点 是输入符号序列0111的下界值，而且正是符号序列0111的累积概率值。188(5)输入符号序列中的第五个符号1时，将对应的区间P(0111),P(1)继续分割为P(0111),P(01111)和P(01111),P(1)两个小区间，其宽度分别为 A(01110)=A(0111)p(0)=p(0111)p(0)=p(01110) A(01111)=A(0111)p(1)=p(0111)p(1)=p(01111)其中分割点 是输入符号序列01111的下界值

88、，而且正是符号序列01111的累积概率值。 由此确定了信源符号序列所对应区间的宽度和该区间所在的位置，即累积概率的值。 按照前述分析，区间宽度的递推公式为：累积概率的递推公式为：其中 为信源符号序列 的累积概率， 为信源符号序列 的联合概率，而P(0)=0，P(1)=p(0)。 在计算信源符号序列 的累积概率值 时， 把区间0,1)分割成许多小区间，不同信源符号序列 对应的区间为 189 可可取取该该小小区区间间内内的的一一点点来来代代表表这这个个信信源源符符号号序序列列，选选取取此点的方法有许多种，实际常取小区间的下界值此点的方法有许多种，实际常取小区间的下界值 。 对信源符号序列的编码方法

89、也可有多种，下面介绍常用的一种算术编码方法。算术编码算术编码 将信源符号序列 的累积概率值写成二进制小数取取小小数数点点后后L位位，若若后后面面有有尾尾数数，就就进进位位到到第第L位位，并使L满足式中 表示大于或等于x的最小整数。 这样得到一个信源符号序列所对应的算术码字c1c2cL。190191例例 设的信源符号序列 对应的算术码字为10111。例例 设二元无记忆信源S=0,1，其中 。对二元序列 进行算术编码。解解 根据上述编码方法，先计算信源符号序列 的联合概 率 决定信源符号序列 的算术码字长度为 再计算信源符号序列的累积概率，按递推公式有：192 193 取 二进制表示小数点后7位，

90、得到信源符号序列的算术码字为1101010。 信源符号序列 的累积概率值 的变化及区间宽度减小的过程如图所示。累积概率值 即为输入符号序列“11111100”区间的下界值。194本例对输入信源符号序列进行算术编码后平均码长为编码效率为 因为这里需编码的序列长为8位，所以一共要把半开区间0,1)分成256个小区间，以对应任一个可能的序列。 由于任一个码字必在某个特定的区间，所以其解码具有唯一性。 195 如果是多元信源序列，则其累积概率和区间宽度的递推公式分别为 其中 为信源符号序列 的累积概率， 为信源符号序列 的联合概率，而 按式 计算。196197例例设四元无记忆信源S=a1,a2,a3,

91、a4，其中p(a1)=0.2，p(a2)=0.2，p(a3)=0.4，p(a4)=0.2。试对 输入信源序列进行算术编码。解解 在编码开始时设符号序列占据整个半开区间0,1)，这个区间先根据各个信源符号的概率分成四段。 序列第一个符号a1对应区间0,0.2)，下一个符号输入时，以这个区间为基础进行分段，如图所示。 198 对这个新区间再根据各个信源符号的概率分成四段，然后对第二个符号a2编码。它所对应的区间为0.04,0.08)，第三个符号输入时，再以这个区间为基础继续分段。 继续这个过程直到最后一个信源符号。 输入最后一个信源符号后得到一个区间0.06752,0.0688，取任何一个该区间内

92、的实数，如0.06752就可用来表示整个符号序列。如果用二元码表示，就可将0.06752用二进制表示， 0.06752=(0.0001000101)2取 二进制表示的小数点后L位，得到信源效率 的算术码字为 0001000110。 译码就是一系列比较过程，每一步比较 CF(s) 与 P(s)P(0)。 F(s0)=F(s) F(s1)=F(s)+P(s)P(0) s前面已译出的序列串 P(s)序列串 s 对应的宽度F(s) 是序列串 s 的累积分布函数，即为 s 对应区间的下界；P(s)P(0) 是此区间内下一个输入为符号“0”所占的子区间宽度；若 CF(s)P(s)P(0) 则译输出符号为“

93、1”。算术编码的译码算术码的译码算术码的译码: 对二元算术码而言，其译码过程是一系列比较过程。 每一步比较 。 其中C为算术码所对应的数值， 为前面已译出的序列串， 是序列串 对应的宽度， 是序列 的累积概率值, 即为 对应区间的下界限， 是此区间内下一个输入为符号“0”所占的子区间宽度。译码规则译码规则 若 ，则译输出符号为“0”； 若 ，则译输出符号为“1”。 由于序列 是用子区间 中的一个点表示其编码的，因此译码时只要判断序列的码字落在哪个区间，就一定能正确地译码。200201举例：算术码的优点算术码的优点 算术编码所需的参数较少，编码效率高、编译码简单，不需要霍夫曼码那样一个很大的码表

94、。 在实际实现算术编码时，常用自适应算术编码对输入的信源序列自适应地估计其概率分布。 算术编码在图像数据压缩标准(如JPEG)中得到广泛的应用。2025.4.3 预测编码 前述编码方法适用于独立信源序列：霍夫曼码是独立多值信源的最佳编码方法；二元序列游程编码的实质是将二元序列转化成适应于霍夫曼编码的多值序列；算术编码对于独立二元信源序列很有效，但由于相关信源的复杂性而难以实现。 建立在信源数据相关性之上的预测编码是数据压缩三大经典技术(统计编码、预测编码、变换编码)之一。203204预测时间或空或空间域，如域，如语音，音，图像信号像信号变换变换域，信号从原来的域，信号从原来的时空域空域变到到变

95、换 域，比如域，比如频谱域，域，DCT，小波域等，小波域等 由信息理论可知，对于相关性很强的信源，条件熵可远小于无条件熵，因此人们常采用尽量解除相关性的办法，使信源输出转化为独立序列，以利于进一步压缩码率。 常用的解除相关性的措施是预测和变换，其实质都是进行序列的一种映射。 预测编码有可能完全解除序列的相关性，但必需确知序列的概率特性。 变换编码一般只解除矢量内部的相关性，但它可有许多可供选择的变换方法，以适应不同的信源特性。205 预测的两个阶段：预测器的训练预测的两个阶段：预测器的训练/ /使用使用 为什么预测有助于压缩？为什么预测有助于压缩？预测编码的一般理论与方法预测编码的一般理论与方

96、法 预测编码的基本思想是通过提取与每个信源符号有关的新信息，并对这些新信息进行编码来消除信源符号之间的相关性。 实际中常用的新信息为信源符号的当前值与预测值的差值。 正是由于信源符号间存在相关性，所以才使预测成为可能，独立信源则不可能进行信源符号间的预测。 206207 预测的理论基础主要是估计理论。所所谓谓估估计计就就是是用用实实验验数据组成一个统计量作为某一物理量的估计值或预测值。数据组成一个统计量作为某一物理量的估计值或预测值。 若估估值值的的数数学学期期望望等等于于原原来来的的物物理理量量，就就称称这这种种估估计计为为无偏估计。无偏估计。 若若估估值值与与原原物物理理量量之之间间的的均

97、均方方误误差差最最小小，就就称称之之为为最最佳佳估估计计。基于均方误差最小方法进行的预测，就称为最小均方误差预测，所以可认为这种预测是最佳的。 要实现最佳预测就是要找到计算预测值的预测函数。要实现最佳预测就是要找到计算预测值的预测函数。预测器的使用预测器的使用 设有信源序列Sr-k,Sr-2,Sr-1,Sr, k阶预测就是由Sr 的前k个数据来预测Sr 。 令预测值为式中f()是待定的预测函数。要使预测值具有最小均方误差，必须确知k个变量Sr-k,Sr-2,Sr-1的联合概率密度函数，这在一般情况下较难得到，因而常用比较简单的线性预测方法。208线性预测线性预测 线性预测是取预测函数为各已知信

98、源符号的线性函数，即取Sr 的预测值为其中ai为预测系数。 208209预测器的训练预测器的训练 预测的均方误差为 最简单的预测是令 称为前值预测前值预测，常用的差值预测就属于这类。 利用预测值来编码的方法可分为两类： 一一类类是是对对实实际际值值与与预预测测值值之之差差进进行行编编码码，也也叫叫差差值值预预测测编码。编码。 另另一一类类方方法法是是根根据据差差值值的的大大小小，决决定定是是否否需需传传送送该该信信源源符符号号。例如，可规定某一阈值T，当差值小于T时可不传送，对于相关性很强的信源序列，常有很长一串符号的差值可以不传送，此时只需传送这串符号的个数，这样能大量压缩码率。这类方法一般

99、是按信宿要求来设计的，也就是压缩码率引起的失真应能满足信宿需求。210211 预测的两个阶段：预测器的训练预测的两个阶段：预测器的训练/ /使用使用 为什么预测有助于压缩为什么预测有助于压缩？ 预测编码：预测编码：不对原信号编码不对原信号编码 而对误差信号编码而对误差信号编码http:/ （10-）差值预测编码系统介绍差值预测编码系统介绍 如果信源的相关性很强，则采用差值编码可得较高的压缩率。由于相关性很强的信源可较精确地预测待编码的值，使得这个差值的方差将远小于原来的信源取值，所以在同样失真要求下，量化级数可大大减少，从而较显著地压缩码率。 差值预测编码系统的框图如下图所示，在编码端主要由一

100、个符号编码器和一个预测器组成，在解码端主要由一个符号解码器和一个预测器组成。212213编码器编码器解码器解码器差值编码系统差值编码系统 当输入信源序列逐个进入编码器时，预测器根据若干个过去的输入产生对当前输入像素的估计值。预测器的输出舍入成最近的整数，并被用来计算预测误差： 这个误差在符号编码器中借助于变长码进行编码，从而产生压缩数据流的下一个元素。 在解码器中根据接收到的变长码字重建er，并执行下列操作而 可通过式 进行预测得到。214差值编码的特点差值编码的特点 在差值编码中所能取得的压缩率与预测误差序列所产生的熵的减少量直接有关。 通过差值预测可消除相关，所以预测误差的概率分布一般在零

101、点附近有一个高峰，并且与输入信源分布相比其方差较小。2155.4.4 变换编码 由前述知，对于有记忆信源，由于信源前后符号之间具有较强相关性，要提高信息传输的效率首先需要解除信源符号之间的相关性，解除相关性可以在时域上进行(如前面介绍的预测编码方法)，也可以在变换域上进行，这就是本节要介绍的变换编码方法。 对对于于图图像像信信源源等等相相关关性性更更强强的的信信源源，常常采采用用基基于正交变换的变换编码方法进行数据压缩于正交变换的变换编码方法进行数据压缩。 216217变换编码的基本原理变换编码的基本原理 将原来在空间(时间)域上描述的信号，通过数学变换(如傅里叶变换等)，将信号变到变换域(如

102、频域等)中进行描述。 在变换域中，变换系数之间的相关性常常显著下降，并常有能量集中于低频或低序系数区域的特点，这样就容易实现码率的压缩，并还可大大降低数据压缩的难度。 最早将正交变换思想用于数据压缩是在20世纪60年代末期，由于快速傅里叶变换的出现，人们开始将离散傅里叶变换(DFT)用于图像压缩。 1969年哈达玛变换用于图像压缩。 1971年KL变换用于图像压缩，得到了最佳的性能，故KL变换又称为最优变换。 1974年出现了综合性能较好的离散余弦变换(DCT)，并很快得到广泛的应用。 20世纪80年代后期，国际电信联盟(ITU)制订的图像压缩标准H.261选定DCT作为核心的压缩模块；随后国

103、际标准化组织(ISO)制定的活动图像压缩标准MPEG-1也以DCT作为视频压缩的基本手段；更新的视频压缩国际标准中也用了到DCT。2181. 变换编码的基本原理变换编码的基本原理 设信源连续发出的两个信源符号s1s2之间存在相关性，如果均为3比特量化，即它们各有八种可能的取值，那么s1与s2之间的相关特性可用图表示。219 以下先介绍变换编码的基本原理，然后介绍变换编码中常用的几种变换。 图中的椭圆区域表示s1与s2相关程度较高的区域，此相关区关于s1轴和s2轴对称。显然如果s1与s2的相关性越强，则椭圆形状越扁长，而且变量s1与s2幅度取值相等的可能性也越大，二者方差近似相等，即 。 如果我

104、们将s1与s2的坐标轴逆时针旋转45,变成y1Oy2 平面，则椭圆区域的长轴落在y1轴上，此时当y1取值变动较大时，y2所受影响很小，说明y1与y2之间的相关性大大减弱。同时由图可以看出：随机变量y1与y2的能量分布也发生了很大的变化，在相关区域内的大部分点上的y1方差均远大于y2的方差，即 。 220 另外，由于坐标变换不会使总能量发生变化，所以有 由此可见，通过上述坐标变换，使变换后得到的新变量y1、y2呈现两个重要的特点： 变量间相关性大大减弱； 能量更集中，即 ，且 小到几乎可忽略。 这两个特点正是变换编码可以实现数据压缩的重要依据。221 上述坐标旋转对应的变换方程为：因为 因此，坐

105、标变换矩阵 是一个正交矩阵，由正交矩阵决定的变换称为正交变换正交变换。222正交变换的特点：正交变换的特点： 设N维矢量 ，取NN正交矩阵T，做变换223224225 由于实矩阵的协方差矩阵必为实对称矩阵，同时由矩阵理论知，对于实对称矩阵CS，总存在正交矩阵T，使TCSTT为对角矩阵，即说明说明 并不是所有正交矩阵都能使Cy成为对角矩阵，仅说明存在这样的正交矩阵。事实上，目前完全满足这一条件的只有KL变换，其他准最佳变换都不能保证在所有情况下满足这一特性。 226 对前述正交变换中，取坐标旋转角=45，则有 可见Cy为对角矩阵，即输出 的两个分量互不相关。 227 通过这一变换获得的另一个重要

106、结果是Cy的第二个分量的方差为0，这说明经过变换，其能量集中到了y1分量上，在y2分量上的能量为0，这与由正交变换原理图得到的直观结论一致。因此，经过变换后y2分量可以不传送，从而达到有效压缩数据的目的。 一般的变换编码系统框图如图所示 高性能的变换编码方法不仅能使输出的压缩信源矢量中各分量之间的相关性大大减弱，而且使能量集中到少数几个分量上，在其他分量上数值很小，甚至为0。因此在对变换后的分量(系数)进行量化再编码时，量化后等于0的系数可以不传送，因此在一定保真度准则下可达到压缩数据率的目的，量化参数的选取主要根据保真度要求或恢复信号的主观评价效果来确定。 在变换编码方法中最关键的是正交变换

107、的选择，最佳的正交变换是KL(卡胡南-列夫)变换，这一变换的基本思想是由Karhunen和Loeve两人分别于1947年和1948年单独提出的，主要用于图像信源的压缩。228 KL变换使变换后随机矢量的各分量之间完全独立，因而它常作为衡量正交变换性能的标准，在评价其它变换的性能时，常与KL变换的结果进行比较。 KL变换的最大缺点是计算复杂，而且其变换矩阵T与信源有关，实用性不强。为此人们又找出了各种实用化程度较高的变换，如离离散散傅傅里里叶叶变变换换(DFT)、离离散散余余弦弦变变换换(DCT)、沃沃尔尔什什- -哈哈达达玛玛变变换换(WHT)等等，其中性能较接近KL变换的是离散余弦变换(DC

108、T)，在某些情况下，DCT能获得与KL变换相同的性能，因此DCT也也被被称称为为准准最最佳佳变变换换。2292 离散余弦变换离散余弦变换 DCT是根据DFT的不足，按实际需要而构造的一种实数域的变换，由于DCT源于DFT，所以需先考察DFT。 DFT是一种常见的正交变换，在数字信号处理中得到广泛应用。 设长度为N的离散序列为f0,f1,fN-1，对应的DFT对对定义为：正变换正变换反变换反变换230其中可将正变换写成矩阵形式其中，T为DFT的变换矩阵。231 虽然DFT为频谱分析提供了有力的工具，但是通常DFT是复数域的运算，尽管有快速傅里叶变换(FFT)，在实际应用中仍有许多不便。 如果将一

109、个实函数对称延拓成一个实偶函数，由于实偶函数的傅里叶变换也是实偶函数，只含有余弦项，因此构造了一种实数域的变换，即离散余弦变换。 设长度为N的离散序列为f0,f1,fN-1，DCT定义对定义对为正变换正变换反变换反变换232其中DCT变换对中的正变换可写成矩阵形式 其中，TC为DCT的变换矩阵233234例例 若已知信源S的协方差矩阵Cs为235从Cy可以看到，此时DCT在去相关方面已达到最佳性能。 若信源的协方差矩阵CS为236237二维二维DCT变换变换238二维二维DCT变换变换239Matlab命令命令A = imread(FILENAME,FMT) B = dct2(A)B = id

110、ct2(A) B = blkproc(A,M N,FUN)例例 给定两幅图像信源如右图所示，对它们进行DCT，则其DCT系数如下图(a)和(b)所示，图中亮度越大表示对应的DCT系数数值也越大。 从本例可看到，经DCT后图像信号的能量向左上角集中，因而有利于数据的压缩。240241实验任务实验任务 1、DCT变换变换 针对给定的精致图像进行DCT变换；2、系数选取、系数选取 可以按一下两种方式选取系数： （1）将DCT系数矩阵中值小于给定阈值的元素置为0； （2）将一个图像矩阵分块，将一个数据块中某些位置的值置为0。2423、IDCT变换变换 将DCT系数进行2中的操作，再进行DCT反变换。4

111、、分析比较、分析比较 （1）利用2中第（1）种系数选取方法，自己设定3种不同的阈值，给出反变换图像，分析保留系数比例与图像质量的关系。 （2）利用2中第（2）种系数选取方法，自己设定3种不同的置0方式，给出反变换图像，分析保留系数比例与图像质量的关系，以及保留系数位置与图像质量的关系。要求：要求：4个人一组，提交报告，课堂演示。3 沃尔什沃尔什- -哈达玛变换哈达玛变换 离散沃尔什-哈达玛变换(Walsh-Hadamard WHT)，其变换矩阵是由“+1”和“-1”组成的，因此在变换过程中只有加法和减法，计算速度快而且易于用硬件实现。 设长度为N的离散序列为f0,f1,fN-1，当N=2n时，

112、WHT对对的定义为正变换正变换 反变换反变换243其中指数上的求和是以2为模的，bi(D)是D的二进制表达式中的第i位的取值。例如当n=3时，对D=6=(110)2，有b0(D)=0， b1(D)=1，b2(D)=1。 WHT变换矩阵是一个对称的正交矩阵，例如当N=8时的WHT变换矩阵为 244 比较正反变换定义式可知, WHT正变换和反变换只差一个常数项1/N，所以用于正变换的算法也可用于反变换，这使得WHT的使用非常方便。 对WHT变换矩阵TH而言，其构成规律具有简单的迭代性质，可以方便地产生各阶变换矩阵。 最小阶(N=2)的TH为： 如果用 代表N阶WHT变换矩阵，则上面所述的迭代关系为

113、245例例 给定如图(a)所示的图像信源，对其进行WHT，则WHT系数如图(b)所示，同样在图中亮度越大表示对应的WHT系数的取数值也越大。 从本例可以看到，经沃尔什-哈达玛变换后图像信号的能量向左上角集中，因而有利于数据的压缩。但WHT的能量集中能力不如DCT。246关于变换方法的进一步讨论关于变换方法的进一步讨论： 许多信号变换方法都可用于变换编码。需要注意的是数数据据的的压压缩缩并并不不是是在在变变换换步步骤骤中中取取得得的的，而而是是在在量量化化变变换换系系数数时时取取得得的的。因为在实实际际编编码码时时，对对应应于于方方差差很很小小的的分分量量，往往往往可可以以不不传传送送，从从而而

114、使使数数据据得得到到压压缩缩。对某一个给定的编码应用，如何选择变换取决于可容许的重建误差和计算要求。 变换具有将信号能量集中于某些系数的能力，不同的变换信号能量集中的能力不同。对常用的变换而言，DCT比比DFT和和WHT有有更更强强的的信信息息集集中中能能力力。从从理理论论上上说说，KL变变换换是是所所有有变变换换中中信信息息集集中中能能力力最最优优的的变变换换，但但KLT的的变变换换矩矩阵阵与与输入数据有关，所以不太实用。输入数据有关，所以不太实用。247 实际中使用的变换其变换矩阵都与输入数据无关，在这些变换中，非非正正弦弦类类变变换换(如如WHT)实实现现起起来来相相对对简简单单，但正弦

115、类变换但正弦类变换(如如DFT和和DCT)更接近更接近KLT的信息集中能力。的信息集中能力。 由于DCT的信息集中能力和计算复杂性综合得比较好，近年来得到了较多的应用，DCT已被设计在单个集成块上。 另外，近年来得到广泛研究和应用的一些编码方法(例如小波变换编码、分形编码等)也直接或间接地与变换编码相关。 248 在实际应用中，需要根据信源特性来选择变换方法以达到解除相关性、压缩码率的目的。 此外，还可以根据一些参数来比较各种变换方法间的性能优劣，如反映编码效率的编码增益、反映编码质量的块效应系数等。 当信源的统计特性很难确知时，可用各种变换分别对信源进行变换编码，然后用实实验验或计计算算机机

116、仿仿真真来计算这些参数，从而选择合适的编码。 无无失失真真信信源源编编码码的的最最短短平平均均码码长长的的极极限限值值是是信信源源的的信息熵信息熵H(S)。 249 通过最最佳佳信信源源编编码码可可以以消消除除信信源源的的剩剩余余度度，提提高高信信息息传传输率。输率。 但信源编码的结果却使码变得十分“脆弱”，经不起信道中噪声的干扰，容易造成译码错误。例如，对信源S=s1,s2,s3,s4,s5进 行 二 元 霍 夫 曼 编 码 ， 得 其 码 书 为1,01,000,0010,0011，若信源发出的符号为s2经信源编码的码字为01，假如在信道传输中发生错误，接收端接收到的符号变成11，则收信者

117、会判断信源发出的符号为s1s1，从而造成严重的接收错误。 由于实实际际信信道道总总有有噪噪声声存存在在，因因此此必必须须进进一一步步研研究究信信息息传输的抗干扰问题，即信道编码问题传输的抗干扰问题，即信道编码问题。250251书面作业 P149153 5.1 5.3 (1)、(2) 5.14 (1)、(2)、(3)、 (4) 、(5) 、(6) 5.21 5.22(并计算此序列的平均码长和编码效率)252C1：等长，非奇异，所以是即时码，也是唯一可译码C2: 0是01的前缀，所以不是即时码 满足kraft不等式253C2001011011101111011111F111111111111111

118、1F1中没有C2中的码字，所以是唯一可译码254C3：可用码树表示，是即时码和唯一可译码C40101101110010011111F101F1中有C2中的码字，所以不是唯一可译码F21F30101100001111255C5：奇异码，不是唯一可译码，也不是即时码C6：可用码树表示，是即时码，唯一可译码256257（1）满足kraft不等式，存在满足要求的即时码（2）满足kraft不等式，存在满足要求的即时码（3）不满足kraft不等式，不存在满足要求的即时码（4）满足kraft不等式，存在满足要求的即时码利用码树可构造符合要求的码字。258259260X1 0.32 X2 0.22X3 0.18X4 0.16X5 0.08X6 0.0401010.120110.410.2800.3200.600 10 11010 0110 0111 262霍夫曼三进制变长编码：X1 0.32 X2 0.22X3 0.18X4 0.16X5 0.08X6 0.04X7 0 1 2 0001 020 021 平均码长：263定长二进制编码：q=6，r=2，所以至少需要3位二进制符号表示2645.22265266