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

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

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

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

Kraft不等式

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

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

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

平均碼長

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

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

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

例

2元編碼。設；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編碼算術編碼LZ編碼21Huffman編碼的最佳性所謂最佳：是指在所有可能的編碼方法中，其編碼得到的平均碼長最短。定理4.4.1：對于給定信源，存在有最佳惟一可譯二元碼，其最小概率的兩個碼字CK-1和CK的長度最長且相等，它們之間僅最后一位碼元取值不同(一個為0，另一個為1)。

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

其中，ak’=ak,Pk’=Pk,當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'的最佳碼，相應碼長為n’1，n’2，…，n’K-1，則對U的碼字C1，C2,…,CK的碼長為nk=n’k

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

例

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

例

對cabcedeacacdeddaaabaababaaabbacdebaceada

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

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

D進制哈夫曼編碼38共有K個符號，概率最小的R個符號碼長最長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個R個B=D-2-((K-2)mod(D-1))R=D-B=2+((K-2)mod(D-1))D進制哈夫曼編碼39例：對如下單符號離散無記憶信源編三進制哈夫曼碼。第一次取D-s=mod(8-2,3-1)+2=2個符號進行編碼。D進制哈夫曼編碼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個像素，則整個圖像將有大約8.4×106個像素。假定該圖像是彩色的，每個像素包含3色，每種顏色用8比特的碼字表示，可以算出該幅圖像將需用大約2×108比特來表示。與其他圖像格式相比，一幀高清晰度的電視圖像包含有大約1.8×106個像素，一幅標準電視圖像包含大約0.33×106個像素，一個高檔電腦顯示器包含1.2~3.1×106個像素。4.4圖像的信源編碼4.4.1圖像消息的信息特征80圖像消息的像素量很大，每一像素還有灰度等級、色度、飽和度等，這些參數相互之間通常具有較強的關聯性，存在著很大的冗余度統(tǒng)計冗余例如空間冗余、時間冗余、信息熵冗余等，它們主要取決于圖像信息的統(tǒng)計特性除此之外，還有結構冗余、知識冗余、視覺冗余等。正是由于圖像消息中存在著這些冗余，才使圖像編碼有著可觀的壓縮潛力。4.4圖像的信源編碼4.4.1圖像消息的信息特征81圖像壓縮編碼方法主要有兩類，即無失真編碼與限失真編碼。壓縮比都是衡量其性能的一個重要指標。定義4.9設信源消息初始編碼的代碼組平均長度為Ls，經壓縮編碼后代碼組的平均長度為Ld，則稱

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

…xi,…,

xK,P(xK

)對應于P(xK

)，有一個累積分布函數F(xK

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

)–P(xK

),F(xK

)]，可以找到一個二進制小數，由于對應于不同的P(xK

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