信息論與編碼理論基礎(chǔ)(第3章)

第三章：信源編碼-離散信源無(wú)失真編碼§3.1信源及其分類(lèi)§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼§3.1信源及其分類(lèi)信源的概念

直觀地理解，信源就是信息的來(lái)源。但是這里必須要注意兩點(diǎn)：在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量。隨著時(shí)間的延續(xù)，信源發(fā)出一個(gè)又一個(gè)隨機(jī)變量，稱(chēng)之為一個(gè)隨機(jī)過(guò)程。因此，一般的信源種類(lèi)太多，其統(tǒng)計(jì)性質(zhì)太復(fù)雜。怎樣做工程實(shí)用的簡(jiǎn)化？離散信源信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)變量；隨著時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序列…U-2U-1U0U1U2…，其中(1)Uk為第k個(gè)時(shí)間段發(fā)出的隨機(jī)變量；(2)每個(gè)Uk都是一個(gè)離散型的隨機(jī)變量。離散無(wú)記憶信源離散無(wú)記憶信源是這樣的離散信源：隨機(jī)變量…、U-2、U-1、U0、U1、U2、…相互獨(dú)立。離散無(wú)記憶簡(jiǎn)單信源離散無(wú)記憶簡(jiǎn)單信源是這樣的離散無(wú)記憶信源：隨機(jī)變量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布?！?.1信源及其分類(lèi)總結(jié)：離散無(wú)記憶簡(jiǎn)單信源就是時(shí)間離散、事件離散、各隨機(jī)變量獨(dú)立同分布的信源。本課程學(xué)習(xí)所面對(duì)的信源將主要是離散無(wú)記憶簡(jiǎn)單信源。一般的信源

連續(xù)信源：有時(shí)間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴(lài)；有限記憶信源：在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴(lài)；非簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量具有不同的概率分布。馬爾可夫信源：信源隨機(jī)過(guò)程是馬爾可夫過(guò)程。

以下將順序地?cái)⑹鱿旅娴南嚓P(guān)概念：§3.1信源及其分類(lèi)§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（1）設(shè)有一個(gè)離散無(wú)記憶簡(jiǎn)單信源，信源發(fā)出的隨機(jī)變量序列為：…U-2U-1U0U1U2…。

設(shè)信源隨機(jī)變量U1的事件有K個(gè)：{a1,a2,…,aK}，則L維信源隨機(jī)向量(U1U2…UL)的事件有KL個(gè)：{(u1u2…uL)|其中每個(gè)分量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離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（2）設(shè)有一個(gè)含D個(gè)字母的字母表。對(duì)于(U1U2…UL)的每一個(gè)事件(u1u2…uL)，都用一個(gè)字母串(c1c2…)來(lái)表示。這種表示方法稱(chēng)為D元編碼；每一個(gè)事件(u1u2…uL)所對(duì)應(yīng)的字母串(c1c2…)稱(chēng)為一個(gè)碼字。

例：離散無(wú)記憶簡(jiǎn)單信源發(fā)出的隨機(jī)變量序列為：…U-2U-1U0U1U2…。其中U1的事件有3個(gè)：{晴,云,陰}。(U1U2)有9個(gè)事件{(晴晴),(晴云),(晴陰),(云晴),(云云),(云陰),(陰晴),(陰云),(陰陰)}。用字母表{0,1}對(duì)(U1U2)的事件進(jìn)行2元編碼如下：（晴晴）→0000，（晴云）→0001，（晴陰）→0011，（云晴）→0100，（云云）→0101，（云陰）→0111，（陰晴）→1100，（陰云）→1101，（陰陰）→1111?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（3）如果限定所有碼字的長(zhǎng)度都為N（即每個(gè)碼字都是一個(gè)長(zhǎng)度為N的字母串，或稱(chēng)為N維向量），則稱(chēng)此編碼為等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為DN。（4）如果限定每個(gè)碼字的長(zhǎng)度都≤N（即每個(gè)碼字都是一個(gè)長(zhǎng)度≤N的字母串），則稱(chēng)此編碼為不等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為D1+D2+…+DN=D(DN-1)/(D-1)。（注意：在不等長(zhǎng)編碼中，并不能同時(shí)使用D(DN-1)/(D-1)個(gè)不同的碼字。一個(gè)長(zhǎng)度為2的字母串究竟是兩個(gè)長(zhǎng)度為1的碼字相連，還是一個(gè)長(zhǎng)度為2的碼字？無(wú)法識(shí)別。而在等長(zhǎng)編碼中不存在這樣的識(shí)別問(wèn)題）§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（本節(jié)以下將專(zhuān)門(mén)討論等長(zhǎng)編碼）（5）編碼速率

R=NlogD/L。（單位時(shí)間內(nèi)碼可以攜帶的信息量，反映了碼的能力）

關(guān)于編碼速率的說(shuō)明：實(shí)際的編碼速率的計(jì)算公式為R=NlogD/L，似乎可以人為地任意設(shè)置N和L，因而可以人為地任意設(shè)置編碼速率。事實(shí)并非如此，存在著編碼設(shè)備的編碼速率R0，它是編碼設(shè)備的性能指標(biāo)。這就是說(shuō)，選擇N和L，必須使得實(shí)際的編碼速率NlogD/L不能超過(guò)編碼設(shè)備的編碼速率R0

：R=NlogD/L≤R0?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（6）無(wú)錯(cuò)編碼

(U1U2…UL)的不同事件用不同的碼字來(lái)表示。能夠?qū)崿F(xiàn)無(wú)錯(cuò)編碼的充要條件是DN≥KL。

（即編碼速率R=NlogD/L≥logK）（7）有錯(cuò)編碼

(U1U2…UL)的有些不同事件用相同的碼字來(lái)表示。（8）有錯(cuò)編碼的譯碼方法與“譯碼錯(cuò)誤”概率當(dāng)使用有錯(cuò)編碼時(shí)，必須給出譯碼方法（即：一個(gè)碼字可能表示幾個(gè)不同的事件，究竟翻譯成哪個(gè)事件）?！白g碼錯(cuò)誤”的概率定義為pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的碼字在譯碼時(shí)并不譯為(u1u2…uL)}?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（9）在無(wú)錯(cuò)編碼的前提下，編碼的最低代價(jià)當(dāng)R≥logK時(shí)，能夠?qū)崿F(xiàn)無(wú)錯(cuò)編碼。（DN≥KL）當(dāng)R<H(U1)時(shí)，無(wú)論怎樣編碼都是有錯(cuò)編碼。這是因?yàn)镽<H(U1)≤logK。（DN<KL）（如果H(U1)=logK，則以上兩種情形已經(jīng)概括了全部情形。但如果H(U1)<logK，則還有一種情形）當(dāng)logK>R>H(U1)時(shí)，雖然無(wú)論怎樣編碼都是有錯(cuò)編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯(cuò)誤的概率pe任意小。這就是所謂“漸進(jìn)無(wú)錯(cuò)編碼”?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（10）漸進(jìn)無(wú)錯(cuò)編碼（簡(jiǎn)單地說(shuō)就是：當(dāng)R>H(U1)時(shí)，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯(cuò)誤的概率pe任意小。嚴(yán)格地說(shuō)就是：）設(shè)給定了編碼設(shè)備的編碼速率R0，R0>H(U1)，則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的等長(zhǎng)編碼和對(duì)應(yīng)的譯碼方法，滿(mǎn)足①實(shí)際的編碼速率R=NlogD/L≤R0，②譯碼錯(cuò)誤的概率pe<ε。（11）漸進(jìn)無(wú)錯(cuò)編碼的原理大數(shù)定律。隨著L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越來(lái)越?。ā?），其發(fā)生的概率卻越來(lái)越大（→1）?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（12）不能漸進(jìn)無(wú)錯(cuò)的編碼（簡(jiǎn)單地說(shuō)就是：當(dāng)R<H(U1)時(shí)，無(wú)論怎樣編碼和譯碼都不能使譯碼錯(cuò)誤的概率pe任意小。嚴(yán)格地說(shuō)就是：）設(shè)給定了編碼設(shè)備的編碼速率R0，R0<H(U1)。則無(wú)論怎樣編碼和譯碼都不能同時(shí)滿(mǎn)足①實(shí)際的編碼速率R≤R0，②譯碼錯(cuò)誤的概率pe任意小?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)…U-2U-1U0U1U2…是離散無(wú)記憶（簡(jiǎn)單）信源的輸出隨機(jī)變量序列。設(shè)U1的概率分布為取Vl是Ul的如下函數(shù)：當(dāng)Ul=ul時(shí)，Vl=loga[1/P(Ul=ul)],其中ul是某個(gè)事件ai。則①隨機(jī)變量序列…V-2V-1V0V1V2…相互獨(dú)立，具有相同的概率分布；§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼②(11)’漸進(jìn)無(wú)錯(cuò)編碼的實(shí)現(xiàn)-漸進(jìn)無(wú)錯(cuò)編碼定理取IL是(V1V2…VL)的如下函數(shù)：則①I(mǎi)L最終是(U1U2…UL)的函數(shù)；②③因此有切比雪夫不等式：對(duì)任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取定L0使得則當(dāng)L≥L0時(shí)總有因此當(dāng)L≥L0時(shí)總有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥1-ε?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定義3.2.1(p57)定義TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，稱(chēng)TU(L,ε)為ε-典型序列集。稱(chēng)TU(L,ε)的補(bǔ)集為非ε-典型序列集。（綜上所述有）定理3.2.1(信源劃分定理，p58)對(duì)任意ε>0，取L0使得則當(dāng)L≥L0時(shí)總有P{(U1U2…UL)∈TU(L,ε)}≥1-ε。§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（簡(jiǎn)記H(U)=H(U1)。設(shè)以下的對(duì)數(shù)都是以2為底的。）系3.2.1(特定典型序列出現(xiàn)的概率，p58)若一個(gè)特定的事件(u1u2…uL)∈TU(L,ε)，則2-L(H(U)+ε)≤P{(U1U2…UL)=(u1u2…uL)}≤2-L(H(U)-ε)。證明設(shè)(u1u2…uL)∈TU(L,ε)。注意到此時(shí)

H(U)-ε≤IL≤H(U)+ε，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼所以§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼系3.2.2(典型序列的數(shù)量，p58)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。證明一方面，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼另一方面，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（如果采用2元編碼，且對(duì)數(shù)都是以2為底的，則編碼速率為R=NlogD/L=N/L。）補(bǔ)充引理

設(shè)給定一個(gè)R0>H(U)。對(duì)每個(gè)正整數(shù)L，對(duì)應(yīng)地取整數(shù)N=[R0L]（R0L的下取整）。則N/L≤R0，limL→+∞N/L=R0。進(jìn)而，任取正數(shù)ε≤(R0-H(U))/2，存在正整數(shù)L0，當(dāng)L>L0時(shí)（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離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理3.2.2(無(wú)錯(cuò)編碼正定理，p60)

給定編碼設(shè)備的編碼速率R0，R0>H(U)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的2元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，①實(shí)際的編碼速率R滿(mǎn)足R0≥R>H(U)，②“譯碼錯(cuò)誤”的概率pe<ε?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼證明

首先聲明，所有的對(duì)數(shù)計(jì)算都是以2為底的。此時(shí)實(shí)際的編碼速率為R=N/L。任取正數(shù)ε≤(R0-H(U))/2，取補(bǔ)充引理所描述的L0，對(duì)于任意L>L0，取N=[LR0]，令R=N/L，即N=LR，則由補(bǔ)充引理的(1)可得R>H(U)+ε，從而，2N=2LR>2L(H(U)+ε)

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

，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼這就是說(shuō)，典型序列集TU(L,ε)中的事件的個(gè)數(shù)不超過(guò)長(zhǎng)度為N的2元碼字的數(shù)量2N。因此，做如下的編碼：將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來(lái)表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來(lái)表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來(lái)表示了TU(L,ε)中的某個(gè)事件?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)應(yīng)的譯碼：所有的碼字均譯為它所表示的TU(L,ε)中的事件。結(jié)論：①實(shí)際的編碼速率R滿(mǎn)足R0≥R>H(U)；②“譯碼錯(cuò)誤”的概率pe=P((U1U2…UL)不屬于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得證。漸進(jìn)無(wú)錯(cuò)編碼的要求給定離散無(wú)記憶簡(jiǎn)單信源：…U-2U-1U0U1U2…；給定編碼設(shè)備的編碼速率R0，滿(mǎn)足R0>H(U)；給定一個(gè)任意小的正數(shù)ε>0；要求：選擇合適的L，N，對(duì)(U1U2…UL)進(jìn)行合適的2元N長(zhǎng)編碼，使得①實(shí)際的編碼速率R=N/L滿(mǎn)足R≤R0；

②“譯碼錯(cuò)誤”的概率pe<ε?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無(wú)錯(cuò)編碼的步驟①由U1的概率分布計(jì)算②取L滿(mǎn)足。③取整數(shù)N=[R0L]（R0L下取整）。④取典型序列集§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無(wú)錯(cuò)編碼的步驟⑤將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來(lái)表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來(lái)表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來(lái)表示了TU(L,ε)中的某個(gè)事件。⑥譯碼時(shí)，所有的碼字均譯為它所表示的TU(L,ε)中的事件。注解：顯然滿(mǎn)足R≤R0；|TU(L,ε)|≤2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)不屬于TU(L,ε)}<ε；一般來(lái)說(shuō)，ε越小，要求L越大，因此對(duì)應(yīng)的N越大?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼例設(shè)§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)給定編碼設(shè)備的編碼速率R0=0.5。則R0>0.037587148=H(U1)。希望：①2元編碼的實(shí)際編碼速率R≤R0；②譯碼錯(cuò)誤的概率不超過(guò)ε。取ε=0.1,找L使得§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取L=253即可，再取N=[R0L]=126。

將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來(lái)表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來(lái)表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來(lái)表示了TU(L,ε)中的某個(gè)事件。

譯碼時(shí)，所有的碼字均譯為它所表示的TU(L,ε)中的事件?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼注：在本題中，TU(L,ε)中的事件有更加簡(jiǎn)單的表達(dá)方式。當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.1)；§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)事件(u1u2…u253)中a1的個(gè)數(shù)不超過(guò)4時(shí)，(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)的個(gè)數(shù)為§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=253，對(duì)應(yīng)地取整數(shù)N=[R0L]=126。則N/L<R0，這就是說(shuō)2元編碼的實(shí)際編碼速率并未超出編碼設(shè)備的編碼速率。2元編碼的編碼方法：將TU(253,0.1)中的事件用不同的126長(zhǎng)碼字表示；將TU(253,0.1)外的事件用同一個(gè)126長(zhǎng)碼字表示，該碼字已經(jīng)用于表示了TU(253,0.1)中的一個(gè)事件。

由于|TU(253,0.1)|≤233.355557444<2126，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(253,0.1)中的事件(u1u2…u253)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u253)不屬于TU(253,0.1))≤ε=0.1?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取ε=0.05。找L使得即L=2020。有P{(U1U2…UL)=(u1u2…uL)|

-0.05≤IL-H(U)≤0.05}≥0.95。另一方面，當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.05)；當(dāng)且僅當(dāng)-0.05≤IL-H(U)≤0.05；§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)設(shè)L=2020。此時(shí)0.01028137L=20.7683674。當(dāng)事件(u1u2…u2020)中a1的個(gè)數(shù)不超過(guò)20時(shí)，(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)的個(gè)數(shù)為§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=2020，對(duì)應(yīng)地取整數(shù)N=[R0L]=1010。則N/L=R0，這就是說(shuō)2元編碼的實(shí)際編碼速率等于編碼設(shè)備的編碼速率。2元編碼的編碼方法：將TU(2020,0.05)中的事件用不同的1010長(zhǎng)碼字表示；將TU(2020,0.05)外的事件用同一個(gè)1010長(zhǎng)碼字表示，該碼字已經(jīng)用于表示了TU(2020,0.05)中的一個(gè)事件。由于|TU(2020,0.05)|≤2176.92603896<21010，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(2020,0.05)中的事件(u1u2…u2020)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u2020)不屬于TU(2020,0.05))≤ε=0.05?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取ε=0.01。找L使得即L=252435。有P{(U1U2…UL)=(u1u2…uL)|

-0.01≤IL-H(U)≤0.01}≥0.99。另一方面，當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.01),當(dāng)且僅當(dāng)-0.01≤IL-H(U)≤0.01；當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)L=252435。此時(shí)0.00274372L=692.61096；0.00525628L=1326.8690。

當(dāng)事件(u1u2…u252435)中a1的個(gè)數(shù)不超出閉區(qū)間[693，1326]內(nèi)時(shí)，(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)的個(gè)數(shù)為§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=252435，對(duì)應(yīng)地取整數(shù)N=[R0L]=126217。則N/L<R0，這就是說(shuō)2元編碼的實(shí)際編碼速率小于編碼設(shè)備的編碼速率。2元編碼的編碼方法：將TU(252435,0.01)中的事件用不同的126217長(zhǎng)碼字表示；將TU(252435,0.01)外的事件用同一個(gè)126217長(zhǎng)碼字表示，該碼字已經(jīng)用于表示了TU(252435,0.01)中的一個(gè)事件。由于|TU(252435,0.01)|≤212012.6617<2126217，碼字足夠用。2元編碼的譯碼方法：將碼字譯為它所表示的TU(252435,0.01)中的事件(u1u2…u252435)。于是，譯碼錯(cuò)誤的概率為P((u1u2…u252435)不屬于TU(252435,0.01))≤ε=0.01。漸進(jìn)無(wú)錯(cuò)編碼的步驟①由U1的概率分布計(jì)算②對(duì)給定的錯(cuò)誤控制概率取L滿(mǎn)足③取整數(shù)N=[R0L]（R0L下取整）。回顧⑤將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來(lái)表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來(lái)表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來(lái)表示了TU(L,ε)中的某個(gè)事件。⑥譯碼時(shí)，所有的碼字均譯為它所表示的TU(L,ε)中的事件。注解：顯然滿(mǎn)足R≤R0；|TU(L,ε)|≤2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)不屬于TU(L,ε)}<ε；一般來(lái)說(shuō)，ε越小，要求L越大，因此對(duì)應(yīng)的N越大。④取典型序列集練習(xí)設(shè)以上是一個(gè)離散無(wú)記憶信源。若對(duì)其輸出的長(zhǎng)為100的事件序列中含有兩個(gè)和更少個(gè)的序列提供不同的碼字。(a)在等長(zhǎng)編碼下，求二元碼的最短碼長(zhǎng)N。(b)求錯(cuò)誤概率(誤組率)?！?.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理3.2.2(無(wú)錯(cuò)編碼反定理，p60)設(shè)給定編碼設(shè)備的編碼速率R0，滿(mǎn)足R0<H(U)。當(dāng)限制實(shí)際的編碼速率R≤R0時(shí)，無(wú)論怎樣編碼和譯碼都不能使“譯碼錯(cuò)誤”的概率任意小。（沒(méi)有證明）§3.2離散無(wú)記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼(12)’不能實(shí)現(xiàn)的漸進(jìn)無(wú)錯(cuò)編碼-無(wú)錯(cuò)編碼反定理§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼主要思想(1)先考慮L=1時(shí)的不等長(zhǎng)編碼；(2)再根據(jù)獨(dú)立同分布性質(zhì)推廣到任意長(zhǎng)的消息序列?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（順序地?cái)⑹鲆韵碌母拍睿?1)不等長(zhǎng)編碼的優(yōu)越性總體上減少碼字的長(zhǎng)度。(2)不等長(zhǎng)編碼的特殊問(wèn)題

①唯一可譯性，或者叫做可識(shí)別性。對(duì)于一個(gè)碼，如果存在一種譯碼方法，使任意若干個(gè)碼字所組成的字母串只能唯一地被翻譯成這幾個(gè)碼字所對(duì)應(yīng)的事件序列。這個(gè)碼就被稱(chēng)為是唯一可譯的?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼解決方案：適當(dāng)?shù)鼐幋a，使得每個(gè)碼字都具有識(shí)別標(biāo)記。（注解：一個(gè)唯一可譯的、碼字長(zhǎng)度不超過(guò)N的D元碼，其碼字個(gè)數(shù)小于D(DN-1)/(D-1)個(gè)。這是因?yàn)閮蓚€(gè)碼字c(1)和c(2)連接成的字母串c(1)c(2)不能是碼字）§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼③實(shí)時(shí)譯碼和容量限制。②平均碼字長(zhǎng)度。設(shè)信源隨機(jī)變量U的概率分布為{ak,q(ak),k=1~K}，事件ak對(duì)應(yīng)的碼字長(zhǎng)度為nk，則平均碼字長(zhǎng)度為希望小。解決方案：在事件與碼字匹配時(shí)，概率大的事件用短碼字?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼唯一可譯性的解決方法一定義3.3.2(p63)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字的開(kāi)頭部分都是一個(gè)相同的字母串；③這個(gè)字母串僅僅出現(xiàn)在碼字的開(kāi)頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個(gè)碼字的結(jié)合部。則稱(chēng)這個(gè)字母串為逗號(hào)，稱(chēng)此碼為逗點(diǎn)碼?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼唯一可譯性的解決方法二定義3.3.4(p63)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字都不是另一個(gè)碼字的開(kāi)頭部分（字頭）。則稱(chēng)此碼為異字頭碼?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼注解逗點(diǎn)碼顯然是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)到逗號(hào)就識(shí)別為一個(gè)碼字的開(kāi)始。異字頭碼也是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)到一個(gè)碼字就識(shí)別為一個(gè)碼字。（許多具體的異字頭碼有更加簡(jiǎn)便的識(shí)別碼字的方法）§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例觀察表3.3.1(p64)。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.12510111110111§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)“0”或“111”就是一個(gè)碼字的結(jié)束。實(shí)際上，碼C是異字頭碼。碼D是唯一可譯的，識(shí)別碼字的方法為：見(jiàn)“0”就是一個(gè)碼字的開(kāi)始。實(shí)際上，碼D是逗點(diǎn)碼，其中“0”是逗號(hào)?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼碼C不是逗點(diǎn)碼。碼D不是異字頭碼。碼C的平均碼長(zhǎng)比碼D的平均碼長(zhǎng)?。捍aC的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+3×0.125=1.75；碼D的平均碼長(zhǎng)為1×0.5+2×0.25+3×0.125+4×0.125=1.875?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第一種構(gòu)造方法：Shannon-Fano編碼法（D元編碼，字母表為{0,1,…,D-1}）

(1)將源隨機(jī)變量的事件按概率從大到小排成一行。(2)將此行切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱(chēng)為1級(jí)標(biāo)號(hào)。(3)將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱(chēng)為2級(jí)標(biāo)號(hào)。(4)將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱(chēng)為3級(jí)標(biāo)號(hào)?！??！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼如此一直到每個(gè)非空段不能再分（只含有一個(gè)事件）為止。此時(shí)，一個(gè)事件的碼字就是這個(gè)事件所在的段的標(biāo)號(hào)序列，從1級(jí)標(biāo)號(hào)到末級(jí)標(biāo)號(hào)。（當(dāng)然，那些空段和它們的標(biāo)號(hào)序列是沒(méi)有用的，要去掉）為了使平均碼長(zhǎng)小，每次切分段時(shí)應(yīng)使D段的概率盡可能相近?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例.對(duì)下面消息源進(jìn)行2-元Shannon—Fano編碼編碼結(jié)果：平均碼長(zhǎng)：§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例.對(duì)下面消息源進(jìn)行3-元Shannon—Fano編碼第一次分組：第二次分組：第三次分組：§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例.對(duì)下面消息源進(jìn)行3-元Shannon—Fano編碼編碼結(jié)果：平均碼長(zhǎng)：§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法（D元編碼，字母表為{0,1,…,D-1}）(0)如果源隨機(jī)變量的事件的個(gè)數(shù)K不是(D-1)的倍數(shù)加1，則添加若干0概率事件使得事件的個(gè)數(shù)是(D-1)的倍數(shù)加1。(1)將概率最小的D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法（D元編碼，字母表為{0,1,…,D-1}）(2)將這D個(gè)事件合并為一個(gè)事件，其概率為這D個(gè)事件概率之和,并將這D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”。重復(fù)(1)-(2)，直到事件的個(gè)數(shù)等于D。此時(shí)，一個(gè)事件的碼字是這個(gè)事件從最后標(biāo)號(hào)開(kāi)始到最先標(biāo)號(hào)為止的標(biāo)號(hào)序列。(當(dāng)然要去掉那些0概率事件和它們的標(biāo)號(hào)序列)編碼完畢?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例.對(duì)下面消息源進(jìn)行2元和3元的Huffman編碼2元編碼結(jié)果：平均碼長(zhǎng)：§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例.對(duì)下面消息源進(jìn)行2-元和3元的Huffman編碼3元編碼結(jié)果：平均碼長(zhǎng)：§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼為什么Shannon-Fano碼和Huffman碼都是異字頭碼？看右圖，稱(chēng)這種圖為碼樹(shù)。碼樹(shù)上的每個(gè)碼字都結(jié)束在樹(shù)梢。這種形狀保證了碼是異字頭碼。如果不是異字頭碼，則有的碼字就不結(jié)束在樹(shù)梢，而在中間節(jié)點(diǎn)。01010101010101010101§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.1(Kraft不等式，p65)設(shè)信源隨機(jī)變量共有K個(gè)事件。則：各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在的充分必要條件是§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼證明不妨設(shè)n1≤n2≤…≤nK。則各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在，當(dāng)且僅當(dāng)：存在這樣一個(gè)D叉樹(shù)，樹(shù)上有一個(gè)n1級(jí)樹(shù)梢，再有一個(gè)n2級(jí)樹(shù)梢，…，再有一個(gè)nK級(jí)樹(shù)梢；當(dāng)且僅當(dāng)：存在nK級(jí)D叉滿(mǎn)樹(shù)，樹(shù)上有個(gè)nK級(jí)樹(shù)梢，§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼再有個(gè)nK級(jí)樹(shù)梢，…，再有個(gè)nK級(jí)樹(shù)梢；當(dāng)且僅當(dāng)：§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.2(p53)設(shè)信源隨機(jī)變量共有K個(gè)事件，則：一個(gè)唯一可譯的、各碼字長(zhǎng)度分別為n1、n2、…、nK的D元不等長(zhǎng)碼存在的充分必要條件是（不加證明）§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼推論：設(shè)信源隨機(jī)變量共有K個(gè)事件，則：一個(gè)唯一可譯的、各碼字長(zhǎng)度分別為n1、n2、…、nK的D元不等長(zhǎng)碼存在的充分必要條件是存在各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼。作業(yè)：3.4對(duì)于有4個(gè)字母的離散無(wú)記憶源有兩個(gè)碼A和B，參看下表。試問(wèn)：(a)各碼是否滿(mǎn)足異字頭條件?是否為唯一可譯碼?(b)當(dāng)收到1時(shí)得到多少關(guān)于字母a1的信息?(c)當(dāng)收到1時(shí)得到多少關(guān)于信源的平均信息?字母概率碼A碼Ba1a2a3a4

0.40.30.20.110100100011101001000

§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.3(p67)任一唯一可譯的D元不等長(zhǎng)碼總滿(mǎn)足存在唯一可譯的D元不等長(zhǎng)碼滿(mǎn)足§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼如果唯一可譯的D元不等長(zhǎng)碼的碼字長(zhǎng)度為證明設(shè)信源隨機(jī)變量U的概率分布為§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼則§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼因此

另一方面，取n1、n2、…、nK，§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼存在碼字長(zhǎng)度為

的唯一可譯的D元不等長(zhǎng)碼。則：由于§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼但此時(shí)，由于§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.3的結(jié)論的推廣(p68)現(xiàn)在對(duì)信源隨機(jī)向量UL=(U1U2…UL)做唯一可譯的D元不等長(zhǎng)碼。此時(shí)UL的事件的個(gè)數(shù)為KL。則任一唯一可譯的D元不等長(zhǎng)碼總滿(mǎn)足存在唯一可譯的D元不等長(zhǎng)碼滿(mǎn)足§3.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定義編碼速率R和編碼效率η分別為

任一唯一可譯的D元不等長(zhǎng)碼總滿(mǎn)足存在唯一可譯的D元不等長(zhǎng)碼滿(mǎn)足注解不等長(zhǎng)編碼與等長(zhǎng)編碼具有相似的性質(zhì)：當(dāng)L增大時(shí)，對(duì)UL的編碼可以更加節(jié)省編碼速率。但節(jié)省編碼速率的下限是H(U)?！?.3離散無(wú)記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例3.3.1（見(jiàn)p68）做2元編碼。設(shè)；H(U)=0.811?！?.4最佳不等長(zhǎng)編碼“最佳不等長(zhǎng)編碼”是指，在唯一可譯碼中，平均碼長(zhǎng)最小的不等長(zhǎng)編碼。本節(jié)的結(jié)論是：Huffman編碼法得到的D元碼，是最佳不等長(zhǎng)D元編碼。鑒于證明的復(fù)雜性，以下只證明：Huffman編碼法得到的2元碼，是最佳不等長(zhǎng)2元編碼。

尋找最佳不等長(zhǎng)編碼，就是在唯一可譯的前提下，使得2元碼的平均碼長(zhǎng)最小。實(shí)際上是求解整數(shù)規(guī)劃問(wèn)題§3.4最佳不等長(zhǎng)編碼補(bǔ)充引理1信源隨機(jī)變量U的最佳2元異字頭碼S，一定滿(mǎn)足以下論斷：“事件的概率越大，對(duì)應(yīng)的碼字越短”。證明如果2元異字頭碼S竟然不完全滿(mǎn)足以上論斷，則存在兩個(gè)事件a和b，其概率具有不等式qa>qb，其碼字長(zhǎng)度也具有不等式na>nb?，F(xiàn)在將事件a和b交換碼字，其它事件的碼字保持不變。此時(shí)2元異字頭碼S變成新的2元異字頭碼T?！?.4最佳不等長(zhǎng)編碼（1）碼S中事件a和b的碼字對(duì)平均碼長(zhǎng)的貢獻(xiàn)為qana+qbnb；（2）碼T中事件a和b的碼字對(duì)平均碼長(zhǎng)的貢獻(xiàn)為qanb+qbna。(qana+qbnb)-(qanb+qbna)=(qa-qb)(na-nb)>0。這就是說(shuō)，碼S的平均碼長(zhǎng)>碼T的平均碼長(zhǎng)。因而碼S不是最佳2元異字頭碼。用反證法已經(jīng)證明了補(bǔ)充引理2?！?.4最佳不等長(zhǎng)編碼補(bǔ)充引理2設(shè)信源隨機(jī)變量U的最佳2元異字頭碼S，則最長(zhǎng)的碼字至少有兩個(gè)。證明如果2元異字頭碼S的最長(zhǎng)的碼字竟然只有一個(gè)。設(shè)這個(gè)碼字為c，是事件a的碼字?，F(xiàn)在將c的最后一位去掉，成為c’，將c’仍然作為事件a的碼字。其它事件的碼字保持不變。此時(shí)2元異字頭碼S變成新的2元碼T。注意到以下兩點(diǎn)：（1）碼T仍然是2元異字頭碼；（2）碼S的平均碼長(zhǎng)>碼T的平均碼長(zhǎng)。因而碼S不是最佳2元異字頭碼。用反證法已經(jīng)證明了補(bǔ)充引理3?！?.4最佳不等長(zhǎng)編碼補(bǔ)充引理3最佳2元異字頭碼S可以滿(mǎn)足以下兩條：（1）概率最小的兩個(gè)事件碼字最長(zhǎng)，且長(zhǎng)度相等；（2）它們的碼字僅僅最后一位不同。證明取概率最小的事件a。在剩下的事件中取概率最小的事件b。根據(jù)補(bǔ)充引理1和補(bǔ)充引理2，事件a和事件b的碼字最長(zhǎng)，且長(zhǎng)度相等。這就是說(shuō)，最佳2元異字頭碼S顯然滿(mǎn)足第（1）條?！?.4最佳不等長(zhǎng)編碼關(guān)于第（2）條，分以下三種情形來(lái)討論：情形一事件a和事件b的碼字僅僅最后一位不同。情形二事件a和事件b的碼字不是僅僅最后一位不同，但有第三個(gè)事件c，其碼字與事件a的碼字僅僅最后一位不同。情形三事件a和事件b的碼字不是僅僅最后一位不同，也沒(méi)有第三個(gè)事件c，其碼字與事件a的碼字僅僅最后一位不同?！?.4最佳不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼補(bǔ)充引理4信源隨機(jī)變量的最佳2元異字頭碼，一定是該信源隨機(jī)變量的最佳2元不等長(zhǎng)碼。（換句話說(shuō)，尋找最佳2元不等長(zhǎng)碼，只要尋找最佳2元異字頭碼即可）證明設(shè)最佳2元異字頭碼的碼字長(zhǎng)度依次為設(shè)最佳2元不等長(zhǎng)碼的碼字長(zhǎng)度依次為首先有：§3.4最佳不等長(zhǎng)編碼取碼字長(zhǎng)度依次為其次，對(duì)于任意滿(mǎn)足Craft不等式的碼字長(zhǎng)度依次為m1、m2、…、mK的2元不等長(zhǎng)碼，總存在碼字長(zhǎng)度依次為m1、m2、…、mK的2元異字頭碼。2元不等長(zhǎng)碼，§3.4最佳不等長(zhǎng)編碼則也存在具有相同碼字長(zhǎng)度的2元異字頭碼，而是最佳的2元異字頭碼的碼長(zhǎng)故有引理得證?！?.4最佳不等長(zhǎng)編碼補(bǔ)充定理

設(shè)信源隨機(jī)變量U有K個(gè)事件，K≥3。(1)取出兩個(gè)概率最小的事件：事件a和事件b。(2)將事件a與事件b合并成一個(gè)事件e，e的概率為事件a與事件b的概率之和；而將信源隨機(jī)變量U的其它事件和其對(duì)應(yīng)的概率保持不變。這樣得到了新的信源隨機(jī)變量U’。(3)找到U’的一個(gè)最佳2元異字頭碼R’。(4)將碼R’中事件e的碼字后面分別添加0和1，分別作為事件a和事件b各自的碼字；而將碼R’中其它事件的碼字保持不變。這樣得到了U的2元碼R。則：碼R是U的最佳2元異字頭碼?！?.4最佳不等長(zhǎng)編碼證明首先說(shuō)明，碼R是U的2元異字頭碼。碼R中，事件a的碼字不是事件b的碼字的字頭，事件b的碼字也不是事件a的碼字的字頭.(兩個(gè)碼字長(zhǎng)度相同，僅僅最后一位不同)事件a的碼字或事件b的碼字不是任何其它碼字的字頭(因?yàn)榇aR’中事件e的碼字不是任何其它碼字的字頭)任何其它碼字不是事件a的碼字或事件b的碼字的字頭。（因?yàn)槭录或事件b的碼字的字頭，要么是碼字本身，要么是碼R’中事件e的碼字的字頭）綜上所述，碼R是U的2元異字頭碼?！?.4最佳不等長(zhǎng)編碼其次，任取U的2元異字頭碼S，要證明碼R的平均碼長(zhǎng)≤碼S的平均碼長(zhǎng)。對(duì)碼S逐步進(jìn)行如下的三次變換?！?.4最佳不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼容易看出，碼T、碼V、碼W也都是信源隨機(jī)變量U的2元異字頭碼。將碼W中事件a的碼字去掉最后一位，當(dāng)作合并事件e的碼字；將碼W中其它事件的碼字保持不變。這樣得到了合并信源U’的2元碼W’。容易看出碼W’是U’的2元異字頭碼，因此碼R’的平均碼長(zhǎng)≤碼W’的平均碼長(zhǎng)?！?.4最佳不等長(zhǎng)編碼另一方面，碼R的平均碼長(zhǎng)=碼R’的平均碼長(zhǎng)+事件a的概率+事件b的概率；碼W的平均碼長(zhǎng)=碼W’的平均碼長(zhǎng)+事件a的概率+事件b的概率。所以:碼R的平均碼長(zhǎng)≤碼W的平均碼長(zhǎng)≤碼V的平均碼長(zhǎng)≤碼T的平均碼長(zhǎng)≤碼S的平均碼長(zhǎng)。補(bǔ)充定理得證?！?.4最佳不等長(zhǎng)編碼補(bǔ)充定理給出了一種構(gòu)造信源隨機(jī)變量U的最佳2元異字頭碼的方法：(1)取出兩個(gè)概率最小的事件a和事件b，分別標(biāo)號(hào)為0和1；(2)然后將事件a和事件b合并成事件e，將信源隨機(jī)變量U合并成U’；(3)尋找U’的最佳2元異字頭碼；(4)然后將該碼中事件e的碼字后面分別添加事件a和事件b的標(biāo)號(hào)（0和1），分別成為事件a和事件b的碼字。這種構(gòu)造方法正是2元Huffman編碼?！?.4最佳不等長(zhǎng)編碼定理對(duì)信源隨機(jī)變量U的2元Huffman編碼是最佳2元異字頭碼，因而是在唯一可譯前提下的最佳2元不等長(zhǎng)編碼。3.6令離散無(wú)記憶信源如上。(a)求對(duì)U（即U1）的最佳二元碼、平均碼長(zhǎng)和編碼效率。(b)求對(duì)U2

（即U1U2）的最佳二元碼、平均碼長(zhǎng)和編碼效率。(c)求對(duì)U3（即U1U2U3）的最佳二元碼、平均碼長(zhǎng)和編碼效率。作業(yè)：§3.4最佳不等長(zhǎng)編碼算術(shù)編碼設(shè)信源隨機(jī)變量U的事件集為{0,1,…,K-1}，其相應(yīng)的概率分布為P(k)(k=0,…,K-1)。定義信源符號(hào)的分布函數(shù)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最佳不等長(zhǎng)編碼設(shè)要對(duì)信源序列L維隨機(jī)變量UL=(U1U2…UL)進(jìn)行2元編碼。事件u=(u1u2…uL)。（1）令G=F(u1)，H=P(u1)。令l=1。（2）如果l=L，則轉(zhuǎn)（4）。（如果l<L，則（3））（3）令G=G+HF(ul+1)，H=HP(ul+1)。令l=l+1。轉(zhuǎn)（2）?！?.4最佳不等長(zhǎng)編碼（4）此時(shí)必然有G<1（可用數(shù)學(xué)歸納法證明）。計(jì)算將G表示成二進(jìn)制小數(shù)。再將該小數(shù)的小數(shù)位數(shù)截?cái)酁閚位，截?cái)嘁?guī)則為：n位后面只要有非0的余數(shù)就要向第n位進(jìn)位。最后得到了小數(shù)0.t。將t作為事件u=(u1u2…uL)的碼字?！?.4最佳不等長(zhǎng)編碼練習(xí)

設(shè)離散無(wú)記憶信源為若信源輸出序列為0100100001001000，試對(duì)其進(jìn)行算術(shù)編碼。答案：給事件對(duì)應(yīng)的小區(qū)間左端點(diǎn)事件的概率故因而碼字為算術(shù)編碼的譯碼過(guò)程(0)s為若干個(gè)二元碼字組成的比特串。記二進(jìn)制有限小數(shù)S=0.s。(1)取u1滿(mǎn)足F(u1)≤S<F(u1+1)。令G=F(u1)，H=P(u1)。令l=1。(2)如果l=L，則轉(zhuǎn)（4）。（如果l<L，則（3））(3)取ul+1滿(mǎn)足G+HF(ul+1)≤S<G+HF(ul+1+1)。令G=G+HF(ul+1)，H=HP(ul+1),令l=l+1。轉(zhuǎn)（2）?！?.4最佳不等長(zhǎng)編碼算術(shù)編碼的譯碼過(guò)程（4）記§3.4最佳不等長(zhǎng)編碼輸出事件u=(u1u2…uL)。將s的前n位作為事件u=(u1u2…uL)的碼字，并從s中去掉這個(gè)碼字，得到新的比特串s。轉(zhuǎn)（0）?！?.4最佳不等長(zhǎng)編碼練習(xí)

設(shè)離散無(wú)記憶信源為若序列00101010011是對(duì)上述信源長(zhǎng)度L=4的信源的算術(shù)編碼，試對(duì)其進(jìn)行算術(shù)譯碼。答：首先計(jì)算該二進(jìn)制小數(shù)的范圍故進(jìn)一步該二進(jìn)制小數(shù)的范圍故§3.4最佳不等長(zhǎng)編碼從而故進(jìn)一步故進(jìn)一步從而§3.4最佳不等長(zhǎng)編碼因?yàn)楣使使士紤]下一個(gè)碼字（00101010011）故進(jìn)一步該二進(jìn)制小數(shù)的范圍故§3.4最佳不等長(zhǎng)編碼從而故進(jìn)一步故進(jìn)一步從而§3.4最佳不等長(zhǎng)編碼因?yàn)楣使室虼怂o2元串是碼字00101與碼字010011串接而成，它們分別是消息源0111和1010所對(duì)應(yīng)的算術(shù)編碼。對(duì)算術(shù)編碼的解釋(1)對(duì)于事件u=(u1u2…uL)，編碼過(guò)程最終得到的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)每個(gè)事件u=(u1u2…uL)對(duì)應(yīng)一個(gè)區(qū)間[G,G+H)，不同的事件u=(u1u2…uL)對(duì)應(yīng)的區(qū)間[G,G+H)是互不相交的，而所有區(qū)間的并集合是區(qū)間[0,1)?！?.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋(3)要將區(qū)間[G,G+H)的左端點(diǎn)G進(jìn)行改造，成為事件u=(u1u2…uL)的碼字。將G表示成二進(jìn)制小數(shù)。再將該小數(shù)的小數(shù)位數(shù)截?cái)酁閚位，截?cái)嘁?guī)則為：n位后面只要有非0的余數(shù)就要向第n位進(jìn)位。最后得到了小數(shù)0.t。t為u的碼字?！?.4最佳不等長(zhǎng)編碼(4)請(qǐng)注意0.t是一個(gè)小數(shù)位數(shù)為n位的二進(jìn)制小數(shù)。而n是巧妙設(shè)置的，所以0.t∈[G,G+H)。不僅如此，還有：將0.t的第n位小數(shù)位后面添加任意一個(gè)比特串，得到新的二進(jìn)制小數(shù)0.s，則0.s∈[G,G+H)。換句話說(shuō)，碼字t后面添加任意若干個(gè)碼字，組成比特串s，仍然能夠在譯碼過(guò)程中找到正確的區(qū)間[G,G+H)?！?.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋(5)譯碼過(guò)程找到正確區(qū)間[G,G+H)的同時(shí)，就找到了事件u=(u1u2…uL)，并在比特串s的前部確定了并去掉了碼字t.§3.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋而是則一般能正確譯碼，但也有譯碼錯(cuò)誤的可能性?。ㄋ伎迹?6)如果n不是§3.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋假設(shè)對(duì)消息(6)設(shè)取碼字長(zhǎng)度為進(jìn)行編碼，設(shè)其對(duì)應(yīng)區(qū)間的左端點(diǎn)坐標(biāo)為其對(duì)應(yīng)概率為則恰有而不是因此碼字為G的n位截?cái)嗲蚁虻趎位進(jìn)位，記為§3.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋假設(shè)另一消息其碼字為則消息u與u1的碼字串接起來(lái)為從而對(duì)應(yīng)的二進(jìn)制小數(shù)為而S與G之間的差值這說(shuō)明S已經(jīng)不在區(qū)間[G,G+H)內(nèi)，譯碼出錯(cuò)！§3.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋假設(shè)對(duì)消息(6)設(shè)取碼字長(zhǎng)度為進(jìn)行編碼，設(shè)其對(duì)應(yīng)區(qū)間的左端點(diǎn)坐標(biāo)為其對(duì)應(yīng)概率為則有因此碼字為G的n+1位截?cái)嗲蚁虻趎+1位進(jìn)位，記為§3.4最佳不等長(zhǎng)編碼對(duì)算術(shù)編碼的解釋假設(shè)另一消息其碼字為則消息u與u1的碼字串接起來(lái)為從而對(duì)應(yīng)的二進(jìn)制小數(shù)為而S與G之間的差值這說(shuō)明S必定在區(qū)間[G,G+H)內(nèi)，譯碼不會(huì)出錯(cuò)！§3.4最佳不等長(zhǎng)編碼算術(shù)編碼的平均碼長(zhǎng)可知：由碼長(zhǎng)的取法：§3.4最佳不等長(zhǎng)編碼算術(shù)編碼的特點(diǎn)特點(diǎn)一當(dāng)L很大時(shí)，平均碼長(zhǎng)接近信源熵H(U)，因此編碼效率接近上限。特點(diǎn)二編譯碼簡(jiǎn)單，存儲(chǔ)量小，速度快。（為什么？思考）算術(shù)編碼的應(yīng)用領(lǐng)域在圖象數(shù)據(jù)壓縮標(biāo)準(zhǔn)（如JPEG）中得到廣泛應(yīng)用。LZ編碼

設(shè)信源隨機(jī)變量U的事件集為A={a1,a2,…,aK}。設(shè)要對(duì)信源序列L維隨機(jī)變量UL=(U1U2…UL)進(jìn)行2元編碼。事件u=(u1u2…uL)。首先進(jìn)行的操作稱(chēng)為“分段”。分段是從前往后分，步驟如下。取最前面一個(gè)事件為一段。移動(dòng)到后面。(2)(2.1)如果已經(jīng)沒(méi)有事件，則分段完畢。

(2.2)如果一個(gè)事件在前面各段的段首沒(méi)有出現(xiàn)過(guò)，則取這個(gè)事件為一段。移動(dòng)到后面。轉(zhuǎn)（2）?！?.4最佳不等長(zhǎng)編碼(2.3)如果一個(gè)事件在前