編碼理論課件

第一章緒論信息論相關(guān)知識(shí)和概念編碼理論信息論相關(guān)知識(shí)介紹信息的產(chǎn)生和傳播信息的定義與分類信息的特性及性質(zhì)狹義信息論：指香農(nóng)信息理論，主要研究信息的測(cè)度，信道容量，信道信源編碼等問(wèn)題，也稱經(jīng)典信息論。是基礎(chǔ)理論一般信息論：泛指通信理論，通信的數(shù)學(xué)理論，廣泛研究信息傳輸和處理的問(wèn)題。廣義信息論：包含上述兩種理解，還包括所有與信息有關(guān)的自然、社會(huì)領(lǐng)域。香農(nóng)信息理論，是為設(shè)計(jì)有效可靠的通信系統(tǒng)提供理論依據(jù)。對(duì)信息論的理解

信息的產(chǎn)生和傳播信息是人類生產(chǎn)實(shí)踐中互通情報(bào)中產(chǎn)生的信息發(fā)展的五次變革，極大的推動(dòng)了社會(huì)的進(jìn)步信息科學(xué)技術(shù)知識(shí)成為最重要的戰(zhàn)略資源，人們現(xiàn)在關(guān)注于信息科學(xué)技術(shù)知識(shí)的開(kāi)發(fā)和利用，人類社會(huì)的發(fā)展與信息傳播速度密切相關(guān)

信息科學(xué)、信息技術(shù)、信息產(chǎn)業(yè)信息的定義與分類1948年，維納提出：信息就是信息，它既不是物質(zhì)也不是能量一般普遍對(duì)信息的理解是，信息=消息=情報(bào)=知識(shí)=信號(hào)？信息不等同于情報(bào)信息不等同于知識(shí)信息與消息：消息是信息的載荷者，需要指出的是：一個(gè)消息可以含有不同的信息量，同一信息也可以用不同的消息來(lái)載荷。數(shù)據(jù)、圖片可能發(fā)布的是同一信息

信息不等同于信號(hào)：信號(hào)是消息的一種表現(xiàn)形式，又是消息的載體，它是一種物理量。信號(hào)攜帶著信息，但不是信息本身，同一信息可以用不同信號(hào)表示，同一信號(hào)也可以表示不同信息。信息的定義與分類信息的定義與分類信息是構(gòu)成客觀世界的三大要素之一信息的定義：信息是事物運(yùn)動(dòng)狀態(tài)或存在方式的不確定性的描述信息的分類：語(yǔ)法信息：事物的狀態(tài)和狀態(tài)改變方式本身。研究事物運(yùn)動(dòng)出現(xiàn)的各種可能狀態(tài)和這些狀態(tài)之間的聯(lián)系。是抽象的。語(yǔ)義信息：研究信息的主體含義。語(yǔ)用信息：研究信息客觀價(jià)值。人們對(duì)客觀世界運(yùn)動(dòng)規(guī)律和存在狀態(tài)的認(rèn)識(shí)結(jié)果。信息傳遞信息處理—再生信息傳遞信息獲取信息施用外部世界問(wèn)題／環(huán)境信息運(yùn)動(dòng)過(guò)程語(yǔ)義信息語(yǔ)法信息語(yǔ)用信息信息的特性及性質(zhì)信息的特性：信息是無(wú)形的（無(wú)形性）信息是可共享的（共享性）共享性的矛盾（競(jìng)爭(zhēng)），加密信息阻礙信息的傳播和發(fā)展。信息是擴(kuò)充的，信息永遠(yuǎn)在產(chǎn)生、更新、演變（無(wú)限性）信息是可以度量的：必須滿足信息的三個(gè)條件——結(jié)構(gòu)的（離散結(jié)構(gòu)）、統(tǒng)計(jì)的（用統(tǒng)計(jì)方式、發(fā)生概率來(lái)測(cè)量不確定性）、語(yǔ)義的（有具體含義）信息的特性及性質(zhì)信息的性質(zhì)：普遍性無(wú)限性性對(duì)性轉(zhuǎn)移性變換性有序性動(dòng)態(tài)性轉(zhuǎn)化性編碼理論編碼理論的基本概念編碼理論的發(fā)展編碼理論研究的內(nèi)容和目的編碼理論的基本概念所謂編碼，廣義地說(shuō)就是信號(hào)的變換，是信息處理的主要手段。編碼的主要目的是提高系統(tǒng)對(duì)某一方面的要求以及優(yōu)化系統(tǒng)某一方面的性能指標(biāo)根據(jù)信息論的各種編碼定理和通信系統(tǒng)的性能指標(biāo)，編碼可分為信源編碼、信道編碼和密碼編碼三類通信系統(tǒng)模型編碼理論的基本概念信源加密密鑰干擾信道信宿信源信源編碼加密信道信道編碼信道解碼解密信源解碼信宿解密密鑰通信系統(tǒng)模型的組成部分和功能說(shuō)明主要實(shí)體：信源和信宿信道及干擾源編碼器譯碼部分——編碼部分的逆過(guò)程編碼理論的發(fā)展信源編碼1、無(wú)失真信源編碼：對(duì)信源進(jìn)行編碼，沒(méi)有帶來(lái)信息量的損失。（適用于離散信源或數(shù)字信號(hào)）

2、限失真信源編碼：在一定準(zhǔn)則下，對(duì)信號(hào)源進(jìn)行編碼。（適用于連續(xù)信源或模擬信號(hào)）信道編碼

編碼理論研究的內(nèi)容和目的

編碼理論是以信息作為主要研究對(duì)象，以信息的運(yùn)動(dòng)規(guī)律和利用信息的原理作為主要的研究?jī)?nèi)容，以信息科學(xué)方法論作為主要的研究方法，以擴(kuò)大人的信息功能為主要研究目的的一門新興科學(xué)。它的基本理論是信息論，控制論和系統(tǒng)論。第二章無(wú)失真信源編碼信息量、熵和互信息信源編碼定理霍夫曼碼及其他編碼方法算術(shù)編碼游程編碼改進(jìn)的霍夫曼碼通用編碼第二章無(wú)失真信源編碼無(wú)失真編碼：保證信源產(chǎn)生的全部信息無(wú)失真地傳遞給信宿。（只有對(duì)離散信源可以實(shí)現(xiàn)無(wú)失真信源編碼。）實(shí)質(zhì)上是一種概率匹配編碼。限失真信源編碼：在確定標(biāo)準(zhǔn)和準(zhǔn)則的條件下，信源所必須傳遞的最小信息量。也稱信息率失真函數(shù)（限定波形失真——波形編碼，限定特性參量失真——參量編碼）。第二章無(wú)失真信源編碼信源中的統(tǒng)計(jì)多余度主要取決于以下兩個(gè)主要因素：一是消息概率分布的非均勻性，另一個(gè)是消息間的相關(guān)性。對(duì)無(wú)記憶信源主要取決于概率分布的非均勻性，但是，對(duì)于有記憶信源，兩者都起作用，且相關(guān)性更加重要。第二章無(wú)失真信源編碼統(tǒng)計(jì)匹配編碼：是根據(jù)信源的不同概率分布而選用與之相匹配的編碼，以達(dá)到的系統(tǒng)同中傳信速率最小，且滿足在信宿復(fù)制時(shí)無(wú)失真或低于某一允許的失真限度值。2．1信息量、熵和互信息量時(shí)間發(fā)生的概率越小，不確定性就越大，給人的信息量就越?。话l(fā)生的概率越大，不確定性就越小，給人的信息量就越大。

條件概率聯(lián)合概率必須掌握的概率論知識(shí)必須掌握的概率論知識(shí)全概率：設(shè)B1

,B2

,…

是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：必須掌握的概率論知識(shí)4)Bayes公式:

設(shè)B1

,B2

,…

是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；

p（Bi）＞0，i=1，2，…，則對(duì)任一事件A，有：一個(gè)離散無(wú)記憶信源是由n個(gè)符號(hào)消息組成的集合:X={x1，x2

·

·

·

xn

}，這n個(gè)符號(hào)消息的概率分布為了：稱為符號(hào)xi

的先驗(yàn)概率,散信源數(shù)學(xué)模型表示為：

稱為概率空間,其中從概率的角度看，可以將符號(hào)消息xi看一個(gè)隨機(jī)事件。因此xi具有不確定性。

2．1信息量、熵和互信息量信息量定義：2．1信息量、熵和互信息量信息量定義：美國(guó)科學(xué)家L.V.R.Hartley于1928年給出了信息的度量方法。定義若信源發(fā)出一符號(hào)xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關(guān)xi的信息量用I(xi；yi)表示，稱為互信息量。

定義上述情況，若信道無(wú)干擾，收到的就是xi本身，這樣I(xi；yi)就可以用I(xi；xi)表示，或簡(jiǎn)單記作I(xi)，并稱為自信息量。一、自信息量1)函數(shù)I(xi)的屬性

1o

若有兩個(gè)事件xi

，xj

，其先驗(yàn)概率為p(xi)＜p(xj)，則事件xi比事件xj有更大的不確定性，同時(shí)會(huì)帶來(lái)更多的信息量；I(xi)>I(xj)2o

事件xi先驗(yàn)概率p(xi)=1（確定事件）,則不存在不確定性，同時(shí)不會(huì)帶來(lái)信息量；I(xi)=0.3o

事件xi先驗(yàn)概率p(xi)=0（不可能事件）,則存在不確定性應(yīng)為無(wú)窮大，同時(shí)會(huì)帶來(lái)無(wú)窮的信息量；I(xi)→∞.4o

兩個(gè)統(tǒng)計(jì)獨(dú)立事件的聯(lián)合自信息量應(yīng)等于它們各自信息量之和;則I(xy)=

I(x)＋I(xiàn)(y)2)

定義一個(gè)符號(hào)消息xi的自信息量為其發(fā)生概率的對(duì)數(shù)的負(fù)數(shù)，并記為I(xi)：

I(xi)=－logp(xi)

當(dāng)p(xi)=0，則I(xi)→∞；當(dāng)p(xi)=1，則I(xi)=0.3)自信息量的單位自信息量的單位與所用對(duì)數(shù)的底有關(guān)：

1o

對(duì)數(shù)的底是2時(shí)，單位為比特—bit(binaryunit)2o

對(duì)數(shù)的底是e(自然對(duì)數(shù))時(shí)，單位為奈特

—nat(natureunit)3o

對(duì)數(shù)的底是10(常用對(duì)數(shù))時(shí)，單位為笛特或哈特

—det(decimalunit)orHart(Hartley)三種信息量單位之間的換算：

1det=log210≈3.322bit1bit=ln2≈0.6931nat

1bit=lg

2≈0.3010det1nat=log2e≈1.4427bit

在信息論中常用以2為底的對(duì)數(shù)，為了書(shū)寫(xiě)方便，以后將log2書(shū)寫(xiě)為log，因其單位為比特bit，不會(huì)產(chǎn)生混淆；注意有些文獻(xiàn)將log2書(shū)寫(xiě)為lb4)自信息量的含義是隨機(jī)量、根據(jù)單個(gè)符號(hào)消息的先驗(yàn)概率確定其信息量和不確定度。二、離散信源熵信源X發(fā)出某一個(gè)符號(hào)提供的信息量不適合描述信源X發(fā)出一個(gè)符號(hào)提供的信息量。定義信息源的平均不確定度為信源中各個(gè)符號(hào)不確定度的數(shù)學(xué)期望，記作H(X)

其中

H(X)又稱為信源X的信源熵。

2)H(X)

的含義

1o

表示的是信源的平均不確定度。

2o

表示信源X發(fā)出一個(gè)符號(hào)提供的平均信息量。

3o

是統(tǒng)計(jì)量、數(shù)學(xué)期望（統(tǒng)計(jì)平均）、各個(gè)符號(hào)平均不確定度和平均信息量。

3)

信源熵單位：二進(jìn)制:bit/信源符號(hào)，或bit/信源序列十進(jìn)制:det/信源符號(hào)，或det/信源序列

e進(jìn)制:nat/信源符號(hào)，或nat/信源序列

4)信源熵的三種特殊情況1o

當(dāng)

p(xi)=0時(shí)（p(xi)→0），則p(xi)logp(xi)=02o

信源X={x1，x2

·

·

·

xn

}

，若其中xi

的概率p(xi)=1

則其余xj的p(xj)=0，因?yàn)閯tH(X)=0bit/信源符號(hào)3o

當(dāng)信源中X所有n個(gè)符號(hào)均有相同的概率p(xi)=1/n，則H(X)=-(1/n)log(1/n)=lognbit/信源符號(hào)2o

聯(lián)合熵（共熵）

聯(lián)合熵是聯(lián)合符號(hào)集合XY上的每個(gè)元素對(duì)xi

,

yj的自信息量的概率加權(quán)的統(tǒng)計(jì)平均值。3o

條件熵與聯(lián)合熵的關(guān)系

I(xi

|yj)=－logp(xi

|

yj)

，I(xi

yj)=－logp(xi

yj)

因

全概率公式5)條件熵與聯(lián)合熵

1o

條件熵在給定yj條件下，xi的條件自信息量為：

I(xi

|yj)=－logp(xi

|

yj)

集合X的條件熵為：

在給定Y（即各個(gè)yj）條件下，集合X的條件熵定義為：三、互信息（一）簡(jiǎn)單的通信模型

若信源發(fā)出符號(hào)xi，由于信道存在干擾，收到的不是xi而是yi，從yi中獲取有關(guān)xi的信息量稱為互信息量，用I(xi;yi)表示。信源X有干擾離散信道信宿Y干擾源所以H(XY)=H(X

)＋H(Y|X)同理H(XY)=H(Y)＋H(X|Y)含義：平均從Y獲得的關(guān)于X的信息量。 （又稱信道 的信息傳輸率R）（二）平均互信息※I(X;Y)與熵：※I(X;Y)與I(x;y)：

I(x;y)表示由隨機(jī)事件y中獲得的關(guān)于事件x的信息?；バ畔?/p>

:關(guān)系：I(X;Y)＝EXY[I(x;y)]注意：（二）平均互信息

※比較：I(x;y)可正可負(fù)，1．非負(fù)性I(X;Y)≥0（三）平均互信息的性質(zhì)

※

當(dāng)I(X;Y)=0全損信道：H(X)=H(X|Y)，說(shuō)明：

通信的意義——通過(guò)消息的傳遞可獲得信息信源加密密鑰源信道解密信宿保密通信系統(tǒng)框圖XY’Y非法用戶全損信道（三）平均互信息的性質(zhì)

※信息處理的一般規(guī)律：通過(guò)傳輸獲得的信息量不大于提供的信息量。

※

I(X;Y)=H(X)無(wú)損信道：H(X|Y)=02．

極值性，P(x|y)=0or1（三）平均互信息的性質(zhì)

I(X;Y)=I(Y;X)３．交互性（對(duì)稱性)（三）平均互信息的性質(zhì)I(X;Y)=H(X)－H(X|Y)=H(Y)－H(Y|X)

4.

I(X;Y)與各類熵的關(guān)系

文氏圖H(X∣Y)H(Y∣X)信源熵信道疑義度（損失熵）噪聲熵（散布度）I(X;Y)

=H(X)+H(Y)－H(XY)信宿熵H(XY)（三）平均互信息的性質(zhì)特殊信道特殊信道總結(jié)

信道名稱信道特征信息傳輸情況全損信道P(xy)=P(x)P(y)H(X︱Y)=H(X)I(X；Y)=0無(wú)噪信道

P(y︱x)=0or1H(Y︱X)=0I(X；Y)=H(Y)無(wú)損信道

P(x︱y)=0or1H(X︱Y)=0I(X；Y)=H(X)（三）平均互信息的性質(zhì)

5．

凸?fàn)钚訧(X;Y)=f[P(x)，P(y|x)]（三）平均互信息的性質(zhì)Th3.2：對(duì)于固定信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的∪型凸函數(shù)?！煌旁赐ㄟ^(guò)不同信道傳輸?shù)玫降钠骄バ畔⒉煌?/p>

5．

凸?fàn)钚訲h3.1：對(duì)于固定信道，平均互信息I(X;Y)是信源概率分布p(x)的∩型凸函數(shù)。平均互信息是信源符號(hào)概率分布的上凸函數(shù)平均互信息是信道轉(zhuǎn)移概率的下凹函數(shù)（三）平均互信息的性質(zhì)

例1．

分析二元信源通過(guò)BSC信道的I(X;Y)特性信源：，信道：1－p1－ppp0011則（三）平均互信息的性質(zhì)其中，

（三）平均互信息的性質(zhì)，得：（三）平均互信息的性質(zhì)

I.

固定信道（p一定），∴H(p)一定I(X;Y)∝H(ω+p－2ωp)由熵上凸性的該I(X;Y)為ω的上凸函數(shù)I(X;Y)1－H(p)01/21ωω＝1/2時(shí)，I(X;Y)極大I(X;Y)＝H(1/2)－H(p)=1－H(p)

（三）平均互信息的性質(zhì)Ⅱ.

固定信源（ω一定）則I(X;Y)～p，∴I(X;Y)=I(p)∴I(p)為下凹函數(shù)可求：p=1/2,I(X;Y)=0,極小p=0,I(X;Y)=H(ω)p=1,I(X;Y)=H(ω)I(X;Y)01/21p（三）平均互信息的性質(zhì)2．2信源編碼定理信源編碼的無(wú)失真編碼：接收端信宿要求無(wú)失真精確的復(fù)制信源輸出的消息。只有對(duì)離散信源才可以實(shí)現(xiàn)無(wú)失真編碼。實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼——根據(jù)信源的不同概率分布而選用與之相匹配的編碼，以達(dá)到在系統(tǒng)中傳送速率最小，且滿足在信宿復(fù)制時(shí)無(wú)失真或低于某一允許的失真限度值。2．2．1信源編碼的基本概念信源編碼：將信源輸出符號(hào)，經(jīng)信源編碼器變換成另外的壓縮符號(hào)，然后將壓縮有信息經(jīng)信道傳送到信宿。只考慮信源和信宿兩個(gè)因素。通信系統(tǒng)模型簡(jiǎn)化為P15圖2-1編碼A器輸入為：編碼器輸出的碼字為：符號(hào)碼1碼2碼3碼4等長(zhǎng)碼變長(zhǎng)碼u100001u201101101u3100000001u311011100012．2．1信源編碼的基本概念樹(shù)圖（碼樹(shù)）法：樹(shù)根=碼字的起點(diǎn)樹(shù)的度=碼元數(shù)分支結(jié)點(diǎn)=碼的符號(hào)的一部分終端結(jié)點(diǎn)=待編碼符號(hào)滿樹(shù)=等長(zhǎng)碼：樹(shù)中各結(jié)點(diǎn)有相同樹(shù)枝數(shù)，且每層結(jié)點(diǎn)樹(shù)達(dá)到最大值。非滿樹(shù)=變長(zhǎng)碼2．2．1信源編碼的基本概念編碼方法：1）將待編碼的字符作為終端結(jié)點(diǎn)，構(gòu)造碼樹(shù)；2）按一定規(guī)則給每個(gè)樹(shù)枝分配一個(gè)標(biāo)記；3）將從根到終端結(jié)點(diǎn)的路徑上的編號(hào)依次相連，作為該終端結(jié)點(diǎn)所表示的字符的編碼。2．2．1信源編碼的基本概念譯碼方法：1）從樹(shù)根出發(fā)，根據(jù)接收到的第一個(gè)碼字符號(hào)來(lái)選擇應(yīng)走的第一條路徑。2）沿所選路徑走到分支結(jié)點(diǎn)，在根據(jù)收到的第而個(gè)碼字選擇應(yīng)走的第二條路徑。直至走到終端結(jié)點(diǎn)為止。3）根據(jù)所走路徑，可立即判斷出接收到的碼符號(hào)。4）重新返回到樹(shù)根，再作下一個(gè)接收碼符號(hào)的判斷。2．2．1信源編碼的基本概念

分組碼（塊碼）分類

1°按碼字的碼長(zhǎng)分類定長(zhǎng)碼：碼集中所有碼字的碼長(zhǎng)相等。變長(zhǎng)碼：碼集中所有碼字的碼長(zhǎng)不全相等。

2°按信源符號(hào)與碼字對(duì)應(yīng)關(guān)系分類非奇異碼：信源符號(hào)與碼字是一一對(duì)應(yīng)的。奇異碼：信源符號(hào)與碼字不是一一對(duì)應(yīng)的。

3°按譯碼唯一性分類

唯一可譯碼：對(duì)于多個(gè)碼字組成的有限長(zhǎng)碼流，只能唯一地分割一個(gè)個(gè)的碼字。唯一可譯碼又稱為單義碼.例碼流100111000…

碼1x1→0x2→10x3→11可分割10,0,11,10,0,0

碼2x1→1x2→10x3→11則無(wú)法唯一分割

唯一可譯碼在傳輸過(guò)程中不需要同步碼。

非唯一可譯碼：對(duì)有限長(zhǎng)碼流，不能唯一地分割一個(gè)個(gè)的碼字。4°按譯碼的即時(shí)性分類

非即時(shí)碼：接收端收到一個(gè)完整的碼字后，不能立即譯碼；還需要等到下一個(gè)碼字開(kāi)始接收后才能判斷是否可以譯碼。

即時(shí)碼：接收端收到一個(gè)完整的碼字后，就能立即譯碼；即時(shí)碼又稱為非延長(zhǎng)碼或異前綴碼。例非即時(shí)碼

碼流01001100…

x1→0x2→01x3→11譯碼為x2,x1,x1,x3,x1,?

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

異前綴碼(即時(shí)碼)指的是碼集任何一個(gè)碼不能是其他碼的前綴.

即時(shí)碼必定是唯一可譯碼,唯一可譯碼不一定是即時(shí)碼.5°有實(shí)用價(jià)值的分組碼分組碼是非奇異碼、唯一可譯碼、即時(shí)碼

2．2．2變長(zhǎng)碼若要實(shí)現(xiàn)無(wú)失真編碼，不但要求信源符號(hào)與每個(gè)符號(hào)的碼字一一對(duì)應(yīng)，而且要求碼符號(hào)序列與信源符號(hào)序列也一一對(duì)應(yīng)。也就是要求所編的碼為惟一可譯碼。我們首先分析等長(zhǎng)編碼，再分析變長(zhǎng)編碼，以做比較。一、等長(zhǎng)碼基本問(wèn)題等長(zhǎng)碼特點(diǎn)：C2={000,001,100,101,111}，l2=3code/sig要求：

問(wèn)題：

例1．

惟一可譯碼等長(zhǎng)編碼C1={00,01,10,11,10}，l1=2code/sig(2)高效奇異碼一、等長(zhǎng)碼基本問(wèn)題可能的碼字?jǐn)?shù)≥消息數(shù)

對(duì)基本信源編碼：對(duì)N長(zhǎng)源編碼：要求：消息數(shù)碼字?jǐn)?shù)：rl∴rl≥q(l≥logrq)（對(duì)例1，q=5,∴要求：2l≥5，即l≥3）∴rl≥qN(l/N≥logrq)一、等長(zhǎng)碼基本問(wèn)題則，q=53=125種<128=27

∴l(xiāng)=7code/3_sigs平均碼長(zhǎng)：l/N=7/3=2.33code/sig<l2

例1（續(xù)）S的三次擴(kuò)展：

※

等長(zhǎng)碼碼長(zhǎng)要求l/N

logrq（保證唯一可譯碼，無(wú)失真）

※

logrq為下限

※

擴(kuò)展信源編碼的平均碼長(zhǎng)<基本源編碼的平均碼長(zhǎng)結(jié)論：一、等長(zhǎng)碼基本問(wèn)題

例2．英文源S：{26個(gè)字母+空格符號(hào)}，q=27

由q=27≤2l，得l≥5code/sig∴編碼后信息傳輸率：R=H(S)/l=1.4/5=0.28bit/code

二元信源[0,1]：H(X)max=1bit/code考察效率：H∞(S)=1.4bit/sig該編碼冗余度大平均碼長(zhǎng)太長(zhǎng)例3：設(shè)信源

則二次擴(kuò)展信源為：

l=2code/sigL2=2code/2_sigsl=1code/sig信源有記憶時(shí)，采用N長(zhǎng)源編碼，l減小一、等長(zhǎng)碼基本問(wèn)題二、等長(zhǎng)信源編碼定理

定理2-1（等長(zhǎng)信源編碼定理） 一個(gè)熵為H(U)的離散無(wú)記憶信源，若對(duì)信源長(zhǎng)為N的符號(hào)序列進(jìn)行等長(zhǎng)編碼，設(shè)碼字是從m個(gè)字母的碼符號(hào)集中選取L個(gè)碼元組成。對(duì)于任意

>0，只要滿足：

則當(dāng)N足夠大時(shí)，可實(shí)現(xiàn)幾乎無(wú)失真編碼，即譯碼錯(cuò)誤概率可為任意小。

則不可能實(shí)現(xiàn)無(wú)失真編碼，且當(dāng)N足夠大時(shí)譯碼錯(cuò)誤概率近似等于1。反之，若：※

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

※

基本方法：N長(zhǎng)源、變長(zhǎng)編碼

※對(duì)等長(zhǎng)編碼,若要實(shí)現(xiàn)幾乎無(wú)失真編碼,則信源長(zhǎng)度必滿足:定理2-1說(shuō)明：二、等長(zhǎng)信源編碼定理當(dāng)δ≤10-5（即PE<10-5）

解：H(S)=0.811bit/sig

例4．DMS進(jìn)行等長(zhǎng)編碼

則有：η=0.5得N≥71687

η=0.8得N≥1146990

η=0.9得N≥5806641

η=0.96得N≥41291672等長(zhǎng)碼的缺點(diǎn)：平均碼長(zhǎng)太長(zhǎng)使信道復(fù)雜化容易產(chǎn)生溢出或取空差錯(cuò)的擴(kuò)散變長(zhǎng)碼特點(diǎn)：每個(gè)碼字長(zhǎng)度可不同要求：唯一可譯定理2-2：（Kraft不等式）設(shè)信源符號(hào)S=｛s1,…,sN｝,碼符號(hào)X＝{x1,…,xm}，又設(shè)碼字W1，W2，…Wn的碼長(zhǎng)分別為l1，l2，…，ln，則存在惟一可譯碼的充要條件是：三、惟一可譯碼的判斷※碼長(zhǎng)結(jié)構(gòu)～惟一可譯碼1、Kraft不等式編碼碼元數(shù)目1、Kraft不等式

——惟一可譯碼存在的必要條件例1．考察：①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}非惟一可譯符號(hào)碼1碼2碼3碼4等長(zhǎng)碼變長(zhǎng)碼u100001u201101101u3100000001u31101110001惟一可譯碼非惟一可譯碼非惟一可譯碼惟一可譯碼2、根據(jù)定義判斷基本準(zhǔn)則：等長(zhǎng)碼——若為非奇異碼，則為唯一可譯碼；變長(zhǎng)碼——碼本身及任意次擴(kuò)展碼均非奇異。主要方法：

樹(shù)圖法（即時(shí)碼必為惟一可譯碼）

尾隨后綴法（尾隨后綴集合F中不含任一碼字）010110010010111010011001110101111例2.C1={0,10,1100,1110,1011,1101}F:{11,00,10,01,0,11,1,100,110,011,101}100非惟一可譯碼eg:1011001110...例2.C2={1,10,100,1000}1101000000

F={0,00}惟一可譯碼C3={1,01,001,0001}

F=一般離散無(wú)記憶信源輸出的各消息（符號(hào)）的概率是不相等的。對(duì)出現(xiàn)頻率大的信源符號(hào)采用較短的碼字；而對(duì)出現(xiàn)概率小的信源符號(hào)采用較長(zhǎng)的碼字。從整個(gè)信源來(lái)看，編成的信源碼字的平均碼長(zhǎng)最短，也實(shí)現(xiàn)了與信源統(tǒng)計(jì)特性相匹配。定義碼字的平均碼長(zhǎng)度：平均碼長(zhǎng)是每個(gè)信源符號(hào)平均需用的碼元數(shù)。它和編碼后的壓縮效果密切相關(guān)。平均碼長(zhǎng)大，則壓縮效果差，系統(tǒng)有效性差。因此，我們一般選用平均碼長(zhǎng)最短的編碼。編碼后每個(gè)碼元攜帶的信息量就是信道的信息傳輸率：例3．對(duì)DMS進(jìn)行無(wú)失真編碼。編碼一：基本源編碼——L=1code/sig編碼二：N長(zhǎng)源編碼aiP(ai)碼CliS1S19/1601S1S23/16102S2S13/161103S2S21/161113四、變長(zhǎng)信源編碼定理

若一個(gè)離散無(wú)記憶信源U具有熵為H(U)，并有m個(gè)碼元的碼符號(hào)X＝｛x1，x2，

xm｝。則總可以找到一種無(wú)失真編碼方法，構(gòu)成惟一可譯碼，使信源S中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿足：

緊致碼：若有一個(gè)唯一可譯碼，其平均碼長(zhǎng)小于所 有其他唯一可譯碼的平均碼長(zhǎng)，稱此碼為緊 致碼或最佳碼。定理2-3：變長(zhǎng)編碼定理四、變長(zhǎng)信源編碼定理

證明若xi

按如下不等式取所對(duì)應(yīng)碼字的碼長(zhǎng)為L(zhǎng)

,

若為整數(shù),則上述不等式左邊取等號(hào).

故可得

四、變長(zhǎng)信源編碼定理

因?yàn)樗?/p>

所有碼字長(zhǎng)度滿足Kraft不等式

如何降低平均碼長(zhǎng)：（1）減少信源熵H(X)

（2）增加信道碼元數(shù)m四、變長(zhǎng)信源編碼定理

注意到li∈Z,∴取其整數(shù)部分例3．Shannon編碼的核心四、變長(zhǎng)信源編碼定理

DMS的N次擴(kuò)展信源UN＝｛

1，

2，

nN｝，其熵為H(UN)，并有碼符號(hào)X＝｛x1，x2，

xn｝。對(duì)信源UN進(jìn)行編碼，總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源U中每個(gè)信源符號(hào)所需的平均碼長(zhǎng)滿足：

定理2-4：香農(nóng)第一定理（無(wú)失真變長(zhǎng)信源編碼定理）

四、變長(zhǎng)信源編碼定理

且當(dāng)N

時(shí)，有：

其中， 為N長(zhǎng)源編碼的平均碼長(zhǎng)，

i是

i所對(duì)應(yīng)的碼字長(zhǎng)度。

信源X

的N次擴(kuò)展信源XNXN

的信源熵為H(XN)bit/N個(gè)信源符號(hào)

XN

所對(duì)應(yīng)碼字的碼長(zhǎng)碼符/N個(gè)信源符號(hào)①平均碼長(zhǎng)的下限即信源熵是無(wú)失真信源編碼的最小平均碼長(zhǎng)?、诖嬖谛远ɡ?方法：N長(zhǎng)源，變長(zhǎng)碼③適用于平穩(wěn)有記憶信源，H(U)=H∞定理2-4說(shuō)明四、變長(zhǎng)信源編碼定理

表述三：（無(wú)噪信道編碼定理） 若信道的信息傳輸率R不大于信道容量，總能對(duì)信源的輸出進(jìn)行適當(dāng)編碼，使得在無(wú)損無(wú)噪信道上能無(wú)差錯(cuò)地以最大信息傳輸率C傳輸信息；但要使信道信息傳輸率R大于C而無(wú)差錯(cuò)地傳輸則是不可能的。表述二：若R

>H(S)，就存在唯一可譯變長(zhǎng)編碼；若R

<H(S)，唯一可譯變長(zhǎng)編碼不存在，不能實(shí)現(xiàn)無(wú)失真編碼。四、變長(zhǎng)信源編碼定理

編碼后每個(gè)信源符號(hào)能載荷的最大信息量為：表述四：設(shè)信源熵為H（比特/符號(hào)），無(wú)噪無(wú)損信道的信道容量為Ct（比特/秒），則總可以找到一種編碼方法對(duì)信源的輸出進(jìn)行無(wú)失真編碼，使得在信道上傳輸?shù)钠骄a速率為（Ct/H-ε）（符號(hào)/秒），其中ε為任意小的正數(shù)，但要使傳輸?shù)钠骄a速率大于Ct/H（符號(hào)/秒）是不可能的。四、變長(zhǎng)信源編碼定理

四、變長(zhǎng)信源編碼定理

若對(duì)信源U進(jìn)行編碼所得到的平均碼長(zhǎng)，因?yàn)槠骄a長(zhǎng)一定大于或等于Hm(U)，所以定義編碼的效率為：對(duì)同一信源來(lái)說(shuō)，碼的平均碼長(zhǎng)越短，越接近極限值Hm(U)，信道的信息傳輸率就越高，越接近無(wú)噪無(wú)損信道容量。碼剩余度定義：對(duì)于二元無(wú)噪無(wú)損信道m(xù)=2，Hm(U)=H(U)αiP(αi)

碼Cλis1s19/1601s1s23/16102s2s13/161103s2s21/161113例3．比較

N長(zhǎng)源編碼的效率。解：H(S)=0.811bit/sig

四、變長(zhǎng)信源編碼定理

五、統(tǒng)計(jì)匹配編碼離散無(wú)失真編碼實(shí)質(zhì)上是一種統(tǒng)計(jì)匹配編碼，是根據(jù)信源符號(hào)的不同概率分布分配與之相對(duì)應(yīng)碼字，對(duì)出現(xiàn)概率大的符號(hào)分配短的碼字，對(duì)出現(xiàn)概率小的符號(hào)分配長(zhǎng)的碼字，這樣可以使信源符號(hào)的平均碼長(zhǎng)最短。編碼器輸入：編碼器輸出的碼字為：要實(shí)現(xiàn)無(wú)失真信源編碼，必須同時(shí)滿足無(wú)失真和有效性兩個(gè)條件，只能從信源統(tǒng)計(jì)特性上去考慮。2.3霍夫曼碼及其他編碼方法一、霍夫曼碼二、費(fèi)諾編碼三、香農(nóng)-費(fèi)諾-埃利斯碼1．二元Huffman編碼一、Huffman編碼

④

分配碼元。縮減信源步驟：①

遞減排序；S=[s1，s2，…，sq]②

合并概率最小的兩個(gè)符號(hào);③

重復(fù)①②，直至縮減信源中只有兩個(gè)符號(hào)為止；合二為一一分為二例1:已知離散無(wú)記憶信源如下所示，對(duì)應(yīng)的霍夫曼編碼為：消息符號(hào)ui符號(hào)概率P(ui)u10.5u20.25u30.125u40.1250.250.51.0010101111111碼長(zhǎng)碼字1021031103111信息熵：平均碼長(zhǎng)：編碼效率：編碼不唯一（0、1分配不同，排序不同）1．二元Huffman編碼消息符號(hào)si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.0101010001010101碼長(zhǎng)碼字21021130003001301040110401111100000101011011例2．平均碼長(zhǎng)唯一0.110.260.350.39一、Huffman編碼

碼長(zhǎng)方差：碼21．二元Huffman編碼（例2）源符Si概率P(Si)S10.4S20.2S30.2S40.1S50.1010001000001001000110100101101001101

一、Huffman編碼

二元Huffman碼的特點(diǎn)：※※每次縮減信源的最后兩個(gè)碼字總是最后一位不同（前面各位相同）1．二元Huffman編碼——惟一可譯一、Huffman編碼

n=(m－1)Q+m

（對(duì)于二元編碼，n=Q+m）※

為使短碼充分利用，，要求最后信源有m個(gè)符號(hào)“合m為一，一分為m”填充法消息數(shù)目縮減次數(shù)一、Huffman編碼

2．m元Huffman編碼一、Huffman編碼

2．m元Huffman編碼步驟：驗(yàn)證n是否滿足n=(m-1)Q+m，若不滿足，可以人為地增加一些概率為零的符號(hào)，使最后一步有m個(gè)信源符號(hào)；取概率最小的m個(gè)符號(hào)合并成一個(gè)新結(jié)點(diǎn)，并分別用0，1，…，（m+1）給各分支賦值，把這些符號(hào)的概率相加作為該新結(jié)點(diǎn)的概率；將新結(jié)點(diǎn)和剩下結(jié)點(diǎn)重新排隊(duì)，重復(fù)步驟2；取樹(shù)根到葉子（信源符號(hào)對(duì)應(yīng)結(jié)點(diǎn)）的各樹(shù)枝上的賦值，得到各符號(hào)碼字。

解：n=5,若取m=32．m元Huffman編碼∴需加入兩個(gè)填充符號(hào)有5=2Q+3n=(m－1)Q+m

一、Huffman編碼

例3．三元Huffman編碼若取m=4有5=3Q+4取5+2=3Q+42．m元Huffman編碼過(guò)程一、Huffman編碼

消息符號(hào)ui符號(hào)概率P(ui)u10.4u20.3u30.2u40.05u50.050120120.30碼字1202122碼長(zhǎng)112222．m元Huffman編碼過(guò)程一、Huffman編碼

消息符號(hào)ui符號(hào)概率P(ui)u10.4u20.3u30.2u40.05u50.05u60u70012301230.1碼字01230313233碼長(zhǎng)1112222填充符號(hào)一、Huffman編碼

H(U)=1.95bit編碼效率：2．r元Huffman編碼過(guò)程

一般情況下，信源符號(hào)集的數(shù)目應(yīng)遠(yuǎn)大于碼元數(shù)。定理在變長(zhǎng)編碼中，如果碼字長(zhǎng)度嚴(yán)格按照所對(duì)應(yīng)符號(hào)的出現(xiàn)概率逆序排列，則其平均碼長(zhǎng)為最小。3．Huffman碼的最佳性

碼字長(zhǎng)度與出現(xiàn)概率逆序排列；每次縮減信源的最后r個(gè)碼字末位不同。一、Huffman編碼

費(fèi)諾（Fano）編碼（即時(shí)碼）二、費(fèi)諾（Fano）編碼

1.遞減排列;2.等概分組P(A)≈P(B);3.每個(gè)子集以符號(hào)“0”或“1”標(biāo)識(shí)。方法：等概分割步驟：費(fèi)諾編碼屬于統(tǒng)計(jì)匹配編碼，但它不是最佳的編碼方法例4：DMS如下，用費(fèi)諾編碼方法編碼消息符號(hào)ui符號(hào)概率P(ui)u10.5u20.25u30.125u40.125第一次分組01第二次分組01第三次分組01碼字010110111碼長(zhǎng)1233H(U)=1.75bit消息符號(hào)si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.01第一次分組01第二次分組0101第三次分組0101第四次分組01碼字碼長(zhǎng)0020103011310211031110411114例5香農(nóng)-費(fèi)諾-埃利斯碼三、香農(nóng)-費(fèi)諾-埃利斯碼方法：根據(jù)信源符號(hào)累積概率分配碼字不是分組碼，也不是最佳碼，但效率高步驟：1.確定信源符號(hào)修正的累積概率函數(shù)；2.將修正的累積概率函數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)，取小數(shù)點(diǎn)后l(uk)位為碼字。設(shè)信源為：信源符號(hào)積累概率為：信源符號(hào)修正的積累概率為：碼長(zhǎng)：平均碼長(zhǎng)：例6：DMS如下，用香農(nóng)-費(fèi)諾-埃利斯編碼方法編碼消息符號(hào)ui符號(hào)概率P(ui)u10.25u20.5u30.125u40.125F(uk)0.150.750.8751F(uk)0.1250.50.81250.9375二進(jìn)制F(uk)0.0010.1000.11010.1111碼長(zhǎng)l(uk)3244碼字0011011011111H(U)=1.75bitHuffman碼在實(shí)際應(yīng)用中的問(wèn)題誤差擴(kuò)散概率匹配速率匹配2.4算術(shù)編碼Huffman編碼更適合于大消息集信源，對(duì)于小消息集信源使用算術(shù)編碼和游程編碼壓縮效果更好。主要內(nèi)容：積累概率的遞推公式算術(shù)編碼原理算術(shù)編碼的碼長(zhǎng)遞推公式的應(yīng)用不做乘法的算術(shù)編碼2.4.1積累概率的遞推公式信源符號(hào)積累概率設(shè)信源信源符號(hào)積累概率：2.4.1積累概率的遞推公式信源序列積累概率傳遞公式設(shè)獨(dú)立信源序列信源序列S添加一個(gè)新的信源符號(hào)ur后所得新序列Sur的積累概率。信源序列S的概率。信源符號(hào)ur的積累概率。信源序列S添加一個(gè)新的信源符號(hào)ur后所得新序列Sur的概率。信源符號(hào)ur的概率。信源序列的積累概率F(S)與信源符號(hào)的積累概率一樣，可用[0,1)區(qū)間內(nèi)的個(gè)點(diǎn)來(lái)表示，因此積累概率F(S)將區(qū)間[0,1)分成許多不同的小區(qū)間，他們互不重疊，序列S的概率p(S)就是兩點(diǎn)間小區(qū)間的長(zhǎng)度。小區(qū)間內(nèi)的一個(gè)點(diǎn)可用來(lái)表示序列的概率。2.4.2算術(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)度與該序列的概率相匹配。算術(shù)編碼的主要任務(wù)是計(jì)算信源序列對(duì)應(yīng)的小區(qū)間。2.4.2算術(shù)編碼原理小區(qū)間劃分的遞推計(jì)算公式小區(qū)間左端點(diǎn)遞推公式：小區(qū)間右端點(diǎn)遞推公式：新序列Sur對(duì)應(yīng)區(qū)間的左端點(diǎn)值。信源序列S對(duì)應(yīng)區(qū)間的左端點(diǎn)值。信源序列S對(duì)應(yīng)區(qū)間的寬度值。信源符號(hào)ur對(duì)應(yīng)區(qū)間的左端點(diǎn)值。新序列Sur對(duì)應(yīng)區(qū)間的右端點(diǎn)值。信源序列S對(duì)應(yīng)區(qū)間的左端點(diǎn)值。信源序列S對(duì)應(yīng)區(qū)間的寬度值。信源符號(hào)ur對(duì)應(yīng)區(qū)間的右端點(diǎn)值。2.4.2算術(shù)編碼原理計(jì)算小區(qū)間端點(diǎn)值的步驟（1）給出信源符號(hào)對(duì)應(yīng)的區(qū)間；（2）初始時(shí)，設(shè)S=?（?代表空集），low(?)=0，high(?)=1，range(?)=1（3）輸入ur，根據(jù)公式計(jì)算序列Sur的左右端點(diǎn)值，依次下去，直到全部信源序列對(duì)應(yīng)的區(qū)間被確定為止。2.4.2算術(shù)編碼原理[例2-10]設(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.36718752.4.2算術(shù)編碼原理信源序列對(duì)應(yīng)區(qū)間的劃分0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.375不同的信源序列分別對(duì)應(yīng)不同的互不重疊的小區(qū)間，取小區(qū)間內(nèi)的一個(gè)點(diǎn)作為對(duì)應(yīng)序列的編碼。--------即時(shí)碼S=abda的編碼2.4.2算術(shù)編碼原理譯碼步驟：（1）判斷碼字落在哪個(gè)符號(hào)區(qū)間，翻譯出1個(gè)符號(hào)；（2）將碼字減去剛翻譯出的符號(hào)的左端點(diǎn)值；（3）用剛翻譯出的符合對(duì)應(yīng)的區(qū)間的長(zhǎng)度去除步驟2的結(jié)果，判斷此值落在哪個(gè)符號(hào)區(qū)間，翻譯出一個(gè)新符號(hào)；（4）反復(fù)步驟（2）（3）直至全部信源序列被翻譯完為止。2.4.2算術(shù)編碼原理0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.3752.4.3算術(shù)編碼的碼長(zhǎng)碼字長(zhǎng)度應(yīng)與序列的概率匹配取信源序列碼字的前L位，若后面有尾數(shù)，就進(jìn)位到第L位。根據(jù)信源編碼定理可知信源序列S的平均碼長(zhǎng)滿足：平均每個(gè)信源符號(hào)的碼長(zhǎng)：對(duì)于DMS有2.4.4遞推公式的應(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)寫(xiě)成二進(jìn)制數(shù)形式，取其前L位作為序列S的碼字，若后面有尾數(shù)就進(jìn)位到第L位。2.4.4遞推公式的應(yīng)用例[2-12]設(shè)二元獨(dú)立信源求信源序列S=1010的算術(shù)編碼。解：信源符號(hào)的積累概率F(0)=0；F(1)=0.25信源序列1010算術(shù)編碼序列F(S)p(S)L序列碼字?01010.010.1111100.010.00112011010.0100110.001001301110100.0100110.00001001501010S=?，F(xiàn)(?)=0，p(?)=12.4.4遞推公式的應(yīng)用算術(shù)編碼具有漸近最佳性：當(dāng)序列無(wú)限增長(zhǎng)時(shí)，平均碼長(zhǎng)漸近地等于序列的熵值。實(shí)際存在問(wèn)題：遞推運(yùn)算中都有乘法——運(yùn)算量大解決辦法：1）編碼對(duì)象是二元序列，符號(hào)概率較小的一個(gè)為2-k的形式，則乘以2-k等于移位，乘以1-2-k等于移位相減。

2）不做乘法的算術(shù)編碼。2.4.5不做乘法的算術(shù)編碼二元信源序列積累概率的遞推公式為：

F(S0)=F(S)+p(S)F(0)=F(S)F(S1)=F(S)+p(S)F(1)p(S1)=p(S)p(1)p(S0)=p(S)p(0)p(S)=p(S0)+p(S1)，F(xiàn)(1)=p(0)如果令p(S1)≈2-qp(S)，則不做乘法的二進(jìn)制算術(shù)編碼的遞推公式為

p(S0)=p(S)-p(S1)F(S0)=F(S)F(S1)=F(S)+p(S)F(1)=F(S)+p(S)p(0)=F(S)+p(S0)即：p(S1)≈2-qp(S)p(S0)=p(S)-p(S1)F(S0)=F(S)F(S1)=F(S)+p(S0)不做乘法的算術(shù)編碼步驟：（1）初始時(shí)，設(shè)S=?，p(?)=0.111….1，F(xiàn)(?)=0.000…0;（2）輸入一個(gè)信源符號(hào)，用遞推公式計(jì)算p(S1)，p(S0)，F(xiàn)(S0)，F(xiàn)(S0)；（3）重復(fù)步驟（2），直至信源序列結(jié)束。2.4.5不做乘法的算術(shù)編碼實(shí)際應(yīng)用時(shí)，由p(S1)≈2-qp(S)，一般2-q近似等于二元序列中小概率符號(hào)的概率值。通常取p(0)≈2-q。2.5游程編碼（RLC）游程編碼屬于無(wú)損壓縮編碼1)二元信源序列將“白”、“黑”二元信源用｛0，1｝表示。2)游程和游程序列

1°游程：規(guī)定以“0”開(kāi)始的二元序列，例000101110010001…2°游程長(zhǎng)度：序列中連續(xù)“0”段稱“0”游程或“白”游程，其0的個(gè)數(shù)稱“0”游程長(zhǎng)度，記lW；序列中連續(xù)“1”段稱“1”游程或“黑”游程，其1的個(gè)數(shù)稱“1”游程長(zhǎng)度，記lB。

3°游程序列:將二元序列中的lW、lB按其在二元序列中的順序排列的序列稱游程序列。上例3113213…3)游程編碼將游程變換成游程序列后,二元序列就變換成多元序列.下面分別對(duì)“白”游程L(0)和黑”游程L(1)的編碼進(jìn)行討論

1°白游程的熵

lW

:白游程的長(zhǎng)度p(lW):白游程長(zhǎng)度的概率

L白游程的最大長(zhǎng)度

2°黑游程的熵

lB:黑游程的長(zhǎng)度p(lB):白游程長(zhǎng)度的概率

L白游程的最大長(zhǎng)度

2.5游程編碼（RLC）2.5游程編碼（RLC）

3°白、黑游程編碼的平均碼長(zhǎng)

4°白、黑游程的平均長(zhǎng)度

5°白、黑像素的熵hWhB與平均碼長(zhǎng)

6°像素的熵h01與平均碼長(zhǎng)

pW:黑像素的概率pB:白像素的概率

2.5游程編碼（RLC）2.6改進(jìn)的Huffman碼（MH）傳真機(jī)信源編碼應(yīng)用于文件傳真：如文件、手寫(xiě)稿、表格、報(bào)紙、圖紙等“白”、“黑”像素點(diǎn)的信息。

CCITT(國(guó)際電話電報(bào)咨詢委員會(huì))為了保證傳真文件的清晰度,對(duì)于A4幅面的文件（210mm×297mm）規(guī)定

1°行掃描線共有：

297mm×4線/mm=1188線或297mm×8線/mm=2376線

2°每條掃描線：

1728像素點(diǎn)/線，8像素點(diǎn)/mm3°對(duì)于A4幅面的文件像素點(diǎn)

1728像素點(diǎn)/線×1188線=2052864像素點(diǎn)

1728像素點(diǎn)/線×2376線=4105728像素點(diǎn)

直接編碼,以碼率2400bit/s或4800bit/s傳輸時(shí)間至少需5min以上.2.6改進(jìn)的Huffman碼（MH）2.6改進(jìn)的Huffman碼（MH）

方法介紹：Huffman編碼＋游程編碼MH編碼：l=K+R，查表對(duì)游程編碼之前,先要測(cè)得白、黑游程的概率分布,作為編碼的依據(jù).CCITT(國(guó)際電話電報(bào)咨詢委員會(huì))推薦8種樣張我國(guó)原郵電部推薦7種樣張為了減少碼表數(shù),采用截?cái)郒uffman編碼(MH)

一類為結(jié)尾碼,白、黑游程的長(zhǎng)度為0--63

另一類為基干碼,游程長(zhǎng)度為64的整倍數(shù)2.6改進(jìn)的Huffman碼（MH）

例．一行中一段解：①lW＝131=2×64+3:K=10010R=1000∴100101000（l1=9）②lB=0×64+4:R=011（l2=3）③lW=0×64+6:R=1110（l3=4）④lB=1×64+6:K=0000001111R=0010（l4=14）比較：MH：碼元表：9+3+4+14=30bit

直接編碼：131+4+6+70=211bit

壓縮比211/30=7.03lW＝131lB=4lW=6lB=70A．比較：碼元表：MH：2×(64+1728/64)＝182個(gè)直接Huffman：2×1729=3458個(gè)性能：P（lW<61）＝80%P（lB<6）＝80%∴工程上性能不差

B．極限壓縮比②

性能分析2.6改進(jìn)的Huffman碼（MH）2.7通用編碼一、分段編碼（LZ碼）二、匹配編碼三、LZW算法一、分段編碼（LZ碼）分段規(guī)則：

使連著的信源符號(hào)盡可能少，但不能出現(xiàn)重復(fù)段。

yj=yiur(j>i)

兩個(gè)數(shù)可用一個(gè)數(shù)Nj（第j段段的碼字）來(lái)表示

Nj=mi+r

特點(diǎn)：編碼與符號(hào)概率無(wú)關(guān)。編碼效率比較高。一、分段編碼（LZ碼）第j段碼長(zhǎng)公式：編碼步驟：1.將信源序列分段2.計(jì)算Nj及第j段碼長(zhǎng)lj3.將Nj編成二進(jìn)制碼，取lj位為段的碼字。[例1]設(shè)信源符號(hào)集U={a0,a1,a2,a3}，求信源序列S=a0a0a2a3a1a1a0a0a0a3a2的LZ編碼。分7段：a0,a0a2,a3,a1,a1a0,a0a0,a3a2j段序號(hào)irNjlj碼字1a00002002a0a212631103a3033400114a1011400015a1a040165100006a0a01045001007a3a23214501110信源序列碼字：0011000110001100000010001110二、段匹配碼（LZ78算法）編碼步驟：1.分段2.將段號(hào)和信源符號(hào)分別進(jìn)行編碼，若組成二元碼，段號(hào)所需碼長(zhǎng)每個(gè)信源符號(hào)所需碼長(zhǎng)：[例2]設(shè)信源符號(hào)集U={a0,a1,a2,a3}，求信源序列S=a0a0a2a3a1a1a0a0a0a3a2的匹配編碼。分7段：a0,a0a2,a3,a1,a1a0,a0a0,a3a2

段號(hào)碼字000001010011100101110段號(hào)1234567符號(hào)a0a0a2a3a1a1a0a0a0a3a2碼字a000a101a210a311C=7段號(hào)所需碼長(zhǎng)：m=4信源符號(hào)所需碼長(zhǎng)：0000101101010000001110信源序列編碼序列：000000010

010010110110

110001

001010

000110111

0二、段匹配碼平均碼長(zhǎng)：當(dāng)n很長(zhǎng)時(shí)：LZ78碼是一種簡(jiǎn)單的通用編碼，編碼方法不需要知道信源的統(tǒng)計(jì)概率分布，而且編碼方法簡(jiǎn)單，編譯碼速度快，又能達(dá)到最佳壓縮編碼效率三、LZW算法LZW編碼算法步驟：1.串表初始化：將所有單個(gè)字符存入串表中，并給每個(gè)符號(hào)賦一個(gè)碼字值；2.將第一個(gè)輸入字符作為“前綴串”P；3.每個(gè)新輸入的字符作為擴(kuò)展字符S。

若PS字符串不在串表中，輸出P對(duì)應(yīng)的碼字，將PS存入串表并分配一個(gè)碼字值；S→P；若PS已在串表中，PS→P；4.重復(fù)步驟3，知道完成編碼。[例3]由三元字符X、Y、Z組成的信源序列為：

S=XYXYZYXYXYXXXXXXX求LZW編碼。X1Y2Z3XY4YX5XYZ6ZY7YXY8YXYX9XX10字符串碼字XXX11XXXX12輸入信源序列XYXYZYXYXYXXXXXX輸出LZW碼字12435811011編碼表（串表）LZW算法是LZ78算法的使用修正形式，保留了LZ碼的自適應(yīng)性能，壓縮效率大致相同，成為計(jì)算機(jī)文件壓縮的標(biāo)準(zhǔn)算法。且算法硬件實(shí)現(xiàn)容易。本章重點(diǎn)內(nèi)容信息量、信息熵、互信息的概念及定義式?？死蛱夭坏仁綗o(wú)失真變長(zhǎng)信源編碼定理（香農(nóng)第一定理）主要的編碼方法：Huffman碼、費(fèi)諾碼、香農(nóng)-費(fèi)諾碼、算術(shù)碼、MH碼、LZ碼。各種編碼方法的平均碼長(zhǎng)和編碼效率的計(jì)算。本章難點(diǎn)克拉夫特不等式:

表述了信源符號(hào)數(shù)與碼字長(zhǎng)度應(yīng)滿足什么條件才能構(gòu)成即時(shí)碼。唯一可譯碼有相同不等式存在----麥克米倫不等式這兩個(gè)不等式都只是描述了可構(gòu)造性，不能作為判定的論據(jù)。唯一可譯碼的判定準(zhǔn)則：樹(shù)圖法：（即時(shí)碼必為惟一可譯碼）尾隨后綴法：（尾隨后綴集合F中不含任一碼字）本章難點(diǎn)010110010010111010011001110101111例.C1={0,10,1100,1110,1011,1101}F:{11,00,10,01,0,11,1,100,110,011,101}100非惟一可譯碼eg:1011001110...例.C2={1,10,100,1000}1101000000

F={0,00}惟一可譯碼C3={1,01,001,0001}

F=第三章相關(guān)信源編碼一、預(yù)測(cè)編碼二、變換編碼一、預(yù)測(cè)編碼(PredictiveCoding)預(yù)測(cè)編碼的基本原理預(yù)測(cè)方法預(yù)測(cè)編碼的基本類型DPCM編譯碼原理(略)預(yù)測(cè)編碼的基本原理預(yù)測(cè)編碼是數(shù)據(jù)壓縮三大經(jīng)典技術(shù)之一是將信源輸出信號(hào)通過(guò)預(yù)測(cè)變換后再對(duì)信源輸出與被測(cè)值的差進(jìn)行編碼。預(yù)測(cè)編碼原理圖：預(yù)測(cè)器編碼器信源輸出編碼輸出預(yù)測(cè)編碼的基本原理實(shí)現(xiàn)預(yù)測(cè)編碼的關(guān)鍵問(wèn)題：1.預(yù)測(cè)誤差準(zhǔn)則的選?。唬Q定了預(yù)測(cè)質(zhì)量）

1）最小均方誤差準(zhǔn)則（MMSE）--最常用，最基本的

2）功率包絡(luò)匹配準(zhǔn)則（PSEM）

3）預(yù)測(cè)系數(shù)不變性準(zhǔn)則（PCIV）--用于多種混合信號(hào)預(yù)測(cè)

4）最大誤差準(zhǔn)則（ME）--遙測(cè)數(shù)據(jù)壓縮2.預(yù)測(cè)函數(shù)的選??；3.預(yù)測(cè)器輸入數(shù)據(jù)的選取。預(yù)測(cè)方法線性預(yù)測(cè)—樣值和預(yù)測(cè)值之間呈線性關(guān)系

1）前值預(yù)測(cè)

2）一維預(yù)測(cè)

3）二維預(yù)測(cè)（非線性預(yù)測(cè)）最佳預(yù)測(cè)—是按某種準(zhǔn)則，選擇線性預(yù)測(cè)系數(shù)使得預(yù)測(cè)誤差為最小。（常用MSE）自適應(yīng)預(yù)測(cè)—預(yù)測(cè)器的預(yù)測(cè)系數(shù)不固定，隨信源統(tǒng)計(jì)特性重新調(diào)整預(yù)測(cè)系數(shù)預(yù)測(cè)編碼的基本類型脈沖編碼調(diào)制—PCM(pulscodemodulation)差分脈沖編碼調(diào)制—DPCM(differentialpulscodemodulation)噪聲反饋編碼—NFC(noisefeedbackcoding)預(yù)測(cè)誤差門限型變換編碼正交變換編碼是圖像數(shù)據(jù)壓縮技術(shù)中的基本方法。主要變化方法：

1°K-L變換:協(xié)方差矩陣

2°離散付里葉變換DFT快速算法FFT3°離散余弦變換DCT快速算法FCT4°Walsh-Hadamard變換DWH5°小波變換K-L變換若信源矢量的相關(guān)矩陣為：則解

可得其特征值和特征矢量

0>1>….>N-1>0i=(ai0,ai1…ai,N-1),i=0,1,2..N-1

各

i必相互正交。(r-s)s’r=s[]’r-r[]’s=0,r≠s。各yr必相互線性無(wú)關(guān)Eyrys=E(rx’)(sx’)=E(rx’)(x’s)=r[]’s=srs=rss.

DFT變換離散余弦變換實(shí)數(shù)運(yùn)算簡(jiǎn)單些.Hardmard-Walsh變換Haar變換非連續(xù)函數(shù)，N必須是2n.連續(xù)信源的熵和互信息信息率失真理論標(biāo)量量化編碼矢量量化編碼語(yǔ)音壓縮編碼圖象壓縮編碼第四章

限失真信源編碼第四章

限失真信源編碼

限失真編碼：信源編碼經(jīng)過(guò)譯碼后能保留應(yīng)用要求的信息，允許信源有一定的失真。為什么要限失真編碼

1°連續(xù)信源的絕對(duì)熵為無(wú)限大，由于信道的帶寬有限，受信道容量的限制。不可能實(shí)現(xiàn)完全無(wú)失真的信源信息的傳輸。(可能性)2°信道資源和技術(shù)經(jīng)濟(jì)因素的限制。(可實(shí)現(xiàn)性)3°實(shí)際應(yīng)用不必要無(wú)失真地恢復(fù)信源消息,不必要完全無(wú)失真的信源信息的傳輸.(必要性)

4°數(shù)字系統(tǒng)的應(yīng)用,模擬量的采樣,量化也會(huì)引入失真.語(yǔ)音信號(hào)傳輸語(yǔ)音（音頻）信號(hào)的帶寬：20～20000HZ

實(shí)際應(yīng)用音頻范圍:電話質(zhì)量:300～3.4KHZ電話公用網(wǎng)調(diào)幅廣播質(zhì)量:50～7KHZ有現(xiàn)場(chǎng)感的語(yǔ)音傳輸高保真音頻信號(hào):20～20KHZ高保真音響圖像信號(hào)傳輸一路6MHz的普通電視信號(hào)數(shù)字化后，其數(shù)碼率將高達(dá)167Mbps，對(duì)儲(chǔ)存器容量要求很大，占有的帶寬將達(dá)80MHz左右表4－1各種圖像信號(hào)應(yīng)用的碼率應(yīng)用種類象素?cái)?shù)

/行行數(shù)/幀碼率bps壓縮前壓縮后HDTV192010801.18G20~25M普通電視720480167M4~8M會(huì)議電視35228836.5M1.5~2M電視電話1281125.2M56k一、連續(xù)消息的統(tǒng)計(jì)特性時(shí)間連續(xù)、取值連續(xù)2.描述:隨機(jī)過(guò)程1.波形信源：例如：

在一個(gè)具體的時(shí)間點(diǎn)ti

，{x(ti)}

為一個(gè)取值連續(xù)的隨機(jī)變量，可用有限維概率密度函數(shù)族描述：4.1連續(xù)信源的熵和互信息平穩(wěn)隨機(jī)過(guò)程：統(tǒng)計(jì)特性不隨時(shí)間平移而變化的隨機(jī)過(guò)程?！?/p>

{x(t)}在時(shí)刻t=ti的集平均:{x(t)}在某一時(shí)刻ti變量x(ti)的統(tǒng)計(jì)平均一、波形信源的特性2.描述:

★

{x(ti)}的時(shí)間平均：{x