北京郵電大學(xué) 通信原理 第七章 信源與信源編碼II教材

第七章信源與信源編碼彭濤pengtao@7.1引言信源編碼：去掉信源輸出中的冗余信息，提高有效性內(nèi)容信源分類及其統(tǒng)計(jì)特性信息熵，信源剩余度互信息，各類熵與互信息的關(guān)系Huffman編碼無(wú)失真/限失真信源編碼定理率失真函數(shù)矢量量化、變換編碼7.2信源分類及其統(tǒng)計(jì)特性描述信源分類連續(xù)/模擬信源離散/數(shù)字信源重點(diǎn)研究7.2信源分類及其統(tǒng)計(jì)特性描述單消息（符號(hào)）離散信源只輸出一個(gè)離散符號(hào)統(tǒng)計(jì)特性描述7.2信源分類及其統(tǒng)計(jì)特性描述離散消息（符號(hào)）序列信源輸出一個(gè)離散消息（符號(hào)）序列統(tǒng)計(jì)特性描述7.2信源分類及其統(tǒng)計(jì)特性描述離散消息（符號(hào)）序列信源離散無(wú)記憶序列信源：序列中前后符號(hào)相互統(tǒng)計(jì)獨(dú)立離散有記憶序列信源：序列中前后符號(hào)不是相互統(tǒng)計(jì)獨(dú)立的可用馬爾可夫鏈表示7.3信息熵H(X)信息的基本特征：不確定性。因此信息應(yīng)該是概率P的函數(shù)信息的兩個(gè)特點(diǎn)隨概率P的遞減性：概率越大，信息量越小可加性：兩個(gè)獨(dú)立消息的總信息量應(yīng)是兩個(gè)消息的信息量的和滿足這兩個(gè)條件的表示信息量的函數(shù)只有一種可能：對(duì)數(shù)函數(shù)7.3信息熵H(X)單消息離散信源的信息度量自信息量：出現(xiàn)某個(gè)消息時(shí)的信息量理解：消息出現(xiàn)概率越小，信息量越大7.3信息熵H(X)單消息離散信源的信息度量?jī)蓚€(gè)單消息離散信源X,Y的聯(lián)合信息量7.3信息熵H(X)單消息離散信源的信息熵前面定義的是一個(gè)具體消息的信息量，因?yàn)樾旁摧敵龅南⒂卸喾N可能性，所以可以把信息熵理解為這個(gè)輸出消息（考慮多種可能性）的平均信息量信息熵也可以理解為對(duì)信源的不確定性的平均度量在各種可能性等概時(shí)，信源的信息熵最大（圖7.3.1）7.3信息熵H(X)信息量和信息熵的單位對(duì)數(shù)以2為底時(shí)，單位為比特(bit)對(duì)數(shù)以e為底時(shí)，單位為奈特(Nat)對(duì)數(shù)以10為底時(shí)，單位為笛特(Det)1bit=0.693Nat=0.301Det7.3信息熵H(X)兩個(gè)單消息離散信源的聯(lián)合熵和條件熵7.3信息熵H(X)聯(lián)合熵和條件熵的一些性質(zhì)7.3信息熵H(X)離散消息序列信源的信息熵、剩余度7.3信息熵H(X)離散消息序列信源的信息熵、剩余度7.4互信息I(X;Y)互信息的定義I(X;Y)及理解7.4互信息I(X;Y)各種信息熵的關(guān)系7.5無(wú)失真離散信源編碼定理信源編碼離散信源輸出的是各種離散消息和符號(hào)模擬信源輸出的是模擬信號(hào)（連續(xù)信號(hào)）為了進(jìn)行數(shù)字通信，必須進(jìn)行信源編碼，將信源輸出轉(zhuǎn)變成數(shù)字信息信源編碼中考慮的兩個(gè)基本問(wèn)題編碼輸出的信息速率（總是希望它盡可能?。┚幋a所造成的失真7.5無(wú)失真離散信源編碼定理無(wú)失真離散信源編碼研究在無(wú)失真編譯碼條件下，傳送離散信源發(fā)出信息的最小編碼速率兩種基本編碼方法等長(zhǎng)編碼：編碼輸出的所有碼字長(zhǎng)度都相同變長(zhǎng)編碼：編碼輸出碼字長(zhǎng)度不相同7.5無(wú)失真離散信源編碼定理等長(zhǎng)編碼定理原理圖無(wú)失真要求：nL<=mK（無(wú)信息丟失）有效性要求：mK盡可能小7.5無(wú)失真離散信源編碼定理等長(zhǎng)編碼定理編碼滿足下式，當(dāng)L足夠大時(shí)，必然可以使譯碼差錯(cuò)率趨近于0（無(wú)失真或近似無(wú)失真）反之，如果上式不滿足，即R=K*log2m/L<H(X)，則無(wú)論如何編碼，譯碼必定出錯(cuò)且差錯(cuò)率不趨近于07.5無(wú)失真離散信源編碼定理變長(zhǎng)編碼定理變長(zhǎng)編碼中，將信源輸出的不同符號(hào)序列（取值概率不同）編碼成長(zhǎng)度不同的碼字，編碼輸出的信息率為如編碼滿足R>=H(X)，則L足夠大時(shí)，必可使譯碼差錯(cuò)率趨近于0；反之，譯碼必定出錯(cuò)且差錯(cuò)率不趨近于07.5無(wú)失真離散信源編碼定理等長(zhǎng)編碼和變長(zhǎng)編碼的比較等長(zhǎng)編碼將信源輸出符號(hào)序列的任意一種取值（概率可能不同）都編碼成相同長(zhǎng)度的輸出碼字，沒有利用信源的統(tǒng)計(jì)特性變長(zhǎng)編碼可以根據(jù)信源輸出符號(hào)序列各種取值的概率大小不同，將他們編碼成不同長(zhǎng)度的輸出碼字，利用了信源的統(tǒng)計(jì)特性。因此又稱其為熵編碼。7.5無(wú)失真離散信源編碼定理等長(zhǎng)編碼和變長(zhǎng)編碼的比較編碼效率由于變長(zhǎng)編碼利用了信源的統(tǒng)計(jì)特性，因此，一般在相同的編碼效率和譯碼差錯(cuò)率要求下，變長(zhǎng)編碼需要的信源消息序列長(zhǎng)度L遠(yuǎn)小于等長(zhǎng)編碼需要的LHuffman編碼等長(zhǎng)編碼：對(duì)信源輸出的各種出現(xiàn)概率的符號(hào)用等長(zhǎng)的碼字表示沒有充分利用信源的統(tǒng)計(jì)特性變長(zhǎng)編碼：根據(jù)信源輸出符號(hào)出現(xiàn)概率不同選擇碼字，出現(xiàn)概率大的用短碼，出現(xiàn)概率小的用長(zhǎng)碼利用了信源的統(tǒng)計(jì)特性，其編碼效率高于等長(zhǎng)編碼Huffman編碼：Huffman提出的一種變長(zhǎng)編碼是單消息信源的最佳變長(zhǎng)編碼Huffman編碼圖解Huffman編碼方法1.寫出消息概率2.對(duì)最小的兩概率編碼（0/1）3.對(duì)這兩概率合并4.重復(fù)2和3，直至結(jié)束5.自頂而下到達(dá)某消息即得編碼Huffman編碼確定了對(duì)信源符號(hào)的編碼規(guī)則，可進(jìn)行編譯碼這種特性得益于Huffman編碼的非延長(zhǎng)性和異前置性非延長(zhǎng)性：把任一許用碼組延長(zhǎng)（添加數(shù)字）都得不到許用碼字；異前置性：將任一許用碼組的最后一位或幾位去掉都得不到許用碼組。這兩種性質(zhì)可以從Huffman編碼的規(guī)則看出來(lái)7.7信息率失真R(D)函數(shù)在前面的討論中，其基本出發(fā)點(diǎn)是如何保證信息的無(wú)失真?zhèn)鬏?。但在許多實(shí)際應(yīng)用中，人們并不要求完全無(wú)失真地恢復(fù)消息，而是只要滿足一定的條件，近似地恢復(fù)信源發(fā)出的消息就可以了。原因1：實(shí)際的信源常常是連續(xù)的，信息率無(wú)限大原因2：實(shí)際信道帶寬是有限的，所以信道容量受限制原因3：實(shí)際生活中，人們一般并不要求獲得完全無(wú)失真的消息，通常只要求近似地再現(xiàn)原始消息，即允許一定的失真存在。如：聽電話、看電影7.7信息率失真R(D)函數(shù)信息率失真理論香農(nóng)定義了信息率失真函數(shù)R(D)定理指出：在允許一定失真度D的情況下，信源輸出的信息率可壓縮到R(D)信息率失真理論是信源編碼（包括量化（模數(shù)轉(zhuǎn)換）、數(shù)模轉(zhuǎn)換、頻帶壓縮和數(shù)據(jù)壓縮）的理論基礎(chǔ)7.7信息率失真R(D)函數(shù)失真函數(shù)和平均失真對(duì)X（單消息信源取值空間）和Y（單消息信宿取值空間），可定義它們的失真函數(shù)在此基礎(chǔ)上，定義平均失真7.7信息率失真R(D)函數(shù)允許失真D和試驗(yàn)信道集合PD人們對(duì)信息傳輸?shù)氖д嬗幸?，這個(gè)要求就是允許失真D當(dāng)信源確定（P(X)已知），允許失真度D也給定時(shí)，選擇信道使平均失真小于允許失真。凡滿足要求的信道稱為D失真許可的試驗(yàn)信道，簡(jiǎn)稱試驗(yàn)信道，所有試驗(yàn)信道的集合就是PD7.7信息率失真R(D)函數(shù)互信息I(X;Y)的性質(zhì)性質(zhì)1：互信息I(X;Y)是先驗(yàn)概率P(X)的上凸函數(shù)，研究信道容量時(shí)用到性質(zhì)2：互信息I(X;Y)是信道轉(zhuǎn)移概率概率P(Y|X)的下凸函數(shù)，研究信息率失真函數(shù)時(shí)用到7.7信息率失真R(D)函數(shù)信息率失真函數(shù)R(D)在信源和允許失真給定以后，PD是滿足允許失真的試驗(yàn)信道集合，平均互信息I(X;Y)是信道傳遞概率p(yj|xi)的下凸函數(shù)，所以在PD中一定可以找到某個(gè)試驗(yàn)信道，使I(X;Y)達(dá)到最小，即這個(gè)最小值R(D)稱為信息率失真函數(shù)，簡(jiǎn)稱率失真函數(shù)7.7信息率失真R(D)函數(shù)信息率失真函數(shù)R(D)的性質(zhì)可以證明：R(D)是關(guān)于允許失真D的單調(diào)遞減的下凸函數(shù)7.7信息率失真R(D)函數(shù)信息率失真函數(shù)的物理意義信息率失真函數(shù)是在滿足保真度條件下，信宿必須獲得的平均信息量的最小值，是信源必須輸出的最小信息率信息傳輸速率本質(zhì)上是描述信源特性的，因此R(D)也應(yīng)該是僅僅用于描述信源若信源消息經(jīng)無(wú)失真編碼后的信息傳輸速率為R，則在保真度條件下信源編碼輸出的信息率就是R(D)，且說(shuō)明在保真度條件下信源編碼比無(wú)失真情況得到了壓縮，同時(shí)R(D)是保真度條件下對(duì)信源進(jìn)行壓縮的極限值，亦即信源信息率可壓縮的最低限度，它僅取決于信源特性和保真度要求，與信道特性無(wú)關(guān)7.7信息率失真R(D)函數(shù)補(bǔ)充內(nèi)容：信道容量問(wèn)題信道容量和信息率失真函數(shù)都是求互信息I(X;Y)的極值問(wèn)題，有相仿之處，故常稱為對(duì)偶問(wèn)題平均互信息I(X;Y)是信源概率分布P(X)的上凸函數(shù)，根據(jù)上凸函數(shù)定義，如果I(X;Y)在定義域內(nèi)對(duì)P(X)的極值存在，則該極值一定是極大值。信道容量就是在固定信道情況下(P(yj|xi)確定)，求平均互信息極大值的問(wèn)題，即7.7信息率失真R(D)函數(shù)補(bǔ)充內(nèi)容：信道容量問(wèn)題信道容量C只與信道情況，即信道的條件轉(zhuǎn)移概率p(yj|xi)有關(guān)，反映信道特性，與信源特性無(wú)關(guān)由于平均互信息與信源的特性有關(guān)，為了排除信源特性P(X)對(duì)信道容量的影響，采用的做法是在所有的信源中以那個(gè)能夠使平均互信息達(dá)到最大的信源為參考。所以信道容量?jī)H與信道特性有關(guān)，信道不同，C亦不同7.7信息率失真R(D)函數(shù)研究信息率失真函數(shù)和信道容量的意義研究信息率失真函數(shù)：為了解決在已知信源和允許失真度D的條件下，使信源必須傳送給信宿的信息率最小。即用盡可能少的碼符號(hào)盡快地傳送盡可能多的信源消息，以提高通信的有效性。這是信源編碼問(wèn)題研究信道容量：在實(shí)際應(yīng)用中，研究信道容量是為了解決在已知信道中傳送最大信息率問(wèn)題。目的是充分利用已給信道，使傳輸?shù)男畔⒘孔畲蠖l(fā)生錯(cuò)誤的概率任意小，以提高通信的可靠性。這就是信道編碼問(wèn)題7.8限失真信源編碼定理限失真信源編碼定理設(shè)有一離散平穩(wěn)無(wú)記憶信源，若該信源的信息率失真函數(shù)是R(D)，對(duì)于任意允許平均失真D≥0，和任意小的ε>0，若實(shí)際傳輸信息率R>R(D)，只要信源序列長(zhǎng)度L足夠長(zhǎng)，一定存在一種編碼方式C，使譯碼后的平均失真d≤D+ε；反之，若R<R(D)，則無(wú)論用什么編碼方式，必有d>D該定理可以推廣到連續(xù)平穩(wěn)無(wú)記憶信源7.8限失真信源編碼定理限失真信源編碼定理理解1：信息率失真函數(shù)R(D)是一個(gè)界限，只要實(shí)際傳輸信息率R大于這個(gè)界限，就可以通過(guò)信源編碼技術(shù)將譯碼失真限制在給定的范圍內(nèi)。即通信的過(guò)程中雖然有失真，但仍能滿足要求，否則就不能滿足要求。理解2：限失真信源編碼的方向是尋求與信源的信息率失真函數(shù)R(D)相匹配的編碼，即RR(D)；這與無(wú)失真信源編碼相似，后者尋求與信源信息熵匹配的編碼，即RH(X)=R(D=0)7.8限失真信源編碼定理實(shí)現(xiàn)限失真信源編碼的兩類方法1.適應(yīng)信源方法，即尋找適應(yīng)信源的客觀概率統(tǒng)計(jì)特性的編碼方法。如充分考慮信源消息序列的各消息變量（或各取樣值）之間的相關(guān)性，進(jìn)行矢量量化編碼2.改造信源方法，即通過(guò)改造信源解除信源消息序列的各消息變量（或各取樣值）之間的相關(guān)性。如預(yù)測(cè)編碼和變換編碼7.9.5矢量量化標(biāo)量量化的問(wèn)題沒有充分利用信源消息序列中各個(gè)樣值之間的相關(guān)性，編碼之后的信息率通常較高矢量量化的思路充分利用信源消息序列中各個(gè)樣值之間的相關(guān)性，通過(guò)聯(lián)合量化，可以大幅度降低編碼后的信息率，提高編碼效率7.9.5矢量量化基本原理將模擬信號(hào)抽樣序列中的每K個(gè)樣值分為一組，構(gòu)成K維歐式空間RK中的一個(gè)隨機(jī)矢量X將K維空間分割成L個(gè)子空間（胞腔）Ci。每個(gè)子空間Ci中有一個(gè)離散的K維矢量Yi，稱為量化矢量或重建矢量若輸入矢量X落在某子空間Ci中，則可將X量化維其中的量化矢量Yi。這樣傳輸時(shí)，只需要傳輸量化矢量Yi的標(biāo)號(hào)i7.9.5矢量量化最佳矢量量化基本算法（LGB算法）使量化誤差/失真最小的矢量量化算法即為最佳矢量量化，常用的失真度量為均方誤差LGB算法的兩個(gè)條件：1.若輸入矢量X與量化矢量Yi之間的失真d(X,Yi)小于與其它任何量化矢量Yj之間的失真d(X,Yj)，則判為屬于Ci，即Ci是符合此條件的所有矢量的集合2.各子空間的量化矢量應(yīng)為該子空間的概率質(zhì)心實(shí)現(xiàn)：迭代算法7.10.1預(yù)測(cè)編碼原理預(yù)測(cè)編碼不直接對(duì)信源輸出信號(hào)進(jìn)行編碼，而是先對(duì)信源輸出信號(hào)進(jìn)行預(yù)測(cè)變換，對(duì)源信號(hào)和預(yù)測(cè)變換后信號(hào)的差值（誤差）信號(hào)進(jìn)行編碼預(yù)測(cè)器輸出預(yù)測(cè)函數(shù)f的選取：線性函數(shù)、非線性函數(shù)7.10.1預(yù)測(cè)編碼根據(jù)預(yù)測(cè)器輸入數(shù)據(jù)來(lái)源進(jìn)行分類DPCM：預(yù)測(cè)器輸入為誤差信號(hào)的量化結(jié)果ΔPCM：直接將信源輸出作為預(yù)測(cè)器輸入噪聲反饋型：前兩類的結(jié)合7.10.1預(yù)測(cè)編碼DPCM其中，線性預(yù)測(cè)器輸出為7.10.1預(yù)測(cè)編碼DPCM易見，線性預(yù)測(cè)器在預(yù)測(cè)編碼中的作用非常關(guān)鍵，其中預(yù)測(cè)系數(shù)的選取對(duì)編碼性能的影響很大最佳線性預(yù)測(cè)（若采用MMSE即最小均方誤差準(zhǔn)則）需滿足如下條件7.10.1預(yù)測(cè)編碼DPCM由前頁(yè)式子可得以下方程由上面方程即可求得線性預(yù)測(cè)器的最優(yōu)預(yù)測(cè)系數(shù)7.10.1預(yù)測(cè)編碼DPCM由于在預(yù)測(cè)時(shí)是采用最小均方誤差準(zhǔn)則，對(duì)一些相關(guān)性較強(qiáng)的信源如話音，誤差信號(hào)的方差遠(yuǎn)小于源信號(hào)，這就意味著量化時(shí)量化級(jí)數(shù)可大大減少，即可降低編碼速率應(yīng)用實(shí)例：CCITT于1984年提出的G.721建議就是速率為32kbps的ADPCM話音編碼7.10.1預(yù)測(cè)編碼ΔM最簡(jiǎn)單的DPCM就是ΔM（增量調(diào)制）ΔM中量化器級(jí)數(shù)只有兩級(jí)，這樣編碼時(shí)僅編碼為1bit（差值為正編為1，反