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

信息论与编码理论基础第三章2023/7/301第1页，课件共195页，创作于2023年2月

信源发出的消息序列通常不能直接送给信道传输，需要经过信源编码和信道编码。

2023/7/302第2页，课件共195页，创作于2023年2月信道编码在传输过程中噪声和干扰在所难免，为了降低差错率，提高传送的可靠性，在信道编码器中可以引入冗余度，在信道解码端就可以利用此冗余度来尽可能地重建输入序列。可靠性：增加冗余2023/7/303第3页，课件共195页，创作于2023年2月信源编码对信源进行压缩、扰乱和加密，用最少的码字最安全地传输最大的信息量：有效性和安全性：去除冗余如何对信源进行建模？（如随机过程）如何测量信源的内容？（熵）如何表示一个信源？（编码：码字设计）2023/7/304第4页，课件共195页，创作于2023年2月为什么需要信源编码/数据压缩数字化视频和音频等媒体信息的数据量很大数字音频格式频带范围（Hz）取样频率（kHz）样本精度（bit）声道数原始码率（Kb/s）电话300~340088164调频（FM）广播20~1500022.03162705.6激光唱盘（CD）20~2000044.11621411.2数字视频格式每秒帧数图像分辨率（像素）样本精度（bit）亮度信号原始码率（Mb/s）CIF格式的亮度信号30352*288824.33HDTV亮度信号一例601920*10808995.32023/7/305第5页，课件共195页，创作于2023年2月为什么需要信源编码/数据压缩减少存储空间文件压缩、图像压缩、语音压缩、视频压缩…减少传输时间2023/7/306第6页，课件共195页，创作于2023年2月信源编码/数据压缩的例子：

摩尔斯式电码19世纪中叶，由SamuelMorse发明每个字符用“.”或“–”表示观察：一些字符比另外一些字符出现的频率更高，如“a,e”比“z,q”出现的频率高因此，为了减少发送信息的平均时间，用较短的序列表示出现频率高的字符，较长的序列表示出现频率低的字符e:.,a:.–q:--.-,j:.---2023/7/307第7页，课件共195页，创作于2023年2月为什么可以进行信源编码/数据压缩自然界中的大多数数据都是冗余的：任何非随机选择的数据都有一定结构，可利用这种结构得到数据的更紧致表示统计冗余：大多数常见的压缩算法都是利用该冗余字母冗余：英文中字母E最常出现，而Z很少出现文本冗余：字母Q后常跟有字母U2023/7/308第8页，课件共195页，创作于2023年2月例：空间冗余图像中存在大面积部分相似或完全一样的像素pmf2023/7/309第9页，课件共195页，创作于2023年2月例：时间冗余视频图像前后几帧的内容变化不大（位置可能不同，可用运动估计方法找到对应位置）2023/7/3010第10页，课件共195页，创作于2023年2月例：结构冗余图像中物体表面纹理等结构存在冗余2023/7/3011第11页，课件共195页，创作于2023年2月怎样进行信源编码无失真编码:若要求将信源输出在接收端精确地重现出来，即保证信源输出所携带的信息全部无损地传达给信宿，就要对信源进行无失真编码。无失真编码只是对信源冗余度进行压缩，并不改变信源熵，它能保证信源序列经无扰信道传输后，得到无失真的恢复。限定失真编码：在实际传信中，要精确的复制出信源的输出是不可能的，根据信源－信宿对定出的可接收准则或保真度准则，计算要保留多少有关信源输出的信息量，以及如何表示它们，这就是限定失真的信源编码问题。2023/7/3012第12页，课件共195页，创作于2023年2月第三章：信源编码（一）

离散信源无失真编码§3.1信源及其分类§3.2离散无记忆（简单）信源的等长编码§3.3离散无记忆（简单）信源的不等长编码§3.4最佳不等长编码2023/7/3013第13页，课件共195页，创作于2023年2月§3.1信源及其分类信源的概念

:信源就是信息的来源。注意：在一个固定的时刻，信源发出的是一个随机变量。随着时间的延续，信源发出一个又一个随机变量，称之为一个随机过程。

因此，可以用概率空间来描述信源。

2023/7/3014第14页，课件共195页，创作于2023年2月§3.1信源及其分类离散信源信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列…U-2U-1U0U1U2…，

其中

Uk为第k个时间段发出的随机变量；每个Uk都是一个离散型的随机变量。离散无记忆信源随机变量…、U-2、U-1、U0、U1、U2、…相互独立的离散信源。离散无记忆随机变量…、U-2、U-1、U0、U1、U2、…简单信源具有相同的概率分布的离散无记忆信源。2023/7/3015第15页，课件共195页，创作于2023年2月§3.1信源及其分类（总结：离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。课程学习所面对的信源将主要是离散无记忆简单信源）一般的信源

连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。2023/7/3016第16页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码（1）设有一个离散无记忆简单信源，信源发出的随机变量序列为：…U-2U-1U0U1U2…。设信源随机变量U1的事件有K个：{a1,a2,…,aK}，则L维信源随机向量(U1U2…UL)的事件有KL个：{(u1u2…uL)|其中每个分量ul跑遍{a1,a2,…,aK}}。P((U1U2…UL)=(u1u2…uL))=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个字母的字母表，对于(U1U2…UL)的每一个事件(u1u2…uL)，都用一个字母串(c1c2…)来表示。

2023/7/3017第17页，课件共195页，创作于2023年2月码长：码字所含码元的个数等长编码：所有码字均有相同的码长N，对应的码叫做等长码(FLC，FixedLengthcode)；否则为变长编码。编码器码字:每一个事件(u1u2…uL)所对应的字母串(c1c2…)。

编码器模型：D个字母的字母表A信源2023/7/3018第18页，课件共195页，创作于2023年2月熵是随机变量平均不确定性的一个测度，表示了描述这个随机变量所需要的平均比特数2023/7/3019第19页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码例：离散无记忆简单信源发出的随机变量序列为：…U-2U-1U0U1U2…。其中U1的事件有3个：{晴,云,阴}。(U1U2)有9个事件

{（晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云），（阴阴）}。用字母表{0,1}对(U1U2)的事件进行2元编码如下：（晴晴）→0000，（晴云）→0001，（晴阴）→0011，（云晴）→0100，（云云）→0101，（云阴）→0111，（阴晴）→1100，（阴云）→1101，（阴阴）→1111。2023/7/3020第20页，课件共195页，创作于2023年2月无错编码（唯一可译码）(U1U2…UL)的不同事件用不同的码字来表示。能够实现无错编码的充要条件是DN≥KL。（即NlogD/L≥logK）这里N/L表示每个信源符号所需要的码符号数；logD是一个码符号所能载荷的最大信息量；N/L≥logK/logD说明对于等长唯一可译码平均每个信源符号至少需要logK/logD个码符号对其进行编码变换；（NlogD）/L是编码后平均每个信源符号所能载荷的信息量的最大值，称为编码速率，记为R.

关于编码速率的说明：由编码速率的计算公式R=NlogD/L，似乎可以任意设置N和L，进而可以任意设置编码速率。事实上存在着编码设备的性能指标：编码速率R0。这就是说，选择N和L，必须使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0

。有错编码

(U1U2…UL)的有些不同事件用相同的码字来表示。编码是一种由消息集到码字集的映射2023/7/3021第21页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码无错编码的最低代价当R=(NlogD)/L≥logK时，能够实现无错编码。（DN≥KL）当R<H(U1)时，无论怎样编码都是有错编码。这是因为R<H(U1)≤logK。（DN<KL）注意：有错编码的译码方法与“译码错误”概率当使用有错编码时，必须给出译码方法（即：一个码字可能表示几个不同的事件，究竟翻译成哪个事件）。“译码错误”的概率定义为

pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的码字在译码时并不译为自身}。2023/7/3022第22页，课件共195页，创作于2023年2月上述分析时，我们完全没有考虑信源的统计特性，（也就是信源符号出现的概率以及信源符号之间的依赖关系，即信源的冗余度）而是认为信源符号独立等概；若注意每个信源信源符号包含的平均信息量为H(U)，编码时若D个符号独立等概，则每个码元符号所能载荷的信息量最大，码长最短，所以理论上最小码长N只要满足(NlogD)/L≥H(U)就可以实现无信息损失，即当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。§3.2离散无记忆（简单）信源的等长编码2023/7/3023第23页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码我们以英文电报为例，由于英文字母之间有很强的关联性，当用字母组合成不同的英文字母序列时，并不是所有的字母组合都是有意义的单词，若再把单词组合成更长的字母序列时，也不是任意的单词组合都是有意义的句子，因此，在足够长的英文字母序列中，就有许多无用和无意义的序列，这些信源序列出现的概率等于零或任意小，那么在编码时，对于那些无用的字母组合，无意义的句子都可以不编码，从而提高传输效率，但同时，会引入一定的误差，但是当L足够大时，这种误差概率就可以任意小，可做到几乎无失真编码。2023/7/3024第24页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码渐进无错编码（简单地说就是：当R>H(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：）设给定了编码设备的编码速率R0，R0>H(U1)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的等长编码和对应的译码方法，满足实际的编码速率R=NlogD/L≤R0，译码错误的概率pe<ε。2023/7/3025第25页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码不能渐进无错的编码（简单地说就是：当R<H(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是：）

设给定了编码设备的编码速率R0，R0<H(U1)。则无论怎样编码和译码都不能同时满足实际的编码速率R≤R0，译码错误的概率pe任意小。2023/7/3026第26页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码----典型序列设…U-2U-1U0U1U2…是离散无记忆（简单）信源的输出随机变量序列。设U1的概率分布为。。。。取Vl是Ul的如下函数：当Ul=ak时，Vl=loga(1/qk)。则随机变量序列…V-2V-1V0V1V2…相互独立，具有相同的概率分布：

2023/7/3027第27页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码取IL是(V1V2…VL)的如下函数：则①IL最终是(U1U2…UL)的函数；②③因此有切比雪夫不等式：对任意ε>0有P{H(U1)-ε≤IL≤H(U1)+ε}≥2023/7/3028第28页，课件共195页，创作于2023年2月切比雪夫不等式注：切比雪夫2023/7/3029第29页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码取定L0使得，则当L≥L0时总有因此当L≥L0时总有这样的一些事件序列，

H(U1)-ε≤IL≤H(U1)+ε，而且P{H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。说明当L足够大时，信源序列的自信息量的均值以概率1收敛于信源熵。当L足够大时，在信源序列中必有一些消息序列其自信息量的均值与信源熵之差小于ε，而对另外一些信源序列其差≥ε

，因此，可以把信源序列分成两个互补的子集。2023/7/3030第30页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码定义3.2.1(p57)定义TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，称TU(L,ε)为ε-典型序列集。称TU(L,ε)的补集为非ε-典型序列集。

（综上所述有）定理3.2.1(信源划分定理，p58)对任意ε>0，取L0使得则当L≥L0时总有P{(U1U2…UL))=(u1u2…uL)|(u1u2…uL)∈TU(L,ε)}≥1-ε。2023/7/3031第31页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码（简记H(U)=H(U1)。设以下的对数都是以2为底的。）系3.2.1(特定典型序列出现的概率，p58)若一个特定的事件(u1u2…uL)∈TU(L,ε)，则2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。证明设(u1u2…uL)∈TU(L,ε)。注意到此时H(U)-ε≤IL≤H(U)+ε，2023/7/3032第32页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码所以2023/7/3033第33页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码系3.2.2(典型序列的数量，p58)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。证明一方面，2023/7/3034第34页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码另一方面，2023/7/3035第35页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码P{(U1U2…UL))=(u1u2…uL)|(u1u2…uL)∈TU(L,ε)}≥1-ε。系3.2.1(特定典型序列出现的概率)2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。系3.2.2(典型序列的数量)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。2023/7/3036第36页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码典型序列集非典型序列集序列集合定理3.2.1，系3.2.1以及系3.2.2就说明：所有典型序列的概率和接近于1，是高概率集；典型序列集中各序列出现的概率近似相等；每个典型序列中一个信源符号的平均信息量接近于信源熵；当L达到无限时，才等于信源熵。2023/7/3037第37页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码补充引理设给定一个R0>H(U)。对每个正整数L，对应地取整数N=[R0L]（R0L的下取整）。则0≤R0L-N<1即0≤R0-N/L<1/L，故N/L≤R0，limL→+∞N/L=R0。任取正数ε≤(R0-H(U))/2，存在正整数L0，当L>L0时N/L≥R0-ε＝R0-(R0-H(U))/2=H(U)+(R0-H(U))/2≥H(U)+ε。P{(U1U2…UL)∈TU(L,ε)}≥1-ε。（由定理3.2.1）2023/7/3038第38页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码定理3.2.2(无错编码正定理，p60)

给定编码设备的编码速率R0，R0>H(U)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的2元等长编码方法和对应的译码方法，①实际的编码速率R满足R0≥R>H(U)，②“译码错误”的概率pe<ε。2023/7/3039第39页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码证明首先声明，所有的对数计算都是以2为底的。此时实际的编码速率为R=N/L。任取正数ε≤(R0-H(U))/2，取补充引理所描述的L0，则

|TU(L,ε)|≤2L(H(U)+ε)

（由系3.2.2）≤2N(由补充引理的(1))

这就是说，典型序列集TU(L,ε)中的事件的个数不超过长度为N的2元码字的数量2N。因此，可以做如下的编码：将TU(L,ε)中的事件用不同的N长2元码字来表示，而将TU(L,ε)以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L,ε)中的某个事件。2023/7/3040第40页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码对应的译码：所有的码字均译为它所表示的TU(L,ε)中的事件。结论：①实际的编码速率R满足R0≥R>H(U)；②“译码错误”的概率pe=P((U1U2…UL)不属于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得证。

定理3.2.2(无错编码反定理，p60)设给定编码设备的编码速率R0，满足R0<H(U)。当限制实际的编码速率R≤R0时，无论怎样编码和译码都不能使“译码错误”的概率任意小。（没有证明）2023/7/3041第41页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码渐进无错编码的要求给定离散无记忆简单信源：…U-2U-1U0U1U2…；给定编码设备的编码速率R0，满足R0>H(U)；给定一个任意小的正数ε>0；要求：选择合适的L，N，对(U1U2…UL)进行合适的2元N长编码，使得

①实际的编码速率R=N/L满足R≤R0；

②“译码错误”的概率pe<ε。2023/7/3042第42页，课件共195页，创作于2023年2月渐进无错编码的步骤①由U1的概率分布计算②取L满足。③取整数N=[R0L]（R0L下取整）。④取典型序列集2023/7/3043第43页，课件共195页，创作于2023年2月渐进无错编码的步骤⑤将TU(L,ε)中的事件用不同的N长2元码字来表示，而将TU(L,ε)以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L,ε)中的某个事件。⑥译码时，所有的码字均译为它所表示的TU(L,ε)中的事件。（注解：显然满足R≤R0；|TU(L,ε)|≤2N，因此码字足够用；译码错误的概率为pe=P((U1U2…UL)=(u1u2…uL)|(u1u2…uL)不属于TU(L,ε))<ε；一般来说，ε越小，要求L越大，因此对应的N越大。）2023/7/3044第44页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码例设，则2023/7/3045第45页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码设给定编码设备的编码速率R0=0.5。则R0>0.037587148=H(U1)。希望：①2元编码的实际编码速率R≤R0；②译码错误的概率不超过ε。其中取ε=0.1。找L使得2023/7/3046第46页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码取L=253即可。再取N=[R0L]=126。将TU(L,ε)中的事件用不同的N长2元码字来表示，而将TU(L,ε)以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L,ε)中的某个事件。译码时，所有的码字均译为它所表示的TU(L,ε)中的事件。另一方面，TU(L,ε)中的事件有更加简单的表达方式。当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，2023/7/3047第47页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.1)；当且仅当2023/7/3048第48页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码当事件(u1u2…u253)中a1的个数不超过4时，(u1u2…u253)∈TU(253,0.1)；否则(u1u2…u253)不属于TU(253,0.1)。(u1u2…u253)∈TU(253,0.1)的概率不小于0.9；(u1u2…u253)∈TU(253,0.1)的个数为2023/7/3049第49页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码对L=253，对应地取整数N=[R0L]=126。则N/L<R0，这就是说2元编码的实际编码速率并未超出编码设备的编码速率。2元编码的编码方法：将TU(253,0.1)中的事件用不同的126长码字表示；将TU(253,0.1)外的事件用同一个126长码字表示，该码字已经用于表示了TU(253,0.1)中的一个事件。由于|TU(253,0.1)|≤233.355557444<2126，码字足够用。2元编码的译码方法：将码字译为它所表示的TU(253,0.1)中的事件(u1u2…u253)。于是，译码错误的概率为P((u1u2…u253)不属于TU(253,0.1))≤ε=0.1。2023/7/3050第50页，课件共195页，创作于2023年2月§3.2离散无记忆（简单）信源的等长编码取ε=0.05。找L使得即L=2020。取ε=0.01。找L使得即L=252435。2023/7/3051第51页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码不等长编码：对信源输出的消息采用不同长度的码字来表示。不等长编码的优越性:编码使得最常出现的消息的码长最短，不常出现的消息的码长较长，这种编码方法得到的平均码长会比较短，进而从总体上减少码字的长度。不等长编码的特殊问题----唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。解决方案：适当地编码，使得每个码字都具有识别标记。2023/7/3052第52页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码平均码字长度。设信源随机变量U的概率分布为{ak,q(ak),k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为希望小。解决方案：概率大的事件用短码字。实时译码：能及时完成每个码字的接收译码，即译码延迟要小；容量限制：为了和一个等速信源匹配，还需要考虑缓存的问题。2023/7/3053第53页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码唯一可译性的两种解决方法定义3.3.2(p63)若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。定义3.3.4(p63)若①事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。2023/7/3054第54页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码注解逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。（许多具体的异字头码有更加简便的识别码字的方法）2023/7/3055第55页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码例观察表3.3.1(p64)。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.125101111101112023/7/3056第56页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码码A不是唯一可译的。码B不是唯一可译的。码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码C是异字头码。码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。码C不是逗点码。码D不是异字头码。码C的平均码长比码D的平均码长小：码C的平均码长为1×0.5+2×0.25+3×0.125+3×0.125=1.75；码D的平均码长为1×0.5+2×0.25+3×0.125+4×0.125=1.875。2023/7/3057第57页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码异字头码的第一种构造方法：Shannon-Fano编码法（D元编码，字母表为{0,1,…,D-1}）

（1）将源随机变量的事件按概率从大到小排成一行。（2）将此行切分为D段（可能有空段），分别赋予标号“0”到“D-1”，称为1级标号。（3）将每个非空段再切分为D段（可能有空段），分别赋予标号“0”到“D-1”，称为2级标号。（4）将每个非空段再切分为D段（可能有空段），分别赋予标号“0”到“D-1”，称为3级标号。…。2023/7/3058第58页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码如此一直到每个非空段不能再分（只含有一个事件）为止。此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。（当然，那些空段和它们的标号序列是没有用的，要去掉）为了使平均码长小，每次切分段时应使D段的概率尽可能相近。2023/7/3059第59页，课件共195页，创作于2023年2月Shannon-Fano编码例子cabcedeacacdeddaaabaababaaabbacdebaceada共40个字母频度a-16，b-7，c-6，d-6，e-51)将给定符号按照其频率从大到小排序。a-16b-7c-6d-6e–52)将序列分成左右两部分，使得左部频率总和尽可能接近右部频率总和。有：(a,b),(c,d,e)2023/7/3060第60页，课件共195页，创作于2023年2月Shannon-Fano编码例子3)我们把第二步中划分出的上部作为二叉树的左子树，记0，下部作为二叉树的右子树，记1。4)分别对左右子树重复23两步，直到所有的符号都成为二叉树的树叶为止。bacde00101011a00b01c10d110e1112023/7/3061第61页，课件共195页，创作于2023年2月Shannon-Fano编码例子编码结果Cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......长91bit采用3bit等长编码需120bit2023/7/3062第62页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码异字头码的第二种构造方法：Huffman编码法（D元编码，字母表为{0,1,…,D-1}）（1）将概率最小的D个事件分别赋予标号“0”到“D-1”。（2）将这D个事件合并为一个事件，其概率为这D个事件概率之和。重复（1）-（2），直到事件的个数等于D。将这D个事件分别赋予标号“0”到“D-1”。编码完毕。此时，一个事件的码字是这个事件从最后标号开始到最先标号为止的标号序列。（当然要去掉那些0概率事件和它们的标号序列）2023/7/3063第63页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码（为什么Shannon-Fano码和Huffman码都是异字头码？请看p71图3.4.1，p71图3.4.2。这些图都是树，称为码树，码树上的每个码字都在树梢。这种形状保证了码是异字头码。如果不是异字头码，则有的码字就不在树梢，而在中间节点。）定理3.3.1(Kraft不等式，p65)设信源随机变量共有K个事件。则：各码字长度分别为n1、n2、…、nK的D元异字头码存在的充分必要条件是2023/7/3064第64页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码证明不妨设n1≤n2≤…≤nK。则各码字长度分别为n1、n2、…、nK的D元异字头码存在；当且仅当：存在这样一个D叉树，树上有一个n1级树梢，再有一个n2级树梢，…，再有一个nK级树梢；当且仅当：存在nK级D叉满树，树上有个nK级树梢，再有个nK级树梢，…，再有个nK级树梢；当且仅当：2023/7/3065第65页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码定理3.3.2(p66)（设信源随机变量共有K个事件）。则：一个唯一可译的、各码字长度分别为n1、n2、…、nK的D元不等长码存在的充分必要条件是这说明虽然异字头码属于唯一可译码，但在码长的选择上，并不比异字头码有什么更宽松的条件，在码长的选择上，两者是一致的。2023/7/3066第66页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码定理3.3.3(p67)任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足2023/7/3067第67页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码证明设信源随机变量U的概率分布为如果唯一可译的D元不等长码的码字长度为则2023/7/3068第68页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码因此。另一方面，取n1、n2、…、nK，则：由于，存在码字长度为的唯一可译的D元不等长码。2023/7/3069第69页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码但此时2023/7/3070第70页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码定理3.3.3的结论的推广(p68)现在对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足2023/7/3071第71页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码定义编码速率R和编码效率η分别为

任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足注解不等长编码与等长编码具有相似的性质：当L增大时，对UL的编码可以更加节省编码速率。但节省编码速率的下限是H(U)。2023/7/3072第72页，课件共195页，创作于2023年2月§3.3离散无记忆（简单）信源的不等长编码例3.3.1（见p68）做2元编码。设；H(U)=0.811。U概率码字平均码长编码速率编码效率a13/40(1×3/4+1×1/4)/1=110.811a21/41U2概率码字平均码长编码速率编码效率a1a19/1601×9/16+2×3/16+3×3/16+3×1/16=27/1627/32=0.843750.961a1a23/1610a2a13/16110a2a21/161112023/7/3073第73页，课件共195页，创作于2023年2月§3.4最佳不等长编码2023/7/3074第74页，课件共195页，创作于2023年2月Huffman编码的最佳性补充引理1：由3.3节的定理3.3.1和定理3.3.2知每个唯一可译的不等长码都可以找到一个码长相同的异字头码，因而寻找最佳2元不等长码，只要寻找最佳2元异字头码即可。所谓最佳：是指在所有可能的编码方法中，其编码得到的平均码长最短。2023/7/3075第75页，课件共195页，创作于2023年2月§3.4最佳不等长编码补充引理2信源随机变量U的最佳2元异字头码S

，一定满足以下论断：“事件的概率越大，对应的码字越短”。证明如果2元异字头码S

竟然不完全满足以上论断，则存在两个事件a和b，其概率具有不等式qa>qb，其码长也具有不等式na>nb。现在将事件a和b交换码字，其它事件的码字保持不变。此时2元异字头码S

变成新的2元异字头码T。由于码S与码T中事件a和b之外的其它事件的码字保持不变，因而它们对平均码长的贡献不变，而码S

中事件a和b的码字对平均码长的贡献为qana+qbnb；码T中事件a和b的码字对平均码长的贡献为qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)>0。这就是说，码S

的平均码长>码T

的平均码长。因而码S

不是最佳2元异字头码。用反证法已经证明了补充引理2。2023/7/3076第76页，课件共195页，创作于2023年2月§3.4最佳不等长编码补充引理3设信源随机变量U的最佳2元异字头码S

，则最长的码字至少有两个。证明如果2元异字头码S

的最长的码字竟然只有一个。设这个码字为c，是事件a的码字。现在将c的最后一位去掉，成为c’，将c’仍然作为事件a的码字。其它事件的码字保持不变。此时2元异字头码S

变成新的2元码T。注意到以下两点：码T仍然是2元异字头码；码S

的平均码长>码T的平均码长。因而码S

不是最佳2元异字头码。用反证法已经证明了补充引理3。2023/7/3077第77页，课件共195页，创作于2023年2月aa2023/7/3078第78页，课件共195页，创作于2023年2月§3.4最佳不等长编码补充引理4最佳2元异字头码S可以满足以下两条：（1）概率最小的两个事件码字最长，且长度相等；（2）它们的码字仅仅最后一位不同。证明取概率最小的事件a。在剩下的事件中取概率最小的事件b。根据补充引理2和补充引理3，事件a和事件b的码字最长，且长度相等。这就是说，最佳2元异字头码S显然满足第（1）条。

关于第（2）条，分以下三种情形来讨论：2023/7/3079第79页，课件共195页，创作于2023年2月§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的码字不是仅仅最后一位不同，也没有第三个事件c，其码字与事件a的码字仅仅最后一位不同。此时：将事件b的码字换为与事件a的码字仅仅最后一位不同，得到新的码T。码T

也是2元异字头码。码T与码S平均码长相同，因此码T也是最佳2元异字头码，且码T满足第（1）条和第（2）条。2023/7/3080第80页，课件共195页，创作于2023年2月abacb§3.4最佳不等长编码abcabab2023/7/3081第81页，课件共195页，创作于2023年2月Huffman编码的最佳性定理3.4.1：对于给定信源，存在有最佳惟一可译二元码，其最小概率的两个码字CK-1和CK的长度最长且相等，它们之间仅最后一位码元取值不同(一个为0，另一个为1)。2023/7/3082第82页，课件共195页，创作于2023年2月§3.4最佳不等长编码补充定理设信源随机变量U有K个事件，K≥3。取出两个概率最小的事件：事件a和事件b。将事件a与事件b合并成一个事件e，e的概率为事件a与事件b的概率之和；而将信源随机变量U的其它事件和其对应的概率保持不变。这样得到了新的信源随机变量U’。找到U’的一个最佳2元异字头码R’。将码R’中事件e的码字后面分别添加0和1，分别作为事件a和事件b各自的码字；而将码R’中其它事件的码字保持不变。这样得到了U的2元码R。则：码R是U的最佳2元异字头码。2023/7/3083第83页，课件共195页，创作于2023年2月§3.4最佳不等长编码证明首先说明，码R是U的2元异字头码。码R’中，每个码字都在树梢，对事件e的码字后面分别添加0和1后，得到码R，码R中，由事件e的码字后面分别添加0和1得到的两个码字对应于码数中的两个新的叶子节点，位于树梢；而其它码字显然也在树梢。综上所述，码R是U的2元异字头码。接下来说明，对辅助集U’为最佳的码，对原始消息集U也是最佳的。2023/7/3084第84页，课件共195页，创作于2023年2月设原始信源随机变量新的信源随机变量§3.4最佳不等长编码2023/7/3085第85页，课件共195页，创作于2023年2月§3.4最佳不等长编码若C’1，C’2，…，C’K-1是信源U‘的最佳码，相应码长为n’1，n’2，…，n’K-1，则对信源U的码字C1，C2,…,CK的码长为nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1同时两信源各事件出现的概率满足关系式：pk=p’k

k≤K–2pK+pK-1=p’K-12023/7/3086第86页，课件共195页，创作于2023年2月§3.4最佳不等长编码

2023/7/3087第87页，课件共195页，创作于2023年2月§3.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元不等长编码。2023/7/3088第88页，课件共195页，创作于2023年2月§3.4最佳不等长编码2元Huffman编码法（字母表{0,1}）（1）将概率最小的2个事件分别赋予标号“0”和“1”。（2）将这2个事件合并为一个事件，其概率为2个事件概率之和。重复（1）-（2），直到合并为所剩的事件为2个。将这2事件分别赋予标号“0”和“1”。编码完毕。此时，一个事件的码字是这个事件从最后标号开始到最先标号为止的标号序列。2023/7/3089第89页，课件共195页，创作于2023年2月例：Huffman编码过程2023/7/3090第90页，课件共195页，创作于2023年2月例：Huffman编码过程2023/7/3091第91页，课件共195页，创作于2023年2月P59Shannon-Fano编码例子采用Huffman编码a16b7c6d6e511132401010101a0b100c101d110e111总比特数88，信源熵为86.601bit2023/7/3092第92页，课件共195页，创作于2023年2月Huffman编码Shannon-Fano编码构造二叉树是自树根到树叶，很难保证最佳性。Huffman编码则是从树叶到树根，是最佳的2023/7/3093第93页，课件共195页，创作于2023年2月总结Huffman需要知道信源的概率分布，这在实际中有时是比较困难的。采用半静态模型、自适应模型、markov模型，部分匹配预测模型等等解决这一问题。2023/7/3094第94页，课件共195页，创作于2023年2月D元Huffman编码D元码全数的端节点数为D+m(D-1)由Huffman编码的最佳性知空缺的端节点应当是码长最长的端节点共有K个符号，设第一次需要合并的消息个数为R，空缺数为BB个R个2023/7/3095第95页，课件共195页，创作于2023年2月D元Huffman编码K+B=D+m(D-1)，因而K-2=m(D-1)+D-2-B

注意R+B=D，有

0≤B≤D-2，0≤D-2-B≤D-2

因而D-2-B=(K-2)mod(D-1)即

R-2=(K-2)mod(D-1)B个R个2023/7/3096第96页，课件共195页，创作于2023年2月Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。今天，在许多知名的压缩工具和压缩算法（如WinRAR、gzip和JPEG）里，都有Huffman编码的身影。不过，Huffman编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将Huffman作为最终的编码手段，而非数据压缩算法的全部。同时科学家们一直没有放弃向信息熵极限挑战的理想。1968年前后，P.Elias发展了Shannon和Fano的编码方法，构造出从数学角度看来更为完美的Shannon-Fano-Elias编码。沿着这一编码方法的思路，1976年，J.Rissanen提出了一种可以成功地逼近信息熵极限的编码方法——算术编码。算术编码2023/7/3097第97页，课件共195页，创作于2023年2月算术编码Shannon-Fano编码，Huffman编码的编码方法：首先对信源的各事件进行编码，然后再对输入的消息序列进行编码变换。算术编码：首先假设一个信源的概率模型,随后直接把整个输入的消息编码为一个(0.0≤n<1.0)内的小区间，在编码的过程中，消息序列集中的每个元素都用来缩短这个区间，消息序列集中的元素越多,所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间，这就是区间作为代码的原理。2023/7/3098第98页，课件共195页，创作于2023年2月使用算术编码的压缩算法通常先要对信源符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。例:对一个简单的信号源进行观察，得到的统计模型如下：60%的机会出现符号中性20%的机会出现符号阳性10%的机会出现符号阴性10%的机会出现符号数据结束符.算术编码2023/7/3099第99页，课件共195页，创作于2023年2月在得到信源随机变量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)。

随后，编码过程的每一步，除了最后一步，都是相同的。算术编码2023/7/30100第100页，课件共195页，创作于2023年2月编码器通常需要考虑下面三种数据：下一个要编码的符号当前的区间(在编第一个符号之前，这个区间是[0,1),但是之后每次编码区间都会变化)模型中在这一步可能出现的各个符号的概率分布编码器利用信源符号的分布函数将当前的区间分成若干子区间，区间之间的分隔线为信源符号的分布函数，每个子区间的长度与可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为下一步编码的初始区间。算术编码2023/7/30101第101页，课件共195页，创作于2023年2月例:对于前面提出的4符号模型:中性对应的区间是[0,0.6)阳性对应的区间是[0.6,0.8)阴性对应的区间是[0.8,0.9)数据结束符对应的区间是[0.9,1)当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和模型参数即可以解码重建得到该符号序列。算术编码2023/7/30102第102页，课件共195页，创作于2023年2月算术码再以二元信源输出序列01110的编码为例P(0)P(1)F(0)F(1)01算术编码2023/7/30103第103页，课件共195页，创作于2023年2月算术码P(00)P(01)F(0)F(01)F(1)P(010)P(011)F(011)P(0110)P(0111)F(0111)P(01110)P(01111)F(01111)算术编码2023/7/30104第104页，课件共195页，创作于2023年2月算术码信源符号序列u对应区间的宽度等于符号序列的概率信源符号序列u对应区间的左端点为算术编码2023/7/30105第105页，课件共195页，创作于2023年2月F(u)将[0,1)分割成许多小区间，以小区间的左端点数值的二进制小数表示该序列，同时要将该小数的小数位数截断为l位，截断规则为：

l位后面只要有非0的余数就要向第l位进位。最后得到了小数0.t。将t作为事件u=(u1u2…uL)的码字。码字长度l为算术编码2023/7/30106第106页，课件共195页，创作于2023年2月算术编码则即因而即2023/7/30107第107页，课件共195页，创作于2023年2月例:

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

算术编码的译码2023/7/30109第109页，课件共195页，创作于2023年2月然后我们将区间[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)的10%

数据结束符的区间是[0.54,0.6).--[0,0.6)的10%

分数0.538在[0.48,0.54)区间；所以消息的第二个符号一定是阴性。算术编码的译码2023/7/30110第110页，课件共195页，创作于2023年2月再一次将当前区间划分成四个子区间：中性的区间是[0.48,0.516)阳性的区间是[0.516,0.528)阴性的区间是[0.528,0.534)数据结束符的区间是[0.534,0.540).分数0.538落在符号数据结束符的区间；所以，这一定是下一个符号。由于它也是内部的结束符号，这也就意味着编码已经结束。算术编码的译码2023/7/30111第111页，课件共195页，创作于2023年2月§3.4最佳不等长编码算术编码的特点特点一当L很大时，平均码长接近信源熵H(U)，因此编码效率接近上限。特点二编译码简单，存储量小，速度快。算术编码的应用领域在图象数据压缩标准（如JPEG）中得到广泛应用。2023/7/30112第112页，课件共195页，创作于2023年2月

1982年，Rissanen和G.G.Langdon一起改进了算术编码。之后，人们又将算术编码与J.G.Cleary和I.H.Witten于1984年提出的部分匹配预测模型（PPM）相结合，开发出了压缩效果近乎完美的算法。今天，那些名为PPMC、PPMD或PPMZ并号称压缩效果天下第一的通用压缩算法，实际上全都是这一思路的具体实现。看起来，压缩技术的发展可以到此为止了。不幸的是，事情往往不像想象中的那样简单：算术编码虽然可以获得最短的编码长度，但其本身的复杂性也使得算术编码的任何具体实现在运行时都慢如蜗牛。即使在摩尔定律大行其道，CPU速度日新月异的今天，算术编码程序的运行速度也很难满足日常应用的需求。如果不是后文将要提到的两个犹太人，我们还不知要到什么时候才能用上WinZIP这样方便实用的压缩工具呢。词典编码方法2023/7/30113第113页，课件共195页，创作于2023年2月逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进Huffman或算术编码，以获得一种兼顾了运行速度和压缩效果的“完美”编码的时候，两个聪明的犹太人J.Ziv和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为LZ系列算法。词典编码方法2023/7/30114第114页，课件共195页，创作于2023年2月说实话，LZ系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是简单地延续了千百年来人们对字典的追崇