信息论与编码理论基础第三章PPT讲稿.ppt

《信息论与编码理论基础第三章PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《信息论与编码理论基础第三章PPT讲稿.ppt（195页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码理论基础第三章2022/9/281第1页，共195页，编辑于2022年，星期五 信源发出的消息序列通常不能直接信源发出的消息序列通常不能直接送给信道传输，需要经过信源编码和信送给信道传输，需要经过信源编码和信道编码。道编码。2022/9/282第2页，共195页，编辑于2022年，星期五信道编码信道编码n在传输过程中噪声和干扰在所难免，为了在传输过程中噪声和干扰在所难免，为了降低差错率，提高降低差错率，提高传送的可靠性，传送的可靠性，在信道编码器中可以引入冗余度，在信道解在信道编码器中可以引入冗余度，在信道解码端就可以利用此冗余度来尽可能地重建输入序列。码端就可以利用此冗余度来尽可

2、能地重建输入序列。n可靠性：增加冗余可靠性：增加冗余2022/9/283第3页，共195页，编辑于2022年，星期五信源编码信源编码n对信源进行对信源进行压缩压缩、扰乱和加密，用最少的码字最安全地传输最大、扰乱和加密，用最少的码字最安全地传输最大的信息量：的信息量：n有效性有效性和安全性：去除冗余和安全性：去除冗余n如何对信源进行建模？（如随机过程）如何对信源进行建模？（如随机过程）n如何测量信源的内容？（熵）如何测量信源的内容？（熵）n如何表示一个信源？（编码：码字设计）如何表示一个信源？（编码：码字设计）2022/9/284第4页，共195页，编辑于2022年，星期五为什么需要信源编码/数

3、据压缩n数字化视频和音频等媒体信息的数据量很大数字音频格式频带范围（Hz）取样频率（kHz）样本精度（bit）声道数原始码率（Kb/s）电话300340088164调频（FM）广播201500022.03162705.6激光唱盘（CD）202000044.11621411.2数字视频格式每秒帧数图像分辨率（像素）样本精度（bit）亮度信号原始码率（Mb/s）CIF格式的亮度信号30352*288824.33HDTV亮度信号一例601920*10808995.32022/9/285第5页，共195页，编辑于2022年，星期五为什么需要信源编码/数据压缩n减少存储空间减少存储空间n文件压缩、图像压

4、缩、语音压缩、视频压缩文件压缩、图像压缩、语音压缩、视频压缩n减少传输时间减少传输时间2022/9/286第6页，共195页，编辑于2022年，星期五信源编码信源编码/数据压缩的数据压缩的例子：例子：摩尔斯式电码摩尔斯式电码n19世纪中叶，由 Samuel Morse发明n每个字符用“.”或“”表示n观察：一些字符比另外一些字符出现的频率更高，如“a,e”比“z,q”出现的频率高n因此，为了减少发送信息的平均时间，用较短的序列表示出现频率高的字符，较长的序列表示出现频率低的字符ne:.,a:.nq:-.-,j:.-2022/9/287第7页，共195页，编辑于2022年，星期五为什么可以进行为

5、什么可以进行信源编码信源编码/数据压缩数据压缩n自然界中的大多数数据都是冗余的：任何非随机选择的数据都有一定结构，可利用这种结构得到数据的更紧致表示n统计冗余：大多数常见的压缩算法都是利用该冗余n字母冗余：英文中字母E最常出现，而Z很少出现n文本冗余：字母Q后常跟有字母U2022/9/288第8页，共195页，编辑于2022年，星期五例：空间冗余n图像中存在大面积部分相似或完全一样的像素图像中存在大面积部分相似或完全一样的像素pmf2022/9/289第9页，共195页，编辑于2022年，星期五例：时间冗余n视频图像前后几帧的内容变化不大（位置可能不同，视频图像前后几帧的内容变化不大（位置可能

6、不同，可用运动估计方法找到对应位置）可用运动估计方法找到对应位置）2022/9/2810第10页，共195页，编辑于2022年，星期五例：结构冗余n图像中物体表面纹理等结构存在冗余图像中物体表面纹理等结构存在冗余2022/9/2811第11页，共195页，编辑于2022年，星期五怎样进行信源编码信源编码n无失真编码无失真编码:若若要求将信源输出在接收端精确地重现出来，即保证信源输出所携带的信息全部无损地传达给信宿，就要对信源进行无失真编码。n无失真编码只是对信源冗余度进行压缩，并不改变信源熵，它能保证信源序列经无扰信道传输后，得到无失真的恢复。n限定失真编码限定失真编码：在实际传信中，要精确的

7、复制出信源的输出是不可能的，根据信源信宿对定出的可接收准则或保真度准则，计算要保留多少有关信源输出的信息量，以及如何表示它们，这就是限定失真的信源编码问题。2022/9/2812第12页，共195页，编辑于2022年，星期五第三章：第三章：信源编码（一）离散信源无失真编码3.1 信源及其分类信源及其分类3.2 离散无记忆（简单）信源的等长编码离散无记忆（简单）信源的等长编码3.3 离散无记忆（简单）信源的不等长编离散无记忆（简单）信源的不等长编码码3.4 最佳不等长编码最佳不等长编码2022/9/2813第13页，共195页，编辑于2022年，星期五3.1 信源及其分类信源及其分类信源的概念信

8、源的概念:信源就是信息的来源。注意注意：n在一个固定的时刻，信源发出的是一个随机变在一个固定的时刻，信源发出的是一个随机变量量。n随着时间的延续，信源发出一个又一个随机变量，随着时间的延续，信源发出一个又一个随机变量，称之为一个随机过程。称之为一个随机过程。因此，可以用概率空间来描述信源。因此，可以用概率空间来描述信源。2022/9/2814第14页，共195页，编辑于2022年，星期五3.1 信源及其分类信源及其分类离散信源离散信源 信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列U-2U-1U0U1U2，其中 Uk为第k个时间段发出的随机变量；每个Uk都是

9、一个离散型的随机变量。离散无记忆信源离散无记忆信源 随机变量、U-2、U-1、U0、U1、U2、相互独立的离散信源。离散无记忆离散无记忆 随机变量、U-2、U-1、U0、U1、U2、简单信源简单信源 具有相同的概率分布的离散无记忆信源。2022/9/2815第15页，共195页，编辑于2022年，星期五3.1 信源及其分类信源及其分类（总结：离散无记忆简单信源离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。课程学习所面对的信源将主要是离散无记忆简单信源）一般的信源一般的信源 连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；

10、有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的 概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。2022/9/2816第16页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码（1）设有一个离散无记忆简单信源离散无记忆简单信源，信源发出的随机变量序列为：U-2U-1U0U1U2。设信源随机变量U1的事件有K个：a1,a2,aK，则L维信源随机向量(U1U2UL)的事件有KL个：(u1u2uL)|其中每个分量ul跑遍a1,a2,aK。P(U1U2UL)=(u1u2uL)=P(U

11、1=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)，都用一个字母串(c1c2)来表示。2022/9/2817第17页，共195页，编辑于2022年，星期五码长：码字所含码元的个数 等长编码：所有码字均有相同的码长N，对应的码 叫做等长码(FLC，Fixed Length code)；否则为变长编码。编码器码字码字:每一个事件每一个事件(u1u2uL)所对应的字母串所对应的字母串(c1c2)。编码器模型：D个字母的字母表A信源

12、2022/9/2818第18页，共195页，编辑于2022年，星期五n熵是随机变量平均不确定性的一个测度，表示了描述这个随机变量所需要的平均比特数2022/9/2819第19页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码例例：离散无记忆简单信源发出的随机变量序列为：U-2U-1U0U1U2。其中U1的事件有3个：晴,云,阴。(U1U2)有9个事件 （晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云），（阴阴）。用字母表0,1对(U1U2)的事件进行2元编码如下：（晴晴）0000，（晴云）0001，（晴阴

13、）0011，（云晴）0100，（云云）0101，（云阴）0111，（阴晴）1100，（阴云）1101，（阴阴）1111。2022/9/2820第20页，共195页，编辑于2022年，星期五n无错编码无错编码（唯一可译码）(U1U2UL)的不同事件用不同的码字来表示。n能够实现无错编码的充要条件是DNKL。（即NlogD/LlogK）n这里nN/L表示每个信源符号所需要的码符号数；logD是一个码符号所能载荷的最大信息量；nN/LlogK/logD说明对于等长唯一可译码平均每个信源符号至少需要logK/logD个码符号对其进行编码变换；n（NlogD）/L是编码后平均每个信源符号所能载荷的信息量

14、的最大值，称为编码速率，记为R.n 关于编码速率的说明：由编码速率的计算公式R=NlogD/L，似乎可以任意设置N和L，进而可以任意设置编码速率。事实上存在着编码设备的性能指标：编码速率R0。这就是说，选择N和L，必须使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0。n有错编码有错编码 (U1U2UL)的有些不同事件用相同的码字来表示。编码是一种由消息集到码字集的映射2022/9/2821第21页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码n无错编码的最低代价无错编码的最低代价n当R=(NlogD)/LlogK时，

15、能够实现无错编码。（DNKL）n当RH(U1)时，无论怎样编码都是有错编码。这是因为RH(U1)logK。（DNRH(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码2022/9/2823第23页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码n我们以英文电报为例，由于英文字母之间有很强的关联性，n当用字母组合成不同的英文字母序列时，并不是所有的字母组合都是有意义的单词，n若再把单词组合成更长

16、的字母序列时，也不是任意的单词组合都是有意义的句子，n因此，在足够长的英文字母序列中，就有许多无用和无意义的序列，这些信源序列出现的概率等于零或任意小，那么在编码时，对于那些无用的字母组合，无意义的句子都可以不编码，从而提高传输效率，但同时，会引入一定的误差，但是当L足够大时，这种误差概率就可以任意小，可做到几乎无失真编码。2022/9/2824第24页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码n渐进无错编码渐进无错编码 （简单地说就是：当RH(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：）设给定

17、了编码设备的编码速率设给定了编码设备的编码速率R0，R0H(U1)。则。则对任意的对任意的0，总存在一个，总存在一个L0，使得对任意的，使得对任意的LL0，都，都有对有对(U1U2UL)的等长编码和对应的译码方法，满足的等长编码和对应的译码方法，满足n实际的编码速率实际的编码速率R=NlogD/LR0，n译码错误的概率译码错误的概率pe。2022/9/2825第25页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码不能渐进无错的编码不能渐进无错的编码 （简单地说就是：当RH(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意

18、小。严格地说就是：）设给定了编码设备的编码速率设给定了编码设备的编码速率R0，R00有PH(U1)-ILH(U1)+2022/9/2828第28页，共195页，编辑于2022年，星期五切比雪夫不等式切比雪夫不等式注：注：切比雪夫切比雪夫2022/9/2829第29页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码取定L0使得 ，则当LL0时总有因此当LL0时总有这样的一些事件序列，H(U1)-ILH(U1)+，而且PH(U1)-ILH(U1)+1-。n说明当L足够大时，信源序列的自信息量的均值以概率1收敛于信源熵。n当L足够大时，在

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

20、/9/2831第31页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码（简记H(U)=H(U1)。设以下的对数都是以2为底的。）系系3.2.1(特定典型序列出现的概率，p58)若一个特定的事件(u1u2uL)TU(L,)，则2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。证明 设(u1u2uL)TU(L,)。注意到此时H(U)-ILH(U)+，2022/9/2832第32页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码所以2022/9/28

21、33第33页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码系系3.2.2(典型序列的数量，p58)(1-)2L(H(U)-)|TU(L,)|2L(H(U)+)。证明 一方面，2022/9/2834第34页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码另一方面，2022/9/2835第35页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码 P(U1U2UL)=(u1u2uL)|(u1u2uL)TU(L,)1-

22、。系系3.2.1(特定典型序列出现的概率)2-L(H(U)+)P(U1U2UL)=(u1u2uL)2-L(H(U)-)。系系3.2.2(典型序列的数量)(1-)2L(H(U)-)|TU(L,)|2L(H(U)+)。2022/9/2836第36页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源的等离散无记忆（简单）信源的等长编码长编码典型序列集典型序列集非典型序列集非典型序列集序列集合序列集合定理3.2.1，系3.2.1以及系3.2.2就说明：n所有典型序列的概率和接近于1，是高概率集；n典型序列集中各序列出现的概率近似相等；n每个典型序列中一个信源符号的平均信息量接近于信源

23、熵；当L达到无限时，才等于信源熵。2022/9/2837第37页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码补充引理补充引理 设给定一个R0H(U)。对每个正整数L，对应地取整数N=R0L（R0L的下取整）。则0R0L-N1 即 0R0-N/LL0时nN/LR0-R0-(R0-H(U)/2=H(U)+(R0-H(U)/2H(U)+。nP(U1U2UL)TU(L,)1-。（由定理3.2.1）2022/9/2838第38页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码定

24、理定理3.2.2(无错编码正定理，无错编码正定理，p60)给定编码设备的编码速率给定编码设备的编码速率R0，R0H(U)。则对任意的则对任意的0，总存在一个，总存在一个L0，使得对任意的，使得对任意的LL0，都有对，都有对(U1U2UL)的的2元等长编码方法和元等长编码方法和对应的译码方法，对应的译码方法，实际的编码速率实际的编码速率R满足满足R0RH(U)，“译码错误译码错误”的概率的概率peH(U)；“译码错误”的概率pe=P(U1U2UL)不属于TU(L,)=1-P(U1U2UL)TU(L,)。得证。定理定理3.2.2(无错编码反定理，p60)设给定编码设备的编码速率R0，满足R0H(U

25、)；给定一个任意小的正数0；要求：选择合适的L，N，对(U1U2UL)进行合适的2元N长编码，使得实际的编码速率R=N/L满足RR0；“译码错误”的概率pe。2022/9/2842第42页，共195页，编辑于2022年，星期五渐进无错编码的步骤渐进无错编码的步骤由U1的概率分布计算取L满足 。取整数N=R0L（R0L下取整）。取典型序列集2022/9/2843第43页，共195页，编辑于2022年，星期五渐进无错编码的步骤渐进无错编码的步骤将TU(L,)中的事件用不同的N长2元码字来表示，而将TU(L,)以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L,)

26、中的某个事件。译码时，所有的码字均译为它所表示的TU(L,)中的事件。（注解：显然满足RR0；|TU(L,)|2N，因此码字足够用；译码错误的概率为pe=P(U1U2UL)=(u1u2uL)|(u1u2uL)不属于TU(L,)0.037587148=H(U1)。希望：2元编码的实际编码速率RR0；译码错误的概率不超过。其中取=0.1。找L使得2022/9/2846第46页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码取L=253即可。再取N=R0L=126。将TU(L,)中的事件用不同的N长2元码字来表示，而将TU(L,)以外的事

27、件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L,)中的某个事件。译码时，所有的码字均译为它所表示的TU(L,)中的事件。另一方面，TU(L,)中的事件有更加简单的表达方式。当事件(u1u2uL)中a1的个数为k，a2的个数为L-k时，2022/9/2847第47页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码事件(u1u2uL)属于典型序列集TU(L,0.1)；当且仅当2022/9/2848第48页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的

28、等长编码当事件(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)的个数为2022/9/2849第49页，共195页，编辑于2022年，星期五3.2 离散无记忆（简单）信源离散无记忆（简单）信源的等长编码的等长编码对L=253，对应地取整数N=R0L=126。则N/LR0，这就是说2元编码的实际编码速率并未超出编码设备的编码速率。n2元编码的编码方法：元编码的编码方法：将TU(253,0.1)中的事件用

29、不同的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之外的其它事件的码字保持不变，因而它们对平均码长的贡献不变，而n码S 中事件a和b的码字对平均码长的贡献为qana+qbnb；n码T中事件a和b的码字对平均码长的贡献为qanb+qbna。n(qana+qbnb)-(qanb+q

30、bna)=(qa-qb)(na-nb)0。这就是说，码S 的平均码长码T 的平均码长。因而码S 不是最佳2元异字头码。用反证法已经证明了补充引理2。2022/9/2876第76页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码补充引理补充引理3 设信源随机变量U的最佳最佳2元异字头码元异字头码S，则最长的码字至最长的码字至少有两个少有两个。证明 如果2元异字头码S 的最长的码字竟然只有一个。设这个码字为c，是事件a的码字。现在将c的最后一位去掉，成为c，将c仍然作为事件a的码字。其它事件的码字保持不变。此时2元异字头码S 变成新的2元码T。注意到以下两点：n码T仍然是

31、2元异字头码；n码S 的平均码长码T 的平均码长。因而码S 不是最佳2元异字头码。用反证法已经证明了补充引理3。2022/9/2877第77页，共195页，编辑于2022年，星期五aa2022/9/2878第78页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码补充引理补充引理4 最佳最佳2元异字头码元异字头码S可以满足以下两条：（1）概率最小的两个事件码字最长，且长度相等；）概率最小的两个事件码字最长，且长度相等；（2）它们的码字仅仅最后一位不同。）它们的码字仅仅最后一位不同。证明证明 取概率最小的事件a。在剩下的事件中取概率最小的事件b。根据补充引理2和补充引理3

32、，事件a和事件b的码字最长，且长度相等。这就是说，最佳2元异字头码S显然满足第（1）条。关于第（2）条，分以下三种情形来讨论：2022/9/2879第79页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码情形一事件a和事件b的码字仅仅最后一位不同。此时：最佳2元异字头码S 满足第（2）条。补充引理4得证。情形二事件a和事件b的码字不是仅仅最后一位不同，但有第三个事件c，其码字与事件a的码字仅仅最后一位不同。此时：将事件b与事件c交换码字，得到新的2元异字头码T。码T与码S平均码长相同，因此码T也是最佳2元异字头码，且码T满足第（1）条和第（2）条。情形三事件a和事件b

33、的码字不是仅仅最后一位不同，也没有第三个事件c，其码字与事件a的码字仅仅最后一位不同。此时：将事件b的码字换为与事件a的码字仅仅最后一位不同，得到新的码T。码T 也是2元异字头码。码T与码S平均码长相同，因此码T也是最佳2元异字头码，且码T满足第（1）条和第（2）条。2022/9/2880第80页，共195页，编辑于2022年，星期五abacb3.4 最佳不等长编码最佳不等长编码abcabab2022/9/2881第81页，共195页，编辑于2022年，星期五Huffman编码的最佳性编码的最佳性n定理定理3.4.1：对于给定信源，存在有最佳惟一：对于给定信源，存在有最佳惟一可译二元码，其最小

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

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

36、2/9/2884第84页，共195页，编辑于2022年，星期五n设原始信源设原始信源随机变量随机变量n新的信源随机变量新的信源随机变量3.4 最佳不等长编码最佳不等长编码2022/9/2885第85页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码n若若C1，C2，CK-1是信源是信源U 的最佳码，相应的最佳码，相应码长为码长为n1，n2，nK-1，则对信源，则对信源U的码字的码字C1，C2,CK的码长为的码长为nnk=nk kK2nnk=nK-1+1 k=K,K1n同时两信源各事件出现的概率满足关系式：同时两信源各事件出现的概率满足关系式：npk=pk kK2npK

37、+pK-1=pK-12022/9/2886第86页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码 2022/9/2887第87页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码补充定理给出了一种构造信源随机变量U的最佳2元异字头码的方法：取出两个概率最小的事件a和事件b，分别标号为0和1；然后将事件a和事件b合并成事件e，因此将信源随机变量U合并成U；寻找U的最佳2元异字头码；然后将该码中事件e的码字后面分别添加事件a和事件b的标号（0和1），分别成为事件a和事件b的码字。这种构造方法正是2元Huffman编码。换句话说，定理定理 对信源随

38、机变量对信源随机变量U的的2元元Huffman编码是最佳编码是最佳2元异字头码，因而是元异字头码，因而是在唯一可译前提下的最佳在唯一可译前提下的最佳2元不等长编码。元不等长编码。2022/9/2888第88页，共195页，编辑于2022年，星期五3.4 最佳不等长编码最佳不等长编码2元元Huffman编码法（字母表编码法（字母表0,1）（1）将概率最小的2个事件分别赋予标号“0”和“1”。（2）将这2个事件合并为一个事件，其概率为2个事件概率之和。重复（1）-（2），直到合并为所剩的事件为2个。将这2事件分别赋予标号“0”和“1”。编码完毕。此时，一个事件的码字是这个事件从最后标号开始到最先标

39、号为止的标号序列。2022/9/2889第89页，共195页，编辑于2022年，星期五例：例：HuffmanHuffman编码过程编码过程2022/9/2890第90页，共195页，编辑于2022年，星期五例：例：HuffmanHuffman编码过程编码过程2022/9/2891第91页，共195页，编辑于2022年，星期五P59 Shannon-Fano编码例子编码例子采采用用Huffman编码编码a 16b 7c 6d 6e 511132401010101a 0b 100c 101d 110e 111总比特数总比特数88，信源熵为，信源熵为86.601bit2022/9/2892第92页，

40、共195页，编辑于2022年，星期五HuffmanHuffman编码编码nShannon-FanoShannon-Fano编码构造二叉树是自树根编码构造二叉树是自树根到树叶，很难保证最佳性。到树叶，很难保证最佳性。nHuffmanHuffman编码则是从树叶到树根，是最佳编码则是从树叶到树根，是最佳的的2022/9/2893第93页，共195页，编辑于2022年，星期五总结总结nHuffmanHuffman需要知道信源的概率分布，这在需要知道信源的概率分布，这在实际中有时是比较困难的。实际中有时是比较困难的。n采用半静态模型、自适应模型、采用半静态模型、自适应模型、markovmarkov模型

41、，部分匹配预测模型等等解决这一模型，部分匹配预测模型等等解决这一问题。问题。2022/9/2894第94页，共195页，编辑于2022年，星期五D元元Huffman编码编码nD元码全数的端节点数为元码全数的端节点数为D+m(D-1)n由由Huffman编码的最佳性知空缺的端节点应当是码长最编码的最佳性知空缺的端节点应当是码长最长的端节点长的端节点n共有共有K个符号，设第一次需要合并的消息个数为个符号，设第一次需要合并的消息个数为R，空缺空缺数为数为BB B个个R个个2022/9/2895第95页，共195页，编辑于2022年，星期五D元元Huffman编码编码 K+B=D+m(D-1)，因而，

42、因而K-2=m(D-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 B个个R个个2022/9/2896第96页，共195页，编辑于2022年，星期五nHuffman 编码效率高，运算速度快，实现方式灵活，从 20 世纪 60 年代至今，在数据压缩领域得到了广泛的应用。今天，在许多知名的压缩工具和压缩算法（如 WinRAR、gzip 和 JPEG）里，都有 Huffman 编码的身影。n不过，Huffman 编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵

43、的极限。正因为如此，现代压缩技术通常只将 Huffman 作为最终的编码手段，而非数据压缩算法的全部。n同时科学家们一直没有放弃向信息熵极限挑战的理想。1968 年前后，P.Elias 发展了 Shannon 和 Fano 的编码方法，构造出从数学角度看来更为完美的 Shannon-Fano-Elias 编码。沿着这一编码方法的思路，1976 年，J.Rissanen 提出了一种可以成功地逼近信息熵极限的编码方法算术编码。算术编码算术编码2022/9/2897第97页，共195页，编辑于2022年，星期五算术编码算术编码n nShannon-FanoShannon-Fano编码，编码，编码，编

44、码，Huffman编码的编码的编码方法：n首先对信源的各事件进行编码，n然后再对输入的消息序列进行编码变换。n算术编码算术编码：n首先假设一个信源的概率模型,n随后直接把整个输入的消息编码为一个(0.0 n 1.0)内的小区间，在编码的过程中，消息序列集中的每个元素都用来缩短这个区间，消息序列集中的元素越多,所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间，这就是区间作为代码的原理。2022/9/2898第98页，共195页，编辑于2022年，星期五n使用算术编码的压缩算法通常先要对信源符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。n例例:对一个简单

45、的信号源进行观察，得到的统计模型如下：n60%的机会出现符号 中性 n20%的机会出现符号 阳性 n10%的机会出现符号 阴性 n10%的机会出现符号 数据结束符.算术编码算术编码2022/9/2899第99页，共195页，编辑于2022年，星期五在得到信源随机变量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)。随后，编码过程的每一步，除了最后一步，都是相同的。算术编码算术编码2022/9/

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

47、:n中性对应的区间是 0,0.6)n阳性对应的区间是 0.6,0.8)n阴性对应的区间是 0.8,0.9)n数据结束符对应的区间是 0.9,1)n当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和模型参数即可以解码重建得到该符号序列。算术编码算术编码2022/9/28102第102页，共195页，编辑于2022年，星期五算术码算术码n再以二元信源输出序列再以二元信源输出序列01110的编码为例的编码为例P(0)P(1)F(0)F(1)01算术编码算术编码2022/9/28103第103页，共195页，编辑于2022年，星期五算术码算术码P(00)P(0

48、1)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算术编码算术编码2022/9/28104第104页，共195页，编辑于2022年，星期五算术码算术码n信源符号序列信源符号序列u对应区间的宽度等于符号序列对应区间的宽度等于符号序列的概率的概率n信源符号序列信源符号序列u对应区间的左端点为对应区间的左端点为算术编码算术编码2022/9/28105第105页，共195页，编辑于2022年，星期五nF(u)将将0,1)分割成许多小区间，以小区间的左端点数值分割成许多小区间，以小区间的左端点数值的

49、二进制小数表示该序列，同时要的二进制小数表示该序列，同时要将该小数的小数位数截将该小数的小数位数截断为断为l位，截断规则为：位，截断规则为：l位后面只要有非位后面只要有非0的余数就要向第的余数就要向第l位进位。位进位。最后得到了小数最后得到了小数0.t。将。将t作为事件作为事件u=(u1u2uL)的码字的码字。码字码字长度长度l为为算术编码算术编码2022/9/28106第106页，共195页，编辑于2022年，星期五算术编码算术编码则则即即因而因而即即2022/9/28107第107页，共195页，编辑于2022年，星期五n例例:下面对使用前面提到的4符号模型进行编码的一段信息进行解码。编码

50、的结果是0.538(为了容易理解，这里使用十进制而不是二进制；我们也假设得到的结果的位数恰好够我们解码)。n类似于编码的过程，我们从区间0,1)开始，使用相同的概率模型，将它分成四个子区间。n中性对应的区间是 0,0.6)n阳性对应的区间是 0.6,0.8)n阴性对应的区间是 0.8,0.9)n数据结束符对应的区间是 0.9,1)算术编码的译码算术编码的译码2022/9/28108第108页，共195页，编辑于2022年，星期五n分数0.538落在中性所在的子区间0,0.6)；这表明编码器所读的第一个符号第一个符号必然是中性中性，这样就可以将它作为消息的第一个符号记下来。算术编码的译码算术编码