信息论与编码理论基础第三章

1、信息论与编码理论基础第三章第1页，共195页，2022年，5月20日，16点41分，星期一2022/9/11 信源发出的消息序列通常不能直接送给信道传输，需要经过信源编码和信道编码。 第2页，共195页，2022年，5月20日，16点41分，星期一2022/9/12信道编码在传输过程中噪声和干扰在所难免，为了降低差错率，提高传送的可靠性，在信道编码器中可以引入冗余度，在信道解码端就可以利用此冗余度来尽可能地重建输入序列。可靠性：增加冗余第3页，共195页，2022年，5月20日，16点41分，星期一2022/9/13信源编码对信源进行压缩、扰乱和加密，用最少的码字最安全地传输最大的信息量：有效

2、性和安全性：去除冗余如何对信源进行建模？（如随机过程）如何测量信源的内容？（熵）如何表示一个信源？（编码：码字设计）第4页，共195页，2022年，5月20日，16点41分，星期一2022/9/14为什么需要信源编码/数据压缩数字化视频和音频等媒体信息的数据量很大数字音频格式频带范围（Hz）取样频率（kHz）样本精度（bit）声道数原始码率（Kb/s）电话300340088164调频（FM）广播201500022.03162705.6激光唱盘（CD）202000044.11621411.2数字视频格式每秒帧数图像分辨率（像素）样本精度（bit）亮度信号原始码率（Mb/s）CIF格式的亮度信号3

3、0352*288824.33HDTV亮度信号一例601920*10808995.3第5页，共195页，2022年，5月20日，16点41分，星期一2022/9/15为什么需要信源编码/数据压缩减少存储空间文件压缩、图像压缩、语音压缩、视频压缩减少传输时间第6页，共195页，2022年，5月20日，16点41分，星期一2022/9/16信源编码/数据压缩的例子： 摩尔斯式电码19世纪中叶，由 Samuel Morse发明每个字符用“ .” 或“” 表示观察：一些字符比另外一些字符出现的频率更高，如 “a, e”比“z, q”出现的频率高因此，为了减少发送信息的平均时间，用较短的序列表示出现频率高

4、的字符，较长的序列表示出现频率低的字符e: . , a: . q: - - . - , j: . - - - 第7页，共195页，2022年，5月20日，16点41分，星期一2022/9/17为什么可以进行信源编码/数据压缩自然界中的大多数数据都是冗余的： 任何非随机选择的数据都有一定结构，可利用这种结构得到数据的更紧致表示统计冗余：大多数常见的压缩算法都是利用该冗余字母冗余：英文中字母E最常出现，而Z很少出现文本冗余：字母Q后常跟有字母U第8页，共195页，2022年，5月20日，16点41分，星期一2022/9/18例：空间冗余图像中存在大面积部分相似或完全一样的像素pmf第9页，共195

5、页，2022年，5月20日，16点41分，星期一2022/9/19例：时间冗余视频图像前后几帧的内容变化不大（位置可能不同，可用运动估计方法找到对应位置）第10页，共195页，2022年，5月20日，16点41分，星期一2022/9/110例：结构冗余图像中物体表面纹理等结构存在冗余第11页，共195页，2022年，5月20日，16点41分，星期一2022/9/111怎样进行信源编码无失真编码:若要求将信源输出在接收端精确地重现出来，即保证信源输出所携带的信息全部无损地传达给信宿，就要对信源进行无失真编码。无失真编码只是对信源冗余度进行压缩，并不改变信源熵，它能保证信源序列经无扰信道传输后，得

6、到无失真的恢复。限定失真编码：在实际传信中，要精确的复制出信源的输出是不可能的，根据信源信宿对定出的可接收准则或保真度准则，计算要保留多少有关信源输出的信息量，以及如何表示它们，这就是限定失真的信源编码问题。第12页，共195页，2022年，5月20日，16点41分，星期一2022/9/112第三章：信源编码（一）离散信源无失真编码3.1 信源及其分类3.2 离散无记忆（简单）信源的等长编码3.3 离散无记忆（简单）信源的不等长编码3.4 最佳不等长编码第13页，共195页，2022年，5月20日，16点41分，星期一2022/9/1133.1 信源及其分类信源的概念 :信源就是信息的来源。注

7、意：在一个固定的时刻，信源发出的是一个随机变量。随着时间的延续，信源发出一个又一个随机变量，称之为一个随机过程。 因此，可以用概率空间来描述信源。 第14页，共195页，2022年，5月20日，16点41分，星期一2022/9/1143.1 信源及其分类离散信源 信源每隔一个定长时间段就发出一个随机变量； 随着时间的延续，信源发出的是随机变量序列U-2U-1U0U1U2， 其中 Uk为第k个时间段发出的随机变量； 每个Uk都是一个离散型的随机变量。离散无记忆信源 随机变量、U-2、U-1、U0、U1、U2、 相互独立的离散信源。离散无记忆 随机变量、U-2、U-1、U0、U1、 U2、 简单信

8、源 具有相同的概率分布的离散无记忆信源。第15页，共195页，2022年，5月20日，16点41分，星期一2022/9/1153.1 信源及其分类（总结：离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。课程学习所面对的信源将主要是离散无记忆简单信源）一般的信源 连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的 概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。 第16页，共195页，2022年，5月20日，16点41分，

9、星期一2022/9/1163.2 离散无记忆（简单）信源的等长编码（1）设有一个离散无记忆简单信源，信源发出的随机变量序列为：U-2U-1U0U1U2。 设信源随机变量U1的事件有K个：a1, a2, , aK，则L维信源随机向量(U1U2UL)的事件有KL个：(u1u2uL)|其中每个分量ul跑遍a1, a2, , aK。P(U1U2UL)=(u1u2uL)=P(U1=u1)P(U2=u2) P(UL=uL)=P(U1=u1)P(U1=u2) P(U1=uL)=q(u1)q(u2) q(uL)（2） D元编码：设有一个含D个字母的字母表，对于(U1U2UL)的每一个事件(u1u2uL)，都用

10、一个字母串(c1c2)来表示。 第17页，共195页，2022年，5月20日，16点41分，星期一2022/9/117码长：码字所含码元的个数 等长编码：所有码字均有相同的码长N，对应的码 叫做等长码(FLC，Fixed Length code)；否则为变长编码。编码器码字:每一个事件(u1u2uL)所对应的字母串(c1c2) 。 编码器模型：D个字母的字母表A信源第18页，共195页，2022年，5月20日，16点41分，星期一2022/9/118熵是随机变量平均不确定性的一个测度，表示了描述这个随机变量所需要的平均比特数第19页，共195页，2022年，5月20日，16点41分，星期一20

11、22/9/1193.2 离散无记忆（简单）信源的等长编码例：离散无记忆简单信源发出的随机变量序列为：U-2U-1U0U1U2。其中U1的事件有3个：晴, 云, 阴。(U1U2)有9个事件 （晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云）， （阴阴）。用字母表0, 1对(U1U2)的事件进行2元编码如下： （晴晴）0000，（晴云）0001，（晴阴）0011， （云晴）0100，（云云）0101，（云阴）0111， （阴晴）1100，（阴云）1101，（阴阴）1111。第20页，共195页，2022年，5月20日，16点41分，星期一2022/9/120无错编码 （

12、唯一可译码） (U1U2UL)的不同事件用不同的码字来表示。 能够实现无错编码的充要条件是DNKL。（即NlogD/LlogK）这里N/L表示每个信源符号所需要的码符号数； logD是一个码符号所能载荷的最大信息量；N/LlogK/logD说明对于等长唯一可译码平均每个信源符号至少需要logK/logD个码符号对其进行编码变换；（NlogD）/L是编码后平均每个信源符号所能载荷的信息量的最大值，称为编码速率，记为R. 关于编码速率的说明： 由编码速率的计算公式R=NlogD/L，似乎可以任意设置N和L，进而可以任意设置编码速率。事实上存在着编码设备的性能指标：编码速率R0。这就是说，选择N和L

13、，必须使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0 。有错编码 (U1U2UL)的有些不同事件用相同的码字来表示。编码是一种由消息集到码字集的映射第21页，共195页，2022年，5月20日，16点41分，星期一2022/9/1213.2 离散无记忆（简单）信源的等长编码无错编码的最低代价当R=(NlogD)/LlogK时，能够实现无错编码。 （DNKL）当RH(U1)时，无论怎样编码都是有错编码。这是因为RH(U1)logK。 （DNRH(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。3.2 离散无记忆

14、（简单）信源的等长编码第23页，共195页，2022年，5月20日，16点41分，星期一2022/9/1233.2 离散无记忆（简单）信源的等长编码我们以英文电报为例，由于英文字母之间有很强的关联性，当用字母组合成不同的英文字母序列时，并不是所有的字母组合都是有意义的单词，若再把单词组合成更长的字母序列时，也不是任意的单词组合都是有意义的句子，因此，在足够长的英文字母序列中，就有许多无用和无意义的序列，这些信源序列出现的概率等于零或任意小，那么在编码时，对于那些无用的字母组合，无意义的句子都可以不编码，从而提高传输效率，但同时，会引入一定的误差，但是当L足够大时，这种误差概率就可以任意小，可做

15、到几乎无失真编码。第24页，共195页，2022年，5月20日，16点41分，星期一2022/9/1243.2 离散无记忆（简单）信源的等长编码渐进无错编码 （简单地说就是：当RH(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：） 设给定了编码设备的编码速率R0，R0H(U1)。则对任意的0，总存在一个L0，使得对任意的LL0，都有对(U1U2UL)的等长编码和对应的译码方法，满足实际的编码速率R=NlogD/LR0，译码错误的概率pe。第25页，共195页，2022年，5月20日，16点41分，星期一2022/9/1253.2 离散无记忆（简单）信源的等长编码不能

16、渐进无错的编码 （简单地说就是：当RH(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是： ） 设给定了编码设备的编码速率R0，R00有PH(U1)-ILH(U1)+第28页，共195页，2022年，5月20日，16点41分，星期一2022/9/128切比雪夫不等式注：切比雪夫第29页，共195页，2022年，5月20日，16点41分，星期一2022/9/1293.2 离散无记忆（简单）信源的等长编码取定L0使得 ，则当LL0时总有因此当LL0时总有这样的一些事件序列， H(U1)-ILH(U1)+，而且PH(U1)-ILH(U1)+1-。说明当L足够大时，信源序列的

17、自信息量的均值以概率1收敛于信源熵。当L足够大时，在信源序列中必有一些消息序列其自信息量的均值与信源熵之差小于，而对另外一些信源序列其差 ，因此，可以把信源序列分成两个互补的子集。 第30页，共195页，2022年，5月20日，16点41分，星期一2022/9/1303.2 离散无记忆（简单）信源的等长编码定义(p57) 定义TU(L, )=(u1u2uL)|H(U1)-ILH(U1)+， 称TU(L, )为-典型序列集。 称TU(L, )的补集为非-典型序列集。 （综上所述有）定理(信源划分定理，p58) 对任意0，取L0使得则当LL0时总有P(U1U2UL) )=(u1u2uL)| (u1

18、u2uL) TU(L, )1-。 第31页，共195页，2022年，5月20日，16点41分，星期一2022/9/1313.2 离散无记忆（简单）信源的等长编码（简记H(U)=H(U1)。设以下的对数都是以2为底的。）系(特定典型序列出现的概率，p58) 若一个特定的事件(u1u2uL)TU(L, )，则2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。 证明 设(u1u2uL)TU(L, )。注意到此时H(U)-ILH(U)+，第32页，共195页，2022年，5月20日，16点41分，星期一2022/9/1323.2 离散无记忆（简单）信源的等长编码所以第33页

19、，共195页，2022年，5月20日，16点41分，星期一2022/9/1333.2 离散无记忆（简单）信源的等长编码系(典型序列的数量，p58) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。证明 一方面，第34页，共195页，2022年，5月20日，16点41分，星期一2022/9/1343.2 离散无记忆（简单）信源的等长编码另一方面，第35页，共195页，2022年，5月20日，16点41分，星期一2022/9/1353.2 离散无记忆（简单）信源的等长编码 P(U1U2UL) )=(u1u2uL)| (u1u2uL) TU(L, )1-。系(特定典型序列出现的概率)

20、2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。系(典型序列的数量) (1-)2L(H(U)-)|TU(L, )|2L(H(U)+)。第36页，共195页，2022年，5月20日，16点41分，星期一2022/9/1363.2 离散无记忆（简单）信源的等长编码典型序列集非典型序列集序列集合定理，系以及系就说明：所有典型序列的概率和接近于1，是高概率集；典型序列集中各序列出现的概率近似相等；每个典型序列中一个信源符号的平均信息量接近于信源熵；当L达到无限时，才等于信源熵。第37页，共195页，2022年，5月20日，16点41分，星期一2022/9/1373.2 离

21、散无记忆（简单）信源的等长编码补充引理 设给定一个R0H(U)。对每个正整数L，对应地取整数N=R0L（R0L的下取整）。则0R0L-N1 即 0R0-N/LL0时N/LR0-R0- (R0 -H(U)/2=H(U)+(R0-H(U)/2H(U)+。P(U1U2UL)TU(L, )1-。 （由定理）第38页，共195页，2022年，5月20日，16点41分，星期一2022/9/1383.2 离散无记忆（简单）信源的等长编码定理3.2.2(无错编码正定理，p60) 给定编码设备的编码速率R0，R0H(U)。则对任意的0，总存在一个L0，使得对任意的LL0，都有对(U1U2UL)的2元等长编码方法

22、和对应的译码方法，实际的编码速率R满足R0RH(U)，“译码错误”的概率peH(U)；“译码错误”的概率pe=P(U1U2UL)不属于TU(L, )=1-P(U1U2UL)TU(L, )。得证。 定理(无错编码反定理，p60) 设给定编码设备的编码速率R0，满足R0H(U)；给定一个任意小的正数0；要求：选择合适的L，N，对(U1U2UL)进行合适的2元N长编码，使得实际的编码速率R=N/L满足RR0；“译码错误”的概率pe。第42页，共195页，2022年，5月20日，16点41分，星期一2022/9/142渐进无错编码的步骤由U1的概率分布计算取L满足 。取整数N=R0L（R0L下取整）。

23、取典型序列集第43页，共195页，2022年，5月20日，16点41分，星期一2022/9/143渐进无错编码的步骤将TU(L, )中的事件用不同的N长2元码字来表示，而将TU(L, )以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L, )中的某个事件。译码时，所有的码字均译为它所表示的TU(L, )中的事件。（注解：显然满足RR0；| TU(L, ) | 2N，因此码字足够用；译码错误的概率为pe=P(U1U2UL)=(u1u2uL)| (u1u2uL)不属于TU(L, )0.037587148=H(U1)。希望：2元编码的实际编码速率RR0；译码错误的

24、概率不超过。其中取=0.1。找L使得第46页，共195页，2022年，5月20日，16点41分，星期一2022/9/1463.2 离散无记忆（简单）信源的等长编码取L=253即可。再取N=R0L=126。将TU(L, )中的事件用不同的N长2元码字来表示，而将TU(L, )以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L, )中的某个事件。译码时，所有的码字均译为它所表示的TU(L, )中的事件。另一方面， TU(L, )中的事件有更加简单的表达方式。当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，第47页，共195页，2022年，5月20日

25、，16点41分，星期一2022/9/1473.2 离散无记忆（简单）信源的等长编码事件(u1u2uL)属于典型序列集TU(L, 0.1)；当且仅当第48页，共195页，2022年，5月20日，16点41分，星期一2022/9/1483.2 离散无记忆（简单）信源的等长编码当事件(u1u2u253)中a1的个数不超过4时， (u1u2u253)TU(253, 0.1)；否则(u1u2u253)不属于TU(253, 0.1)。(u1u2u253)TU(253, 0.1)的概率不小于0.9；(u1u2u253)TU(253, 0.1)的个数为第49页，共195页，2022年，5月20日，16点41分

26、，星期一2022/9/1493.2 离散无记忆（简单）信源的等长编码对L=253，对应地取整数N=R0L=126。则N/LR0，这就是说2元编码的实际编码速率并未超出编码设备的编码速率。2元编码的编码方法： 将TU(253, 0.1)中的事件用不同的126长码字表示；将TU(253, 0.1)外的事件用同一个126长码字表示，该码字已经用于表示了TU(253, 0.1)中的一个事件。由于|TU(253, 0.1)|233.355557444qb，其码长也具有不等式nanb。 现在将事件a和b交换码字，其它事件的码字保持不变。此时2元异字头码S 变成新的2元异字头码T。由于码S与码T中事件a和b

27、之外的其它事件的码字保持不变，因而它们对平均码长的贡献不变，而码S 中事件a和b的码字对平均码长的贡献为qana+qbnb；码T中事件a和b的码字对平均码长的贡献为qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)0。 这就是说，码S 的平均码长码T 的平均码长。因而码S 不是最佳2元异字头码。 用反证法已经证明了补充引理2。 第76页，共195页，2022年，5月20日，16点41分，星期一2022/9/1763.4 最佳不等长编码补充引理3 设信源随机变量U的最佳2元异字头码S ，则最长的码字至少有两个。证明 如果2元异字头码S 的最长的码字竟

28、然只有一个。 设这个码字为c，是事件a的码字。 现在将c的最后一位去掉，成为c，将c仍然作为事件a的码字。其它事件的码字保持不变。此时2元异字头码S 变成新的2元码T。注意到以下两点：码T仍然是2元异字头码；码S 的平均码长码T 的平均码长。 因而码S 不是最佳2元异字头码。用反证法已经证明了补充引理3。第77页，共195页，2022年，5月20日，16点41分，星期一2022/9/177aa第78页，共195页，2022年，5月20日，16点41分，星期一2022/9/1783.4 最佳不等长编码补充引理4 最佳2元异字头码S可以满足以下两条：（1）概率最小的两个事件码字最长，且长度相等；（

29、2）它们的码字仅仅最后一位不同。证明 取概率最小的事件a。在剩下的事件中取概率最小的事件b。根据补充引理2和补充引理3，事件a和事件b的码字最长，且长度相等。这就是说，最佳2元异字头码S显然满足第（1）条。 关于第（2）条，分以下三种情形来讨论：第79页，共195页，2022年，5月20日，16点41分，星期一2022/9/1793.4 最佳不等长编码情形一事件a和事件b的码字仅仅最后一位不同。此时：最佳2元异字头码S 满足第（2）条。补充引理4得证。情形二事件a和事件b的码字不是仅仅最后一位不同，但有第三个事件c，其码字与事件a的码字仅仅最后一位不同。此时：将事件b与事件c交换码字，得到新的

30、2元异字头码T。码T与码S平均码长相同，因此码T也是最佳2元异字头码，且码T满足第（1）条和第（2）条。情形三事件a和事件b的码字不是仅仅最后一位不同，也没有第三个事件c，其码字与事件a的码字仅仅最后一位不同。此时：将事件b的码字换为与事件a的码字仅仅最后一位不同，得到新的码T。码T 也是2元异字头码。码T与码S平均码长相同，因此码T也是最佳2元异字头码，且码T满足第（1）条和第（2）条。第80页，共195页，2022年，5月20日，16点41分，星期一2022/9/180abacb3.4 最佳不等长编码abcabab第81页，共195页，2022年，5月20日，16点41分，星期一2022/

31、9/181Huffman编码的最佳性定理：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。 第82页，共195页，2022年，5月20日，16点41分，星期一2022/9/1823.4 最佳不等长编码补充定理 设信源随机变量U有K个事件， K3。取出两个概率最小的事件：事件a和事件b。将事件a与事件b合并成一个事件e， e的概率为事件a与事件b的概率之和；而将信源随机变量U的其它事件和其对应的概率保持不变。这样得到了新的信源随机变量U。找到U的一个最佳2元异字头码R。将码R中事件e的码字后面分别

32、添加0和1，分别作为事件a和事件b各自的码字；而将码R中其它事件的码字保持不变。这样得到了U的2元码R。则：码R是U的最佳2元异字头码。第83页，共195页，2022年，5月20日，16点41分，星期一2022/9/1833.4 最佳不等长编码证明 首先说明， 码R是U的2元异字头码。 码R中，每个码字都在树梢，对事件e的码字后面分别添加0和1后，得到码R， 码R中，由事件e的码字后面分别添加0和1得到的两个码字对应于码数中的两个新的叶子节点，位于树梢；而其它码字显然也在树梢。 综上所述，码R是U的2元异字头码。 接下来说明，对辅助集U 为最佳的码，对原始消息集U也是最佳的。第84页，共195

33、页，2022年，5月20日，16点41分，星期一2022/9/184设原始信源随机变量新的信源随机变量3.4 最佳不等长编码第85页，共195页，2022年，5月20日，16点41分，星期一2022/9/1853.4 最佳不等长编码若C1，C2，CK-1是信源U 的最佳码，相应码长为n1，n2，nK-1，则对信源U的码字C1，C2, CK的码长为nk= nk kK2nk= nK-1+1 k=K, K1同时两信源各事件出现的概率满足关系式：pk= pk kK2pK+pK-1= pK-1第86页，共195页，2022年，5月20日，16点41分，星期一2022/9/1863.4 最佳不等长编码 第

34、87页，共195页，2022年，5月20日，16点41分，星期一2022/9/1873.4 最佳不等长编码补充定理给出了一种构造信源随机变量U的最佳2元异字头码的方法：取出两个概率最小的事件a和事件b，分别标号为0和1；然后将事件a和事件b合并成事件e，因此将信源随机变量U合并成U；寻找U的最佳2元异字头码；然后将该码中事件e的码字后面分别添加事件a和事件b的标号（0和1），分别成为事件a和事件b的码字。这种构造方法正是2元Huffman编码。换句话说，定理 对信源随机变量U的2元Huffman编码是最佳2元异字头码，因而是在唯一可译前提下的最佳2元不等长编码。第88页，共195页，2022年

35、，5月20日，16点41分，星期一2022/9/1883.4 最佳不等长编码2元Huffman编码法（字母表0, 1）（1）将概率最小的2个事件分别赋予标号“0”和“1”。（2）将这2个事件合并为一个事件，其概率为2个事件概率之和。重复（1）-（2），直到合并为所剩的事件为2个。将这2事件分别赋予标号“0”和“1”。编码完毕。此时，一个事件的码字是这个事件从最后标号开始到最先标号为止的标号序列。第89页，共195页，2022年，5月20日，16点41分，星期一2022/9/189例：Huffman编码过程第90页，共195页，2022年，5月20日，16点41分，星期一2022/9/190例：

36、Huffman编码过程第91页，共195页，2022年，5月20日，16点41分，星期一2022/9/191P59 Shannon-Fano编码例子采用Huffman编码a 16b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111总比特数88，信源熵为86.601bit第92页，共195页，2022年，5月20日，16点41分，星期一2022/9/192Huffman编码Shannon-Fano编码构造二叉树是自树根到树叶，很难保证最佳性。Huffman编码则是从树叶到树根，是最佳的第93页，共195页，2022年，5月20日，16点41分，星期一

37、2022/9/193总结Huffman需要知道信源的概率分布，这在实际中有时是比较困难的。采用半静态模型、自适应模型、markov模型，部分匹配预测模型等等解决这一问题。第94页，共195页，2022年，5月20日，16点41分，星期一2022/9/194D元Huffman编码D元码全数的端节点数为D+m(D-1)由Huffman编码的最佳性知空缺的端节点应当是码长最长的端节点共有K个符号，设第一次需要合并的消息个数为R，空缺数为BB个R个第95页，共195页，2022年，5月20日，16点41分，星期一2022/9/195D元Huffman编码 K+B=D+m(D-1)，因而K-2=m(D-

38、1)+D-2-B 注意R+B=D，有 0BD-2， 0D-2-BD-2 因而D-2-B=(K-2)mod(D-1)即 R-2=(K-2)mod(D-1)B个R个第96页，共195页，2022年，5月20日，16点41分，星期一2022/9/196Huffman 编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。今天，在许多知名的压缩工具和压缩算法（如 WinRAR 、 gzip 和 JPEG ）里，都有 Huffman 编码的身影。不过， Huffman 编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此

39、，现代压缩技术通常只将 Huffman 作为最终的编码手段，而非数据压缩算法的全部。同时科学家们一直没有放弃向信息熵极限挑战的理想。 1968 年前后， P. Elias 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路， 1976 年， J. Rissanen 提出了一种可以成功地逼近信息熵极限的编码方法算术编码。算术编码第97页，共195页，2022年，5月20日，16点41分，星期一2022/9/197算术编码Shannon-Fano编码，Huffman编码的编码方法：首先对信源的各事件进

40、行编码，然后再对输入的消息序列进行编码变换。算术编码：首先假设一个信源的概率模型,随后直接把整个输入的消息编码为一个(0.0 n 1.0)内的小区间，在编码的过程中，消息序列集中的每个元素都用来缩短这个区间，消息序列集中的元素越多,所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间，这就是区间作为代码的原理。第98页，共195页，2022年，5月20日，16点41分，星期一2022/9/198使用算术编码的压缩算法通常先要对信源符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。 例: 对一个简单的信号源进行观察，得到的统计模型如下：60% 的机会出现符号

41、中性 20% 的机会出现符号 阳性 10% 的机会出现符号 阴性 10% 的机会出现符号 数据结束符. 算术编码第99页，共195页，2022年，5月20日，16点41分，星期一2022/9/199在得到信源随机变量U的事件集的概率分布P(ak)，(k=0,1, K-1)之后，我们需要定义信源符号的分布函数 ，(k=0, 1, , K-1)。 其中F(a0)=0； F(a1)=P(a0)；F(a2)=P(a0)+P(a1)； F(aK-1)=P(a0)+P(a1)+ +P(aK-2)。 随后，编码过程的每一步，除了最后一步，都是相同的。算术编码第100页，共195页，2022年，5月20日，1

42、6点41分，星期一2022/9/1100编码器通常需要考虑下面三种数据：下一个要编码的符号 当前的区间(在编第一个符号之前，这个区间是0,1), 但是之后每次编码区间都会变化) 模型中在这一步可能出现的各个符号的概率分布编码器利用信源符号的分布函数将当前的区间分成若干子区间，区间之间的分隔线为信源符号的分布函数，每个子区间的长度与可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为下一步编码的初始区间。算术编码第101页，共195页，2022年，5月20日，16点41分，星期一2022/9/1101例: 对于前面提出的4符号模型:中性对应的区间是 0, 0.6) 阳性对应的区间是

43、0.6, 0.8) 阴性对应的区间是 0.8, 0.9) 数据结束符对应的区间是 0.9, 1) 当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和模型参数即可以解码重建得到该符号序列。算术编码第102页，共195页，2022年，5月20日，16点41分，星期一2022/9/1102算术码再以二元信源输出序列01110的编码为例P(0)P(1)F(0)F(1)01算术编码第103页，共195页，2022年，5月20日，16点41分，星期一2022/9/1103算术码P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0

44、110)P(0111)F(0111)P(01110)P(01111)F(01111)算术编码第104页，共195页，2022年，5月20日，16点41分，星期一2022/9/1104算术码信源符号序列u对应区间的宽度等于符号序列的概率信源符号序列u对应区间的左端点为算术编码第105页，共195页，2022年，5月20日，16点41分，星期一2022/9/1105F(u)将0,1)分割成许多小区间，以小区间的左端点数值的二进制小数表示该序列，同时要将该小数的小数位数截断为l位，截断规则为： l位后面只要有非0的余数就要向第l位进位。 最后得到了小数0.t。将t作为事件u=(u1u2uL)的码字。

45、码字长度l为算术编码第106页，共195页，2022年，5月20日，16点41分，星期一2022/9/1106算术编码则即因而即第107页，共195页，2022年，5月20日，16点41分，星期一2022/9/1107例: 下面对使用前面提到的4符号模型进行编码的一段信息进行解码。编码的结果是0.538(为了容易理解，这里使用十进制而不是二进制；我们也假设得到的结果的位数恰好够我们解码)。类似于编码的过程，我们从区间0,1)开始，使用相同的概率模型，将它分成四个子区间。中性对应的区间是 0, 0.6) 阳性对应的区间是 0.6, 0.8) 阴性对应的区间是 0.8, 0.9) 数据结束符对应的

46、区间是 0.9, 1) 算术编码的译码第108页，共195页，2022年，5月20日，16点41分，星期一2022/9/1108分数0.538落在中性所在的子区间0,0.6)；这表明编码器所读的第一个符号必然是中性，这样就可以将它作为消息的第一个符号记下来。 算术编码的译码第109页，共195页，2022年，5月20日，16点41分，星期一2022/9/1109然后我们将区间0,0.6)再分成四个子区间：中性的区间是 0, 0.36) - 0, 0.6) 的 60% 阳性的区间是 0.36, 0.48) - 0, 0.6) 的 20% 阴性的区间是 0.48, 0.54) - 0, 0.6)

47、的 10% 数据结束符的区间是 0.54, 0.6). - 0, 0.6) 的 10% 分数0.538 在 0.48, 0.54) 区间；所以消息的第二个符号一定是阴性。 算术编码的译码第110页，共195页，2022年，5月20日，16点41分，星期一2022/9/1110再一次将当前区间划分成四个子区间：中性 的区间是 0.48, 0.516) 阳性 的区间是 0.516, 0.528) 阴性 的区间是 0.528, 0.534) 数据结束符的区间是 0.534, 0.540). 分数 0.538 落在符号数据结束符的区间；所以，这一定是下一个符号。由于它也是内部的结束符号，这也就意味着编

48、码已经结束。 算术编码的译码第111页，共195页，2022年，5月20日，16点41分，星期一2022/9/11113.4 最佳不等长编码算术编码的特点特点一 当L很大时，平均码长接近信源熵H(U)，因此编码效率接近上限。特点二 编译码简单，存储量小，速度快。算术编码的应用领域在图象数据压缩标准（如JPEG）中得到广泛应用。第112页，共195页，2022年，5月20日，16点41分，星期一2022/9/1112 1982 年， Rissanen 和 G. G. Langdon 一起改进了算术编码。之后，人们又将算术编码与 J. G. Cleary 和 I. H. Witten 于 1984

49、 年提出的部分匹配预测模型（ PPM ）相结合，开发出了压缩效果近乎完美的算法。今天，那些名为 PPMC 、 PPMD 或 PPMZ 并号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。 看起来，压缩技术的发展可以到此为止了。不幸的是，事情往往不像想象中的那样简单：算术编码虽然可以获得最短的编码长度，但其本身的复杂性也使得算术编码的任何具体实现在运行时都慢如蜗牛。即使在摩尔定律大行其道， CPU 速度日新月异的今天，算术编码程序的运行速度也很难满足日常应用的需求。如果不是后文将要提到的两个犹太人，我们还不知要到什么时候才能用上 WinZIP 这样方便实用的压缩工具呢。词典编码

50、方法第113页，共195页，2022年，5月20日，16点41分，星期一2022/9/1113逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进 Huffman 或算术编码，以获得一种兼顾了运行速度和压缩效果的“完美”编码的时候，两个聪明的犹太人 J. Ziv 和 A. Lempel 独辟蹊径，完全脱离 Huffman 及算术编码的设计思路，创造出了一系列比 Huffman 编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为 LZ 系列算法。 词典编码方法第114页，共195页，2022年，5月20日，16点41分，星期一2022/

51、9/1114说实话， LZ 系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是简单地延续了千百年来人们对字典的追崇和喜好，并用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。通俗地说，当你用字典中的页码和行号代替文章中每个单词的时候，你实际上已经掌握了 LZ 系列算法的真谛。这种基于字典模型的思路在表面上虽然和 Shannon 、 Huffman 等人开创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且，可以从理论上证明， LZ 系列算法在本质上仍然符合信息熵的基本规律。 词典编码方法第115页，共195页，2022年，5月20日，16点41分，

52、星期一2022/9/1115词典编码方法词典编码方法是基于数据中许多结构频繁重复再现这一事实, 人们可以对相同符号串分配同一码字、通过索引、或者其他诸如此类的方法编码。70 年代末提出、80 年代中期走向实用化的LZ 压缩技术开创了现代词典编码方法, 并且已经牢固地统治着通用压缩世界。LZ 的基本思想是: 数据中的子串可以通过用指代先前已处理数据(即历史数据) 中相同子串的方式来描述。对历史数据的存储方式可以不同,例如，LZ77 采用滑动的缓冲区(或称窗口) 记录, LZ78 则选择词典方式进行登录。应该指出的是, 两者的压缩效率没有显著差异, 而且都是当重复的子串越长压缩效率越高。 第116

53、页，共195页，2022年，5月20日，16点41分，星期一2022/9/1116按照时间顺序， LZ 系列算法的发展历程大致是： Ziv 和 Lempel 于 1977 年发表题为“顺序数据压缩的一个通用算法”的论文，论文中描述的算法被后人称为 LZ77 算法。 1978 年，二人又发表了该论文的续篇“通过可变比率编码的独立序列的压缩”，描述了后来被命名为 LZ78 的压缩算法。 1984 年， T. A. Welch 发表了名为“高性能数据压缩技术”的论文，描述了他在 Sperry 研究中心（该研究中心后来并入了 Unisys 公司）的研究成果，这是 LZ78 算法的一个变种，也就是后来非

54、常有名的 LZW 算法。 1990 年后， T. C. Bell 等人又陆续提出了许多 LZ 系列算法的变体或改进版本。 词典编码方法第117页，共195页，2022年，5月20日，16点41分，星期一2022/9/1117今天， LZ77 、 LZ78 、 LZW 算法以及它们的各种变体几乎垄断了整个通用数据压缩领域，我们熟悉的 PKZIP 、 WinZIP 、 WinRAR 、 gzip 等压缩工具以及 ZIP 、 GIF 、 PNG 等文件格式都是 LZ 系列算法的受益者，甚至连 PGP 这样的加密文件格式也选择了 LZ 系列算法作为其数据压缩的标准。 词典编码方法第118页，共195页

55、，2022年，5月20日，16点41分，星期一2022/9/1118LZ编码首先进行的操作称为“分段”。分段是从前往后分，每次取最短长度的连续符号构成段，并保证各段互不相同，具体步骤如下。先取一个符号分段，若与前面段相同，就再取一个符号，直至构成一个新段.如果到最后面分不出一段，则这个分不出段的事件串也算一段，是末尾段。设信源随机变量U的事件集为A=a1, a2, , aK。现要对信源序列L维随机变量UL=(U1U2UL)进行2元编码。事件u=(u1u2uL)。第119页，共195页，2022年，5月20日，16点41分，星期一2022/9/1119其次进行的操作是“事件编号”和“段编号”。事

56、件编号：首先将事件a1, a2, , aK分别标号为0, 1, , K-1，随后将这些编号写成长度相同二进制比特串，比特串的长度都是例如，a1, a2, a3, a4, a5, a6分别标号为000, 001, 010, 011, 100, 101。又例如， a1, a2, a3, a4, a5, a6 , a7, a8, a9分别标号为0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000。段编号：首先将所划分的各段按前后顺序分别标号为1, 2, , ，随后将这些编号写成二进制的比特串，长度为LZ编码第120页，共195页，2022年，5月2

57、0日，16点41分，星期一2022/9/1120最后进行的操作是“按段进行编码”，每个码字分为两个部分：段号（最后一个事件）事件编号 下面分三种情形为段赋予码字：情形一 段如果只有一个事件，则码字的段号为000（长度为段编号长度），码字后一部分就是这个事件的编号。情形二 非末尾段如果有不止一个事件，则该段去掉最后一个事件就是前面曾经出现过的旧段。 该段的码字的前一部分就是这个旧段的段编号，码字的后一部分就是最后一个事件的事件编号。情形三 末尾段如果既有不止一个事件，又是前面曾经出现过的旧段，则末尾段的码字就是该旧段的码字。LZ编码第121页，共195页，2022年，5月20日，16点41分，星

58、期一2022/9/1121 LZ编码的译码方法非常简单，因为码字的长度相等，不需要识别码字之间的分界点，只需要将码字翻译成段即可。一个码字如果前一部分为000，则该段只有一个事件，事件的编号就是码字的后一部分。一个码字如果不是最后一个码字，而且前一部分不为000，则该段应该是这样的：以码字前一部分作为段编号找到旧段，再以码字后一部分作为事件编号找到事件，“旧段+事件”就是该段。一个码字如果是最后一个码字，而且该码字在以前没有出现过，则译码规则为如上所述。一个码字如果是最后一个码字，而且该码字在以前出现过，则该末尾段值等同于相同码字的旧段。LZ编码第122页，共195页，2022年，5月20日，

59、16点41分，星期一2022/9/1122LZ编码的特点特点一 编码效率可以接近信息熵的上限。特点二 不需要事先知道信源的概率分布。特点三 用一种巧妙的方式使用字典技术。特点四 文件越小，压缩比例越小；文件越大，压缩比例越大。LZ编码第123页，共195页，2022年，5月20日，16点41分，星期一2022/9/1123例（p77）设信源随机变量U的事件集为A=a1, a2, a3, a4。设要对信源序列(a1a2a1a3a2a4a2a4a3a1a1a4)进行2元编码。“分段”： (a1，a2，a1a3，a2a4，a2a4a3，a1a1，a4)；“事件编号”依次为 a100， a201, a

60、310, a411；“段编号”依次为a1a2a1a3a2a4a2a4a3a1a1a4001010011100101110111LZ编码第124页，共195页，2022年，5月20日，16点41分，星期一2022/9/1124“按段进行编码”：a1a2a1a3a2a4a2a4a3a1a1a400000000010011001011100100010000011LZ编码第125页，共195页，2022年，5月20日，16点41分，星期一2022/9/1125译码过程比特串“按照码字长度为3+2=5来分割码字：00000，00001，00110，01011，10010，00100，00011码字00