信息论与编码2016(第3章)教材

信息理论与编码朱仁祥zhurx@电子与信息工程学院12024/6/232第三章：信源编码

离散信源无失真编码§3.1信源及其分类§3.2离散无记忆（简单）信源的等长编码§3.3离散无记忆（简单）信源的不等长编码§3.4最佳不等长编码3通信的根本问题是将信源的输出在接收端精确地或近似地重新出来。两个问题：

1.信源的输出应如何描述，即如何计算它产生的信息量。2.如何表示信源的输出，即信源编码问题。2024/6/234无失真信源编码保证信源产生的全部信息无损地递给信宿；限定失真的信源编码不要求完全精确地复制出信源的输出，但要满足一定的保真度准则。5§3.1信源及其分类信源的概念

（直观地理解，信源就是信息的来源。但是必须要注意两点）：在一个固定的时刻，信源发出的是一个随机变量。随着时间的延续，信源发出一个又一个随机变量，称之为一个随机过程。（因此，一般的信源种类太多，其统计性质太复杂。怎样做工程实用的简化？）6§3.1信源及其分类离散信源信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列

…U-2U-1U0U1U2…其中Uk为第k个时间段发出的随机变量；每个Uk都是一个离散型的随机变量。§3.1信源及其分类离散无记忆信源离散无记忆信源是这样的离散信源：随机变量…、U-2、U-1、U0、U1、U2、…相互独立。离散无记忆简单信源离散无记忆简单信源是这样的离散无记忆信源：随机变量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布。78§3.1信源及其分类小结离散无记忆简单信源

就是时间离散、事件离散、各随机变量独立同分布的信源.课程学习所面对的信源将主要是离散无记忆简单信源.§3.1信源及其分类一般的信源

连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。9§3.2离散无记忆（简单）信源的等长编码编码实质上是对信源的原始符号按一定的数学规则进行的一种变换，映射成码字以适合信道传输。102024/6/2311§3.2离散无记忆（简单）信源的等长编码设有一个离散无记忆简单信源，信源发出的随机变量序列为：…U-2U-1U0U1U2…。设信源随机变量U1的事件有K个：{a1,a2,…,aK}，则L维信源随机向量(U1U2…UL)的事件有KL个：{(u1u2…uL)|其中每个分量ul跑遍{a1,a2,…,aK}}。§3.2离散无记忆（简单）信源的等长编码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)1213§3.2离散无记忆（简单）信源的等长编码设有一个含D个字母的字母表。对于(U1U2…UL)的每一个事件(u1u2…uL)，都用一个字母串(c1c2…)来表示。这种表示方法称为D元编码；每一个事件(u1u2…uL)所对应的字母串(c1c2…)称为一个码字。14§3.2离散无记忆（简单）信源的等长编码例：离散无记忆简单信源发出的随机变量序列为：…U-2U-1U0U1U2…，其中U1的事件有3个：{晴,云,阴}.将(U1U2)进行2元编码.§3.2离散无记忆（简单）信源的等长编码(U1U2)有9个事件{（晴晴），（晴云），（晴阴），（云晴），（云云），（云阴），（阴晴），（阴云），（阴阴）}15§3.2离散无记忆（简单）信源的等长编码用字母表{0,1}对(U1U2)的事件进行2元编码如下：（晴晴）→0000，（晴云）→0001，（晴阴）→0011，（云晴）→0100，（云云）→0101，（云阴）→0111，（阴晴）→1100，（阴云）→1101，（阴阴）→1111。1617§3.2离散无记忆（简单）信源的等长编码如果限定所有码字的长度都为N（即每个码字都是一个长度为N的字母串，或称为N维向量），则称此编码为等长编码，能够选择的不同码字的个数为DN。18§3.2离散无记忆（简单）信源的等长编码如果限定每个码字的长度都≤N（即每个码字都是一个长度≤N的字母串），则称此编码为不等长编码，能够选择的不同码字的个数为D1+D2+…+DN=D(DN-1)/(D-1)。19§3.2离散无记忆（简单）信源的等长编码问题：在不等长编码中，能否同时使用D(DN-1)/(D-1)个不同的码字？一个长度为2的字母串究竟是两个长度为1的码字相连，还是一个长度为2的码字？无法识别。在等长编码中不存在这样的识别问题。20§3.2离散无记忆（简单）信源的等长编码对等长码若对每个消息都至少有一个码字与之对应，且不同的消息对应不同的码字，则称这样的码为单义可译码或唯一可译码。在无扰传输时，单义可译码的译码错误概率为0，又称为无错编码。21§3.2离散无记忆（简单）信源的等长编码无错编码

(U1U2…UL)的不同事件用不同的码字来表示。消息集是K元字母表L长消息序列，编码成D元N长码字。能够实现无错编码的充要条件是DN≥KL即NlogD

≥

LlogK或NlogD/L

≥

logK

(下界)等长码基本问题

C2={000,001,100,101,111}，K2=3

code/sig惟一可译码C1={00,01,10,11,10}，K1=2

code/sig奇异码等长码特点：Ki=K要求：xi—yj

高效问题：K=?等长编码:

要求:可能的码字数≥消息数对基本信源编码：xi∈X=(x1,x2,…xn

)--yj

码字数：mK

∴mK≥n(K≥logmn)

（对例1，n=5,∴要求：2K≥5，即K≥3）对L长源编码：ai∈XL=(a1,a2,…anL)—yj

’

∴mK≥nL

(K/L≥logmn)例（续）X的三次扩展：X3:{a1=(x1x1

x1),,…,a53=(x5x5

x5)}

则，nL=53=125种<128=27∴K=7code/3sigs

平均码长：K/L=7/3=2.33code/sig<K2

结论:等长码码长要求K/L

logmn(保证唯一可译码,无失真)

logmn为下限扩展信源编码的平均码长<基本源编码的平均码长25§3.2离散无记忆（简单）信源的等长编码编码速率

R=NlogD/L实现无错编码的充要条件是

编码速率R=NlogD/L≥logK26§3.2离散无记忆（简单）信源的等长编码

有错编码

(U1U2…UL)的有些不同事件用相同的码字来表示。27§3.2离散无记忆（简单）信源的等长编码编码速率的说明实际的编码速率的计算公式为R=NlogD/L，似乎可以人为地任意设置N和L，因而可以人为地任意设置编码速率。?

§3.2离散无记忆（简单）信源的等长编码事实并非如此，存在着编码设备的编码速率R0，它是编码设备的性能指标.这就是说，选择N和L，必须使得实际的编码速率NlogD/L不能超过编码设备的编码速率R0

：R=NlogD/L≤R0

2829§3.2离散无记忆（简单）信源的等长编码有错编码的译码方法与“译码错误”概率当使用有错编码时，必须给出译码方法（即：一个码字可能表示几个不同的事件，究竟翻译成哪个事件）。“译码错误”的概率定义为

pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。30§3.2离散无记忆（简单）信源的等长编码在无错编码的前提下，编码的最低代价当R≥logK时，能够实现无错编码。（DN≥KL）当R<H(U1)时，无论怎样编码都是有错编码。

这是因为R<H(U1)≤logK。（DN<KL）如果H(U1)=logK，则以上两种情形已经概括了全部情形。但如果H(U1)<logK，则还有一种情形。当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。31§3.2离散无记忆（简单）信源的等长编码logKH(U1)·RRR无错编码不能渐进无错编码渐进无错编码○·○○○32§3.2离散无记忆（简单）信源的等长编码渐进无错编码

简单地说就是：当R>H(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。33§3.2离散无记忆（简单）信源的等长编码渐进无错编码

严格地说就是：设给定了编码设备的编码速率R0，R0>H(U1)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的等长编码和对应的译码方法，满足①实际的编码速率R=NlogD/L≤R0，②译码错误的概率pe<ε。34§3.2离散无记忆（简单）信源的等长编码渐进无错编码的原理

大数定律。随着L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越来越小（→0），其发生的概率却越来越大（→1）。35§3.2离散无记忆（简单）信源的等长编码不能渐进无错的编码

简单地说就是：当R<H(U1)时，无论怎样编码和译码都不能使译码错误的概率pe

任意小。

严格地说就是：设给定了编码设备的编码速率R0，R0<H(U1)，则无论怎样编码和译码都不能同时满足①实际的编码速率R≤R0，②译码错误的概率pe任意小。36§3.2离散无记忆（简单）信源的等长编码设…U-2U-1U0U1U2…是离散无记忆（简单）信源的输出随机变量序列。设U1的概率分布为取Vl是Ul的如下函数：当Ul=ak时，Vl=loga(1/qk)。则①随机变量序列…V-2V-1V0V1V2…相互独立，具有相同的概率分布；②37§3.2离散无记忆（简单）信源的等长编码取IL是(V1V2…VL)的如下函数：则①IL最终是(U1U2…UL)的函数；②③因此有切比雪夫不等式：对任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥38§3.2离散无记忆（简单）信源的等长编码取定L0使得则当L≥L0时总有因此当L≥L0时总有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。39§3.2离散无记忆（简单）信源的等长编码定义3.2.1(p50)定义TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，称TU(L,ε)为ε-典型序列集。称TU(L,ε)的补集为非ε-典型序列集。（综上所述有）定理3.2.1(信源划分定理，p51)对任意ε>0，取L0使得则当L≥L0时总有P{(U1U2…UL)∈TU(L,ε)}≥1-ε。2024/6/2340§3.2离散无记忆（简单）信源的等长编码（简记H(U)=H(U1)。设以下的对数都是以2为底的。）系3.2.1(特定典型序列出现的概率，p51)若一个特定的事件(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)+ε，41§3.2离散无记忆（简单）信源的等长编码所以42§3.2离散无记忆（简单）信源的等长编码系3.2.2(典型序列的数量，p51)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。证明一方面，43§3.2离散无记忆（简单）信源的等长编码另一方面，44§3.2离散无记忆（简单）信源的等长编码（如果采用2元编码，且对数都是以2为底的，则编码速率为R=NlogD/L=N/L。）补充引理

设给定一个R0>H(U)。对每个正整数L，对应地取整数N=[R0L]（R0L的下取整）。则N/L≤R0，limL→+∞N/L=R0。任取正数ε≤(R0-H(U))/2，存在正整数L0，当L>L0时（1）N/L≥R0-(R0-H(U))/2=H(U)+(R0-H(U))/2≥H(U)+ε。（2）P{(U1U2…UL)∈TU(L,ε)}≥1-ε。（由定理3.2.1）45§3.2离散无记忆（简单）信源的等长编码定理3.2.2(无错编码正定理，p53)

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

（由系3.2.2）≤2LR=2N

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

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

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

②“译码错误”的概率pe<ε。49渐进无错编码的步骤①由U1的概率分布计算②取L满足。③取整数N=[R0L]（R0L下取整）。④取典型序列集50渐进无错编码的步骤⑤将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越大。）51§3.2离散无记忆（简单）信源的等长编码例设52§3.2离散无记忆（简单）信源的等长编码设给定编码设备的编码速率R0=0.5。则R0>0.037587148=H(U1)。希望：①2元编码的实际编码速率R≤R0；②译码错误的概率不超过ε。其中取ε=0.1。找L使得2024/6/2353§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时，54§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.1)；当且仅当55§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)的个数为56§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。57§3.2离散无记忆（简单）信源的等长编码取ε=0.05。找L使得即L=2020。有P{(U1U2…UL)=(u1u2…uL)|

-0.05≤IL-H(U)≤0.05}≥0.95。另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，58§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.05)；当且仅当-0.05≤IL-H(U)≤0.05；当且仅当59§3.2离散无记忆（简单）信源的等长编码设L=2020。此时0.01028137L=20.7683674。当事件(u1u2…u2020)中a1的个数不超过20时，(u1u2…u2020)∈TU(2020,0.05)；否则(u1u2…u2020)不属于TU(2020,0.05)。(u1u2…u2020)∈TU(2020,0.05)的概率不小于0.95；(u1u2…u2020)∈TU(2020,0.05)的个数为60§3.2离散无记忆（简单）信源的等长编码对L=2020，对应地取整数N=[R0L]=1010。则N/L=R0，这就是说2元编码的实际编码速率等于编码设备的编码速率。2元编码的编码方法：将TU(2020,0.05)中的事件用不同的1010长码字表示；将TU(2020,0.05)外的事件用同一个1010长码字表示，该码字已经用于表示了TU(2020,0.05)中的一个事件。由于|TU(2020,0.05)|≤2176.92603896<21010，码字足够用。2元编码的译码方法：将码字译为它所表示的TU(2020,0.05)中的事件(u1u2…u2020)。于是，译码错误的概率为P((u1u2…u2020)不属于TU(2020,0.05))≤ε=0.05。61§3.2离散无记忆（简单）信源的等长编码取ε=0.01。找L使得即L=252435。有P{(U1U2…UL)=(u1u2…uL)|

-0.01≤IL-H(U)≤0.01}≥0.99。另一方面，当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，62§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.01)；当且仅当-0.01≤IL-H(U)≤0.01；当且仅当2024/6/2363§3.2离散无记忆（简单）信源的等长编码设L=252435。此时0.00274372L=692.61096；0.00525628L=1326.8690。

当事件(u1u2…u252435)中a1的个数不超出闭区间[693，1326]内时，(u1u2…u252435)∈TU(252435,0.01)；否则(u1u2…u252435)不属于TU(252435,0.01)。(u1u2…u252435)∈TU(252435,0.01)的概率不小于0.99；(u1u2…u252435)∈TU(252435,0.01)的个数为64§3.2离散无记忆（简单）信源的等长编码对L=252435，对应地取整数N=[R0L]=126217。则N/L<R0，这就是说2元编码的实际编码速率小于编码设备的编码速率。2元编码的编码方法：将TU(252435,0.01)中的事件用不同的126217长码字表示；将TU(252435,0.01)外的事件用同一个126217长码字表示，该码字已经用于表示了TU(252435,0.01)中的一个事件。由于|TU(252435,0.01)|≤212012.6617<2126217，码字足够用。2元编码的译码方法：将码字译为它所表示的TU(252435,0.01)中的事件(u1u2…u252435)。于是，译码错误的概率为P((u1u2…u252435)不属于TU(252435,0.01))≤ε=0.01。65§3.2离散无记忆（简单）信源的等长编码（直观理解）等长编码定理（信源划分定理）1.信源序列集=典型序列集（高概率集，>=1-\epsilon）+非典型序列集（低概率集）；2.将典型序列集中的信源序列一一编码（无错编码），而将非典型序列集中的信源序列编码成刚才的一个码字；3.典型序列集势约为2^{LH(U)}，占K^L少,非典型序列集势占多。注意:※

适用于DMS及无记忆平稳信源※平均码长下限：※

基本方法：L长源、等长编码※对等长编码,若要实现几乎无失真编码,则信源长度必满足:其中:当Pe<10-5则有：η=0.5得L≥71687

η=0.8得L≥1146990

η=0.9得L≥5806641

η=0.96得L≥41291672解：H(X)=0.811bit/sig

信源方差D[I(xi)]=E[I2(xi)]－{E[I(xi)]}2=0.4715等长码的缺点：平均码长太长L无法实现变长码的特点：每个码字长度可不同要求：惟一可译69§3.3离散无记忆（简单）信源的不等长编码（顺序地叙述以下的概念）（1）不等长编码的优越性总体上减少码字的长度。（2）不等长编码的特殊问题

①唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。解决方案：适当地编码，使得每个码字都具有识别标记。（注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2)连接成的字母串c(1)c(2)不能是码字）70§3.3离散无记忆（简单）信源的不等长编码②平均码字长度。设信源随机变量U的概率分布为{ak,q(ak),k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为希望小。解决方案：概率大的事件用短码字。③实时译码和容量限制。71§3.3离散无记忆（简单）信源的不等长编码唯一可译性的两种解决方法定义3.3.2(p55)若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。定义3.3.4(p55)若①事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。72§3.3离散无记忆（简单）信源的不等长编码注解逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。（许多具体的异字头码有更加简便的识别码字的方法）按译码的即时性分类非即时码：接收端收到一个完整的码字后,不能立即译码；还需要等到下一个码字开始接收后才能判断是否可以译码;非即时码,又名延长码,一码字是其他码字的延长。即时码：接收端收到一个完整的码字后，就能立即译码；即时码又称为非延长码或非前缀码，任何一个码不能是其他码的前缀。例：非即时码——码流01001100…x1→0x2→01x3→11译码为x2,x1,x1,x3,x1,?

即时码——码流01001100…x1→0x2→10x3→11译码为x1,x2,x1,x3,x1,x1

[记忆]非前缀码必定是即时码，即时码必定是唯一可译码,

但唯一可译码不一定是即时码。有实用价值的分组码是非奇异码、唯一可译码、即时码74§3.3离散无记忆（简单）信源的不等长编码例观察表3.3.1(p55)。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.1251011111011175§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。[基本术语]终端节点——后面不再分支的节点。中间节点——除树根、终端节点外的节点。联枝——串联的树枝码字——从树根出发，到达某一终端节点的联枝即时码——每个码字都到达终端节点满树

——每个码字的联枝数均相同时(定长码)非满树——当码字的联枝数不同时(变长码)全树——每个中间节点的后续分支数均为m非全树——有些中间节点的后续分支数不足m码树法满树全树，非满树非全树二进制码树、满树、全树012000001111122222三进制码树、非满树、全树A01000000000000011111111111(1)规则树根=码字的起点树的度=码元数分支结点=码的符号的一部分终端结点=待编码符号(2)码树画法(m进制)①从树根出发，画m条分支，分支端点称为节。②第一节有m个端点，每端点对应一个码字③从第一节每个端点出发，再画m条分支，得第二节。第二节有m2个端点④以此类推(3)编码方法：①将待编码的字符作为终端结点，构造码树；②按一定规则给每个树枝分配一个标记；③将从根到终端结点的路径上的编号依次相连，作为该终端结点所表示的字符的编码。(4)译码方法：①从树根出发,根据接收到的第一个码字符号来选择应走的第一条路径②沿所选路径走到分支结点,再根据收到的第二个码字选择应走的第二条路径,直至走到终端结点为止③根据所走路径,可立即判断出接收到的码符号④重新返回到树根,再作下一个接收码符号的判断例题:非满二叉树acdb(0)0(10)00111(110)(111)构造二元码树:编码:信源序列X={bacabd}100110010111译码:100110010111信源序列X={bacabd}提问:为什么码树法构造的码就是即时码？81§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级标号。…。82§3.3离散无记忆（简单）信源的不等长编码如此一直到每个非空段不能再分（只含有一个事件）为止。此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。（当然，那些空段和它们的标号序列是没有用的，要去掉）为了使平均码长小，每次切分段时应使D段的概率尽可能相近。（注解：当然可以把“切分段”操作换为“任意分组”操作，使D组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。）83例设有一单符号离散信源对该信源编二进制费诺码。信源符号xi

符号概率p(xi)第1次分组第2次分组第3次分组码字码长x10.400002x40.05100103x50.0510113x20.310102x30.21112信源符号xi

符号概率p(xi)第1分组第2分组第3分组第4分组码字码长x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均码长：n=2.1编码效率:η=93%平均码长：n=2.0编码效率:η=97.5%84平均码长编码效率费诺码比较适合于每次分组概率都很接近的信源特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。85例有一单符号离散无记忆信源对该信源编二进制费诺码,编码过程如表:86信源熵为H(X)=2.75(比特/符号)平均码长为编码效率为

η=1之所以如此,因为每次所分两组的概率恰好相等。87§3.3离散无记忆（简单）信源的不等长编码异字头码的第二种构造方法：Huffman编码法88二元Huffman编码法89例子

设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表信源符号xi

符号概率p(xi)编码过程x10.20x20.19x30.18x40.17x50.15x60.10x70.01010.200.190.180.170.150.11010.260.200.190.180.17010.350.260.200.19010.390.350.26010.610.3901码字101100000101001100111在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的异前置码。90熵平均码长为编码效率例2.源符Si概率P(Si)S10.4S20.2S30.2S40.1S50.1010001000001001000110100101101001101

合并后概率下放合并后概率上放这两种编码哪一种更好呢，我们来计算一下二者的码长。

两种编码的平均码长是一样的，都是2.2，那一种更好呢，我们可以计算一下平均码长的方差。定义码字长度的方差σ2：可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有2种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好结论：在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。[结论]＊两法平均码长相同，因而信息率R、编码效率

相同＊但码方差不同，码方差小要好各次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长也不变，所以没有本质区别，不会影响码字的长度。缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度ki也不尽相同。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差。编码不唯一（0、1分配不同，排序不同）平均码长唯一为什么哈夫曼编码方法得到的码并非是唯一的?

95D元Huffman编码法（D元编码，字母表为{0,1,…,D-1}）（0）如果源随机变量的事件的个数K不是(D-1)的倍数加1，则添加若干0概率事件使得事件的个数是(D-1)的倍数加1。（1）将概率最小(排序)的D个事件分别赋予标号“0”到“D-1”。（2）将这D个事件合并为一个事件，其概率为这D个事件概率之和。重复（1）-（2），直到事件的个数等于D。将这D个事件分别赋予标号“0”到“D-1”。编码完毕。此时，一个事件的码字是这个事件从最后标号开始到最先标号为止的标号序列。（当然要去掉那些0概率事件和它们的标号序列）为了使短码得到充分利用，使平均码长为最短，必须使最后一步的缩减信源有D个信源符号，因此对于D元编码，信源的符号个数K必须满足K=(D-1)r+D=(D-1)(r+1)+1,其中r为缩减的次数。K-(D-1)r=D96哈夫曼的编法并不惟一。对二元Huffman编码，每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。对D元Huffman编码，有类似结果。哈夫曼编码97哈夫曼编码不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别；缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。不同的编法得到的码字长度Ki也不尽相同。2024/6/2398§3.3离散无记忆（简单）信源的不等长编码（为什么Shannon-Fano码和Huffman码都是异字头码？请看p62图3.4.1，p62图3.4.2。这些图都是树，称为码树，码树上的每个码字都在树梢。这种形状保证了码是异字头码。如果不是异字头码，则有的码字就不在树梢，而在中间节点。）P56,若一个码树的各分支都能延伸到最高级端点（共有D^{n_K}个码字），就称为满树，否则为非满树。若消息占满了所有的端节点，即树上每一个中间节点都有D个分支，称为全树。99定理3.3.1(Kraft不等式，p57)设信源随机变量共有K个事件。则：各码字长度分别为n1、n2、…、nK的D元异字头码存在的充分必要条件是100§3.3离散无记忆（简单）信源的不等长编码证明不妨设n1≤n2≤…≤nK。则各码字长度分别为n1、n2、…、nK的D元异字头码存在；当且仅当：存在这样一个D叉树，树上有一个n1级树梢，再有一个n2级树梢，…，再有一个nK级树梢；当且仅当：存在nK级D叉满树，树上有个nK级树梢，再有个nK级树梢，…，再有个nK级树梢；当且仅当：101§3.3离散无记忆（简单）信源的不等长编码表明：异字头码的各码组长度nK

必须满足上式，而对满足上式的一组整数nK

必有相应码长的异字头码。但这并不是说满足上式的异字头码是唯一的，而且这个不意味着满足该式的码就一定是异字头码。102§3.3离散无记忆（简单）信源的不等长编码定理3.3.2(p57)设信源随机变量共有K个事件，则一个唯一可译的、各码字长度分别为n1、n2、…、nK的D元不等长码存在的充分必要条件是103§3.3离散无记忆（简单）信源的不等长编码上述两定理表明：1.任一唯一可译码可用各相应码字长度一样的异字头码代替。2.异字头码属于唯一可译码，唯一可译码是满足Kraft不等式的码。对任一满足Kraft不等式的非异字头码又可以找到一个码字长度不变的异字头码。唯一可译码存在的充分和必要条件

说明：Kraft不等式——惟一可译码存在的充要条件。必要性表现在如果码是惟一可译码,则一定满足Kraft不等式；充分性表现在如果满足Kraft不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可译码

Kraft不等式是惟一可译码存在的充要条件，而不是惟一可译码的充要条件。例:考察：①l1=1，l2=2，l3=l4=3的二元码如：C1={1,01,001,000}

C2={0,10,110,111}②l1=1，l2=l3=l4=2的二元码

∴必存在惟一可译码

∴必不存在惟一可译码惟一可译码C3={0,00,000,000}非惟一可译码长结构～惟一可译码而106§3.3离散无记忆（简单）信源的不等长编码定理3.3.3(p56)（不等长编码定理）任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足2024/6/23107§3.3离散无记忆（简单）信源的不等长编码证明设信源随机变量U的概率分布为如果唯一可译的D元不等长码的码字长度为则108§3.3离散无记忆（简单）信源的不等长编码因此。另一方面，取n1、n2、…、nK，则：由于，存在码字长度为的唯一可译的D元不等长码。109§3.3离散无记忆（简单）信源的不等长编码但此时110§3.3离散无记忆（简单）信源的不等长编码定理3.3.3的结论的推广(p59-60)现在对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足111§3.3离散无记忆（简单）信源的不等长编码定义：编码速率R和编码效率η分别为

任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足注解不等长编码与等长编码具有相似的性质：当L增大时，对UL的编码可以更加节省编码速率。但节省编码速率的下限是H(U)。112§3.3离散无记忆（简单）信源的不等长编码例3.3.1（见p60）做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/320.961a1a23/1610a2a13/16110a2a21/16111Huffman编码效率高，运算速度快，实现方式灵活，从20世纪60年代至今，在数据压缩领域得到了广泛的应用。今天，在许多知名的压缩工具和压缩算法（如WinRAR

、gzip

和JPEG）里，都有Huffman编码的身影。不过，Huffman编码所得的编码长度只是对信息熵计算结果的一种近似，还无法真正逼近信息熵的极限。正因为如此，现代压缩技术通常只将Huffman作为最终的编码手段，而非数据压缩算法的全部。同时科学家们一直没有放弃向信息熵极限挑战的理想。1968年前后，P.Elias发展了Shannon和Fano

的编码方法，构造出从数学角度看来更为完美的Shannon-Fano-Elias编码。沿着这一编码方法的思路，1976年，J.Rissanen

提出了一种可以成功地逼近信息熵极限的编码方法——算术编码。算术编码算术编码Shannon-Fano编码，Huffman编码的编码方法：首先对信源的各事件进行编码，然后再对输入的消息序列进行编码变换。算术编码：首先假设一个信源的概率模型,随后直接把整个输入的消息编码为一个(0.0≤n<1.0)内的小区间，在编码的过程中，消息序列集中的每个元素都用来缩短这个区间，消息序列集中的元素越多,所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间，这就是区间作为代码的原理。使用算术编码的压缩算法通常先要对信源符号的概率进行估计，然后再编码。这个估计越准，编码结果就越接近最优的结果。例:对一个简单的信号源进行观察，得到的统计模型如下：60%的机会出现符号中性20%的机会出现符号阳性10%的机会出现符号阴性10%的机会出现符号数据结束符.算术编码在得到信源随机变量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)。

随后，编码过程的每一步，除了最后一步，都是相同的。算术编码编码器通常需要考虑下面三种数据：下一个要编码的符号当前的区间(在编第一个符号之前，这个区间是[0,1),但是之后每次编码区间都会变化)模型中在这一步可能出现的各个符号的概率分布编码器利用信源符号的分布函数将当前的区间分成若干子区间，区间之间的分隔线为信源符号的分布函数，每个子区间的长度与可能出现的对应符号的概率成正比。当前要编码的符号对应的子区间成为下一步编码的初始区间。算术编码例:对于前面提出的4符号模型:中性对应的区间是[0,0.6)阳性对应的区间是[0.6,0.8)阴性对应的区间是[0.8,0.9)数据结束符对应的区间是[0.9,1)当所有的符号都编码完毕，最终得到的结果区间即唯一的确定了已编码的符号序列。任何人使用该区间和模型参数即可以解码重建得到该符号序列。算术编码算术编码原理把信源序列的积累概率映射到[0,1)区间上，使每个序列对应该区间内的一点，这些点把区间[0,1)分成许多不同的小区间，这些小区间的长度等于对应序列的概率，在小区间内取一个浮点小数，使其长度与该序列的积累概率相匹配。因而达到高效编码的目的。算术编码的主要任务是计算信源序列对应的小区间再以二元信源输出序列01110的编码为例P(0)P(1)F(0)F(1)01算术编码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)算术编码信源符号序列u对应区间的宽度等于符号序列的概率信源符号序列u对应区间的左端点为算术编码信源序列积累概率传递公式设独立信源序列信源序列S添加一个新的信源符号ur后所得新序列Sur的积累概率。信源序列S的概率。信源序列的积累概率F(S)与信源符号的积累概率一样，可用[0,1)区间内的个点来表示，因此积累概率F(S)将区间[0,1)分成许多不同的小区间，他们互不重叠，序列S的概率p(S)就是两点间小区间的长度。小区间内的一个点可用来表示序列的概率。递推公式的应用用序列积累概率的递推公式进行序列的算术编码的计算步骤：（1）根据信源符号积累概率公式计算信源符号的积累概率（2）初始时，设S=Ø，F(Ø)=0，p(Ø)=1；（3）根据序列的积累概率递推公式，计算序列的积累概率

F(ur)和序列的概率p(ur)；（4）计算码长；（5）将F(s)写成二进制数形式，取其前L位作为序列S的码字，若后面有尾数就进位到第L位。F(u)将[0,1)分割成许多小区间，以小区间的左端点数值的二进制小数表示该序列，同时要将该小数的小数位数截断为l位，截断规则为：l位后面只要有非0的余数就要向第l位进位。最后得到了小数0.t。将t作为事件u=(u1u2…uL)的码字。码字长度l为算术编码算术编码则即因而即[例]设信源

求信源序列S=abda对应的小区间解:信源符号对应区间端点值符号概率区间a0.5[0,0.5)b0.25[0.5,0.75)c0.125[0.75,0.875)d0.125[0.875,1)信源序列对应区间端点值信源序列lowhigha00.5ab0.250.375abd0.3593750.375abda0.3593750.3671875信源序列S=abda对应区间的划分过程图0.75

a

bcd00.50.8751

aa

abacad0.2500.3750.5

aba

abbabcabd0.250.3593750.375

a

bcd0.3593750.36718750.375不同的信源序列分别对应不同的互不重叠的小区间，取小区间内的一个点作为对应序列的编码。--------即时码S=abda的编码译码——编码的逆过程根据接收到的码字译出对应的信源序列[译码步骤](1)判断码字落在哪个符号区间，译出第1个符号(2)将码字减去刚译出符号的左端点值，得差值并以刚译出符号对应的区间长度去除差值再判断此值落在哪个符号区间，译出第2个符号(3)重复步骤(2)，直至全部信源序列被译完为止例:

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

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

1982年，Rissanen

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

这样方便实用的压缩工具呢。词典编码方法逆向思维永远是科学和技术领域里出奇制胜的法宝。就在大多数人绞尽脑汁想改进Huffman或算术编码，以获得一种兼顾了运行速度和压缩效果的“完美”编码的时候，两个聪明的犹太人J.Ziv

和A.Lempel独辟蹊径，完全脱离Huffman及算术编码的设计思路，创造出了一系列比Huffman编码更有效，比算术编码更快捷的压缩算法。我们通常用这两个犹太人姓氏的缩写，将这些算法统称为LZ系列算法。词典编码方法说实话，LZ系列算法的思路并不新鲜，其中既没有高深的理论背景，也没有复杂的数学公式，它们只是简单地延续了千百年来人们对字典的追崇和喜好，并用一种极为巧妙的方式将字典技术应用于通用数据压缩领域。通俗地说，当你用字典中的页码和行号代替文章中每个单词的时候，你实际上已经掌握了LZ系列算法的真谛。这种基于字典模型的思路在表面上虽然和Shannon、Huffman等人开创的统计学方法大相径庭，但在效果上一样可以逼近信息熵的极限。而且，可以从理论上证明，LZ系列算法在本质上仍然符合信息熵的基本规律。词典编码方法词典编码方法词典编码方法是基于数据中许多结构频繁重复再现这一事实,人们可以对相同符号串分配同一码字、通过索引、或者其他诸如此类的方法编码。70年代末提出、80年代中期走向实用化的LZ压缩技术开创了现代词典编码方法,并且已经牢固地统治着通用压缩世界。LZ的基本思想是:数据中的子串可以通过用指代先前已处理数据(即历史数据)中相同子串的方式来描述。对历史数据的存储方式可以不同,例如，LZ77采用滑动的缓冲区(或称窗口)记录,LZ78则选择词典方式进行登录。应该指出的是,两者的压缩效率没有显著差异,而且都是当重复的子串越长压缩效率越高。按照时间顺序，LZ系列算法的发展历程大致是：Ziv

和Lempel