第五章信源编码

1、第五章第五章 信源编码信源编码第一节第一节 编码的定义编码的定义第二节第二节 无失真信源编码无失真信源编码第三节第三节 限失真信源编码定理限失真信源编码定理第四节第四节 常用编码方法常用编码方法引言引言 限失真信源编码限失真信源编码：熵压缩，信息量减少。：熵压缩，信息量减少。 的条件下，的条件下，尽量降低信息率尽量降低信息率, ,最小值为最小值为R(D).R(D).主要用于连续信源或模拟信主要用于连续信源或模拟信号，如语音、图像等信号。号，如语音、图像等信号。DD _回顾：冗余度的概念、定义及产生的原因回顾：冗余度的概念、定义及产生的原因无失真信源编码则是（无失真信源编码则是（1）解相关（）解

2、相关（2）使新的符号等概出现）使新的符号等概出现无失真信源编码无失真信源编码：保熵编码，信息量不变，无失真压缩冗余：保熵编码，信息量不变，无失真压缩冗余适用于离散信源或数字信号。适用于离散信源或数字信号。本章以无失真信源编码为主，介绍相关的编码定理和编码方本章以无失真信源编码为主，介绍相关的编码定理和编码方法。法。信源编码分为信源编码分为无失真信源编码无失真信源编码和和限失真信源编码限失真信源编码。第一节 编码的定义一、编码：对信源输出的原始符号按一定的一、编码：对信源输出的原始符号按一定的数学规则数学规则进行进行变换变换.信源编码：变换成适合在信道中传输的符号，并进行冗余压缩信源编码：变换成

3、适合在信道中传输的符号，并进行冗余压缩 或熵压缩。或熵压缩。信道编码：变换后，能在接收端进行检错或纠错信道编码：变换后，能在接收端进行检错或纠错二、信源编码的数学描述：（单符号信源编码）二、信源编码的数学描述：（单符号信源编码）iiijiwaf n21iwm21jbn21ia-:.,.,.,。构成的码字成由码元射规则转换根据某种变换规则或映，将输入符号信源编码码字集码字集W：码字构成的集合。：码字构成的集合。 某种映射规则某种映射规则f下产生一种码字集，简称为码。不同的映射规下产生一种码字集，简称为码。不同的映射规则产生不同的码（码字集）。所有的码字集构成码表。则产生不同的码（码字集）。所有的

4、码字集构成码表。编码也可以这样描述：编码也可以这样描述： 选择不同的码表即选择不同的映选择不同的码表即选择不同的映射规则射规则f,从而产生不同的码。从而产生不同的码。0100111001yaaaaax11100,01,10,W11wa10wa 01wa00waf10bbBaa,aaAX23412443322111214321时，输出序列为：当输入序列为，称为码那么，码字集为，为：若映射规则，码元集：信源符号集,举例10100110010yaaaaax20110,01,001,W011wa001wa 01wa0waf23412443322112时，输出序列为：当输入序列为，称为码那么，码字集为，

5、为：若映射规则n1iiii_iKaPWEK /W)( 平均码长信源符号的个数）。码元的长度（码字所含码元码字码长码长Ki及其意义及其意义意义：衡量意义：衡量码的性能码的性能的重要参数的重要参数 对于无失真信源编码，平均码长对于无失真信源编码，平均码长 越短，说明通过编码压越短，说明通过编码压缩去的冗余越多。反之，冗余压缩越少。缩去的冗余越多。反之，冗余压缩越少。_K 这是因为无失真编码前后，信息量不变，这是因为无失真编码前后，信息量不变， 越小说明每个越小说明每个码元携带的信息量越大，冗余越小，压缩掉的冗余就越多。码元携带的信息量越大，冗余越小，压缩掉的冗余就越多。_K三、几种常见的码：三、几

6、种常见的码： 1、定长码和非定长码：、定长码和非定长码：Wi=Wj，i,j=1,2.n。则为定长码。则为定长码 2、奇异码和非奇异码：、奇异码和非奇异码：ij,则则WiWj；或：；或：ai与与Wi一一对应一一对应信源符号信源符号码码1码码2码码3码码4码码5a1a2a3a400011011000010111000110110110111101011111码码1 1、码、码2 2为定长码为定长码码码3 3、4 4、5 5非定长码非定长码码码1 1、3 3、4 4、5 5是非奇是非奇异码，码异码，码2 2是奇异码是奇异码举例：码举例：码w1,w2,w3=0,10,11 ，惟一可译，惟一可译 码码w

7、1,w2,w3 , w4=1,00,01,10 ，非惟一可译（举出一个反，非惟一可译（举出一个反例即可）例即可） 注：奇异码一定非惟一可译。（非奇异码则不一定）注：奇异码一定非惟一可译。（非奇异码则不一定） 3、惟一可译码和非惟一可译码：、惟一可译码和非惟一可译码： 从编码器输出的码元序列（码字序列）能惟一地恢复出输入从编码器输出的码元序列（码字序列）能惟一地恢复出输入的信源符号序列；或者说，任意有限长的码元序列只能惟一地的信源符号序列；或者说，任意有限长的码元序列只能惟一地分割成一个个的码字。称为惟一可译。分割成一个个的码字。称为惟一可译。任一任一有限长的码元序列，如：有限长的码元序列，如：

8、1 0 0 1 1 1 0 0 0 只能分割成只能分割成1 0 0 1 1 1 0 0 0 即：即：w2, w1, w3,w2,w1, w1 如：如：1 0 0 1 0 0 1可以分割成可以分割成 1 00 10 01 =w1, w2, w4,w3;或者或者10 01 00 1=w4, w3 w2, w1；或者；或者= 1 00 1 00 1=w1,w2 ,w1 ,w2,w1 4、即时码和非即时码：、即时码和非即时码： 收到一个完整的码字后能立即译码，或曰及时可译收到一个完整的码字后能立即译码，或曰及时可译-即时码即时码收到一个完整的码字后不能立即译码，还需要根据下一个码字收到一个完整的码字后

9、不能立即译码，还需要根据下一个码字才能判断是否可译才能判断是否可译-非即时码。非即时码。 如：码如：码1,10,100,1000 ，为非即时码。延长码，前缀码，为非即时码。延长码，前缀码 如：码如：码1,01,001,0001 ，为立即码。非延长码，异前缀码，为立即码。非延长码，异前缀码且惟一可译。且惟一可译。码码非分组码非分组码分组码分组码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码非即时码非即时码即时码即时码分组码分组码：将信源符号序列分成：将信源符号序列分成若干组或块，再进行编码若干组或块，再进行编码四、码树和四、码树和kraft不等式不等式1、 即时码可以用

10、码树来构造，如用二进制码树。即时码可以用码树来构造，如用二进制码树。树根树根A(倒着长）倒着长）二进制二进制-两个树枝，两个树枝，标号标号0，1；产生两个；产生两个一级节点。一级节点。第第n级级,2n个个n级节点级节点终端节点终端节点-不再长不再长出分枝的节点。出分枝的节点。例如：例如：n=4,共共16个终端节点，可以表示符号数为个终端节点，可以表示符号数为16 的信源的的信源的每一个符号每一个符号a1,a2,a3 a4 a5 a16。用树根到每个终端节点的树枝用树根到每个终端节点的树枝标号构成的序列作为该节点信源符号的编码输出标号构成的序列作为该节点信源符号的编码输出（即码字）（即码字）若信

11、源符号数小于若信源符号数小于16，可以去掉几个节点，码树为非满树，可以去掉几个节点，码树为非满树（只有部分树枝延伸到最后一级）（只有部分树枝延伸到最后一级）r 进制进制 -每个节点长出每个节点长出r个树枝。个树枝。如如r=3,三进制码树三进制码树0120000011111222222、kraft(克劳夫特克劳夫特)不等式不等式 惟一可译码惟一可译码存在的存在的充分和必要条件是，各码字的长度充分和必要条件是，各码字的长度Ki应符合克劳夫特不等式：应符合克劳夫特不等式： 11niKimm是进制数是进制数(码元集中码符号的个数）码元集中码符号的个数）n是信源符号数。是信源符号数。 强调强调：作为必要

12、条件，满足不等式，则一定存在相应码长：作为必要条件，满足不等式，则一定存在相应码长Ki的惟一可译码。但不能作为某种码是否惟一可译的判据。的惟一可译码。但不能作为某种码是否惟一可译的判据。例题例题5-1 二进制编码二进制编码的惟一可译码。、编码，不存在长度为对四元符号进行二进制，则：若；32211893K2K2K1K12m10B4naaaaAX143214321niKim,)(,的惟一可译码。、编码，存在长度为对四元符号进行二进制，满足不等式，则：若332113K3K2K1K214321niKim,)(用码树验证以上结果：用码树验证以上结果：无论如何也不能构造出长无论如何也不能构造出长度为度为1

13、、2、2、3的即时码的即时码第二节 无失真信源编码定理1、符号序列编码、符号序列编码:对信源符号序列进行编码对信源符号序列进行编码(而非对单符号编码而非对单符号编码)iiLijLif n21i m21jb n21i L-yxyx:.,(.,.,。也称为码字）构成的码元序列元或映射规则转换成由码根据某种变换规则，长输入符号序列将信源编码LL_LLL2L1in1iLiL_LLiKKKKKKPKK n21iKLnL，定长编码：符号序列码元；平均码长：，码长./)(.,y2、码长的意义：衡量、码长的意义：衡量码的性能码的性能的重要参数的重要参数 对于无失真信源编码，平均码长对于无失真信源编码，平均码长

14、 越长，说明通过编码越长，说明通过编码压缩去的冗余越少。反之平均码长压缩去的冗余越少。反之平均码长 越短，冗余压缩越多。越短，冗余压缩越多。LK_ 平均码长平均码长 最小是多少呢？最小是多少呢？ （小于此值，就会产生失（小于此值，就会产生失真）。有下面的定理：真）。有下面的定理： LK_一、定长编码定理：一、定长编码定理： 。就可以输出惟一可译码；显然，只要序列总数为个，而被编码的符号进制定长非奇异码共有的码长为,.LKLKLnm nm mKLL：稍加整理即是如下定理又两边取对数，整理后有不等式对 )X(HLK )X(Hn nLK nm LLLLLKLmmloglogloglog 由由L个符号

15、组成的、每个符号的熵为个符号组成的、每个符号的熵为 的无记忆平稳的无记忆平稳信源符号序列信源符号序列 ,可用可用KL个符号个符号 （每个符号有（每个符号有m种可能值）进行定长编码。对任意的种可能值）进行定长编码。对任意的 只要只要 ，则：当，则：当L足够大时，必可使译码差足够大时，必可使译码差 错小于错小于 （几乎无失真编码）；（几乎无失真编码）；Ll21XXXXLKk21Y,Y,Y,Y0, 0logm)X(HLKLL)X(HL 反之，当反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几乎必定足够大时，译码几乎必定 出错（译码错误概率接近于出错（译码错误概

16、率接近于1 1）。）。 logm2)X(HLKLL1、解释：、解释： KL/L-编码时，每个信源符号输出的编码时，每个信源符号输出的 码长。即每个信源符码长。即每个信源符号用号用KL/L 个码元来表示。个码元来表示。 )()()()()(XHaPlogaPlogmalogPaPlogmH(X) logm)X(HmiimiiiiL平稳平均平均m进制符号熵。进制符号熵。编码时，编码时，KL/L，越小越好。只要，越小越好。只要KL/L比平均比平均m进制熵稍大一点，进制熵稍大一点，那么当那么当L足够大时，编码就可以做到几乎无失真。否则，不可能足够大时，编码就可以做到几乎无失真。否则，不可能实现无失真编

17、码，且当实现无失真编码，且当L足够大时，译码几乎必定出错。足够大时，译码几乎必定出错。另一种解释：另一种解释： )X(HlogmLK )X(HLKLLLLmlog或者称为编码器容许的输出信息率。或者称为编码器容许的输出信息率。以以2为底时，单位是为底时，单位是bit/信源符号，所信源符号，所以它表示了每个信源符号在编码时用多少以它表示了每个信源符号在编码时用多少bie来表示。来表示。（教材也称之为每个信源符号所必须输出的码长）（教材也称之为每个信源符号所必须输出的码长）编码时，编码时， 越小越好。只要越小越好。只要 比平均符号熵稍大一点，那么当比平均符号熵稍大一点，那么当L足够大时，编码就可以

18、做到几乎无失真。否则，不可能实现无足够大时，编码就可以做到几乎无失真。否则，不可能实现无失真编码，且当失真编码，且当L足够大时，译码几乎必定出错。足够大时，译码几乎必定出错。_K_K 由于码元有由于码元有m种取值，长度为种取值，长度为KL的码字的最大信息量为的码字的最大信息量为KLlogm。用该码字表示。用该码字表示L长的信源序列长的信源序列,则则平均送出一个信源平均送出一个信源符号符号所需要的最大信息率为所需要的最大信息率为:logmLKKL_又一种解释：又一种解释：其中：左边其中：左边-KL长码字所能携带的最大信息量，长码字所能携带的最大信息量， 右边右边-L长信源序列携带的信息量。长信源

19、序列携带的信息量。定理表明，只要码字所能携带的信息量大于信源序列输出的信定理表明，只要码字所能携带的信息量大于信源序列输出的信息量，则可以实现几乎无失真编码，当然条件是息量，则可以实现几乎无失真编码，当然条件是L足够大。足够大。反之，不可能实现无失真的编码，也就是不可能做一种编码反之，不可能实现无失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。器，能使收端译码时差错概率趋于零。LLLL)XH()X(LHlogmK )X(HLKmlog2、举例：、举例：信源符号。，等概分布单符号信源，/)()(,3bitlb8XHXH1L8n.aaaAX(1)1821实现无失真编码。信源符号

20、，就可以码元要仍进行二进制编码，只信源符号。计算得分布，上例中，符号不再等概/)(/)()(.,.,.,.,.,.,.,.)( 2.55logmXHK2.55bitXHXH04,00500660070101018040aP(2)L1i无失真编码。信源符号，就可以实现码元，据定理，只要若进行二进制编码，/)(,3logmXHKLK2m10BLL种信源符号。示位二进制码确实可以表事实上，83无失真编码。几乎所谓小，即码），差错概率会足够足够大时（符号序列编但是，当来失真。种信源符号，编码会带，只能区分然而，L5586522.55 .那么，那么，L的取值多大，才得到满意的译码差错概率？的取值多大，才

21、得到满意的译码差错概率？E222P)XL)X0 差错率由编码效率确定），（为需要给定的正数，那么：当，号序列的自信息方差为的很小的实数，信源符是大于设,(2n1i2ii2i2i2iii2ii)XH(logPPIEIEIEIEDI)XlogPIL()()()()()(),()(xxxxxxx那么自信息量为注：某信源符号序列的3、编码效率：、编码效率：)(长每个信源符号输出的码息率为编码器容许的输出信熵为序列信源的平均符号其中：，logmLKK)XH K)XHL_L_L码器的编码效率表示了信源编低。所以越大，说明编码效率越码效率越高。反之，的冗余越多，也就是编越小，说明编码压缩掉 K K_)XH)

22、XH11)XH)XHK)XH)XHKLLLL_LL_(最佳编佳编码(，有最大值，称为取等号时，的信源编码是存在的。码效率接近于是很小的正数，说明编由编码定理，)(22L2222LLL_L-)(1XH)X)XL)XH1 logmLK)XHK)XH）（由最佳编码效率推出而，很大组长度）信源符号序列长度（分很小的编码方法，要求很大而译码错误概率想要获得编码效率L%.,/.)(.9010B55bit2XH0.0405006007010101800.4aaaaaaaaPX2587654322要求编码效率为码，对它进行定长二进制编信源符号计算得：信源例题符号即单符号编码。若取/.(,)(83bit2905

23、52X)H)XHK1L1L_不能应用。序列编码。太大。的错误概率为编码会带来失真，最小没有对应的码字号种信源符号，有一种符，只能区分和表示然而，,040777.1122.83?)(L1090%26，计算且译码错误概率若要求难以实现难以实现72222n1i2iiii2LL1089)XLbit827X)H(logPPDIDI)X280X)HX)H )XH)XH.()(.()()(.(xx得：平稳由：二、变长编码定理二、变长编码定理 若一离散无记忆信源的符号熵为若一离散无记忆信源的符号熵为H（X），每个信源符号），每个信源符号用用m进制码元进行变长编码，一定存在一种无失真编码方法进制码元进行变长编码

24、，一定存在一种无失真编码方法其平均码长其平均码长 满足下列不等式：满足下列不等式： 1logmH(X)KlogmH(X)_n1iiii_KaPWEK)(1、单符号变长编码定理、单符号变长编码定理2、离散平稳无记忆序列变长编码定理（、离散平稳无记忆序列变长编码定理（香农第一极限定理香农第一极限定理）)(:.,.,长每个信源符号输出的码的输出信息率为编码器容许平均码长构成的码字元由码，长输入符号序列logmLKK KPKEKf n21ib n21i LL_n1iiLiiLL_iiLijLiLyxyx是任意小的正数。，满足不等式：法，使平均信息率一种无失真信源编码方，必存在的离散平稳无记忆信源对于平

25、均符号熵为 )X(HK)X(HK )X(H LLL_Ln1iiLiiLL_L_n1iiii_LLKPKEKlogmLKK KaPWEK )X(HK)X(H 1logmH(X)KlogmH(X) K )(注：_，平稳序列变长变码单符号变长变码定理的区别两个定理中 1logm)XH(K logm)XH( 1logmH(X)KlogmH(X) L_平稳序列变长变码单符号变长变码定理样的其实，二者本质上是一3、编码效率、编码效率 定义）（同定长编码的 K)XH_L(）（定长编码代入定理中的不等式，1 1 )XH)XHLL()X(HK)X(H Llogm Llogm)X(HK)X(H logmLKK),

26、X(LH)XH(LLLL_L_L_/得：取代入右式，和将 logPPKEK , logmKX)H niiii_(注这里，：对于单符号变长变码logmKX)H X)H)XHKK1,L logmLK)XH K)XH _L_L_L_L_L(,(单符号编码有4、剩余度、剩余度 缩的冗余的多少。亦即：编码后尚未被压编码的差距，表示了编码方法与最佳 K)XH1 -1 _L(复习一、信源编码的模型：一、信源编码的模型：单符号编码和符号序列编码单符号编码和符号序列编码n1iiii_iKaPWEK /W)( 平均码长信源符号的长度。码元码字单符号编码：1、码长及其意义：、码长及其意义：意义：衡量意义：衡量码的性

27、能码的性能的重要参数的重要参数 对于无失真信源编码，平均码长对于无失真信源编码，平均码长 越短，说明通过编码压越短，说明通过编码压缩去的冗余越多。反之，冗余压缩越少。缩去的冗余越多。反之，冗余压缩越少。_KLL_LLL2L1in1iLiL_LLiKKKKKKPKK n21iK LnL，定长编码：符号序列码元平均码长：；，符号序列编码：码长./)(.,y码码非分组码非分组码分组码分组码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码非即时码非即时码即时码即时码3、码树和、码树和kraft不等式不等式 惟一可译码惟一可译码存在的存在的充分和必要条件是，充分和必要条件是，各码

28、字的长度各码字的长度Ki应符合克劳夫特不等式：应符合克劳夫特不等式： 11niKim2、分类：、分类： 由由L个符号组成的、每个符号的熵为个符号组成的、每个符号的熵为 的无记忆平稳的无记忆平稳信源符号序列信源符号序列 ,可用可用KL个符号个符号 （每个符号有（每个符号有m种可能值）进行定长编码。对任意的种可能值）进行定长编码。对任意的 只要只要 ，则：当，则：当L足够大时，必可使译码差足够大时，必可使译码差 错小于错小于 （几乎无失真编码）；（几乎无失真编码）；Ll21XXXXLKk21Y,Y,Y,Y0, 0logm)X(HLKLL)X(HL二、定长编码定理二、定长编码定理 反之，当反之，当

29、时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几乎必定足够大时，译码几乎必定出错（译码错误概率接近于出错（译码错误概率接近于1 1）。）。 logm2)X(HLKLL )X(HK L_平均送出一个信源符号所需要的最大信息率平均送出一个信源符号所需要的最大信息率编码器容许的输出信息率编码器容许的输出信息率每个信源符号所必须输出的码长每个信源符号所必须输出的码长logmLKKL_编码时，编码时， 越小越好。只要越小越好。只要 比平均符号熵稍大一点，那么当比平均符号熵稍大一点，那么当L足够大时，编码就可以做到几乎无失真。否则，不可能实现无足够大时，编码就可以做到几乎无失

30、真。否则，不可能实现无失真编码，且当失真编码，且当L足够大时，译码几乎必定出错。足够大时，译码几乎必定出错。_K_K2、L的取值：的取值：E222P)XL)X0 错率由编码效率确定），差（为需要给定的正数，那么：当方差为号序列的自信息的很小的实数，信源符是大于设,(_LK)XH (3、编码效率：、编码效率：1 1、解释、解释：无法物理实现计算得：译码错误概率要求编码效率为码，对它进行定长二进制编举例：信源 1089)XL 109010B0.0405006007010101800.4aaaaaaaaPX722687654322.(%,.,.二、变长编码定理二、变长编码定理1、单符号变长编码定理、

31、单符号变长编码定理 无失真编码的平均码长无失真编码的平均码长 满足不等式：满足不等式： 1logmH(X)KlogmH(X)_n1iiii_KaPWEK)(2、离散平稳无记忆序列变长编码定理（、离散平稳无记忆序列变长编码定理（香农第一极限定理香农第一极限定理）是任意小的正数。，满足不等式：法，使平均信息率一种无失真信源编码方，必存在的离散平稳无记忆信源对于平均符号熵为 )X(HK)X(HK )X(H LLL_)(长每个信源符号输出的码的输出信息率为编码器容许平均码长logmLKK KPKEKL_n1iiLiiLL_L K)XH_L() logPPKEK , logmKX)H niiii_(，单

32、符号时Go on5、举例、举例5-3 %.(,;,:)(/)()(/_181KX)H 2m logmKX)H ; 1KEK1KK1a0af10.811bitXHXH413/4aaPX_i2121121平均码长二元定长编码信源符号。，计算得信源码元信源符号码元信源符号编码器输出的信息率：/.(/(811bit0KX)H 1L / bit/ LK )XH R_L_L的二元序列变长编码2L2)(码元961bit/03227X)H LK )XH R 96.13227X)HK)XHL_L2_L2./(/(%/(符号比特平均信息率符号序列码元平均码长/3227lb221627logmLKK /27/16

33、KPKEKL_41iiLiiLL_/ 99.1 98.543L43%时、同理：9510134L10963.%)(计算得，）若要求定长编码（上一节内容性能比较：性能比较： 定长编码定长编码 非定长编码非定长编码 0 99.1 4L 10 96 104L 0 96 2L 0 81.1 1L 5-7，%哪个性能更好？哪个性能更好？6、补充说明：、补充说明： 以上编码定理以上编码定理,适用于离散无记忆平稳信源适用于离散无记忆平稳信源,只考虑了信源符号只考虑了信源符号分布不均匀性造成的冗余分布不均匀性造成的冗余,而未考虑符号间的相关性造成的冗余而未考虑符号间的相关性造成的冗余三、最佳变长编码方法三、最佳

34、变长编码方法1、最佳码最佳码的定义的定义：凡是能载荷一定的信息量，且码字的凡是能载荷一定的信息量，且码字的平均平均长度最短长度最短（压缩后冗余最少），可分离的变长码的码字集合（压缩后冗余最少），可分离的变长码的码字集合都可称为最佳码。都可称为最佳码。2、最佳编码的指导思想：、最佳编码的指导思想： 将概率大的信息符号编以短的码字，概率小的符号编以长将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。的码字，使得平均码字长度最短。3、最佳编码的主要方法最佳编码的主要方法 ：香农（：香农（Shannon）、费诺（）、费诺（Fano）、）、 哈夫曼（哈夫曼（Huffman）

35、编码等。）编码等。 1logm)XH(K logm)XH( L_:序列熵之间的关系均码长和信源了无失真信源编码时平香农第一极限定理给出 以下主要介绍单符号编码时，香农、费诺以下主要介绍单符号编码时，香农、费诺 、哈夫曼等编码方法、哈夫曼等编码方法 1、香农编码：、香农编码：1)XH(K)XH(2m L_），有：如果是二进制编码（长码叫做香农码。这样确定的无失真不定：确定每个码字的长度。可按照这一关系对于单符号编码则有：1I(aKI(a K1H(X)KH(X)iiii_)(1)将信源符号按其出现的概率大小依次排列：将信源符号按其出现的概率大小依次排列： P1P2P3. Pn （指导思想）（指导思

36、想）(2)确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki)(iiiiiaPP 1-lbPKlbP- ，(3)为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个符号的累加概率个符号的累加概率1i1kkiPP(4)将累加概率将累加概率Pi 变换成二进制数。变换成二进制数。 (乘乘2取整）取整）(5)取取Pi二进数的小数点后二进数的小数点后Ki位即为该信源符号的二进制码字。位即为该信源符号的二进制码字。 具体编码步骤：具体编码步骤： 例题例题5-4：设信源共：设信源共7个符号，其概率和累加概率如下表所示。个符号，其概率和累加概率如下表所示。以以i=4为例，为例， 3K563562

37、 1170lbK170lb444,.K，累加概率累加概率P4=0.57，变换成二进制为，变换成二进制为0.1001，由于，由于K4=3，所以，所以第第4个消息的编码码字为个消息的编码码字为100。其它的码字可用同样方法求得。其它的码字可用同样方法求得。 （1） （3） （2） （4、5）码字集为码字集为000,001,011,100,101,1110,1111110惟一可译码；且是即时码（惟一可译码；且是即时码（7个码字都不是延长码）个码字都不是延长码）%./.(183143612KX)H 2m logmKX)H / 3.14KPK _71iii编码效率：符号码元：单符号编码，平均码长（数学可

38、以证明）。说明香农码不是最佳码更短的惟一可译码其实，可以构造出码长。香农编码输出为，信源例题,.)(,11100110100W104050aPaaaAX 5-5i321码元编码输出的信息率：/./.(0.831bit 143612 K X)H R 2、费诺编码：、费诺编码：(1)将信源符号按其出现的概率大小依次排列：将信源符号按其出现的概率大小依次排列： P1P2P3. Pn （指导思想）（指导思想）(2)将依次排列的信源符号按概率值分为两大组，使两个组的将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近于相同，并对各组赋予一个二进制码元概率之和近于相同，并对各组赋予一个二进制码元“

39、0”和和“1”。(3)将每一大组的信源符号进一步再分成两组，使划分后的两将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符号个组的概率之和近于相同，并又赋予两个组一个二进制符号“0和和“1”。(4)如此重复，直至每个组只剩下一个信源符号为止。如此重复，直至每个组只剩下一个信源符号为止。(5)信源符号所对应的码字即为费诺码。信源符号所对应的码字即为费诺码。 例题例题5-6：信源同例题：信源同例题5-4，进行费诺编码，进行费诺编码实际上，费诺编码构造了一个码树（根在左边）。非满树。实际上，费诺编码构造了一个码树（根在左边）。非满树。7个端点，表示个

40、端点，表示7个信源符号。个信源符号。%/.( 95.32.74612KX)H 2m logmKX)H / 2.74KPK _71iii编码效率：符号码元：单符号编码，平均码长码元编码输出的信息率：/.(0.953bit 2.74612 K X)H R 比较：优于香农码。对于该信源，香农码的编码效率为比较：优于香农码。对于该信源，香农码的编码效率为83.1%3、哈夫曼编码：、哈夫曼编码： 最佳编码最佳编码，码长最短，码长最短(1)将信源符号按其出现的概率大小依次排列：将信源符号按其出现的概率大小依次排列： P1P2P3. Pn （指导思想）（指导思想）(2)取两个概率最小的符号，分别赋以码元取两

41、个概率最小的符号，分别赋以码元0和和1，并将这两个，并将这两个概率相加作为一个概率相加作为一个“新符号新符号”的概率。的概率。(3) “新符号新符号”与其它符号构成缩减信源。按概率大小进行重新与其它符号构成缩减信源。按概率大小进行重新排列，重复（排列，重复（2）的操作）的操作 ，直到最后只剩下两个符号。，直到最后只剩下两个符号。(4)从最后一级开始，向前返回得到各个信源符号所对应的码字。从最后一级开始，向前返回得到各个信源符号所对应的码字。 例题例题5-7：信源同例题：信源同例题5-4，进行霍夫曼编码，进行霍夫曼编码实际上，霍夫曼编码也构造了一个码树实际上，霍夫曼编码也构造了一个码树(根在右边

42、根在右边);非满树非满树.7个个端点端点,表示表示7个信源符号。所以读码时，从最后一级向前返回。个信源符号。所以读码时，从最后一级向前返回。如：如： 从最右边的从最右边的“1”开始：开始：1(0.39)0(0.20)不再分，得不再分，得10是符号是符号a1的码字；的码字；1(0.39)1(0.19)不再分，得不再分，得11是符号是符号a2的码字；的码字；从最右边的从最右边的“0”开始：开始：0(0.61)1(0.26)1(0.11)0(0.10)，得，得0110是符号是符号a6的码字的码字码元编码输出的信息率：/.(0.96bit 2.72612 K X)H R 比较：优于香农码和费诺码。对于

43、该信源，香农码的编码效率比较：优于香农码和费诺码。对于该信源，香农码的编码效率为为83.1%；费诺码编码效率为；费诺码编码效率为95.3%数学上可以证明霍夫曼码是最佳编码。数学上可以证明霍夫曼码是最佳编码。%/.( 962.72612KX)H 2m logmKX)H / 2.72KPK _71iii编码效率：符号码元：单符号编码，平均码长原因：原因：A.每次对信源缩减时，赋予信源最后两个概率最小的符每次对信源缩减时，赋予信源最后两个概率最小的符号，用号，用0和和1是可以任意的，所以可以得到不同的哈夫曼码，但是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。不会影响码字的长度。B.

44、对信源进行缩减时，两个概率最小的符号合并后的概率与其对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码其位置放置次序是可以任意的，故会得到不同的哈夫曼码,此此时将影响码字的长度。时将影响码字的长度。（2）信源缩减时，若合并后的新符号的概率与其它符号的概）信源缩减时，若合并后的新符号的概率与其它符号的概率相等，重新排序时，将新符号放置在上面，以减少再次合并率相等，重新排序时，将新符号放置在上面，以减少再次合并的次数，充分利用短码，获得

45、码字长度方差较小的码，提高码的次数，充分利用短码，获得码字长度方差较小的码，提高码的质量。的质量。 4、霍夫曼编码的进一步讨论：、霍夫曼编码的进一步讨论：（1）霍夫曼编码方法得到的码并非是唯一的）霍夫曼编码方法得到的码并非是唯一的例题例题5-8：如下信源，进行霍夫曼编码。信源缩减时新符号的概：如下信源，进行霍夫曼编码。信源缩减时新符号的概率与某一符号相同。重新排序时，新符号分别放置在该符号的率与某一符号相同。重新排序时，新符号分别放置在该符号的上面和下面，比较得到的编码输出有何区别。上面和下面，比较得到的编码输出有何区别。%( 96.5 K X)H / 2.2KPK 51iii符号；码元两种方

46、法都有：360K(KPKKE 361K(KPKKE 251iii2iK251iii2iKii.)(.)(：第二种方法的码长方差：第一种方法的码长方差 码方差越大，说明码长越分散，需要大容量的存储器来缓码方差越大，说明码长越分散，需要大容量的存储器来缓冲码字长度的差异，给编码器的实现增加难度。冲码字长度的差异，给编码器的实现增加难度。5、m进制的霍夫曼编码（如进制的霍夫曼编码（如m=3) 如果缩减到最后是剩下不到如果缩减到最后是剩下不到m个符号，就要添加无用的符个符号，就要添加无用的符号（使其概率为号（使其概率为0）。该例中）。该例中a7就是添加的符号。就是添加的符号。码元编码输出的信息率：/.

47、(1.49bit 1.58352 K X)H R %.( 93.8lb3581352logmKX)H / 1.58KPK _71iii编码效率：符号码元：单符号编码，平均码长第三节第三节 限失真信源编码定理限失真信源编码定理即：香农第三定理即：香农第三定理 设有一离散、平稳、无记忆信源，其率失真函数为设有一离散、平稳、无记忆信源，其率失真函数为R(D)，则对任意选定的则对任意选定的D0，当传信率，当传信率RR(D)时，时， 只要信源序列长只要信源序列长度度L足够长，必存在一种编码方式足够长，必存在一种编码方式C，使译码后的失真，使译码后的失真 D+, 为任意小的正数为任意小的正数 。 反之反之

48、, 若若R0，平均码长满足不，平均码长满足不等式：等式：R(D)K R(D)解释：在失真限度内，使得信息率接近解释：在失真限度内，使得信息率接近R(D)的编码方法是存的编码方法是存在的。在的。R(D)是满足保真度准则的最小信息率。是满足保真度准则的最小信息率。n香农编码、费诺编码、哈夫曼编码主要是针对无香农编码、费诺编码、哈夫曼编码主要是针对无记忆信源。当信源有记忆时上述编码效率不高；记忆信源。当信源有记忆时上述编码效率不高；n游程编码、算术编码等对相关信源编码更有效；游程编码、算术编码等对相关信源编码更有效； 游程编码实际上是对哈夫曼编码的改进。游程编码实际上是对哈夫曼编码的改进。n预测编码

49、、矢量量化等是限失真编码预测编码、矢量量化等是限失真编码n主要介绍游程编码主要介绍游程编码第四节 常用信源编码方法简介*一、游程编码一、游程编码n游程游程：数字序列中连续出现相同符号的一段。：数字序列中连续出现相同符号的一段。n二元序列的游程：只有二元序列的游程：只有“0”和和“1”两种符号。两种符号。连连“0”这一段称为这一段称为“0”游程，它的长度称为游程，它的长度称为游程长度游程长度L(0)；连连“1”这一段称为这一段称为“1”游程，它的游程长度用游程，它的游程长度用L(1)表示。表示。1、二元独立序列游程长度概率、二元独立序列游程长度概率n若规定二元序列总是从若规定二元序列总是从“0”

50、开始。开始。n对于随机序列对于随机序列,游程长度是随机的其取值可为游程长度是随机的其取值可为1,2,3,直至无穷直至无穷n游程长度序列游程长度序列/游程序列：用交替出现的游程序列：用交替出现的“0”游程和游程和“1”游程长游程长度表示任意二元序列。度表示任意二元序列。n游程变换：是一种一一对应的变换，也是可逆变换。游程变换：是一种一一对应的变换，也是可逆变换。 例如：二元序列：例如：二元序列：000101110010001，可变换成如下游程序，可变换成如下游程序列：列：31132131n游程变换减弱了原序列符号间的相关性。游程变换减弱了原序列符号间的相关性。n游程变换将二元序列变换成了游程变换

51、将二元序列变换成了多元序列多元序列；这样就适合于用其；这样就适合于用其他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。他方法，如哈夫曼编码，进一步压缩信源，提高通信效率。n编码方法：编码方法：n首先测定首先测定“0”游程长度和游程长度和“1”游程长度的概率分布，即游程长度的概率分布，即以游程长度为元素，构造一个新的信源；以游程长度为元素，构造一个新的信源；n对新的信源（游程序列）进行哈夫曼编码。对新的信源（游程序列）进行哈夫曼编码。2、 二元独立序列游程长度的熵二元独立序列游程长度的熵n若二元序列的概率特性已知，由于二元序列与游程变换序列若二元序列的概率特性已知，由于二元序列与游程变换序列

52、的一一对应性，可计算出游程序列的概率特性。的一一对应性，可计算出游程序列的概率特性。n令令“0”和和“1”的概率分别为的概率分别为p0和和p1，则，则“0”游程长度游程长度L(0)的的概率为概率为 pL(0)=p0L(0)1p1 式中式中L(0)=1,2, 在计算在计算pL(0)时必然已有时必然已有“0”出现，否则就不是出现，否则就不是“0”游程，游程，若下一个符号是若下一个符号是“1”，则游程长度为，则游程长度为1，其概率是，其概率是p1 =1p0；若下一个符号为若下一个符号为“0”、再下一个符号为、再下一个符号为“1”，则游程长度为，则游程长度为2，其概率将为，其概率将为p0p1 ；依此类

53、推。；依此类推。n同理可得同理可得“1”游程长度游程长度L(1)的概率为：的概率为：PL(1)=p1L(1)-1p002(0) 11() (0) (0)log (0)LH pH Lp Lp Lp n“0”游程长度的熵：游程长度的熵：3、 二元独立序列的平均游程长度二元独立序列的平均游程长度n“0”游程序列的平均游程长度游程序列的平均游程长度n同理可得同理可得“1”游程长度的熵和平均游程长度游程长度的熵和平均游程长度(0) 1001(0) 1(0) 1(0)10(0) 1011234 (0)(0) (0)(0)1(1)1LLLLLlE LLp LLppdppdppxxxxx 0100()1 (1

54、) (1)H pH LlE Lpp4、 二元独立序列的熵二元独立序列的熵n“0”游程序列的熵与游程序列的熵与“1”游程长度的熵之和除以它们的平均游程游程长度的熵之和除以它们的平均游程长度之和，即为对应原二元序列的熵长度之和，即为对应原二元序列的熵H(X)n游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，游程变换后符号熵没有变。因为游程变换是一一对应的可逆变换，所以变换后熵值不变。所以变换后熵值不变。0101 (0) (1)()()()H LH LH XH pH plln游程变换有较好的去相关效果，因而对游程序列进行哈夫曼游程变换有较好的去相关效果，因而对游程序列进行哈夫曼编码可获得较

55、高的编码效率。编码可获得较高的编码效率。n假设假设“0”游程长度的哈夫曼编码效率为游程长度的哈夫曼编码效率为0，“1”游程长度的游程长度的哈夫曼编码效率为哈夫曼编码效率为1，由编码效率的定义可得对应二元序列，由编码效率的定义可得对应二元序列的编码效率（信源熵和信息率之比为编码效率的编码效率（信源熵和信息率之比为编码效率=H(X)/R）n当当“0”游程和游程和“1”游程的编码效率都很高时，采用游程编游程的编码效率都很高时，采用游程编码的效率也很高，至少不会低于较小的那个效率。要想编码的效率也很高，至少不会低于较小的那个效率。要想编码效率尽可能高，应尽可能提高熵值较大的游程编码效率。码效率尽可能高

56、，应尽可能提高熵值较大的游程编码效率。01 (0) (1)0101 (0) (1)H LH LH LH L假设，则有n算术编码不同于哈夫曼码，它算术编码不同于哈夫曼码，它是非分组（非块）码。是非分组（非块）码。它从全序它从全序列出发，考虑符号之间的关系来进行编码。列出发，考虑符号之间的关系来进行编码。n算术编码利用了算术编码利用了累积概率累积概率的概念。的概念。n算术码主要的编码方法是算术码主要的编码方法是计算输入信源符号序列所对应的区间计算输入信源符号序列所对应的区间n因为在编码过程中，每输入一个符号要进行乘法和加法运算，因为在编码过程中，每输入一个符号要进行乘法和加法运算，所以称此编码方法

57、为算术编码所以称此编码方法为算术编码二、算术编码二、算术编码1、设信源符号集、设信源符号集A=a1,a2,an，其相应概率分布为，其相应概率分布为P (ai)， P (ai) 0(i=1,2, ,n)n信源符号的累积分布函数为：信源符号的累积分布函数为： 所得累积分布函数为每台级的下界值，则其区间为所得累积分布函数为每台级的下界值，则其区间为0,1)左左闭右开区间。闭右开区间。 F (a1)=0 F (a2)=P (a1) F (a3)=P (a1)+P (a2) n当当A=0,1二元信源时：二元信源时： F (0)= 0，F (1)=P (0)n计算计算二元无记忆信源序列二元无记忆信源序列的

58、累积分布函数的累积分布函数n初始时：在初始时：在0,1)区间内由区间内由F (1)划分成二个子区间划分成二个子区间0,F (1)和和F (1),1)， F (1)= P (0)。n子区间子区间0,F (1)的宽度为的宽度为A(0)= P (0)，对应于信源，对应于信源符号符号“0”；n子区间子区间F (1),1)的宽度为的宽度为A(1)= P (1)，对应于信源，对应于信源符号符号“1”；n若输入符号序列的第一个符号为若输入符号序列的第一个符号为s s=“0”，落入，落入0,F (1)区间，得累积分布函数区间，得累积分布函数F (s s=“0”)= F (0)=0； n输入第二个符号为输入第二

59、个符号为“1”，s s=“01”ns s=“01”所对应的区间是在区间所对应的区间是在区间0,F (1)中进行分割中进行分割n符号序列符号序列“00”对应的区间宽度为对应的区间宽度为: A(00)=A(0)P (0)=P (0)P (0)=P (00)；n对应的区间为对应的区间为0,F (s=“01”)。n符号序列符号序列“01”对应的区间宽度为对应的区间宽度为 A(01)=A(0)P (1)=P (0)P (1)=P (01)= A(0)A(00)；n对应的区间为对应的区间为F (s=“01”),F (1)。n累积分布函数累积分布函数F (s s=“01”)=P (00)= P (0)P (

60、0) 输入第三个符号为输入第三个符号为“1”：n输入序列可记做输入序列可记做s s1=“011”（若第三个符号输入为（若第三个符号输入为“0”，可记做，可记做s s0=“010”）；）；n现在，输入序列现在，输入序列s s1=“011”对应的区间是对区间对应的区间是对区间F(s s),F(1)进行分割；进行分割；n序列序列s s0=“010”对应的区间宽度为对应的区间宽度为 A(s s=“010”)=A(s s=“01”) P(0)=A(s s) P(0) 其对应的区间为其对应的区间为F(s s), F(s s)+ A(s s) P(0)；n序列序列s s1=“011”对应的区间宽度为对应的区