信息論與編碼2016(第3章)教材

信息理論與編碼朱仁祥zhurx@電子與信息工程學(xué)院12024/6/232第三章：信源編碼

離散信源無失真編碼§3.1信源及其分類§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼§3.4最佳不等長(zhǎng)編碼3通信的根本問題是將信源的輸出在接收端精確地或近似地重新出來。兩個(gè)問題：

1.信源的輸出應(yīng)如何描述，即如何計(jì)算它產(chǎn)生的信息量。2.如何表示信源的輸出，即信源編碼問題。2024/6/234無失真信源編碼保證信源產(chǎn)生的全部信息無損地遞給信宿；限定失真的信源編碼不要求完全精確地復(fù)制出信源的輸出，但要滿足一定的保真度準(zhǔn)則。5§3.1信源及其分類信源的概念

（直觀地理解，信源就是信息的來源。但是必須要注意兩點(diǎn)）：在一個(gè)固定的時(shí)刻，信源發(fā)出的是一個(gè)隨機(jī)變量。隨著時(shí)間的延續(xù)，信源發(fā)出一個(gè)又一個(gè)隨機(jī)變量，稱之為一個(gè)隨機(jī)過程。（因此，一般的信源種類太多，其統(tǒng)計(jì)性質(zhì)太復(fù)雜。怎樣做工程實(shí)用的簡(jiǎn)化？）6§3.1信源及其分類離散信源信源每隔一個(gè)定長(zhǎng)時(shí)間段就發(fā)出一個(gè)隨機(jī)變量；隨著時(shí)間的延續(xù)，信源發(fā)出的是隨機(jī)變量序列

…U-2U-1U0U1U2…其中Uk為第k個(gè)時(shí)間段發(fā)出的隨機(jī)變量；每個(gè)Uk都是一個(gè)離散型的隨機(jī)變量?！?.1信源及其分類離散無記憶信源離散無記憶信源是這樣的離散信源：隨機(jī)變量…、U-2、U-1、U0、U1、U2、…相互獨(dú)立。離散無記憶簡(jiǎn)單信源離散無記憶簡(jiǎn)單信源是這樣的離散無記憶信源：隨機(jī)變量…、U-2、U-1、U0、U1、U2、…具有相同的概率分布。78§3.1信源及其分類小結(jié)離散無記憶簡(jiǎn)單信源

就是時(shí)間離散、事件離散、各隨機(jī)變量獨(dú)立同分布的信源.課程學(xué)習(xí)所面對(duì)的信源將主要是離散無記憶簡(jiǎn)單信源.§3.1信源及其分類一般的信源

連續(xù)信源：有時(shí)間連續(xù)的信源，也有事件連續(xù)的信源；有記憶信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量相互依賴；有限記憶信源：在有限時(shí)間差內(nèi)的信源隨機(jī)變量相互依賴；非簡(jiǎn)單信源：信源在不同時(shí)刻發(fā)出的隨機(jī)變量具有不同的概率分布。馬爾可夫信源：信源隨機(jī)過程是馬爾可夫過程。9§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼編碼實(shí)質(zhì)上是對(duì)信源的原始符號(hào)按一定的數(shù)學(xué)規(guī)則進(jìn)行的一種變換，映射成碼字以適合信道傳輸。102024/6/2311§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)有一個(gè)離散無記憶簡(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}}?！?.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼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離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)有一個(gè)含D個(gè)字母的字母表。對(duì)于(U1U2…UL)的每一個(gè)事件(u1u2…uL)，都用一個(gè)字母串(c1c2…)來表示。這種表示方法稱為D元編碼；每一個(gè)事件(u1u2…uL)所對(duì)應(yīng)的字母串(c1c2…)稱為一個(gè)碼字。14§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼例：離散無記憶簡(jiǎn)單信源發(fā)出的隨機(jī)變量序列為：…U-2U-1U0U1U2…，其中U1的事件有3個(gè)：{晴,云,陰}.將(U1U2)進(jìn)行2元編碼.§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼(U1U2)有9個(gè)事件{（晴晴），（晴云），（晴陰），（云晴），（云云），（云陰），（陰晴），（陰云），（陰陰）}15§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼用字母表{0,1}對(duì)(U1U2)的事件進(jìn)行2元編碼如下：（晴晴）→0000，（晴云）→0001，（晴陰）→0011，（云晴）→0100，（云云）→0101，（云陰）→0111，（陰晴）→1100，（陰云）→1101，（陰陰）→1111。1617§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼如果限定所有碼字的長(zhǎng)度都為N（即每個(gè)碼字都是一個(gè)長(zhǎng)度為N的字母串，或稱為N維向量），則稱此編碼為等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為DN。18§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼如果限定每個(gè)碼字的長(zhǎng)度都≤N（即每個(gè)碼字都是一個(gè)長(zhǎng)度≤N的字母串），則稱此編碼為不等長(zhǎng)編碼，能夠選擇的不同碼字的個(gè)數(shù)為D1+D2+…+DN=D(DN-1)/(D-1)。19§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼問題：在不等長(zhǎng)編碼中，能否同時(shí)使用D(DN-1)/(D-1)個(gè)不同的碼字？一個(gè)長(zhǎng)度為2的字母串究竟是兩個(gè)長(zhǎng)度為1的碼字相連，還是一個(gè)長(zhǎng)度為2的碼字？無法識(shí)別。在等長(zhǎng)編碼中不存在這樣的識(shí)別問題。20§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)等長(zhǎng)碼若對(duì)每個(gè)消息都至少有一個(gè)碼字與之對(duì)應(yīng)，且不同的消息對(duì)應(yīng)不同的碼字，則稱這樣的碼為單義可譯碼或唯一可譯碼。在無擾傳輸時(shí)，單義可譯碼的譯碼錯(cuò)誤概率為0，又稱為無錯(cuò)編碼。21§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼無錯(cuò)編碼

(U1U2…UL)的不同事件用不同的碼字來表示。消息集是K元字母表L長(zhǎng)消息序列，編碼成D元N長(zhǎng)碼字。能夠?qū)崿F(xiàn)無錯(cuò)編碼的充要條件是DN≥KL即NlogD

≥

LlogK或NlogD/L

≥

logK

(下界)等長(zhǎng)碼基本問題

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

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

code/sig奇異碼等長(zhǎng)碼特點(diǎn)：Ki=K要求：xi—yj

高效問題：K=?等長(zhǎng)編碼:

要求:可能的碼字?jǐn)?shù)≥消息數(shù)對(duì)基本信源編碼：xi∈X=(x1,x2,…xn

)--yj

碼字?jǐn)?shù)：mK

∴mK≥n(K≥logmn)

（對(duì)例1，n=5,∴要求：2K≥5，即K≥3）對(duì)L長(zhǎng)源編碼：ai∈XL=(a1,a2,…anL)—yj

’

∴mK≥nL

(K/L≥logmn)例（續(xù)）X的三次擴(kuò)展：X3:{a1=(x1x1

x1),,…,a53=(x5x5

x5)}

則，nL=53=125種<128=27∴K=7code/3sigs

平均碼長(zhǎng)：K/L=7/3=2.33code/sig<K2

結(jié)論:等長(zhǎng)碼碼長(zhǎng)要求K/L

logmn(保證唯一可譯碼,無失真)

logmn為下限擴(kuò)展信源編碼的平均碼長(zhǎng)<基本源編碼的平均碼長(zhǎng)25§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼編碼速率

R=NlogD/L實(shí)現(xiàn)無錯(cuò)編碼的充要條件是

編碼速率R=NlogD/L≥logK26§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼

有錯(cuò)編碼

(U1U2…UL)的有些不同事件用相同的碼字來表示。27§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼編碼速率的說明實(shí)際的編碼速率的計(jì)算公式為R=NlogD/L，似乎可以人為地任意設(shè)置N和L，因而可以人為地任意設(shè)置編碼速率。?

§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事實(shí)并非如此，存在著編碼設(shè)備的編碼速率R0，它是編碼設(shè)備的性能指標(biāo).這就是說，選擇N和L，必須使得實(shí)際的編碼速率NlogD/L不能超過編碼設(shè)備的編碼速率R0

：R=NlogD/L≤R0

2829§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼有錯(cuò)編碼的譯碼方法與“譯碼錯(cuò)誤”概率當(dāng)使用有錯(cuò)編碼時(shí)，必須給出譯碼方法（即：一個(gè)碼字可能表示幾個(gè)不同的事件，究竟翻譯成哪個(gè)事件）。“譯碼錯(cuò)誤”的概率定義為

pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)的碼字在譯碼時(shí)并不譯為(u1u2…uL)}。30§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼在無錯(cuò)編碼的前提下，編碼的最低代價(jià)當(dāng)R≥logK時(shí)，能夠?qū)崿F(xiàn)無錯(cuò)編碼。（DN≥KL）當(dāng)R<H(U1)時(shí)，無論怎樣編碼都是有錯(cuò)編碼。

這是因?yàn)镽<H(U1)≤logK。（DN<KL）如果H(U1)=logK，則以上兩種情形已經(jīng)概括了全部情形。但如果H(U1)<logK，則還有一種情形。當(dāng)logK>R>H(U1)時(shí)，雖然無論怎樣編碼都是有錯(cuò)編碼，但可以適當(dāng)?shù)鼐幋a和譯碼使譯碼錯(cuò)誤的概率pe任意小。這就是所謂“漸進(jìn)無錯(cuò)編碼”。31§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼logKH(U1)·RRR無錯(cuò)編碼不能漸進(jìn)無錯(cuò)編碼漸進(jìn)無錯(cuò)編碼○·○○○32§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼

簡(jiǎn)單地說就是：當(dāng)R>H(U1)時(shí)，可以適當(dāng)?shù)鼐幋a和譯碼使得譯碼錯(cuò)誤的概率pe任意小。33§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼

嚴(yán)格地說就是：設(shè)給定了編碼設(shè)備的編碼速率R0，R0>H(U1)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的等長(zhǎng)編碼和對(duì)應(yīng)的譯碼方法，滿足①實(shí)際的編碼速率R=NlogD/L≤R0，②譯碼錯(cuò)誤的概率pe<ε。34§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼的原理

大數(shù)定律。隨著L的增加，(U1U2…UL)的所有事件中，某些事件所占的比例越來越小（→0），其發(fā)生的概率卻越來越大（→1）。35§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼不能漸進(jìn)無錯(cuò)的編碼

簡(jiǎn)單地說就是：當(dāng)R<H(U1)時(shí)，無論怎樣編碼和譯碼都不能使譯碼錯(cuò)誤的概率pe

任意小。

嚴(yán)格地說就是：設(shè)給定了編碼設(shè)備的編碼速率R0，R0<H(U1)，則無論怎樣編碼和譯碼都不能同時(shí)滿足①實(shí)際的編碼速率R≤R0，②譯碼錯(cuò)誤的概率pe任意小。36§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)…U-2U-1U0U1U2…是離散無記憶（簡(jiǎn)單）信源的輸出隨機(jī)變量序列。設(shè)U1的概率分布為取Vl是Ul的如下函數(shù)：當(dāng)Ul=ak時(shí)，Vl=loga(1/qk)。則①隨機(jī)變量序列…V-2V-1V0V1V2…相互獨(dú)立，具有相同的概率分布；②37§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取IL是(V1V2…VL)的如下函數(shù)：則①IL最終是(U1U2…UL)的函數(shù)；②③因此有切比雪夫不等式：對(duì)任意ε>0有P{(U1U2…UL)=(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}≥38§3.2離散無記憶（簡(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-ε。39§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定義3.2.1(p50)定義TU(L,ε)={(u1u2…uL)|H(U1)-ε≤IL≤H(U1)+ε}，稱TU(L,ε)為ε-典型序列集。稱TU(L,ε)的補(bǔ)集為非ε-典型序列集。（綜上所述有）定理3.2.1(信源劃分定理，p51)對(duì)任意ε>0，取L0使得則當(dāng)L≥L0時(shí)總有P{(U1U2…UL)∈TU(L,ε)}≥1-ε。2024/6/2340§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（簡(jiǎn)記H(U)=H(U1)。設(shè)以下的對(duì)數(shù)都是以2為底的。）系3.2.1(特定典型序列出現(xiàn)的概率，p51)若一個(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)+ε，41§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼所以42§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼系3.2.2(典型序列的數(shù)量，p51)(1-ε)2L(H(U)-ε)≤|TU(L,ε)|≤2L(H(U)+ε)。證明一方面，43§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼另一方面，44§3.2離散無記憶（簡(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。任取正數(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）45§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼定理3.2.2(無錯(cuò)編碼正定理，p53)

給定編碼設(shè)備的編碼速率R0，R0>H(U)。則對(duì)任意的ε>0，總存在一個(gè)L0，使得對(duì)任意的L>L0，都有對(duì)(U1U2…UL)的2元等長(zhǎng)編碼方法和對(duì)應(yīng)的譯碼方法，①實(shí)際的編碼速率R滿足R0≥R>H(U)，②“譯碼錯(cuò)誤”的概率pe<ε。46§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼證明首先聲明，所有的對(duì)數(shù)計(jì)算都是以2為底的。此時(shí)實(shí)際的編碼速率為R=N/L。任取正數(shù)ε≤(R0-H(U))/2，取補(bǔ)充引理所描述的L0，則|TU(L,ε)|≤2L(H(U)+ε)

（由系3.2.2）≤2LR=2N

（由補(bǔ)充引理的（1））這就是說，典型序列集TU(L,ε)中的事件的個(gè)數(shù)不超過長(zhǎng)度為N的2元碼字的數(shù)量2N。因此，可以做如下的編碼：將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L,ε)中的某個(gè)事件。47§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)應(yīng)的譯碼：所有的碼字均譯為它所表示的TU(L,ε)中的事件。結(jié)論：①實(shí)際的編碼速率R滿足R0≥R>H(U)；②“譯碼錯(cuò)誤”的概率pe=P((U1U2…UL)不屬于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得證。

定理3.2.2(無錯(cuò)編碼反定理，p53)設(shè)給定編碼設(shè)備的編碼速率R0，滿足R0<H(U)。當(dāng)限制實(shí)際的編碼速率R≤R0時(shí)，無論怎樣編碼和譯碼都不能使“譯碼錯(cuò)誤”的概率任意小。（沒有證明）48§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼漸進(jìn)無錯(cuò)編碼的要求給定離散無記憶簡(jiǎn)單信源：…U-2U-1U0U1U2…；給定編碼設(shè)備的編碼速率R0，滿足R0>H(U)；給定一個(gè)任意小的正數(shù)ε>0；要求：選擇合適的L，N，對(duì)(U1U2…UL)進(jìn)行合適的2元N長(zhǎng)編碼，使得

①實(shí)際的編碼速率R=N/L滿足R≤R0；

②“譯碼錯(cuò)誤”的概率pe<ε。49漸進(jìn)無錯(cuò)編碼的步驟①由U1的概率分布計(jì)算②取L滿足。③取整數(shù)N=[R0L]（R0L下取整）。④取典型序列集50漸進(jìn)無錯(cuò)編碼的步驟⑤將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L,ε)中的某個(gè)事件。⑥譯碼時(shí)，所有的碼字均譯為它所表示的TU(L,ε)中的事件。（注解：顯然滿足R≤R0；|TU(L,ε)|≤2N，因此碼字足夠用；譯碼錯(cuò)誤的概率為pe=P((U1U2…UL)=(u1u2…uL)|(u1u2…uL)不屬于TU(L,ε))<ε；一般來說，ε越小，要求L越大，因此對(duì)應(yīng)的N越大。）51§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼例設(shè)52§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)給定編碼設(shè)備的編碼速率R0=0.5。則R0>0.037587148=H(U1)。希望：①2元編碼的實(shí)際編碼速率R≤R0；②譯碼錯(cuò)誤的概率不超過ε。其中取ε=0.1。找L使得2024/6/2353§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼取L=253即可。再取N=[R0L]=126。將TU(L,ε)中的事件用不同的N長(zhǎng)2元碼字來表示，而將TU(L,ε)以外的事件用一個(gè)固定的N長(zhǎng)2元碼字來表示，這個(gè)固定的N長(zhǎng)2元碼字已經(jīng)用來表示了TU(L,ε)中的某個(gè)事件。譯碼時(shí)，所有的碼字均譯為它所表示的TU(L,ε)中的事件。另一方面，TU(L,ε)中的事件有更加簡(jiǎn)單的表達(dá)方式。當(dāng)事件(u1u2…uL)中a1的個(gè)數(shù)為k，a2的個(gè)數(shù)為L(zhǎng)-k時(shí)，54§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.1)；當(dāng)且僅當(dāng)55§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼當(dāng)事件(u1u2…u253)中a1的個(gè)數(shù)不超過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ù)為56§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=253，對(duì)應(yīng)地取整數(shù)N=[R0L]=126。則N/L<R0，這就是說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。57§3.2離散無記憶（簡(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í)，58§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼事件(u1u2…uL)屬于典型序列集TU(L,0.05)；當(dāng)且僅當(dāng)-0.05≤IL-H(U)≤0.05；當(dāng)且僅當(dāng)59§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼設(shè)L=2020。此時(shí)0.01028137L=20.7683674。當(dāng)事件(u1u2…u2020)中a1的個(gè)數(shù)不超過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ù)為60§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=2020，對(duì)應(yīng)地取整數(shù)N=[R0L]=1010。則N/L=R0，這就是說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。61§3.2離散無記憶（簡(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í)，62§3.2離散無記憶（簡(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)2024/6/2363§3.2離散無記憶（簡(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ù)為64§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼對(duì)L=252435，對(duì)應(yīng)地取整數(shù)N=[R0L]=126217。則N/L<R0，這就是說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。65§3.2離散無記憶（簡(jiǎn)單）信源的等長(zhǎng)編碼（直觀理解）等長(zhǎng)編碼定理（信源劃分定理）1.信源序列集=典型序列集（高概率集，>=1-\epsilon）+非典型序列集（低概率集）；2.將典型序列集中的信源序列一一編碼（無錯(cuò)編碼），而將非典型序列集中的信源序列編碼成剛才的一個(gè)碼字；3.典型序列集勢(shì)約為2^{LH(U)}，占K^L少,非典型序列集勢(shì)占多。注意:※

適用于DMS及無記憶平穩(wěn)信源※平均碼長(zhǎng)下限：※

基本方法：L長(zhǎng)源、等長(zhǎng)編碼※對(duì)等長(zhǎng)編碼,若要實(shí)現(xiàn)幾乎無失真編碼,則信源長(zhǎng)度必滿足:其中:當(dāng)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等長(zhǎng)碼的缺點(diǎn)：平均碼長(zhǎng)太長(zhǎng)L無法實(shí)現(xiàn)變長(zhǎng)碼的特點(diǎn)：每個(gè)碼字長(zhǎng)度可不同要求：惟一可譯69§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（順序地?cái)⑹鲆韵碌母拍睿?）不等長(zhǎng)編碼的優(yōu)越性總體上減少碼字的長(zhǎng)度。（2）不等長(zhǎng)編碼的特殊問題

①唯一可譯性，或者叫做可識(shí)別性。對(duì)于一個(gè)碼，如果存在一種譯碼方法，使任意若干個(gè)碼字所組成的字母串只能唯一地被翻譯成這幾個(gè)碼字所對(duì)應(yīng)的事件序列。這個(gè)碼就被稱為是唯一可譯的。解決方案：適當(dāng)?shù)鼐幋a，使得每個(gè)碼字都具有識(shí)別標(biāo)記。（注解：一個(gè)唯一可譯的、碼字長(zhǎng)度不超過N的D元碼，其碼字個(gè)數(shù)小于D(DN-1)/(D-1)個(gè)。這是因?yàn)閮蓚€(gè)碼字c(1)和c(2)連接成的字母串c(1)c(2)不能是碼字）70§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼②平均碼字長(zhǎng)度。設(shè)信源隨機(jī)變量U的概率分布為{ak,q(ak),k=1~K}，事件ak對(duì)應(yīng)的碼字長(zhǎng)度為nk，則平均碼字長(zhǎng)度為希望小。解決方案：概率大的事件用短碼字。③實(shí)時(shí)譯碼和容量限制。71§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼唯一可譯性的兩種解決方法定義3.3.2(p55)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字的開頭部分都是一個(gè)相同的字母串；③這個(gè)字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個(gè)碼字的結(jié)合部。則稱這個(gè)字母串為逗號(hào)，稱此碼為逗點(diǎn)碼。定義3.3.4(p55)若①事件與碼字一一對(duì)應(yīng)；②每個(gè)碼字都不是另一個(gè)碼字的開頭部分（字頭）。則稱此碼為異字頭碼。72§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼注解逗點(diǎn)碼顯然是唯一可譯的，識(shí)別碼字的方法為：見到逗號(hào)就識(shí)別為一個(gè)碼字的開始。異字頭碼也是唯一可譯的，識(shí)別碼字的方法為：見到一個(gè)碼字就識(shí)別為一個(gè)碼字。（許多具體的異字頭碼有更加簡(jiǎn)便的識(shí)別碼字的方法）按譯碼的即時(shí)性分類非即時(shí)碼：接收端收到一個(gè)完整的碼字后,不能立即譯碼；還需要等到下一個(gè)碼字開始接收后才能判斷是否可以譯碼;非即時(shí)碼,又名延長(zhǎng)碼,一碼字是其他碼字的延長(zhǎng)。即時(shí)碼：接收端收到一個(gè)完整的碼字后，就能立即譯碼；即時(shí)碼又稱為非延長(zhǎng)碼或非前綴碼，任何一個(gè)碼不能是其他碼的前綴。例：非即時(shí)碼——碼流01001100…x1→0x2→01x3→11譯碼為x2,x1,x1,x3,x1,?

即時(shí)碼——碼流01001100…x1→0x2→10x3→11譯碼為x1,x2,x1,x3,x1,x1

[記憶]非前綴碼必定是即時(shí)碼，即時(shí)碼必定是唯一可譯碼,

但唯一可譯碼不一定是即時(shí)碼。有實(shí)用價(jià)值的分組碼是非奇異碼、唯一可譯碼、即時(shí)碼74§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例觀察表3.3.1(p55)。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.1251011111011175§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識(shí)別碼字的方法為：見“0”或“111”就是一個(gè)碼字的結(jié)束。實(shí)際上，碼C是異字頭碼。碼D是唯一可譯的，識(shí)別碼字的方法為：見“0”就是一個(gè)碼字的開始。實(shí)際上，碼D是逗點(diǎn)碼，其中“0”是逗號(hào)。碼C不是逗點(diǎn)碼。碼D不是異字頭碼。碼C的平均碼長(zhǎng)比碼D的平均碼長(zhǎng)小：碼C的平均碼長(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。[基本術(shù)語]終端節(jié)點(diǎn)——后面不再分支的節(jié)點(diǎn)。中間節(jié)點(diǎn)——除樹根、終端節(jié)點(diǎn)外的節(jié)點(diǎn)。聯(lián)枝——串聯(lián)的樹枝碼字——從樹根出發(fā)，到達(dá)某一終端節(jié)點(diǎn)的聯(lián)枝即時(shí)碼——每個(gè)碼字都到達(dá)終端節(jié)點(diǎn)滿樹

——每個(gè)碼字的聯(lián)枝數(shù)均相同時(shí)(定長(zhǎng)碼)非滿樹——當(dāng)碼字的聯(lián)枝數(shù)不同時(shí)(變長(zhǎng)碼)全樹——每個(gè)中間節(jié)點(diǎn)的后續(xù)分支數(shù)均為m非全樹——有些中間節(jié)點(diǎn)的后續(xù)分支數(shù)不足m碼樹法滿樹全樹，非滿樹非全樹二進(jìn)制碼樹、滿樹、全樹012000001111122222三進(jìn)制碼樹、非滿樹、全樹A01000000000000011111111111(1)規(guī)則樹根=碼字的起點(diǎn)樹的度=碼元數(shù)分支結(jié)點(diǎn)=碼的符號(hào)的一部分終端結(jié)點(diǎn)=待編碼符號(hào)(2)碼樹畫法(m進(jìn)制)①從樹根出發(fā)，畫m條分支，分支端點(diǎn)稱為節(jié)。②第一節(jié)有m個(gè)端點(diǎn)，每端點(diǎn)對(duì)應(yīng)一個(gè)碼字③從第一節(jié)每個(gè)端點(diǎn)出發(fā)，再畫m條分支，得第二節(jié)。第二節(jié)有m2個(gè)端點(diǎn)④以此類推(3)編碼方法：①將待編碼的字符作為終端結(jié)點(diǎn)，構(gòu)造碼樹；②按一定規(guī)則給每個(gè)樹枝分配一個(gè)標(biāo)記；③將從根到終端結(jié)點(diǎn)的路徑上的編號(hào)依次相連，作為該終端結(jié)點(diǎn)所表示的字符的編碼。(4)譯碼方法：①從樹根出發(fā),根據(jù)接收到的第一個(gè)碼字符號(hào)來選擇應(yīng)走的第一條路徑②沿所選路徑走到分支結(jié)點(diǎn),再根據(jù)收到的第二個(gè)碼字選擇應(yīng)走的第二條路徑,直至走到終端結(jié)點(diǎn)為止③根據(jù)所走路徑,可立即判斷出接收到的碼符號(hào)④重新返回到樹根,再作下一個(gè)接收碼符號(hào)的判斷例題:非滿二叉樹acdb(0)0(10)00111(110)(111)構(gòu)造二元碼樹:編碼:信源序列X={bacabd}100110010111譯碼:100110010111信源序列X={bacabd}提問:為什么碼樹法構(gòu)造的碼就是即時(shí)碼？81§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第一種構(gòu)造方法：Shannon-Fano編碼法（D元編碼，字母表為{0,1,…,D-1}）

（1）將源隨機(jī)變量的事件按概率從大到小排成一列。（2）將此列切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為1級(jí)標(biāo)號(hào)。（3）將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為2級(jí)標(biāo)號(hào)。（4）將每個(gè)非空段再切分為D段（可能有空段），分別賦予標(biāo)號(hào)“0”到“D-1”，稱為3級(jí)標(biāo)號(hào)?！?。82§3.3離散無記憶（簡(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)序列是沒有用的，要去掉）為了使平均碼長(zhǎng)小，每次切分段時(shí)應(yīng)使D段的概率盡可能相近。（注解：當(dāng)然可以把“切分段”操作換為“任意分組”操作，使D組的概率盡可能相近。這樣可以使平均碼長(zhǎng)更小。但是，這不是一種有效的操作。）83例設(shè)有一單符號(hào)離散信源對(duì)該信源編二進(jìn)制費(fèi)諾碼。信源符號(hào)xi

符號(hào)概率p(xi)第1次分組第2次分組第3次分組碼字碼長(zhǎng)x10.400002x40.05100103x50.0510113x20.310102x30.21112信源符號(hào)xi

符號(hào)概率p(xi)第1分組第2分組第3分組第4分組碼字碼長(zhǎng)x10.4001x20.310102x30.2101103x40.051011104x50.05111114平均碼長(zhǎng)：n=2.1編碼效率:η=93%平均碼長(zhǎng)：n=2.0編碼效率:η=97.5%84平均碼長(zhǎng)編碼效率費(fèi)諾碼比較適合于每次分組概率都很接近的信源特別是對(duì)每次分組概率都相等的信源進(jìn)行編碼時(shí),可達(dá)到理想的編碼效率。85例有一單符號(hào)離散無記憶信源對(duì)該信源編二進(jìn)制費(fèi)諾碼,編碼過程如表:86信源熵為H(X)=2.75(比特/符號(hào))平均碼長(zhǎng)為編碼效率為

η=1之所以如此,因?yàn)槊看嗡謨山M的概率恰好相等。87§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法88二元Huffman編碼法89例子

設(shè)單符號(hào)離散無記憶信源如下,要求對(duì)信源編二進(jìn)制哈夫曼碼。編碼過程如下表信源符號(hào)xi

符號(hào)概率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在圖中讀取碼字的時(shí)候,要從后向前讀,此時(shí)編出來的碼字是可分離的異前置碼。90熵平均碼長(zhǎng)為編碼效率例2.源符Si概率P(Si)S10.4S20.2S30.2S40.1S50.1010001000001001000110100101101001101

合并后概率下放合并后概率上放這兩種編碼哪一種更好呢，我們來計(jì)算一下二者的碼長(zhǎng)。

兩種編碼的平均碼長(zhǎng)是一樣的，都是2.2，那一種更好呢，我們可以計(jì)算一下平均碼長(zhǎng)的方差。定義碼字長(zhǎng)度的方差σ2：可見：第二種編碼方法的碼長(zhǎng)方差要小許多。意味著第二種編碼方法的碼長(zhǎng)變化較小，比較接近于平均碼長(zhǎng)。第一種方法編出的5個(gè)碼字有4種不同的碼長(zhǎng)；第二種方法編出的碼長(zhǎng)只有2種不同的碼長(zhǎng)；顯然，第二種編碼方法更簡(jiǎn)單、更容易實(shí)現(xiàn)，所以更好結(jié)論：在哈夫曼編碼過程中，對(duì)縮減信源符號(hào)按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號(hào)盡可能排在靠前的位置，這樣可使合并后的新符號(hào)重復(fù)編碼次數(shù)減少，使短碼得到充分利用。[結(jié)論]＊兩法平均碼長(zhǎng)相同，因而信息率R、編碼效率

相同＊但碼方差不同，碼方差小要好各次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的，所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性，即能得到可分離碼字。不同的碼元分配，得到的具體碼字不同，但碼長(zhǎng)ki不變，平均碼長(zhǎng)也不變，所以沒有本質(zhì)區(qū)別，不會(huì)影響碼字的長(zhǎng)度。縮減信源時(shí)，若合并后的新符號(hào)概率與其他符號(hào)概率相等，從編碼方法上來說，這幾個(gè)符號(hào)的次序可任意排列，編出的碼都是正確的，但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度ki也不盡相同。此時(shí)將影響碼字的長(zhǎng)度，一般將合并的概率放在上面，這樣可獲得較小的碼方差。編碼不唯一（0、1分配不同，排序不同）平均碼長(zhǎng)唯一為什么哈夫曼編碼方法得到的碼并非是唯一的?

95D元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”。（2）將這D個(gè)事件合并為一個(gè)事件，其概率為這D個(gè)事件概率之和。重復(fù)（1）-（2），直到事件的個(gè)數(shù)等于D。將這D個(gè)事件分別賦予標(biāo)號(hào)“0”到“D-1”。編碼完畢。此時(shí)，一個(gè)事件的碼字是這個(gè)事件從最后標(biāo)號(hào)開始到最先標(biāo)號(hào)為止的標(biāo)號(hào)序列。（當(dāng)然要去掉那些0概率事件和它們的標(biāo)號(hào)序列）為了使短碼得到充分利用，使平均碼長(zhǎng)為最短，必須使最后一步的縮減信源有D個(gè)信源符號(hào)，因此對(duì)于D元編碼，信源的符號(hào)個(gè)數(shù)K必須滿足K=(D-1)r+D=(D-1)(r+1)+1,其中r為縮減的次數(shù)。K-(D-1)r=D96哈夫曼的編法并不惟一。對(duì)二元Huffman編碼，每次對(duì)縮減信源兩個(gè)概率最小的符號(hào)分配“0”和“1”碼元是任意的,所以可得到不同的碼字。只要在各次縮減信源中保持碼元分配的一致性,即能得到可分離碼字。對(duì)D元Huffman編碼，有類似結(jié)果。哈夫曼編碼97哈夫曼編碼不同的碼元分配,得到的具體碼字不同,但碼長(zhǎng)Ki不變,平均碼長(zhǎng)也不變,所以沒有本質(zhì)區(qū)別；縮減信源時(shí),若合并后的新符號(hào)概率與其他符號(hào)概率相等,從編碼方法上來說,這幾個(gè)符號(hào)的次序可任意排列,編出的碼都是正確的,但得到的碼字不相同。不同的編法得到的碼字長(zhǎng)度Ki也不盡相同。2024/6/2398§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼（為什么Shannon-Fano碼和Huffman碼都是異字頭碼？請(qǐng)看p62圖3.4.1，p62圖3.4.2。這些圖都是樹，稱為碼樹，碼樹上的每個(gè)碼字都在樹梢。這種形狀保證了碼是異字頭碼。如果不是異字頭碼，則有的碼字就不在樹梢，而在中間節(jié)點(diǎn)。）P56,若一個(gè)碼樹的各分支都能延伸到最高級(jí)端點(diǎn)（共有D^{n_K}個(gè)碼字），就稱為滿樹，否則為非滿樹。若消息占滿了所有的端節(jié)點(diǎn)，即樹上每一個(gè)中間節(jié)點(diǎn)都有D個(gè)分支，稱為全樹。99定理3.3.1(Kraft不等式，p57)設(shè)信源隨機(jī)變量共有K個(gè)事件。則：各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在的充分必要條件是100§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼證明不妨設(shè)n1≤n2≤…≤nK。則各碼字長(zhǎng)度分別為n1、n2、…、nK的D元異字頭碼存在；當(dāng)且僅當(dāng)：存在這樣一個(gè)D叉樹，樹上有一個(gè)n1級(jí)樹梢，再有一個(gè)n2級(jí)樹梢，…，再有一個(gè)nK級(jí)樹梢；當(dāng)且僅當(dāng)：存在nK級(jí)D叉滿樹，樹上有個(gè)nK級(jí)樹梢，再有個(gè)nK級(jí)樹梢，…，再有個(gè)nK級(jí)樹梢；當(dāng)且僅當(dāng)：101§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼表明：異字頭碼的各碼組長(zhǎng)度nK

必須滿足上式，而對(duì)滿足上式的一組整數(shù)nK

必有相應(yīng)碼長(zhǎng)的異字頭碼。但這并不是說滿足上式的異字頭碼是唯一的，而且這個(gè)不意味著滿足該式的碼就一定是異字頭碼。102§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.2(p57)設(shè)信源隨機(jī)變量共有K個(gè)事件，則一個(gè)唯一可譯的、各碼字長(zhǎng)度分別為n1、n2、…、nK的D元不等長(zhǎng)碼存在的充分必要條件是103§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼上述兩定理表明：1.任一唯一可譯碼可用各相應(yīng)碼字長(zhǎng)度一樣的異字頭碼代替。2.異字頭碼屬于唯一可譯碼，唯一可譯碼是滿足Kraft不等式的碼。對(duì)任一滿足Kraft不等式的非異字頭碼又可以找到一個(gè)碼字長(zhǎng)度不變的異字頭碼。唯一可譯碼存在的充分和必要條件

說明：Kraft不等式——惟一可譯碼存在的充要條件。必要性表現(xiàn)在如果碼是惟一可譯碼,則一定滿足Kraft不等式；充分性表現(xiàn)在如果滿足Kraft不等式，則這種碼長(zhǎng)的惟一可譯碼一定存在，但并不表示所有滿足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}非惟一可譯碼長(zhǎng)結(jié)構(gòu)～惟一可譯碼而106§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.3(p56)（不等長(zhǎng)編碼定理）任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足2024/6/23107§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼證明設(shè)信源隨機(jī)變量U的概率分布為如果唯一可譯的D元不等長(zhǎng)碼的碼字長(zhǎng)度為則108§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼因此。另一方面，取n1、n2、…、nK，則：由于，存在碼字長(zhǎng)度為的唯一可譯的D元不等長(zhǎng)碼。109§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼但此時(shí)110§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定理3.3.3的結(jié)論的推廣(p59-60)現(xiàn)在對(duì)信源隨機(jī)向量UL=(U1U2…UL)做唯一可譯的D元不等長(zhǎng)碼。此時(shí)UL的事件的個(gè)數(shù)為KL。則任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足111§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼定義：編碼速率R和編碼效率η分別為

任一唯一可譯的D元不等長(zhǎng)碼總滿足存在唯一可譯的D元不等長(zhǎng)碼滿足注解不等長(zhǎng)編碼與等長(zhǎng)編碼具有相似的性質(zhì)：當(dāng)L增大時(shí)，對(duì)UL的編碼可以更加節(jié)省編碼速率。但節(jié)省編碼速率的下限是H(U)。112§3.3離散無記憶（簡(jiǎn)單）信源的不等長(zhǎng)編碼例3.3.1（見p60）做2元編碼。設(shè)；H(U)=0.811。U概率碼字平均碼長(zhǎng)編碼速率編碼效率a13/40(1×3/4+1×1/4)/1=110.811a21/41U2概率碼字平均碼長(zhǎng)編碼速率編碼效率a1a19/1601×9/16+2×3/16+3×3/16+3×1/16=27/1627/320.961a1a23/1610a2a13/16110a2a21/16111Huffman編碼效率高，運(yùn)算速度快，實(shí)現(xiàn)方式靈活，從20世紀(jì)60年代至今，在數(shù)據(jù)壓縮領(lǐng)域得到了廣泛的應(yīng)用。今天，在許多知名的壓縮工具和壓縮算法（如WinRAR

、gzip

和JPEG）里，都有Huffman編碼的身影。不過，Huffman編碼所得的編碼長(zhǎng)度只是對(duì)信息熵計(jì)算結(jié)果的一種近似，還無法真正逼近信息熵的極限。正因?yàn)槿绱耍F(xiàn)代壓縮技術(shù)通常只將Huffman作為最終的編碼手段，而非數(shù)據(jù)壓縮算法的全部。同時(shí)科學(xué)家們一直沒有放棄向信息熵極限挑戰(zhàn)的理想。1968年前后，P.Elias發(fā)展了Shannon和Fano

的編碼方法，構(gòu)造出從數(shù)學(xué)角度看來更為完美的Shannon-Fano-Elias編碼。沿著這一編碼方法的思路，1976年，J.Rissanen

提出了一種可以成功地逼近信息熵極限的編碼方法——算術(shù)編碼。算術(shù)編碼算術(shù)編碼Shannon-Fano編碼，Huffman編碼的編碼方法：首先對(duì)信源的各事件進(jìn)行編碼，然后再對(duì)輸入的消息序列進(jìn)行編碼變換。算術(shù)編碼：首先假設(shè)一個(gè)信源的概率模型,隨后直接把整個(gè)輸入的消息編碼為一個(gè)(0.0≤n<1.0)內(nèi)的小區(qū)間，在編碼的過程中，消息序列集中的每個(gè)元素都用來縮短這個(gè)區(qū)間，消息序列集中的元素越多,所得到的區(qū)間就越小，當(dāng)區(qū)間變小時(shí)，就需要更多的數(shù)位來表示這個(gè)區(qū)間，這就是區(qū)間作為代碼的原理。使用算術(shù)編碼的壓縮算法通常先要對(duì)信源符號(hào)的概率進(jìn)行估計(jì)，然后再編碼。這個(gè)估計(jì)越準(zhǔn)，編碼結(jié)果就越接近最優(yōu)的結(jié)果。例:對(duì)一個(gè)簡(jiǎn)單的信號(hào)源進(jìn)行觀察，得到的統(tǒng)計(jì)模型如下：60%的機(jī)會(huì)出現(xiàn)符號(hào)中性20%的機(jī)會(huì)出現(xiàn)符號(hào)陽性10%的機(jī)會(huì)出現(xiàn)符號(hào)陰性10%的機(jī)會(huì)出現(xiàn)符號(hào)數(shù)據(jù)結(jié)束符.算術(shù)編碼在得到信源隨機(jī)變量U的事件集的概率分布P(ak)，(k=0,1,…,K-1)之后，我們需要定義信源符號(hào)的分布函數(shù)，(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)。

隨后，編碼過程的每一步，除了最后一步，都是相同的。算術(shù)編碼編碼器通常需要考慮下面三種數(shù)據(jù)：下一個(gè)要編碼的符號(hào)當(dāng)前的區(qū)間(在編第一個(gè)符號(hào)之前，這個(gè)區(qū)間是[0,1),但是之后每次編碼區(qū)間都會(huì)變化)模型中在這一步可能出現(xiàn)的各個(gè)符號(hào)的概率分布編碼器利用信源符號(hào)的分布函數(shù)將當(dāng)前的區(qū)間分成若干子區(qū)間，區(qū)間之間的分隔線為信源符號(hào)的分布函數(shù)，每個(gè)子區(qū)間的長(zhǎng)度與可能出現(xiàn)的對(duì)應(yīng)符號(hào)的概率成正比。當(dāng)前要編碼的符號(hào)對(duì)應(yīng)的子區(qū)間成為下一步編碼的初始區(qū)間。算術(shù)編碼例:對(duì)于前面提出的4符號(hào)模型:中性對(duì)應(yīng)的區(qū)間是[0,0.6)陽性對(duì)應(yīng)的區(qū)間是[0.6,0.8)陰性對(duì)應(yīng)的區(qū)間是[0.8,0.9)數(shù)據(jù)結(jié)束符對(duì)應(yīng)的區(qū)間是[0.9,1)當(dāng)所有的符號(hào)都編碼完畢，最終得到的結(jié)果區(qū)間即唯一的確定了已編碼的符號(hào)序列。任何人使用該區(qū)間和模型參數(shù)即可以解碼重建得到該符號(hào)序列。算術(shù)編碼算術(shù)編碼原理把信源序列的積累概率映射到[0,1)區(qū)間上，使每個(gè)序列對(duì)應(yīng)該區(qū)間內(nèi)的一點(diǎn)，這些點(diǎn)把區(qū)間[0,1)分成許多不同的小區(qū)間，這些小區(qū)間的長(zhǎng)度等于對(duì)應(yīng)序列的概率，在小區(qū)間內(nèi)取一個(gè)浮點(diǎn)小數(shù)，使其長(zhǎng)度與該序列的積累概率相匹配。因而達(dá)到高效編碼的目的。算術(shù)編碼的主要任務(wù)是計(jì)算信源序列對(duì)應(yīng)的小區(qū)間再以二元信源輸出序列01110的編碼為例P(0)P(1)F(0)F(1)01算術(shù)編碼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)算術(shù)編碼信源符號(hào)序列u對(duì)應(yīng)區(qū)間的寬度等于符號(hào)序列的概率信源符號(hào)序列u對(duì)應(yīng)區(qū)間的左端點(diǎn)為算術(shù)編碼信源序列積累概率傳遞公式設(shè)獨(dú)立信源序列信源序列S添加一個(gè)新的信源符號(hào)ur后所得新序列Sur的積累概率。信源序列S的概率。信源序列的積累概率F(S)與信源符號(hào)的積累概率一樣，可用[0,1)區(qū)間內(nèi)的個(gè)點(diǎn)來表示，因此積累概率F(S)將區(qū)間[0,1)分成許多不同的小區(qū)間，他們互不重疊，序列S的概率p(S)就是兩點(diǎn)間小區(qū)間的長(zhǎng)度。小區(qū)間內(nèi)的一個(gè)點(diǎn)可用來表示序列的概率。遞推公式的應(yīng)用用序列積累概率的遞推公式進(jìn)行序列的算術(shù)編碼的計(jì)算步驟：（1）根據(jù)信源符號(hào)積累概率公式計(jì)算信源符號(hào)的積累概率（2）初始時(shí)，設(shè)S=?，F(xiàn)(?)=0，p(?)=1；（3）根據(jù)序列的積累概率遞推公式，計(jì)算序列的積累概率

F(ur)和序列的概率p(ur)；（4）計(jì)算碼長(zhǎng)；（5）將F(s)寫成二進(jìn)制數(shù)形式，取其前L位作為序列S的碼字，若后面有尾數(shù)就進(jìn)位到第L位。F(u)將[0,1)分割成許多小區(qū)間，以小區(qū)間的左端點(diǎn)數(shù)值的二進(jìn)制小數(shù)表示該序列，同時(shí)要將該小數(shù)的小數(shù)位數(shù)截?cái)酁閘位，截?cái)嘁?guī)則為：l位后面只要有非0的余數(shù)就要向第l位進(jìn)位。最后得到了小數(shù)0.t。將t作為事件u=(u1u2…uL)的碼字。碼字長(zhǎng)度l為算術(shù)編碼算術(shù)編碼則即因而即[例]設(shè)信源

求信源序列S=abda對(duì)應(yīng)的小區(qū)間解:信源符號(hào)對(duì)應(yīng)區(qū)間端點(diǎn)值符號(hào)概率區(qū)間a0.5[0,0.5)b0.25[0.5,0.75)c0.125[0.75,0.875)d0.125[0.875,1)信源序列對(duì)應(yīng)區(qū)間端點(diǎn)值信源序列l(wèi)owhigha00.5ab0.250.375abd0.3593750.375abda0.3593750.3671875信源序列S=abda對(duì)應(yīng)區(qū)間的劃分過程圖0.75

a

bcd00.50.8751

aa

abacad0.2500.3750.5

aba

abbabcabd0.250.3593750.375

a

bcd0.3593750.36718750.375不同的信源序列分別對(duì)應(yīng)不同的互不重疊的小區(qū)間，取小區(qū)間內(nèi)的一個(gè)點(diǎn)作為對(duì)應(yīng)序列的編碼。--------即時(shí)碼S=abda的編碼譯碼——編碼的逆過程根據(jù)接收到的碼字譯出對(duì)應(yīng)的信源序列[譯碼步驟](1)判斷碼字落在哪個(gè)符號(hào)區(qū)間，譯出第1個(gè)符號(hào)(2)將碼字減去剛譯出符號(hào)的左端點(diǎn)值，得差值并以剛譯出符號(hào)對(duì)應(yīng)的區(qū)間長(zhǎng)度去除差值再判斷此值落在哪個(gè)符號(hào)區(qū)間，譯出第2個(gè)符號(hào)(3)重復(fù)步驟(2)，直至全部信源序列被譯完為止例:

下面對(duì)使用前面提到的4符號(hào)模型進(jìn)行編碼的一段信息進(jìn)行解碼。編碼的結(jié)果是0.538(為了容易理解，這里使用十進(jìn)制而不是二進(jìn)制；我們也假設(shè)得到的結(jié)果的位數(shù)恰好夠我們解碼)。類似于編碼的過程，我們從區(qū)間[0,1)開始，使用相同的概率模型，將它分成四個(gè)子區(qū)間。中性對(duì)應(yīng)的區(qū)間是[0,0.6)陽性對(duì)應(yīng)的區(qū)間是[0.6,0.8)陰性對(duì)應(yīng)的區(qū)間是[0.8,0.9)數(shù)據(jù)結(jié)束符對(duì)應(yīng)的區(qū)間是[0.9,1)算術(shù)編碼的譯碼分?jǐn)?shù)0.538落在中性所在的子區(qū)間[0,0.6)；這表明編碼器所讀的第一個(gè)符號(hào)必然是中性，這樣就可以將它作為消息的第一個(gè)符號(hào)記下來。

算術(shù)編碼的譯碼然后我們將區(qū)間[0,0.6)再分成四個(gè)子區(qū)間：中性的區(qū)間是[0,0.36)--[0,0.6)的60%

陽性的區(qū)間是[0.36,0.48)--[0,0.6)的20%

陰性的區(qū)間是[0.48,0.54)--[0,0.6)的10%

數(shù)據(jù)結(jié)束符的區(qū)間是[0.54,0.6).--[0,0.6)的10%

分?jǐn)?shù)0.538在[0.48,0.54)區(qū)間；所以消息的第二個(gè)符號(hào)一定是陰性。算術(shù)編碼的譯碼再一次將當(dāng)前區(qū)間劃分成四個(gè)子區(qū)間：中性的區(qū)間是[0.48,0.516)陽性的區(qū)間是[0.516,0.528)陰性的區(qū)間是[0.528,0.534)數(shù)據(jù)結(jié)束符的區(qū)間是[0.534,0.540).分?jǐn)?shù)0.538落在符號(hào)數(shù)據(jù)結(jié)束符的區(qū)間；所以，這一定是下一個(gè)符號(hào)。由于它也是內(nèi)部的結(jié)束符號(hào)，這也就意味著編碼已經(jīng)結(jié)束。算術(shù)編碼的譯碼§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)用。

1982年，Rissanen

和G.G.Langdon一起改進(jìn)了算術(shù)編碼。之后，人們又將算術(shù)編碼與J.G.Cleary和I.H.Witten于1984年提出的部分匹配預(yù)測(cè)模型（PPM）相結(jié)合，開發(fā)出了壓縮效果近乎完美的算法。今天，那些名為PPMC、PPMD或PPMZ并號(hào)稱壓縮效果天下第一的通用壓縮算法，實(shí)際上全都是這一思路的具體實(shí)現(xiàn)?？雌饋?，壓縮技術(shù)的發(fā)展可以到此為止了。不幸的是，事情往往不像想象中的那樣簡(jiǎn)單：算術(shù)編碼雖然可以獲得最短的編碼長(zhǎng)度，但其本身的復(fù)雜性也使得算術(shù)編碼的任何具體實(shí)現(xiàn)在運(yùn)行時(shí)都慢如蝸牛。即使在摩爾定律大行其道，CPU速度日新月異的今天，算術(shù)編碼程序的運(yùn)行速度也很難滿足日常應(yīng)用的需求。如果不是后文將要提到的兩個(gè)猶太人，我們還不知要到什么時(shí)候才能用上WinZIP

這樣方便實(shí)用的壓縮工具呢。詞典編碼方法逆向思維永遠(yuǎn)是科學(xué)和技術(shù)領(lǐng)域里出奇制勝的法寶。就在大多數(shù)人絞盡腦汁想改進(jìn)Huffman或算術(shù)編碼，以獲得一種兼顧了運(yùn)行速度和壓縮效果的“完美”編碼的時(shí)候，兩個(gè)聰明的猶太人J.Ziv

和A.Lempel獨(dú)辟蹊徑，完全脫離Huffman及算術(shù)編碼的設(shè)計(jì)思路，創(chuàng)造出了一系列比Huffman編碼更有效，比算術(shù)編碼更快捷的壓縮算法。我們通常用這兩個(gè)猶太人姓氏的縮寫，將這些算法統(tǒng)稱為L(zhǎng)Z系列算法。詞典編碼方法說實(shí)話，LZ系列算法的思路并不新鮮，其中既沒有高深的理論背景，也沒有復(fù)雜的數(shù)學(xué)公式，它們只是簡(jiǎn)單地延續(xù)了千百年來人們對(duì)字典的追崇和喜好，并用一種極為巧妙的方式將字典技術(shù)應(yīng)用于通用數(shù)據(jù)壓縮領(lǐng)域。通俗地說，當(dāng)你用字典中的頁碼和行號(hào)代替文章中每個(gè)單詞的時(shí)候，你實(shí)際上已經(jīng)掌握了LZ系列算法的真諦。這種基于字典模型的思路在表面上雖然和Shannon、Huffman等人開創(chuàng)的統(tǒng)計(jì)學(xué)方法大相徑庭，但在效果上一樣可以逼近信息熵的極限。而且，可以從理論上證明，LZ系列算法在本質(zhì)上仍然符合信息熵的基本規(guī)律。詞典編碼方法詞典編碼方法詞典編碼方法是基于數(shù)據(jù)中許多結(jié)構(gòu)頻繁重復(fù)再現(xiàn)這一事實(shí),人們可以對(duì)相同符號(hào)串分配同一碼字、通過索引、或者其他諸如此類的方法編碼。70年代末提出、80年代中期走向?qū)嵱没腖Z壓縮技術(shù)開創(chuàng)了現(xiàn)代詞典編碼方法,并且已經(jīng)牢固地統(tǒng)治著通用壓縮世界。LZ的基本思想是:數(shù)據(jù)中的子串可以通過用指代先前已處理數(shù)據(jù)(即歷史數(shù)據(jù))中相同子串的方式來描述。對(duì)歷史數(shù)據(jù)的存儲(chǔ)方式可以不同,例如，LZ77采用滑動(dòng)的緩沖區(qū)(或稱窗口)記錄,LZ78則選擇詞典方式進(jìn)行登錄。應(yīng)該指出的是,兩者的壓縮效率沒有顯著差異,而且都是當(dāng)重復(fù)的子串越長(zhǎng)壓縮效率越高。按照時(shí)間順序，LZ系列算法的發(fā)展歷程大致是：Ziv

和Lempel