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

第三章：信源編碼-離散信源無失真編碼§3.1信源及其分類§3.2離散無記憶（簡單）信源的等長編碼§3.3離散無記憶（簡單）信源的不等長編碼§3.4最佳不等長編碼§3.1信源及其分類信源的概念

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

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

以下將順序地敘述下面的相關(guān)概念：§3.1信源及其分類§3.2離散無記憶（簡單）信源的等長編碼（1）設(shè)有一個離散無記憶簡單信源，信源發(fā)出的隨機變量序列為：…U-2U-1U0U1U2…。

設(shè)信源隨機變量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）設(shè)有一個含D個字母的字母表。對于(U1U2…UL)的每一個事件(u1u2…uL)，都用一個字母串(c1c2…)來表示。這種表示方法稱為D元編碼；每一個事件(u1u2…uL)所對應的字母串(c1c2…)稱為一個碼字。

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

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

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

：R=NlogD/L≤R0?！?.2離散無記憶（簡單）信源的等長編碼（6）無錯編碼

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

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

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

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

設(shè)給定一個R0>H(U)。對每個正整數(shù)L，對應地取整數(shù)N=[R0L]（R0L的下取整）。則N/L≤R0，limL→+∞N/L=R0。進而，任取正數(shù)ε≤(R0-H(U))/2，存在正整數(shù)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)

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

首先聲明，所有的對數(shù)計算都是以2為底的。此時實際的編碼速率為R=N/L。任取正數(shù)ε≤(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,ε)中的事件的個數(shù)不超過長度為N的2元碼字的數(shù)量2N。因此，做如下的編碼：將TU(L,ε)中的事件用不同的N長2元碼字來表示，而將TU(L,ε)以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L,ε)中的某個事件?！?.2離散無記憶（簡單）信源的等長編碼對應的譯碼：所有的碼字均譯為它所表示的TU(L,ε)中的事件。結(jié)論：①實際的編碼速率R滿足R0≥R>H(U)；②“譯碼錯誤”的概率pe=P((U1U2…UL)不屬于TU(L,ε))=1-P((U1U2…UL)∈TU(L,ε))<ε。得證。漸進無錯編碼的要求給定離散無記憶簡單信源：…U-2U-1U0U1U2…；給定編碼設(shè)備的編碼速率R0，滿足R0>H(U)；給定一個任意小的正數(shù)ε>0；要求：選擇合適的L，N，對(U1U2…UL)進行合適的2元N長編碼，使得①實際的編碼速率R=N/L滿足R≤R0；

②“譯碼錯誤”的概率pe<ε?！?.2離散無記憶（簡單）信源的等長編碼漸進無錯編碼的步驟①由U1的概率分布計算②取L滿足。③取整數(shù)N=[R0L]（R0L下取整）。④取典型序列集§3.2離散無記憶（簡單）信源的等長編碼漸進無錯編碼的步驟⑤將TU(L,ε)中的事件用不同的N長2元碼字來表示，而將TU(L,ε)以外的事件用一個固定的N長2元碼字來表示，這個固定的N長2元碼字已經(jīng)用來表示了TU(L,ε)中的某個事件。⑥譯碼時，所有的碼字均譯為它所表示的TU(L,ε)中的事件。注解：顯然滿足R≤R0；|TU(L,ε)|≤2N，因此碼字足夠用；譯碼錯誤的概率為pe=P{(U1U2…UL)=(u1u2…uL)|(u1u2…uL)不屬于TU(L,ε)}<ε；一般來說，ε越小，要求L越大，因此對應的N越大?！?.2離散無記憶（簡單）信源的等長編碼例設(shè)§3.2離散無記憶（簡單）信源的等長編碼設(shè)給定編碼設(shè)備的編碼速率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元碼字已經(jīng)用來表示了TU(L,ε)中的某個事件。

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

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

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

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

①唯一可譯性，或者叫做可識別性。對于一個碼，如果存在一種譯碼方法，使任意若干個碼字所組成的字母串只能唯一地被翻譯成這幾個碼字所對應的事件序列。這個碼就被稱為是唯一可譯的。§3.3離散無記憶（簡單）信源的不等長編碼解決方案：適當?shù)鼐幋a，使得每個碼字都具有識別標記。（注解：一個唯一可譯的、碼字長度不超過N的D元碼，其碼字個數(shù)小于D(DN-1)/(D-1)個。這是因為兩個碼字c(1)和c(2)連接成的字母串c(1)c(2)不能是碼字）§3.3離散無記憶（簡單）信源的不等長編碼③實時譯碼和容量限制。②平均碼字長度。設(shè)信源隨機變量U的概率分布為{ak,q(ak),k=1~K}，事件ak對應的碼字長度為nk，則平均碼字長度為希望小。解決方案：在事件與碼字匹配時，概率大的事件用短碼字。§3.3離散無記憶（簡單）信源的不等長編碼唯一可譯性的解決方法一定義3.3.2(p63)若①事件與碼字一一對應；②每個碼字的開頭部分都是一個相同的字母串；③這個字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個碼字的結(jié)合部。則稱這個字母串為逗號，稱此碼為逗點碼?！?.3離散無記憶（簡單）信源的不等長編碼唯一可譯性的解決方法二定義3.3.4(p63)若①事件與碼字一一對應；②每個碼字都不是另一個碼字的開頭部分（字頭）。則稱此碼為異字頭碼?！?.3離散無記憶（簡單）信源的不等長編碼注解逗點碼顯然是唯一可譯的，識別碼字的方法為：見到逗號就識別為一個碼字的開始。異字頭碼也是唯一可譯的，識別碼字的方法為：見到一個碼字就識別為一個碼字。（許多具體的異字頭碼有更加簡便的識別碼字的方法）§3.3離散無記憶（簡單）信源的不等長編碼例觀察表3.3.1(p64)。事件概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.12510111110111§3.3離散無記憶（簡單）信源的不等長編碼碼A不是唯一可譯的。碼B不是唯一可譯的。碼C是唯一可譯的，識別碼字的方法為：見“0”或“111”就是一個碼字的結(jié)束。實際上，碼C是異字頭碼。碼D是唯一可譯的，識別碼字的方法為：見“0”就是一個碼字的開始。實際上，碼D是逗點碼，其中“0”是逗號?！?.3離散無記憶（簡單）信源的不等長編碼碼C不是逗點碼。碼D不是異字頭碼。碼C的平均碼長比碼D的平均碼長?。捍aC的平均碼長為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離散無記憶（簡單）信源的不等長編碼異字頭碼的第一種構(gòu)造方法：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離散無記憶（簡單）信源的不等長編碼如此一直到每個非空段不能再分（只含有一個事件）為止。此時，一個事件的碼字就是這個事件所在的段的標號序列，從1級標號到末級標號。（當然，那些空段和它們的標號序列是沒有用的，要去掉）為了使平均碼長小，每次切分段時應使D段的概率盡可能相近?！?.3離散無記憶（簡單）信源的不等長編碼例.對下面消息源進行2-元Shannon—Fano編碼編碼結(jié)果：平均碼長：§3.3離散無記憶（簡單）信源的不等長編碼例.對下面消息源進行3-元Shannon—Fano編碼第一次分組：第二次分組：第三次分組：§3.3離散無記憶（簡單）信源的不等長編碼例.對下面消息源進行3-元Shannon—Fano編碼編碼結(jié)果：平均碼長：§3.3離散無記憶（簡單）信源的不等長編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法（D元編碼，字母表為{0,1,…,D-1}）(0)如果源隨機變量的事件的個數(shù)K不是(D-1)的倍數(shù)加1，則添加若干0概率事件使得事件的個數(shù)是(D-1)的倍數(shù)加1。(1)將概率最小的D個事件分別賦予標號“0”到“D-1”?！?.3離散無記憶（簡單）信源的不等長編碼異字頭碼的第二種構(gòu)造方法：Huffman編碼法（D元編碼，字母表為{0,1,…,D-1}）(2)將這D個事件合并為一個事件，其概率為這D個事件概率之和,并將這D個事件分別賦予標號“0”到“D-1”。重復(1)-(2)，直到事件的個數(shù)等于D。此時，一個事件的碼字是這個事件從最后標號開始到最先標號為止的標號序列。(當然要去掉那些0概率事件和它們的標號序列)編碼完畢。§3.3離散無記憶（簡單）信源的不等長編碼例.對下面消息源進行2元和3元的Huffman編碼2元編碼結(jié)果：平均碼長：§3.3離散無記憶（簡單）信源的不等長編碼例.對下面消息源進行2-元和3元的Huffman編碼3元編碼結(jié)果：平均碼長：§3.3離散無記憶（簡單）信源的不等長編碼為什么Shannon-Fano碼和Huffman碼都是異字頭碼？看右圖，稱這種圖為碼樹。碼樹上的每個碼字都結(jié)束在樹梢。這種形狀保證了碼是異字頭碼。如果不是異字頭碼，則有的碼字就不結(jié)束在樹梢，而在中間節(jié)點。01010101010101010101§3.3離散無記憶（簡單）信源的不等長編碼定理3.3.1(Kraft不等式，p65)設(shè)信源隨機變量共有K個事件。則：各碼字長度分別為n1、n2、…、nK的D元異字頭碼存在的充分必要條件是§3.3離散無記憶（簡單）信源的不等長編碼證明不妨設(shè)n1≤n2≤…≤nK。則各碼字長度分別為n1、n2、…、nK的D元異字頭碼存在，當且僅當：存在這樣一個D叉樹，樹上有一個n1級樹梢，再有一個n2級樹梢，…，再有一個nK級樹梢；當且僅當：存在nK級D叉滿樹，樹上有個nK級樹梢，§3.3離散無記憶（簡單）信源的不等長編碼再有個nK級樹梢，…，再有個nK級樹梢；當且僅當：§3.3離散無記憶（簡單）信源的不等長編碼定理3.3.2(p53)設(shè)信源隨機變量共有K個事件，則：一個唯一可譯的、各碼字長度分別為n1、n2、…、nK的D元不等長碼存在的充分必要條件是（不加證明）§3.3離散無記憶（簡單）信源的不等長編碼推論：設(shè)信源隨機變量共有K個事件，則：一個唯一可譯的、各碼字長度分別為n1、n2、…、nK的D元不等長碼存在的充分必要條件是存在各碼字長度分別為n1、n2、…、nK的D元異字頭碼。作業(yè)：3.4對于有4個字母的離散無記憶源有兩個碼A和B，參看下表。試問：(a)各碼是否滿足異字頭條件?是否為唯一可譯碼?(b)當收到1時得到多少關(guān)于字母a1的信息?(c)當收到1時得到多少關(guān)于信源的平均信息?字母概率碼A碼Ba1a2a3a4

0.40.30.20.110100100011101001000

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

另一方面，取n1、n2、…、nK，§3.3離散無記憶（簡單）信源的不等長編碼存在碼字長度為

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

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

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

設(shè)信源隨機變量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元異字頭碼?！?.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’的平均碼長?！?.4最佳不等長編碼另一方面，碼R的平均碼長=碼R’的平均碼長+事件a的概率+事件b的概率；碼W的平均碼長=碼W’的平均碼長+事件a的概率+事件b的概率。所以:碼R的平均碼長≤碼W的平均碼長≤碼V的平均碼長≤碼T的平均碼長≤碼S的平均碼長。補充定理得證。§3.4最佳不等長編碼補充定理給出了一種構(gòu)造信源隨機變量U的最佳2元異字頭碼的方法：(1)取出兩個概率最小的事件a和事件b，分別標號為0和1；(2)然后將事件a和事件b合并成事件e，將信源隨機變量U合并成U’；(3)尋找U’的最佳2元異字頭碼；(4)然后將該碼中事件e的碼字后面分別添加事件a和事件b的標號（0和1），分別成為事件a和事件b的碼字。這種構(gòu)造方法正是2元Huffman編碼?！?.4最佳不等長編碼定理對信源隨機變量U的2元Huffman編碼是最佳2元異字頭碼，因而是在唯一可譯前提下的最佳2元不等長編碼。3.6令離散無記憶信源如上。(a)求對U（即U1）的最佳二元碼、平均碼長和編碼效率。(b)求對U2

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

設(shè)離散無記憶信源為若信源輸出序列為0100100001001000，試對其進行算術(shù)編碼。答案：給事件對應的小區(qū)間左端點事件的概率故因而碼字為算術(shù)編碼的譯碼過程(0)s為若干個二元碼字組成的比特串。記二進制有限小數(shù)S=0.s。(1)取u1滿足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滿足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最佳不等長編碼算術(shù)編碼的譯碼過程（4）記§3.4最佳不等長編碼輸出事件u=(u1u2…uL)。將s的前n位作為事件u=(u1u2…uL)的碼字，并從s中去掉這個碼字，得到新的比特串s。轉(zhuǎn)（0）。§3.4最佳不等長編碼練習

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

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

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