信息论与编码理论基础 王育民(第三章)1-3

2024/6/231第三章：信源编码（一）

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

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

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

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

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

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

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

≥

logK(下界)2024/6/2321§3.2离散无记忆（简单）信源的等长编码编码速率

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

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

有错编码

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

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

：R=NlogD/L≤R0

2024/6/23242024/6/2325§3.2离散无记忆（简单）信源的等长编码有错编码的译码方法与“译码错误”概率当使用有错编码时，必须给出译码方法（即：一个码字可能表示几个不同的事件，究竟翻译成哪个事件）。“译码错误”的概率定义为pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的码字在译码时并不译为(u1u2…uL)}。2024/6/2326§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任意小。这就是所谓“渐进无错编码”。2024/6/2327§3.2离散无记忆（简单）信源的等长编码logKH(U1)·RRR无错编码不能渐进无错编码渐进无错编码○

·○○○2024/6/2328§3.2离散无记忆（简单）信源的等长编码渐进无错编码

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

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

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

严格地说就是：设给定了编码设备的编码速率R0，R0<H(U1)，则无论怎样编码和译码都不能同时满足①实际的编码速率R≤R0，②译码错误的概率pe任意小。2024/6/2332§3.2离散无记忆（简单）信源的等长编码设…U-2U-1U0U1U2…是离散无记忆（简单）信源的输出随机变量序列。设U1的概率分布为取Vl是Ul的如下函数：当Ul=ak时，Vl=loga(1/qk)。则①随机变量序列…V-2V-1V0V1V2…相互独立，具有相同的概率分布；②2024/6/2333§3.2离散无记忆（简单）信源的等长编码取IL是(V1V2…VL)的如下函数：则①IL最终是(U1U2…UL)的函数；②③因此有切比雪夫不等式：对任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥2024/6/2334§3.2离散无记忆（简单）信源的等长编码取定L0使得则当L≥L0时总有因此当L≥L0时总有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε。2024/6/2335§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/2336§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)+ε，2024/6/2337§3.2离散无记忆（简单）信源的等长编码所以2024/6/2338§3.2离散无记忆（简单）信源的等长编码系3.2.2(典型序列的数量，p52)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。证明一方面，2024/6/2339§3.2离散无记忆（简单）信源的等长编码另一方面，2024/6/2340§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）2024/6/2341§3.2离散无记忆（简单）信源的等长编码定理3.2.2(无错编码正定理，p53)

给定编码设备的编码速率R0，R0>H(U)。则对任意的ε>0，总存在一个L0，使得对任意的L>L0，都有对(U1U2…UL)的2元等长编码方法和对应的译码方法，①实际的编码速率R满足R0≥R>H(U)，②“译码错误”的概率pe<ε。2024/6/2342§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,ε)中的某个事件。2024/6/2343§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时，无论怎样编码和译码都不能使“译码错误”的概率任意小。（没有证明）2024/6/2344§3.2离散无记忆（简单）信源的等长编码渐进无错编码的要求给定离散无记忆简单信源：…U-2U-1U0U1U2…；给定编码设备的编码速率R0，满足R0>H(U)；给定一个任意小的正数ε>0；要求：选择合适的L，N，对(U1U2…UL)进行合适的2元N长编码，使得

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

②“译码错误”的概率pe<ε。2024/6/2345渐进无错编码的步骤①由U1的概率分布计算②取L满足。③取整数N=[R0L]（R0L下取整）。④取典型序列集2024/6/2346渐进无错编码的步骤⑤将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越大。）2024/6/2347§3.2离散无记忆（简单）信源的等长编码例设2024/6/2348§3.2离散无记忆（简单）信源的等长编码设给定编码设备的编码速率R0=0.5。则R0>0.037587148=H(U1)。希望：①2元编码的实际编码速率R≤R0；②译码错误的概率不超过ε。其中取ε=0.1。找L使得2024/6/2349§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时，2024/6/2350§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.1)；当且仅当2024/6/2351§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)的个数为2024/6/2352§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。2024/6/2353§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时，2024/6/2354§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.05)；当且仅当-0.05≤IL-H(U)≤0.05；当且仅当2024/6/2355§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)的个数为2024/6/2356§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。2024/6/2357§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时，2024/6/2358§3.2离散无记忆（简单）信源的等长编码事件(u1u2…uL)属于典型序列集TU(L,0.01)；当且仅当-0.01≤IL-H(U)≤0.01；当且仅当2024/6/2359§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)的个数为2024/6/2360§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。2024/6/2361§3.2离散无记忆（简单）信源的等长编码（直观理解）等长编码定理（信源划分定理）1.信源序列集=典型序列集（高概率集，>=1-\epsilon）+非典型序列集（低概率集）；2.将典型序列集中的信源序列一一编码（无错编码），而将非典型序列集中的信源序列编码成刚才的一个码字；3.典型序列集势约为2^{LH(U)}，占K^L少,非典型序列集势占多。2024/6/2362§3.3离散无记忆（简单）信源的不等长编码（顺序地叙述以下的概念）（1）不等长编码的优越性总体上减少码字的长度。（2）不等长编码的特殊问题

①唯一可译性，或者叫做可识别性。对于一个码，如果存在一种译码方法，使任意若干个码字所组成的字母串只能唯一地被翻译成这几个码字所对应的事件序列。这个码就被称为是唯一可译的。解决方案：适当地编码，使得每个码字都具有识别标记。（注解：一个唯一可译的、码字长度不超过N的D元码，其码字个数小于D(DN-1)/(D-1)个。这是因为两个码字c(1)和c(2)连接成的字母串c(1)c(2)不能是码字）2024/6/2363§3.3离散无记忆（简单）信源的不等长编码②平均码字长度。设信源随机变量U的概率分布为{ak,q(ak),k=1~K}，事件ak对应的码字长度为nk，则平均码字长度为希望小。解决方案：概率大的事件用短码字。③实时译码和容量限制。2024/6/2364§3.3离散无记忆（简单）信源的不等长编码唯一可译性的两种解决方法定义3.3.2(p55)若①事件与码字一一对应；②每个码字的开头部分都是一个相同的字母串；③这个字母串仅仅出现在码字的开头，不出现在码字的其它部位，也不出现在两个码字的结合部。则称这个字母串为逗号，称此码为逗点码。定义3.3.4(p55)若①事件与码字一一对应；②每个码字都不是另一个码字的开头部分（字头）。则称此码为异字头码。2024/6/2365§3.3离散无记忆（简单）信源的不等长编码注解逗点码显然是唯一可译的，识别码字的方法为：见到逗号就识别为一个码字的开始。异字头码也是唯一可译的，识别码字的方法为：见到一个码字就识别为一个码字。（许多具体的异字头码有更加简便的识别码字的方法）2024/6/2366§3.3离散无记忆（简单）信源的不等长编码例观察表3.3.1(p55)。事件概率码A码B码C码Da10.50000a20.25011001a30.125100110011a40.125101111101112024/6/2367§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。2024/6/2368§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级标号。…。2024/6/2369§3.3离散无记忆（简单）信源的不等长编码如此一直到每个非空段不能再分（只含有一个事件）为止。此时，一个事件的码字就是这个事件所在的段的标号序列，从1级标号到末级标号。（当然，那些空段和它们的标号序列是没有用的，要去掉）为了使平均码长小，每次切分段时应使D段的概率尽可能相近。（注解：当然可以把“切分段”操作换为“任意分组”操作，使D组的概率尽可能相近。这样可以使平均码长更小。但是，这不是一种有效的操作。）2024/6/2370例设有一单符号离散信源对该信源编二进制费诺码。信源符号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%2024/6/2371平均码长编码效率费诺码比较适合于每次分组概率都很接近的信源特别是对每次分组概率都相等的信源进行编码时,可达到理想的编码效率。2024/6/2372例有一单符号离散无记忆信源对该信源编二进制费诺码,编码过程如表:2024/6/2373信源熵为H(X)=2.75(比特/符号)平均码长为编码效率为

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

设单符号离散无记忆信源如下,要求对信源编二进制哈夫曼码。编码过程如下表信源符号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在图中读取码字的时候,要从后向前读,此时编出来的码字是可分离的异前置码。2024/6/2377熵平均码长为编码效率2024/6/2378D元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=D2024/6/2379哈夫曼的编法并不惟一。对二元Huffman编码，每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的,所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性,即能得到可分离码字。对D元Huffman编码，有类似结果。哈夫曼编码2024/6/2380哈夫曼编码不同的码元分配,得到的具体码字不同,但码长Ki不变,平均码长也不变,所以没有本质区别；缩减信源时,若合并后的新符号概率与其他符号概率相等,从编码方法上来说,这几个符号的次序可任意排列,编出的码都是正确的,但得到的码字不相同。不同的编法得到的码字长度Ki也不尽相同。2024/6/2381§3.3离散无记忆（简单）信源的不等长编码（为什么Shannon-Fano码和Huffman码都是异字头码？请看p62图3.4.1，p62图3.4.2。这些图都是树，称为码树，码树上的每个码字都在树梢。这种形状保证了码是异字头码。如果不是异字头码，则有的码字就不在树梢，而在中间节点。）P56,若一个码树的各分支都能延伸到最高级端点（共有D^{n_K}个码字），就称为满树，否则为非满树。若消息占满了所有的端节点，即树上每一个中间节点都有D个分支，称为全树。2024/6/2382定理3.3.1(Kraft不等式，p57)设信源随机变量共有K个事件。则：各码字长度分别为n1、n