信息论与编码理论基础(第3章)

第三章：信源编码-离散信源无失真编码§3.1信源及其分类§3.2离散无记忆（简单）信源的等长编码§3.3离散无记忆（简单）信源的不等长编码§3.4最佳不等长编码§3.1信源及其分类信源的概念

直观地理解，信源就是信息的来源。但是这里必须要注意两点：在一个固定的时刻，信源发出的是一个随机变量。随着时间的延续，信源发出一个又一个随机变量，称之为一个随机过程。因此，一般的信源种类太多，其统计性质太复杂。怎样做工程实用的简化？离散信源信源每隔一个定长时间段就发出一个随机变量；随着时间的延续，信源发出的是随机变量序列…U-2U-1U0U1U2…，其中(1)Uk为第k个时间段发出的随机变量；(2)每个Uk都是一个离散型的随机变量。离散无记忆信源离散无记忆信源是这样的离散信源：随机变量…、U-2、U-1、U0、U1、U2、…相互独立。离散无记忆简单信源离散无记忆简单信源是这样的离散无记忆信源：随机变量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布。§3.1信源及其分类总结：离散无记忆简单信源就是时间离散、事件离散、各随机变量独立同分布的信源。本课程学习所面对的信源将主要是离散无记忆简单信源。一般的信源

连续信源：有时间连续的信源，也有事件连续的信源；有记忆信源：信源在不同时刻发出的随机变量相互依赖；有限记忆信源：在有限时间差内的信源随机变量相互依赖；非简单信源：信源在不同时刻发出的随机变量具有不同的概率分布。马尔可夫信源：信源随机过程是马尔可夫过程。

以下将顺序地叙述下面的相关概念：§3.1信源及其分类§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)§3.2离散无记忆（简单）信源的等长编码（2）设有一个含D个字母的字母表。对于(U1U2…UL)的每一个事件(u1u2…uL)，都用一个字母串(c1c2…)来表示。这种表示方法称为D元编码；每一个事件(u1u2…uL)所对应的字母串(c1c2…)称为一个码字。

例：离散无记忆简单信源发出的随机变量序列为：…U-2U-1U0U1U2…。其中U1的事件有3个：{晴,云,阴}。(U1U2)有9个事件{(晴晴),(晴云),(晴阴),(云晴),(云云),(云阴),(阴晴),(阴云),(阴阴)}。用字母表{0,1}对(U1U2)的事件进行2元编码如下：（晴晴）→0000，（晴云）→0001，（晴阴）→0011，（云晴）→0100，（云云）→0101，（云阴）→0111，（阴晴）→1100，（阴云）→1101，（阴阴）→1111。§3.2离散无记忆（简单）信源的等长编码（3）如果限定所有码字的长度都为N（即每个码字都是一个长度为N的字母串，或称为N维向量），则称此编码为等长编码，能够选择的不同码字的个数为DN。（4）如果限定每个码字的长度都≤N（即每个码字都是一个长度≤N的字母串），则称此编码为不等长编码，能够选择的不同码字的个数为D1+D2+…+DN=D(DN-1)/(D-1)。（注意：在不等长编码中，并不能同时使用D(DN-1)/(D-1)个不同的码字。一个长度为2的字母串究竟是两个长度为1的码字相连，还是一个长度为2的码字？无法识别。而在等长编码中不存在这样的识别问题）§3.2离散无记忆（简单）信源的等长编码（本节以下将专门讨论等长编码）（5）编码速率

R=NlogD/L。（单位时间内码可以携带的信息量，反映了码的能力）

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

：R=NlogD/L≤R0。§3.2离散无记忆（简单）信源的等长编码（6）无错编码

(U1U2…UL)的不同事件用不同的码字来表示。能够实现无错编码的充要条件是DN≥KL。

（即编码速率R=NlogD/L≥logK）（7）有错编码

(U1U2…UL)的有些不同事件用相同的码字来表示。（8）有错编码的译码方法与“译码错误”概率当使用有错编码时，必须给出译码方法（即：一个码字可能表示几个不同的事件，究竟翻译成哪个事件）。“译码错误”的概率定义为pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。§3.2离散无记忆（简单）信源的等长编码（9）在无错编码的前提下，编码的最低代价当R≥logK时，能够实现无错编码。（DN≥KL）当R<H(U1)时，无论怎样编码都是有错编码。这是因为R<H(U1)≤logK。（DN<KL）（如果H(U1)=logK，则以上两种情形已经概括了全部情形。但如果H(U1)<logK，则还有一种情形）当logK>R>H(U1)时，虽然无论怎样编码都是有错编码，但可以适当地编码和译码使译码错误的概率pe任意小。这就是所谓“渐进无错编码”。§3.2离散无记忆（简单）信源的等长编码（10）渐进无错编码（简单地说就是：当R>H(U1)时，可以适当地编码和译码使得译码错误的概率pe任意小。严格地说就是：）设给定了编码设备的编码速率R0，R0>H(U1)，则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的等长编码和对应的译码方法，满足①实际的编码速率R=NlogD/L≤R0，②译码错误的概率pe<ε。（11）渐进无错编码的原理大数定律。随着L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越来越小（→0），其发生的概率却越来越大（→1）。§3.2离散无记忆（简单）信源的等长编码（12）不能渐进无错的编码（简单地说就是：当R<H(U1)时，无论怎样编码和译码都不能使译码错误的概率pe任意小。严格地说就是：）设给定了编码设备的编码速率R0，R0<H(U1)。则无论怎样编码和译码都不能同时满足①实际的编码速率R≤R0，②译码错误的概率pe任意小。§3.2离散无记忆（简单）信源的等长编码设…U-2U-1U0U1U2…是离散无记忆（简单）信源的输出随机变量序列。设U1的概率分布为取Vl是Ul的如下函数：当Ul=ul时，Vl=loga[1/P(Ul=ul)],其中ul是某个事件ai。则①随机变量序列…V-2V-1V0V1V2…相互独立，具有相同的概率分布；§3.2离散无记忆（简单）信源的等长编码②(11)’渐进无错编码的实现-渐进无错编码定理取IL是(V1V2…VL)的如下函数：则①IL最终是(U1U2…UL)的函数；②③因此有切比雪夫不等式：对任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥§3.2离散无记忆（简单）信源的等长编码取定L0使得则当L≥L0时总有因此当L≥L0时总有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。§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)∈TU(L,ε)}≥1-ε。§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)+ε，§3.2离散无记忆（简单）信源的等长编码所以§3.2离散无记忆（简单）信源的等长编码系3.2.2(典型序列的数量，p58)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。证明一方面，§3.2离散无记忆（简单）信源的等长编码另一方面，§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）§3.2离散无记忆（简单）信源的等长编码定理3.2.2(无错编码正定理，p60)

给定编码设备的编码速率R0，R0>H(U)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的2元等长编码方法和对应的译码方法，①实际的编码速率R满足R0≥R>H(U)，②“译码错误”的概率pe<ε。§3.2离散无记忆（简单）信源的等长编码证明

首先声明，所有的对数计算都是以2为底的。此时实际的编码速率为R=N/L。任取正数ε≤(R0-H(U))/2，取补充引理所描述的L0，对于任意L>L0，取N=[LR0]，令R=N/L，即N=LR，则由补充引理的(1)可得R>H(U)+ε，从而，2N=2LR>2L(H(U)+ε)

再由系3.2.2，|TU(L,ε)|≤2L(H(U)+ε)≤2LR=2N

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

②“译码错误”的概率pe<ε。§3.2离散无记忆（简单）信源的等长编码渐进无错编码的步骤①由U1的概率分布计算②取L满足。③取整数N=[R0L]（R0L下取整）。④取典型序列集§3.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越大。§3.2离散无记忆（简单）信源的等长编码例设§3.2离散无记忆（简单）信源的等长编码设给定编码设备的编码速率R0=0.5。则R0>0.037587148=H(U1)。希望：①2元编码的实际编码速率R≤R0；②译码错误的概率不超过ε。取ε=0.1,找L使得§3.2离散无记忆（简单）信源的等长编码取L=253即可，再取N=[R0L]=126。

将TU(L,ε)中的事件用不同的N长2元码字来表示，而将TU(L,ε)以外的事件用一个固定的N长2元码字来表示，这个固定的N长2元码字已经用来表示了TU(L,ε)中的某个事件。

译码时，所有的码字均译为它所表示的TU(L,ε)中的事件。§3.2离散无记忆（简单）信源的等长编码注：在本题中，TU(L,ε)中的事件有更加简单的表达方式。当事件(u1u2…uL)中a1的个数为k，a2的个数为L-k时，§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.1)；§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)的个数为§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。§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时，§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.05)；当且仅当-0.05≤IL-H(U)≤0.05；§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)的个数为§3.2离散无记忆（简单）信源的等长编码§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。§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时，§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.01),当且仅当-0.01≤IL-H(U)≤0.01；当且仅当当且仅当当且仅当§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)的个数为§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。渐进无错编码的步骤①由U1的概率分布计算②对给定的错误控制概率取L满足③取整数N=[R0L]（R0L下取整）。回顾⑤将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越大。④取典型序列集练习设以上是一个离散无记忆信源。若对其输出的长为100的事件序列中含有两个和更少个的序列提供不同的码字。(a)在等长编码下，求二元码的最短码长N。(b)求错误概率(误组率)。§3.2离散无记忆（简单）信源的等长编码§3.2离散无记忆（简单）信源的等长编码定理3.2.2(无错编码反定理，p60)设给定编码设备的编码速率R0，满足R0<H(U)。当限制实际的编码速率R≤R0时，无论怎样编码和译码都不能使“译码错误”的概率任意小。（没有证明）§3.2离散无记忆（简单）信源的等长编码(12)’不能实现的渐进无错编码-无错编码反定理§3.3离散无记忆（简单）信源的不等长编码主要思想(1)先考虑L=1时的不等长编码；(2)再根据独立同分布性质推广到任意长的消息序列。§3.3离散无记忆（简单）信源的不等长编码（顺序地叙述以下的概念）(1)不等长编码的优越性总体上减少码字的长度。(2)不等长编码的特殊问题

①唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。§3.3离散无记忆（简单）信源的不等长编码解决方案：适当地编码，使得每个码字都具有识别标记。（注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2)连接成的字母串c(1)c(2)不能是码字）§3.3离散无记忆（简单）信源的不等长编码③实时译码和容量限制。②平均码字长度。设信源随机变量U的概率分布为{ak,q(ak),k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为希望小。解决方案：在事件与码字匹配时，概率大的事件用短码字。§3.3离散无记忆（简单）信源的不等长编码唯一可译性的解决方法一定义3.3.2(p63)若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。§3.3离散无记忆（简单）信源的不等长编码唯一可译性的解决方法二定义3.3.4(p63)若①事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。§3.3离散无记忆（简单）信源的不等长编码注解逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。（许多具体的异字头码有更加简便的识别码字的方法）§3.3离散无记忆（简单）信源的不等长编码例观察表3.3.1(p64)。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.12510111110111§3.3离散无记忆（简单）信源的不等长编码码A不是唯一可译的。码B不是唯一可译的。码C是唯一可译的，识别码字的方法为：见“0”或“111”就是一个码字的结束。实际上，码C是异字头码。码D是唯一可译的，识别码字的方法为：见“0”就是一个码字的开始。实际上，码D是逗点码，其中“0”是逗号。§3.3离散无记忆（简单）信源的不等长编码码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。§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级标号。…。§3.3离散无记忆（简单）信源的不等长编码如此一直到每个非空段不能再分（只含有一个事件）为止。此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。（当然，那些空段和它们的标号序列是没有用的，要去掉）为了使平均码长小，每次切分段时应使D段的概率尽可能相近。§3.3离散无记忆（简单）信源的不等长编码例.对下面消息源进行2-元Shannon—Fano编码编码结果：平均码长：§3.3离散无记忆（简单）信源的不等长编码例.对下面消息源进行3-元Shannon—Fano编码第一次分组：第二次分组：第三次分组：§3.3离散无记忆（简单）信源的不等长编码例.对下面消息源进行3-元Shannon—Fano编码编码结果：平均码长：§3.3离散无记忆（简单）信源的不等长编码异字头码的第二种构造方法：Huffman编码法（D元编码，字母表为{0,1,…,D-1}）(0)如果源随机变量的事件的个数K不是(D-1)的倍数加1，则添加若干0概率事件使得事件的个数是(D-1)的倍数加1。(1)将概率最小的D个事件分别赋予标号“0”到“D-1”。§3.3离散无记忆（简单）信源的不等长编码异字头码的第二种构造方法：Huffman编码法（D元编码，字母表为{0,1,…,D-1}）(2)将这D个事件合并为一个事件，其概率为这D个事件概率之和,并将这D个事件分别赋予标号“0”到“D-1”。重复(1)-(2)，直到事件的个数等于D。此时，一个事件的码字是这个事件从最后标号开始到最先标号为止的标号序列。(当然要去掉那些0概率事件和它们的标号序列)编码完毕。§3.3离散无记忆（简单）信源的不等长编码例.对下面消息源进行2元和3元的Huffman编码2元编码结果：平均码长：§3.3离散无记忆（简单）信源的不等长编码例.对下面消息源进行2-元和3元的Huffman编码3元编码结果：平均码长：§3.3离散无记忆（简单）信源的不等长编码为什么Shannon-Fano码和Huffman码都是异字头码？看右图，称这种图为码树。码树上的每个码字都结束在树梢。这种形状保证了码是异字头码。如果不是异字头码，则有的码字就不结束在树梢，而在中间节点。01010101010101010101§3.3离散无记忆（简单）信源的不等长编码定理3.3.1(Kraft不等式，p65)设信源随机变量共有K个事件。则：各码字长度分别为n1、n2、…、nK的D元异字头码存在的充分必要条件是§3.3离散无记忆（简单）信源的不等长编码证明不妨设n1≤n2≤…≤nK。则各码字长度分别为n1、n2、…、nK的D元异字头码存在，当且仅当：存在这样一个D叉树，树上有一个n1级树梢，再有一个n2级树梢，…，再有一个nK级树梢；当且仅当：存在nK级D叉满树，树上有个nK级树梢，§3.3离散无记忆（简单）信源的不等长编码再有个nK级树梢，…，再有个nK级树梢；当且仅当：§3.3离散无记忆（简单）信源的不等长编码定理3.3.2(p53)设信源随机变量共有K个事件，则：一个唯一可译的、各码字长度分别为n1、n2、…、nK的D元不等长码存在的充分必要条件是（不加证明）§3.3离散无记忆（简单）信源的不等长编码推论：设信源随机变量共有K个事件，则：一个唯一可译的、各码字长度分别为n1、n2、…、nK的D元不等长码存在的充分必要条件是存在各码字长度分别为n1、n2、…、nK的D元异字头码。作业：3.4对于有4个字母的离散无记忆源有两个码A和B，参看下表。试问：(a)各码是否满足异字头条件?是否为唯一可译码?(b)当收到1时得到多少关于字母a1的信息?(c)当收到1时得到多少关于信源的平均信息?字母概率码A码Ba1a2a3a4

0.40.30.20.110100100011101001000

§3.3离散无记忆（简单）信源的不等长编码定理3.3.3(p67)任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足§3.3离散无记忆（简单）信源的不等长编码如果唯一可译的D元不等长码的码字长度为证明设信源随机变量U的概率分布为§3.3离散无记忆（简单）信源的不等长编码则§3.3离散无记忆（简单）信源的不等长编码因此

另一方面，取n1、n2、…、nK，§3.3离散无记忆（简单）信源的不等长编码存在码字长度为

的唯一可译的D元不等长码。则：由于§3.3离散无记忆（简单）信源的不等长编码但此时，由于§3.3离散无记忆（简单）信源的不等长编码定理3.3.3的结论的推广(p68)现在对信源随机向量UL=(U1U2…UL)做唯一可译的D元不等长码。此时UL的事件的个数为KL。则任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足§3.3离散无记忆（简单）信源的不等长编码定义编码速率R和编码效率η分别为

任一唯一可译的D元不等长码总满足存在唯一可译的D元不等长码满足注解不等长编码与等长编码具有相似的性质：当L增大时，对UL的编码可以更加节省编码速率。但节省编码速率的下限是H(U)。§3.3离散无记忆（简单）信源的不等长编码例3.3.1（见p68）做2元编码。设；H(U)=0.811。§3.4最佳不等长编码“最佳不等长编码”是指，在唯一可译码中，平均码长最小的不等长编码。本节的结论是：Huffman编码法得到的D元码，是最佳不等长D元编码。鉴于证明的复杂性，以下只证明：Huffman编码法得到的2元码，是最佳不等长2元编码。

寻找最佳不等长编码，就是在唯一可译的前提下，使得2元码的平均码长最小。实际上是求解整数规划问题§3.4最佳不等长编码补充引理1信源随机变量U的最佳2元异字头码S，一定满足以下论断：“事件的概率越大，对应的码字越短”。证明如果2元异字头码S竟然不完全满足以上论断，则存在两个事件a和b，其概率具有不等式qa>qb，其码字长度也具有不等式na>nb。现在将事件a和b交换码字，其它事件的码字保持不变。此时2元异字头码S变成新的2元异字头码T。§3.4最佳不等长编码（1）码S中事件a和b的码字对平均码长的贡献为qana+qbnb；（2）码T中事件a和b的码字对平均码长的贡献为qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)>0。这就是说，码S的平均码长>码T的平均码长。因而码S不是最佳2元异字头码。用反证法已经证明了补充引理2。§3.4最佳不等长编码补充引理2设信源随机变量U的最佳2元异字头码S，则最长的码字至少有两个。证明如果2元异字头码S的最长的码字竟然只有一个。设这个码字为c，是事件a的码字。现在将c的最后一位去掉，成为c’，将c’仍然作为事件a的码字。其它事件的码字保持不变。此时2元异字头码S变成新的2元码T。注意到以下两点：（1）码T仍然是2元异字头码；（2）码S的平均码长>码T的平均码长。因而码S不是最佳2元异字头码。用反证法已经证明了补充引理3。§3.4最佳不等长编码补充引理3最佳2元异字头码S可以满足以下两条：（1）概率最小的两个事件码字最长，且长度相等；（2）它们的码字仅仅最后一位不同。证明取概率最小的事件a。在剩下的事件中取概率最小的事件b。根据补充引理1和补充引理2，事件a和事件b的码字最长，且长度相等。这就是说，最佳2元异字头码S显然满足第（1）条。§3.4最佳不等长编码关于第（2）条，分以下三种情形来讨论：情形一事件a和事件b的码字仅仅最后一位不同。情形二事件a和事件b的码字不是仅仅最后一位不同，但有第三个事件c，其码字与事件a的码字仅仅最后一位不同。情形三事件a和事件b的码字不是仅仅最后一位不同，也没有第三个事件c，其码字与事件a的码字仅仅最后一位不同。§3.4最佳不等长编码§3.4最佳不等长编码补充引理4信源随机变量的最佳2元异字头码，一定是该信源随机变量的最佳2元不等长码。（换句话说，寻找最佳2元不等长码，只要寻找最佳2元异字头码即可）证明设最佳2元异字头码的码字长度依次为设最佳2元不等长码的码字长度依次为首先有：§3.4最佳不等长编码取码字长度依次为其次，对于任意满足Craft不等式的码字长度依次为m1、m2、…、mK的2元不等长码，总存在码字长度依次为m1、m2、…、mK的2元异字头码。2元不等长码，§3.4最佳不等长编码则也存在具有相同码字长度的2元异字头码，而是最佳的2元异字头码的码长故有引理得证。§3.4最佳不等长编码补充定理

设信源随机变量U有K个事件，K≥3。(1)取出两个概率最小的事件：事件a和事件b。(2)将事件a与事件b合并成一个事件e，e的概率为事件a与事件b的概率之和；而将信源随机变量U的其它事件和其对应的概率保持不变。这样得到了新的信源随机变量U’。(3)找到U’的一个最佳2元异字头码R’。(4)将码R’中事件e的码字后面分别添加0和1，分别作为事件a和事件b各自的码字；而将码R’中其它事件的码字保持不变。这样得到了U的2元码R。则：码R是U的最佳2元异字头码。§3.4最佳不等长编码证明首先说明，码R是U的2元异字头码。码R中，事件a的码字不是事件b的码字的字头，事件b的码字也不是事件a的码字的字头.(两个码字长度相同，仅仅最后一位不同)事件a的码字或事件b的码字不是任何其它码字的字头(因为码R’中事件e的码字不是任何其它码字的字头)任何其它码字不是事件a的码字或事件b的码字的字头。（因为事件a或事件b的码字的字头，要么是码字本身，要么是码R’中事件e的码字的字头）综上所述，码R是U的2元异字头码。§3.4最佳不等长编码其次，任取U的2元异字头码S，要证明码R的平均码长≤码S的平均码长。对码S逐步进行如下的三次变换。§3.4最佳不等长编码§3.4最佳不等长编码容易看出，码T、码V、码W也都是信源随机变量U的2元异字头码。将码W中事件a的码字去掉最后一位，当作合并事件e的码字；将码W中其它事件的码字保持不变。这样得到了合并信源U’的2元码W’。容易看出码W’是U’的2元异字头码，因此码R’的平均码长≤码W’的平均码长。§3.4最佳不等长编码另一方面，码R的平均码长=码R’的平均码长+事件a的概率+事件b的概率；码W的平均码长=码W’的平均码长+事件a的概率+事件b的概率。所以:码R的平均码长≤码W的平均码长≤码V的平均码长≤码T的平均码长≤码S的平均码长。补充定理得证。§3.4最佳不等长编码补充定理给出了一种构造信源随机变量U的最佳2元异字头码的方法：(1)取出两个概率最小的事件a和事件b，分别标号为0和1；(2)然后将事件a和事件b合并成事件e，将信源随机变量U合并成U’；(3)寻找U’的最佳2元异字头码；(4)然后将该码中事件e的码字后面分别添加事件a和事件b的标号（0和1），分别成为事件a和事件b的码字。这种构造方法正是2元Huffman编码。§3.4最佳不等长编码定理对信源随机变量U的2元Huffman编码是最佳2元异字头码，因而是在唯一可译前提下的最佳2元不等长编码。3.6令离散无记忆信源如上。(a)求对U（即U1）的最佳二元码、平均码长和编码效率。(b)求对U2

（即U1U2）的最佳二元码、平均码长和编码效率。(c)求对U3（即U1U2U3）的最佳二元码、平均码长和编码效率。作业：§3.4最佳不等长编码算术编码设信源随机变量U的事件集为{0,1,…,K-1}，其相应的概率分布为P(k)(k=0,…,K-1)。定义信源符号的分布函数F(k)，(0,1,…,K-1,K)。其中F(0)=0；F(1)=P(0);F(2)=P(0)+P(1);…;

F(k)=P(0)+…+P(k-1),…,F(K)=P(0)+…+P(K-1)=1§3.4最佳不等长编码设要对信源序列L维随机变量UL=(U1U2…UL)进行2元编码。事件u=(u1u2…uL)。（1）令G=F(u1)，H=P(u1)。令l=1。（2）如果l=L，则转（4）。（如果l<L，则（3））（3）令G=G+HF(ul+1)，H=HP(ul+1)。令l=l+1。转（2）。§3.4最佳不等长编码（4）此时必然有G<1（可用数学归纳法证明）。计算将G表示成二进制小数。再将该小数的小数位数截断为n位，截断规则为：n位后面只要有非0的余数就要向第n位进位。最后得到了小数0.t。将t作为事件u=(u1u2…uL)的码字。§3.4最佳不等长编码练习

设离散无记忆信源为若信源输出序列为0100100001001000，试对其进行算术编码。答案：给事件对应的小区间左端点事件的概率故因而码字为算术编码的译码过程(0)s为若干个二元码字组成的比特串。记二进制有限小数S=0.s。(1)取u1满足F(u1)≤S<F(u1+1)。令G=F(u1)，H=P(u1)。令l=1。(2)如果l=L，则转（4）。（如果l<L，则（3））(3)取ul+1满足G+HF(ul+1)≤S<G+HF(ul+1+1)。令G=G+HF(ul+1)，H=HP(ul+1),令l=l+1。转（2）。§3.4最佳不等长编码算术编码的译码过程（4）记§3.4最佳不等长编码输出事件u=(u1u2…uL)。将s的前n位作为事件u=(u1u2…uL)的码字，并从s中去掉这个码字，得到新的比特串s。转（0）。§3.4最佳不等长编码练习

设离散无记忆信源为若序列00101010011是对上述信源长度L=4的信源的算术编码，试对其进行算术译码。答：首先计算该二进制小数的范围故进一步该二进制小数的范围故§3.4最佳不等长编码从而故进一步故进一步从而§3.4最佳不等长编码因为故故故考虑下一个码字（00101010011）故进一步该二进制小数的范围故§3.4最佳不等长编码从而故进一步故进一步从而§3.4最佳不等长编码因为故故因此所给2元串是码字00101与码字010011串接而成，它们分别是消息源0111和1010所对应的算术编码。对算术编码的解释(1)对于事件u=(u1u2…uL)，编码过程最终得到的H=P(u1)P(u2)…P(uL)=P(u)；G=F(u1)+P(u1)F(u2)+P(u1)P(u2)F(u3)+…+P(u1)P(u2)…P(uL-1)F(uL)。(2)每个事件u=(u1u2…uL)对应一个区间[G,G+H)，不同的事件u=(u1u2…uL)对应的区间[G,G+H)是互不相交的，而所有区间的并集合是区间[0,1)。§3.4最佳不等长编码对算术编码的解释(3)要将区间[G,G+H)的左端点G进行改造，成为事件u=(u1u2…uL)的码字。将G表示成二进制小数。再将该小数的小数位数截断为n位，截断规则为：n位后面只要有非0的余数就要向第n位进位。最后得到了小数0.t。t为u的码字。§3.4最佳不等长编码(4)请注意0.t是一个小数位数为n位的二进制小数。而n是巧妙设置的，所以0.t∈[G,G+H)。不仅如此，还有：将0.t的第n位小数位后面添加任意一个比特串，得到新的二进制小数0.s，则0.s∈[G,G+H)。换句话说，码字t后面添加任意若干个码字，组成比特串s，仍然能够在译码过程中找到正确的区间[G,G+H)。§3.4最佳不等长编码对算术编码的解释(5)译码过程找到正确区间[G,G+H)的同时，就找到了事件u=(u1u2…uL)，并在比特串s的前部确定了并去掉了码字t.§3.4最佳不等长编码对算术编码的解释而是则一般能正确译码，但也有译码错误的可能性！（思考）(6)如果n不是§3.4最佳不等长编码对算术编码的解释假设对消息(6)设取码字长度为进行编码，设其对应区间的左端点坐标为其对应概率为则恰有而不是因此码字为G的n位截断且向第n位进位，记为§3.4最佳不等长编码对算术编码的解释假设另一消息其码字为则消息u与u1的码字串接起来为从而对应的二进制小数为而S与G之间的差值这说明S已经不在区间[G,G+H)内，译码出错！§3.4最佳不等长编码对算术编码的解释假设对消息(6)设取码字长度为进行编码，设其对应区间的左端点坐标为其对应概率为则有因此码字为G的n+1位截断且向第n+1位进位，记为§3.4最佳不等长编码对算术编码的解释假设另一消息其码字为则消息u与u1的码字串接起来为从而对应的二进制小数为而S与G之间的差值这说明S必定在区间[G,G+H)内，译码不会出错！§3.4最佳不等长编码算术编码的平均码长可知：由码长的取法：§3.4最佳不等长编码算术编码的特点特点一当L很大时，平均码长接近信源熵H(U)，因此编码效率接近上限。特点二编译码简单，存储量小，速度快。（为什么？思考）算术编码的应用领域在图象数据压缩标准（如JPEG）中得到广泛应用。LZ编码

设信源随机变量U的事件集为A={a1,a2,…,aK}。设要对信源序列L维随机变量UL=(U1U2…UL)进行2元编码。事件u=(u1u2…uL)。首先进行的操作称为“分段”。分段是从前往后分，步骤如下。取最前面一个事件为一段。移动到后面。(2)(2.1)如果已经没有事件，则分段完毕。

(2.2)如果一个事件在前面各段的段首没有出现过，则取这个事件为一段。移动到后面。转（2）。§3.4最佳不等长编码(2.3)如果一个事件在前