編碼理論課件

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

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

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

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

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

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

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

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

,B2

,…

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

Bj=0），且有B1

∪B2

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

設(shè)B1

,B2

,…

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

Bj=0），且有B1

∪B2

∪…=Ω（樣本空間）；

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

·

·

·

xn

}，這n個符號消息的概率分布為了：稱為符號xi

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

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

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

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

1o

若有兩個事件xi

，xj

，其先驗概率為p(xi)＜p(xj)，則事件xi比事件xj有更大的不確定性，同時會帶來更多的信息量；I(xi)>I(xj)2o

事件xi先驗概率p(xi)=1（確定事件）,則不存在不確定性，同時不會帶來信息量；I(xi)=0.3o

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

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

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

定義一個符號消息xi的自信息量為其發(fā)生概率的對數(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)自信息量的單位自信息量的單位與所用對數(shù)的底有關(guān)：

1o

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

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

—nat(natureunit)3o

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

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

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

1bit=lg

2≈0.3010det1nat=log2e≈1.4427bit

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

其中

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

2)H(X)

的含義

1o

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

2o

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

3o

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

3)

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

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

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

當(dāng)

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

信源X={x1，x2

·

·

·

xn

}

，若其中xi

的概率p(xi)=1

則其余xj的p(xj)=0，因為則H(X)=0bit/信源符號3o

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

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

聯(lián)合熵是聯(lián)合符號集合XY上的每個元素對xi

,

yj的自信息量的概率加權(quán)的統(tǒng)計平均值。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（即各個yj）條件下，集合X的條件熵定義為：三、互信息（一）簡單的通信模型

若信源發(fā)出符號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)，說明：

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

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

※

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

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

I(X;Y)=I(Y;X)３．交互性（對稱性)（三）平均互信息的性質(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無噪信道

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

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：對于固定信源分布，平均互信息I(X;Y)是信道傳遞概率p(y|x)的∪型凸函數(shù)?！煌旁赐ㄟ^不同信道傳輸?shù)玫降钠骄バ畔⒉煌?/p>

5．

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

例1．

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

分組碼（塊碼）分類

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

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

3°按譯碼唯一性分類

唯一可譯碼：對于多個碼字組成的有限長碼流，只能唯一地分割一個個的碼字。唯一可譯碼又稱為單義碼.例碼流100111000…

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

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

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

非唯一可譯碼：對有限長碼流，不能唯一地分割一個個的碼字。4°按譯碼的即時性分類

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

即時碼：接收端收到一個完整的碼字后，就能立即譯碼；即時碼又稱為非延長碼或異前綴碼。例非即時碼

碼流01001100…

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

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

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

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

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

問題：

例1．

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

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

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

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

※

等長碼碼長要求l/N

logrq（保證唯一可譯碼，無失真）

※

logrq為下限

※

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

例2．英文源S：{26個字母+空格符號}，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該編碼冗余度大平均碼長太長例3：設(shè)信源

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

l=2code/sigL2=2code/2_sigsl=1code/sig信源有記憶時，采用N長源編碼，l減小一、等長碼基本問題二、等長信源編碼定理

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

>0，只要滿足：

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

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

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

※

基本方法：N長源、變長編碼

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

解：H(S)=0.811bit/sig

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

則有：η=0.5得N≥71687

η=0.8得N≥1146990

η=0.9得N≥5806641

η=0.96得N≥41291672等長碼的缺點：平均碼長太長使信道復(fù)雜化容易產(chǎn)生溢出或取空差錯的擴(kuò)散變長碼特點：每個碼字長度可不同要求：唯一可譯定理2-2：（Kraft不等式）設(shè)信源符號S=｛s1,…,sN｝,碼符號X＝{x1,…,xm}，又設(shè)碼字W1，W2，…Wn的碼長分別為l1，l2，…，ln，則存在惟一可譯碼的充要條件是：三、惟一可譯碼的判斷※碼長結(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}非惟一可譯符號碼1碼2碼3碼4等長碼變長碼u100001u201101101u3100000001u31101110001惟一可譯碼非惟一可譯碼非惟一可譯碼惟一可譯碼2、根據(jù)定義判斷基本準(zhǔn)則：等長碼——若為非奇異碼，則為唯一可譯碼；變長碼——碼本身及任意次擴(kuò)展碼均非奇異。主要方法：

樹圖法（即時碼必為惟一可譯碼）

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

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

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

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

證明若xi

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

,

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

故可得

四、變長信源編碼定理

因為所以

所有碼字長度滿足Kraft不等式

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

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

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

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

1，

2，

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

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

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

四、變長信源編碼定理

且當(dāng)N

時，有：

其中， 為N長源編碼的平均碼長，

i是

i所對應(yīng)的碼字長度。

信源X

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

的信源熵為H(XN)bit/N個信源符號

XN

所對應(yīng)碼字的碼長碼符/N個信源符號①平均碼長的下限即信源熵是無失真信源編碼的最小平均碼長！②存在性定理 方法：N長源，變長碼③適用于平穩(wěn)有記憶信源，H(U)=H∞定理2-4說明四、變長信源編碼定理

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

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

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

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

四、變長信源編碼定理

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

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

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

四、變長信源編碼定理

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

④

分配碼元?？s減信源步驟：①

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

合并概率最小的兩個符號;③

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

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

一、Huffman編碼

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

n=(m－1)Q+m

（對于二元編碼，n=Q+m）※

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

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

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

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

一、Huffman編碼

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

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

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

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

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

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

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

1.遞減排列;2.等概分組P(A)≈P(B);3.每個子集以符號“0”或“1”標(biāo)識。方法：等概分割步驟：費(fèi)諾編碼屬于統(tǒng)計匹配編碼，但它不是最佳的編碼方法例4：DMS如下，用費(fèi)諾編碼方法編碼消息符號ui符號概率P(ui)u10.5u20.25u30.125u40.125第一次分組01第二次分組01第三次分組01碼字010110111碼長1233H(U)=1.75bit消息符號si消息概率P(si)s10.20s20.19s30.18s40.17s50.15s60.10s70.01第一次分組01第二次分組0101第三次分組0101第四次分組01碼字碼長0020103011310211031110411114例5香農(nóng)-費(fèi)諾-埃利斯碼三、香農(nóng)-費(fèi)諾-埃利斯碼方法：根據(jù)信源符號累積概率分配碼字不是分組碼，也不是最佳碼，但效率高步驟：1.確定信源符號修正的累積概率函數(shù)；2.將修正的累積概率函數(shù)轉(zhuǎn)換成二進(jìn)制小數(shù)，取小數(shù)點后l(uk)位為碼字。設(shè)信源為：信源符號積累概率為：信源符號修正的積累概率為：碼長：平均碼長：例6：DMS如下，用香農(nóng)-費(fèi)諾-埃利斯編碼方法編碼消息符號ui符號概率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碼長l(uk)3244碼字0011011011111H(U)=1.75bitHuffman碼在實際應(yīng)用中的問題誤差擴(kuò)散概率匹配速率匹配2.4算術(shù)編碼Huffman編碼更適合于大消息集信源，對于小消息集信源使用算術(shù)編碼和游程編碼壓縮效果更好。主要內(nèi)容：積累概率的遞推公式算術(shù)編碼原理算術(shù)編碼的碼長遞推公式的應(yīng)用不做乘法的算術(shù)編碼2.4.1積累概率的遞推公式信源符號積累概率設(shè)信源信源符號積累概率：2.4.1積累概率的遞推公式信源序列積累概率傳遞公式設(shè)獨(dú)立信源序列信源序列S添加一個新的信源符號ur后所得新序列Sur的積累概率。信源序列S的概率。信源符號ur的積累概率。信源序列S添加一個新的信源符號ur后所得新序列Sur的概率。信源符號ur的概率。信源序列的積累概率F(S)與信源符號的積累概率一樣，可用[0,1)區(qū)間內(nèi)的個點來表示，因此積累概率F(S)將區(qū)間[0,1)分成許多不同的小區(qū)間，他們互不重疊，序列S的概率p(S)就是兩點間小區(qū)間的長度。小區(qū)間內(nèi)的一個點可用來表示序列的概率。2.4.2算術(shù)編碼原理基本思路：把信源序列的積累概率映射到[0,1)區(qū)間上，使每個序列對應(yīng)該區(qū)間內(nèi)的一點，這些點把區(qū)間[0,1)分成許多不同的小區(qū)間，這些小區(qū)間的長度等于對應(yīng)序列的概率，在小區(qū)間內(nèi)取一個浮點小數(shù)，使其長度與該序列的概率相匹配。算術(shù)編碼的主要任務(wù)是計算信源序列對應(yīng)的小區(qū)間。2.4.2算術(shù)編碼原理小區(qū)間劃分的遞推計算公式小區(qū)間左端點遞推公式：小區(qū)間右端點遞推公式：新序列Sur對應(yīng)區(qū)間的左端點值。信源序列S對應(yīng)區(qū)間的左端點值。信源序列S對應(yīng)區(qū)間的寬度值。信源符號ur對應(yīng)區(qū)間的左端點值。新序列Sur對應(yīng)區(qū)間的右端點值。信源序列S對應(yīng)區(qū)間的左端點值。信源序列S對應(yīng)區(qū)間的寬度值。信源符號ur對應(yīng)區(qū)間的右端點值。2.4.2算術(shù)編碼原理計算小區(qū)間端點值的步驟（1）給出信源符號對應(yīng)的區(qū)間；（2）初始時，設(shè)S=?（?代表空集），low(?)=0，high(?)=1，range(?)=1（3）輸入ur，根據(jù)公式計算序列Sur的左右端點值，依次下去，直到全部信源序列對應(yīng)的區(qū)間被確定為止。2.4.2算術(shù)編碼原理[例2-10]設(shè)信源

求信源序列S=abda對應(yīng)的小區(qū)間信源符號對應(yīng)區(qū)間端點值符號概率區(qū)間a0.5[0,0.5)b0.25[0.5,0.75)c0.125[0.75,0.875)d0.125[0.875,1)信源序列對應(yīng)區(qū)間端點值信源序列l(wèi)owhigha00.5ab0.250.375abd0.3593750.375abda0.3593750.36718752.4.2算術(shù)編碼原理信源序列對應(yīng)區(qū)間的劃分0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.375不同的信源序列分別對應(yīng)不同的互不重疊的小區(qū)間，取小區(qū)間內(nèi)的一個點作為對應(yīng)序列的編碼。--------即時碼S=abda的編碼2.4.2算術(shù)編碼原理譯碼步驟：（1）判斷碼字落在哪個符號區(qū)間，翻譯出1個符號；（2）將碼字減去剛翻譯出的符號的左端點值；（3）用剛翻譯出的符合對應(yīng)的區(qū)間的長度去除步驟2的結(jié)果，判斷此值落在哪個符號區(qū)間，翻譯出一個新符號；（4）反復(fù)步驟（2）（3）直至全部信源序列被翻譯完為止。2.4.2算術(shù)編碼原理0.75abcd00.50.8751aaabacad0.2500.3750.5abaabbabcabd0.250.3593750.375abcd0.3593750.36718750.3752.4.3算術(shù)編碼的碼長碼字長度應(yīng)與序列的概率匹配取信源序列碼字的前L位，若后面有尾數(shù)，就進(jìn)位到第L位。根據(jù)信源編碼定理可知信源序列S的平均碼長滿足：平均每個信源符號的碼長：對于DMS有2.4.4遞推公式的應(yīng)用用序列積累概率的遞推公式進(jìn)行序列的算術(shù)編碼的計算步驟：（1）根據(jù)信源符號積累概率公式計算信源符號的積累概率；（2）初始時，設(shè)S=?，F(xiàn)(?)=0，p(?)=1；（3）根據(jù)序列的積累概率遞推公式，計算序列的積累概率F(ur)和序列的概率p(ur)；（4）計算碼長；（5）將F(s)寫成二進(jìn)制數(shù)形式，取其前L位作為序列S的碼字，若后面有尾數(shù)就進(jìn)位到第L位。2.4.4遞推公式的應(yīng)用例[2-12]設(shè)二元獨(dú)立信源求信源序列S=1010的算術(shù)編碼。解：信源符號的積累概率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)序列無限增長時，平均碼長漸近地等于序列的熵值。實際存在問題：遞推運(yùn)算中都有乘法——運(yùn)算量大解決辦法：1）編碼對象是二元序列，符號概率較小的一個為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è)S=?，p(?)=0.111….1，F(xiàn)(?)=0.000…0;（2）輸入一個信源符號，用遞推公式計算p(S1)，p(S0)，F(xiàn)(S0)，F(xiàn)(S0)；（3）重復(fù)步驟（2），直至信源序列結(jié)束。2.4.5不做乘法的算術(shù)編碼實際應(yīng)用時，由p(S1)≈2-qp(S)，一般2-q近似等于二元序列中小概率符號的概率值。通常取p(0)≈2-q。2.5游程編碼（RLC）游程編碼屬于無損壓縮編碼1)二元信源序列將“白”、“黑”二元信源用｛0，1｝表示。2)游程和游程序列

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

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

1°白游程的熵

lW

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

L白游程的最大長度

2°黑游程的熵

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

L白游程的最大長度

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

3°白、黑游程編碼的平均碼長

4°白、黑游程的平均長度

5°白、黑像素的熵hWhB與平均碼長

6°像素的熵h01與平均碼長

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

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

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

1°行掃描線共有：

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

2°每條掃描線：

1728像素點/線，8像素點/mm3°對于A4幅面的文件像素點

1728像素點/線×1188線=2052864像素點

1728像素點/線×2376線=4105728像素點

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

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

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

另一類為基干碼,游程長度為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個直接Huffman：2×1729=3458個性能：P（lW<61）＝80%P（lB<6）＝80%∴工程上性能不差

B．極限壓縮比②

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

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

yj=yiur(j>i)

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

Nj=mi+r

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

段號碼字000001010011100101110段號1234567符號a0a0a2a3a1a1a0a0a0a3a2碼字a000a101a210a311C=7段號所需碼長：m=4信源符號所需碼長：0000101101010000001110信源序列編碼序列：000000010

010010110110

110001

001010

000110111

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

若PS字符串不在串表中，輸出P對應(yīng)的碼字，將PS存入串表并分配一個碼字值；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ī)文件壓縮的標(biāo)準(zhǔn)算法。且算法硬件實現(xiàn)容易。本章重點內(nèi)容信息量、信息熵、互信息的概念及定義式?？死蛱夭坏仁綗o失真變長信源編碼定理（香農(nóng)第一定理）主要的編碼方法：Huffman碼、費(fèi)諾碼、香農(nóng)-費(fèi)諾碼、算術(shù)碼、MH碼、LZ碼。各種編碼方法的平均碼長和編碼效率的計算。本章難點克拉夫特不等式:

表述了信源符號數(shù)與碼字長度應(yīng)滿足什么條件才能構(gòu)成即時碼。唯一可譯碼有相同不等式存在----麥克米倫不等式這兩個不等式都只是描述了可構(gòu)造性，不能作為判定的論據(jù)。唯一可譯碼的判定準(zhǔn)則：樹圖法：（即時碼必為惟一可譯碼）尾隨后綴法：（尾隨后綴集合F中不含任一碼字）本章難點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ù)測編碼二、變換編碼一、預(yù)測編碼(PredictiveCoding)預(yù)測編碼的基本原理預(yù)測方法預(yù)測編碼的基本類型DPCM編譯碼原理(略)預(yù)測編碼的基本原理預(yù)測編碼是數(shù)據(jù)壓縮三大經(jīng)典技術(shù)之一是將信源輸出信號通過預(yù)測變換后再對信源輸出與被測值的差進(jìn)行編碼。預(yù)測編碼原理圖：預(yù)測器編碼器信源輸出編碼輸出預(yù)測編碼的基本原理實現(xiàn)預(yù)測編碼的關(guān)鍵問題：1.預(yù)測誤差準(zhǔn)則的選取；（決定了預(yù)測質(zhì)量）

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

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

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

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

1）前值預(yù)測

2）一維預(yù)測

3）二維預(yù)測（非線性預(yù)測）最佳預(yù)測—是按某種準(zhǔn)則，選擇線性預(yù)測系數(shù)使得預(yù)測誤差為最小。（常用MSE）自適應(yīng)預(yù)測—預(yù)測器的預(yù)測系數(shù)不固定，隨信源統(tǒng)計特性重新調(diào)整預(yù)測系數(shù)預(yù)測編碼的基本類型脈沖編碼調(diào)制—PCM(pulscodemodulation)差分脈沖編碼調(diào)制—DPCM(differentialpulscodemodulation)噪聲反饋編碼—NFC(noisefeedbackcoding)預(yù)測誤差門限型變換編碼正交變換編碼是圖像數(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必相互線性無關(guān)Eyrys=E(rx’)(sx’)=E(rx’)(x’s)=r[]’s=srs=rss.

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

限失真信源編碼第四章

限失真信源編碼

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

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

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

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

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

在一個具體的時間點ti

，{x(ti)}

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

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

★

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