第四章 離散信源的無失真編碼

1第四章離散信源的無失真編碼Shannon三大定理：Shannon第一定理——可變長無失真信源編碼定理Shannon第二定理——信道編碼定理Shannon第三定理——限失真信源編碼定理1第四章離散信源無失真編碼4.1離散無記憶信源的不等長編碼4.2最佳不等長編碼4.3漢字編碼方法及其討論4.4圖像的信源編碼4.5誤碼對信源譯碼的影響2離散無記憶信源的不等長編碼不等長編碼的優(yōu)越性

總體上減少碼字的長度。不等長編碼的特殊問題

①唯一可譯性，或者叫做可識別性。解決方案：適當(dāng)?shù)鼐幋a，使得每個(gè)碼字都具有識別標(biāo)記。一個(gè)唯一可譯的、碼字長度不超過N的D元碼，其碼字個(gè)數(shù)小于D(DN-1)/(D-1)個(gè)。這是因?yàn)閮蓚€(gè)碼字c(1)和c(2)連接成的字母串c(1)c(2)不能是碼字。3離散無記憶信源的不等長編碼不等長編碼的特殊問題②平均碼字長度。設(shè)信源隨機(jī)變量U的概率分布為{ak,p(ak),k=1~K}，事件ak對應(yīng)的碼字長度為nk，則平均碼字長度為希望小。解決方案：概率大的事件用短碼字。4離散無記憶信源的不等長編碼唯一可譯性的兩種解決方法Def.逗點(diǎn)碼①每個(gè)碼字的開頭部分都是一個(gè)相同的字母串；②這個(gè)字母串僅僅出現(xiàn)在碼字的開頭，不出現(xiàn)在碼字的其它部位，也不出現(xiàn)在兩個(gè)碼字的結(jié)合部。則稱這個(gè)字母串為逗號，稱此碼為逗點(diǎn)碼。5逗點(diǎn)碼顯然是唯一可譯的，見到逗號就識別為一個(gè)碼字的開始。離散無記憶信源的不等長編碼Def.異字頭碼每個(gè)碼字都不是另一個(gè)碼字的開頭部分（字頭）。則稱此碼為異字頭碼。6異字頭碼也是唯一可譯的，見到一個(gè)碼字就識別為一個(gè)碼字。（即時(shí)性）離散無記憶信源的不等長編碼信源字母集概率碼A碼B碼C碼Da10.50000a20.25011001a30.125100110011a40.12510111110111唯一可譯:C,D逗點(diǎn)碼：D異字頭碼：C7例離散無記憶信源的不等長編碼構(gòu)造方法一：Shannon-Fano編碼法D元碼每次信源符號化為概率近似相等的D個(gè)子集這樣可以保證D個(gè)碼元近似等概，每個(gè)碼字承載的信息量近似最大，碼就近似最短。理想情況I(ak)=nklogD8構(gòu)造方法二：Huffman編碼法Shannon-Fano編碼例子cabcedeacacdeddaaabaababaaabbacdebaceada共40個(gè)字母頻度a-16，b-7，c-6，d-6，e-51)將給定符號按照其頻率從大到小排序。a-16，b-7，c-6，d-6，e-52)將序列分成左右兩部分，使得左部頻率總和盡可能接近右部頻率總和。有：(a,b),(c,d,e)Shannon-Fano編碼例子3)第二步中劃分出的上部作為二叉樹的左子樹，記0，下部作為二叉樹的右子樹，記14)分別對左右子樹重復(fù)2)、3)兩步，直到所有的符號都成為二叉樹的樹葉為止。bacde00101011a00b01c10d110e111Shannon-Fano編碼例子為什么Shannon-Fano碼是異字頭碼？碼樹上的每個(gè)碼字都在樹梢。如果不是異字頭碼，則有的碼字就不在樹梢，而在中間節(jié)點(diǎn)。bacde00101011a00b01c10d110e111Shannon-Fano編碼例子編碼結(jié)果cabcedeacacdeddaaabaababaaabbacdebaceada1000011011111011100100010......長97bit采用3bit等長編碼需120bit采用ASCII碼需要320bit離散無記憶信源的不等長編碼Th.

Kraft不等式

設(shè)信源隨機(jī)變量共有K個(gè)事件。則：各碼字長度分別為n1、n2、…、nK的D元異字頭碼存在的充分必要條件是Th.唯一可譯碼必滿足Kraft不等式。13離散無記憶信源的不等長編碼Th.

不等長編碼定理（Shannon第一定理）14任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足離散無記憶信源的不等長編碼Th.

不等長編碼定理的推廣現(xiàn)在對信源隨機(jī)向量UL=(U1U2…UL)做唯一可譯的D元不等長碼。此時(shí)UL的事件的個(gè)數(shù)為KL。則15任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足離散無記憶信源的不等長編碼Def.

平均碼長

(重新定義)16任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足離散無記憶信源的不等長編碼Def.

編碼速率R和編碼效率η分別為

17任一唯一可譯的D元不等長碼總滿足存在唯一可譯的D元不等長碼滿足離散無記憶信源的不等長編碼18不等長編碼與等長編碼具有相似的性質(zhì)：當(dāng)L增大時(shí)，對UL的編碼可以使用更短的平均碼長，因而更加節(jié)省編碼速率。但節(jié)省編碼速率的下限是H(U)。離散無記憶信源的不等長編碼

例

2元編碼。設(shè)；H(U)=0.811。19U概率碼字平均碼長編碼速率編碼效率a13/40(1×3/4+1×1/4)/1=110.811a21/41U2概率碼字平均碼長編碼速率編碼效率a1a19/160(1×9/16+2×3/16+3×3/16+3×1/16)/2=27/3227/320.961a1a23/1610a2a13/16110a2a21/16111第四章離散信源無失真編碼4.1離散無記憶信源的不等長編碼4.2最佳不等長編碼4.3漢字編碼方法及其討論4.4圖像的信源編碼4.5誤碼對信源譯碼的影響20最佳不等長編碼Huffman編碼算術(shù)編碼LZ編碼21Huffman編碼的最佳性所謂最佳：是指在所有可能的編碼方法中，其編碼得到的平均碼長最短。定理4.4.1：對于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個(gè)碼字CK-1和CK的長度最長且相等，它們之間僅最后一位碼元取值不同(一個(gè)為0，另一個(gè)為1)。

Huffman編碼的最佳性對信源可對aK-1和aK的碼字的最后一位分別指定為1和0，然后作一輔助集

其中，ak’=ak,Pk’=Pk,當(dāng)k<K-1

aK-1’=aK-1∪aK,PK-1’=PK-1+PK

Huffman編碼的最佳性定理3.4.2

對輔助集U’為最佳的碼，對原始消息集U也是最佳的。若C’1，C’2，…，C’K-1是對輔助集U'的最佳碼，相應(yīng)碼長為n’1，n’2，…，n’K-1，則對U的碼字C1，C2,…,CK的碼長為nk=n’k

k≤K–2nk=n’K-1+1k=K,K–1Huffman編碼的最佳性概率大的采用短碼，概率小的采用長碼。與編碼無關(guān)哈夫曼編碼26

例

設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制哈夫曼碼。哈夫曼編碼27讀取碼字的時(shí)候，一定要從后向前讀，此時(shí)編出來的碼字異字頭碼。例設(shè)單符號離散無記憶信源如下，要求對信源編二進(jìn)制哈夫曼碼。哈夫曼編碼哈夫曼編碼左右顛倒過來重畫一下，即可得到二進(jìn)制哈夫曼碼的碼樹。哈夫曼編碼哈夫曼編碼和Shannon-Fano編碼的對比31

例

對cabcedeacacdeddaaabaababaaabbacdebaceada

進(jìn)行Huffman編碼。a16b7c6d6e511132401010101a0b100c101d110e111總比特?cái)?shù)88，信源熵為86.601bitShannon-Fano編碼：總比特?cái)?shù)97bit哈夫曼編碼和Shannon-Fano編碼的對比32Shannon-Fano編碼構(gòu)造二叉樹是自樹根到樹葉，很難保證最佳性。Huffman編碼則是從樹葉到樹根，是最佳的Huffman需要知道信源的概率分布，這在實(shí)際中有時(shí)是比較困難的。采用半靜態(tài)模型、自適應(yīng)模型、markov模型，部分匹配預(yù)測模型等等解決這一問題。哈夫曼編碼對比33例

單符號離散無記憶信源，哈夫曼的編碼方法并不唯一。哈夫曼編碼對比34方法一：合并后的新符號排在其它相同概率符號后面。哈夫曼編碼對比35方法二：合并后的新符號排在其它相同概率符號前面。哈夫曼編碼對比36平均碼長：2.2碼長方差：1.360100011x5x4x3x2x110001011x5x4x3x2x11平均碼長：2.2碼長方差：0.16編碼效率相同。第二種編碼方法的碼長變化較小，比較接近于平均碼長。4種不同的碼長2種不同的碼長哈夫曼編碼對比37在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時(shí)，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使短碼得到充分利用。

D進(jìn)制哈夫曼編碼38共有K個(gè)符號，概率最小的R個(gè)符號碼長最長K+B=D+m(D-1)滿樹注意B<D-1K-2=m(D-1)+D-2-B

D-2-B=

(K-2)mod(D-1)B個(gè)R個(gè)B=D-2-((K-2)mod(D-1))R=D-B=2+((K-2)mod(D-1))D進(jìn)制哈夫曼編碼39例：對如下單符號離散無記憶信源編三進(jìn)制哈夫曼碼。第一次取D-s=mod(8-2,3-1)+2=2個(gè)符號進(jìn)行編碼。D進(jìn)制哈夫曼編碼4041平均碼長為信息率為編碼效率為00001211x5x4x3x2x1221x6x8x7令離散無記憶信源如上。(a)求對U（即U1）的最佳二元碼、平均碼長和編碼效率。(b)求對U2

（即U1U2）的最佳二元碼、平均碼長和編碼效率。(c)求對U3（即U1U2U3）的最佳二元碼、平均碼長和編碼效率。例題（U1U2U3）~a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a20.1250.0750.0750.0750.0500.0500.0500.0450.045a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30.0450.0300.0300.0300.0300.0300.0300.0270.020a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30.0200.0200.0180.0180.0180.0120.0120.0120.008（U1U2）的最佳二元碼（U1U2）的最佳二元碼（U1U2）的最佳二元碼（U1U2）的最佳二元碼平均碼長和編碼效率：（U1U2U3）的碼字a1a1a1a1a1a2a1a2a1a2a1a1a1a1a3a1a3a1a3a1a1a1a2a2a2a1a201000000001011011101000100110101011a2a2a1a1a2a3a1a3a2a2a1a3a3a1a2a2a3a1a3a2a1a2a2a2a1a3a30010001110110001100111010110111111011111001100a3a1a3a3a3a1a2a2a3a2a3a2a3a2a2a2a3a3a3a2a3a3a3a2a3a3a30011010011100011110111100111110010100001010100101100010111（U1U2U3）的最佳二元碼平均碼長：（U1U2U3）的最佳二元碼編碼效率：第四章離散信源無失真編碼4.1離散無記憶信源的不等長編碼4.2最佳不等長編碼4.3漢字編碼方法及其討論4.4圖像的信源編碼4.5誤碼對信源譯碼的影響7879考慮一幅8.5×11.0英寸的圖像，若每平方英寸包含300個(gè)像素，則整個(gè)圖像將有大約8.4×106個(gè)像素。假定該圖像是彩色的，每個(gè)像素包含3色，每種顏色用8比特的碼字表示，可以算出該幅圖像將需用大約2×108比特來表示。與其他圖像格式相比，一幀高清晰度的電視圖像包含有大約1.8×106個(gè)像素，一幅標(biāo)準(zhǔn)電視圖像包含大約0.33×106個(gè)像素，一個(gè)高檔電腦顯示器包含1.2~3.1×106個(gè)像素。4.4圖像的信源編碼4.4.1圖像消息的信息特征80圖像消息的像素量很大，每一像素還有灰度等級、色度、飽和度等，這些參數(shù)相互之間通常具有較強(qiáng)的關(guān)聯(lián)性，存在著很大的冗余度統(tǒng)計(jì)冗余例如空間冗余、時(shí)間冗余、信息熵冗余等，它們主要取決于圖像信息的統(tǒng)計(jì)特性除此之外，還有結(jié)構(gòu)冗余、知識冗余、視覺冗余等。正是由于圖像消息中存在著這些冗余，才使圖像編碼有著可觀的壓縮潛力。4.4圖像的信源編碼4.4.1圖像消息的信息特征81圖像壓縮編碼方法主要有兩類，即無失真編碼與限失真編碼。壓縮比都是衡量其性能的一個(gè)重要指標(biāo)。定義4.9設(shè)信源消息初始編碼的代碼組平均長度為Ls，經(jīng)壓縮編碼后代碼組的平均長度為Ld，則稱

為壓縮編碼的壓縮比。無失真編碼的任務(wù)是尋求最佳編碼，主要手段是壓縮信源的冗余度。4.4圖像的信源編碼4.4.2壓縮編碼的主要方法82限失真編碼的方法是用小的失真換取大的壓縮比，它在圖像的壓縮編碼中得到了快速發(fā)展。在允許的失真度下減少信息熵的方法又稱為熵壓縮法，其理論根據(jù)是率失真理論和香農(nóng)第三定理?；舴蚵幋a等方法均可應(yīng)用于無失真圖像編碼。隨著圖像通信需求的快速增長，新的編碼方法也不斷涌現(xiàn)，如預(yù)測編碼、變換編碼、矢量量化、子帶編碼、分形編碼、模型編碼、小波編碼等。國際標(biāo)準(zhǔn)化組織和國際電信聯(lián)盟先后提出了靜止圖像編碼標(biāo)準(zhǔn)JPEG、電視電話/會議電視的視頻編碼標(biāo)準(zhǔn)H.261和活動圖像的編碼標(biāo)準(zhǔn)MPEG-1、MPEG-2和MPEG-4。4.4圖像的信源編碼4.4.2壓縮編碼的主要方法83算術(shù)編碼是香農(nóng)編碼方法在圖像編碼中的應(yīng)用。是一種無失真的非分組信源編碼，基本思想是將一定的精度數(shù)值作為序列的編碼。它是從全序列出發(fā)，采用遞推形式的連續(xù)編碼。以二進(jìn)制為例，它不是將單個(gè)的信源符號映射成一個(gè)碼字，而是將整個(gè)輸入序列的符號依據(jù)其概率映射為實(shí)數(shù)軸上[0,1)區(qū)間內(nèi)的一個(gè)小區(qū)間，再在該小區(qū)間內(nèi)選擇一個(gè)代表性的二進(jìn)制小數(shù)，作為實(shí)際編碼輸出。假設(shè)信源為二元平穩(wěn)的馬爾可夫信源，需要預(yù)先存儲的不再是碼字，而是由信源序列狀態(tài)確定的一些參數(shù)，因而算術(shù)編碼不需要傳送像霍夫曼碼表一類的編碼表。4.4.3算術(shù)編碼4.4圖像的信源編碼84算術(shù)編碼的具體方法：對初始信源進(jìn)行K重?cái)U(kuò)展，即

…xi,…,

xK,P(xK

)對應(yīng)于P(xK

)，有一個(gè)累積分布函數(shù)F(xK

)。在區(qū)間[F(xK

)–P(xK

),F(xK

)]，可以找到一個(gè)二進(jìn)制小數(shù)，由于對應(yīng)于不同的P(xK

)，區(qū)間的小數(shù)值一定不同，故可構(gòu)成單義可譯碼。在區(qū)間找位數(shù)最少的二進(jìn)制小數(shù)，用小數(shù)點(diǎn)后的數(shù)作為編碼。4.4.3算術(shù)編碼4.4圖像的信源編碼85算術(shù)編碼把信源X的任一給定序列和[0,1]的一個(gè)子區(qū)間聯(lián)系在一起，該子區(qū)間的長度等于這個(gè)序列的概率。編碼過程從第一個(gè)符號開始，逐個(gè)處理。隨著處理符號數(shù)目的增加，同序列聯(lián)系在一起的區(qū)間長度越來越小。隨著區(qū)間的縮小，區(qū)間首尾二進(jìn)制代碼相同位數(shù)增多，這些二進(jìn)制代碼惟一確定了輸入符號序列，并可以惟一譯碼。概率大的符號對應(yīng)區(qū)間大，描述所需比特少。隨著輸入序列長度增加，平均編碼所用比特?cái)?shù)趨向信源熵。它利用了關(guān)聯(lián)信息，使得編碼效率得到提高。4.4.3算術(shù)編碼4.4圖像的信源編碼86傳真之類的二值圖像只有1、0兩個(gè)灰度級，若直接對其編碼，則比特?cái)?shù)等于像素?cái)?shù)，編碼效率較低。在空白較多時(shí)則可以采用跳躍空白編碼，即把行分段，如把8、10或12個(gè)像素分為一段，全白段用“0”表示，其他段則用標(biāo)識“1”加上段中像素的直接編碼表示。游程編碼是一種對相關(guān)性的信源較為有效的擴(kuò)展符號集的變換方法。在二元序列中，連“0”段稱為“0”游程，連“1”段稱為“1”游程，其長度分別稱為游程長度L(0)和L(1)?！?”游程和“1”游程總是交替出現(xiàn)?？梢园讶魏味蛄凶儞Q成游程長度的序列，簡稱游程序列。這種變換是一一對應(yīng)的，也就是可逆的，如二元序列“000101110010001……”可變換成游程序列“3113213……”。4.4.4游程編碼4.4圖像的信源編碼87游程序列已是多元序列，各長度就可以按Huffman編碼或其他方法處理以達(dá)到壓縮碼率的目的。因?yàn)橛纬涕L度的計(jì)數(shù)比較容易，得到游程長度后就可以從碼表中找出碼字輸出，同時(shí)去數(shù)下一個(gè)游程長度，因此這種從二元序列轉(zhuǎn)換成多元序列的方法，在實(shí)現(xiàn)時(shí)比較簡單。在減弱原有序列符號間的相關(guān)性方面，采用游程變換也較為有效。當(dāng)然，要對二元序列進(jìn)行Huffman編碼時(shí)，應(yīng)先測定“0”游程長度和“1”游程長度的概率分布，或由二元序列的概率特性去計(jì)算各種游程長度的概率。4.4.4游程編碼4.4圖像的信源編碼88針對一幅圖像中可能存在著若干具有相同灰度等級甚至相同圖像區(qū)域的這一特征，人們提出了輪廓編碼的方法來提高編碼效率。輪廓編碼的要點(diǎn)：（1）記錄邊界線，定義具有同一灰度等特征的圖像區(qū)域的邊界線為等值線，即找出“輪廓”；（2）發(fā)現(xiàn)、跟蹤等值線；（3）確定一條等值線的起始點(diǎn)；（4）對等值線進(jìn)行描述，分別對灰度級、等值線的初始位置、方向序列（上、下，左、右）等進(jìn)行編碼。輪廓編碼的方法適合灰度級較少的圖像。4.4.5輪廓編碼4.4圖像的信源編碼第四