第2章無失真信源編碼

第2章無失真信源編碼2.1信息量、熵和互信息量2.2信源編碼定理2.3霍夫曼碼及其他編碼方法2.4算術(shù)編碼2.5游程編碼2.6改進的霍夫曼碼2.7通用編碼2.1信息量、熵和互信息量由于信源發(fā)出的消息是不確定的，只有當信源發(fā)出的消息通過信道傳輸給收方信宿后，才能消除不確定性并獲得信息。事件發(fā)生的不確定性與事件發(fā)生的概率有關(guān)。事件發(fā)生的概率越小，猜測它有沒有發(fā)生的困難程度就越大，不確定性就越大；而事件發(fā)生的概率越大，猜測這事件發(fā)生的可能性就越大，不確定性就越小。對于發(fā)生概率等于1的必然事件，就不存在不確定性。也就是說，信源發(fā)生的概率越小，一旦它出現(xiàn)必然使人感到意外，給人的信息量就越大；當消息的概率很小，即幾乎不可能的消息出現(xiàn)了，則會給人以巨大的信息量。反之，消息出現(xiàn)的概率很大，一旦出現(xiàn)人們不會感到意外，所以給人的信息量就很小，對必然出現(xiàn)的信息，則不具任何信息量，從數(shù)學(xué)理論知對數(shù)函數(shù)就有上述特征。因此給出如下的信息量定義。給出一個離散信源：其中p（ui）為ui出現(xiàn)概率，且如果消息ui已發(fā)生，則ui包含的自信息量為（2―1）式中：p（ui）——ui發(fā)生的先驗概率；I（ui

）——ui發(fā)生所含信息量。自信息量的單位與所用對數(shù)底有關(guān)。在信息論中常用的對數(shù)底是2，信息量的單位是比特（bit），即：I(ui)＝－lbp（ui

）（比特）；若取自然對數(shù)e為底，則信息量的單位為奈特（nat），即：I(ui)＝－lnp（ui

）（奈特）；若以10為對數(shù)底，則信息量的單位為笛特（det），即I(ui)＝－lgp（ui

）（笛特）。這三個信息量單位之間的轉(zhuǎn)換關(guān)系如下：1bit≈0.693nat≈0.301det如果p（ui）＝0.5,則由式（2―1）得I（ui）＝1bit。所以1比特信息量就是兩個互不相容的等可能事件之一發(fā)生時所提供的信息量。在這里，比特是指抽象的信息量單位，與計算機術(shù)語中“比特”的含義有所不同。當事件ui發(fā)生前，其自信息量I(ui)表示事件發(fā)生的不確定性；當事件ui發(fā)生后，其自信息量I(ui)表示事件所能提供的信息量。自信息量是針對信源發(fā)出的某一個消息而言所得出的信息量，不同的消息對應(yīng)不同的自信息量。自信息量I(ui)是一個隨機變量，其中任何一個消息的自信息量都代表不了信源所包含的平均自信息量。不能作為整個信源的信息測度，因此定義自信息量的數(shù)學(xué)期望為信源的平均自信息量，即：(2―2)這個平均自信息量的表達式和統(tǒng)計物理學(xué)中熱熵的表達式很相似。在統(tǒng)計物理學(xué)中，熱熵是一個物理系統(tǒng)雜亂性（無序性）的度量。這在概念上也有相似之處。因而就借用“熵”這個詞把平均自信息量H（U）稱為“信息熵”。信息熵的單位由自信息量的單位決定，即取決于對數(shù)底的選取，今后如不特殊說明，信息熵的單位為比特。信源的信息熵是從整個信源的統(tǒng)計特性來考慮的，它是從平均意義上來表征信源的總體信息測度的。對于某特定的信源（概率空間給定），其信息熵是一個特定的值。不同的信源因統(tǒng)計特性不同，其熵也不同。信息熵用以表征信息源的平均不確定性，平均自信息量是消除信源不確定性時所需信息的量度，即收到一個信源符號，全部解除了這個符號的不確定性?；蛘哒f獲得這樣大的信息量后，信源不確定性就被消除了。信息熵和平均自信息量兩者在數(shù)值上相等，但含義不同。某一信源，不管它是否輸出符號，只要這些符號具有某些概率特性，就必有信源的熵值；這熵值在總體平均上才有意義，因而是一個確定的值。而另一方面，信息量則只有當信源輸出的符號被接收者收到后才有意義，信息量就是給予接收者的信息度量，該值本身可以是隨機量，也可以與接收者的情況有關(guān)。因此說信息熵是信源的平均不確定性的描述，一般情況下它并不等于平均獲得的信息量。只是在無噪情況下，接收者才能正確無誤地接收到信源所發(fā)出的信息，消除了信息熵H（U）值大小的平均不確定性，所以獲得的平均信息量就等于信息熵H（U）的值。在一般情況下獲得的信息量是兩熵之差，并不是信息熵本身。信息熵是信源輸出的信息量，是信源包含的平均信息量，或信息的平均不確定性，而真正被接收者收到的信息是互信息。它是與收發(fā)雙方都有關(guān)系的相對量，是指接收者從信源發(fā)送者中所獲得的信息量。設(shè)信道輸入為其中p（xi）為xi出現(xiàn)概率,i＝１,２,…,n。信道輸出為其中p（yj）為yj出現(xiàn)概率，j＝１,２,…,m。由于收方信宿事先不知道信源在某一時刻發(fā)出的是哪一個符號，所以每個符號消息是一個隨機事件。通常信宿可以預(yù)先知道信源X發(fā)出的各個消息的集合，以及它們的概率分布，即預(yù)知信源X的先驗概率p（xi）。信息熵H（X）是在接收到Y(jié)以前，關(guān)于X的先驗不確定性的度量，是X中某一個符號（事件）出現(xiàn)所必須提供的信息量，所以稱為先驗熵。如果信道中無干擾（噪聲），信道輸出符號與輸入符號一一對應(yīng)，那么，接收到傳送過來的符號就消除了對發(fā)送符號的先驗不確定性。但一般信道中有干擾（噪聲）存在，接收到Y(jié)后對發(fā)送的是什么符號仍有不確定性。那么，怎樣來度量接收到Y(jié)后關(guān)于X的不確定性呢？下面討論這個問題。收到一個消息yj（yj∈{y1,y2,…,ym}）后，信宿可以計算各消息條件概率p（xi|yj），i＝１，２，３，…，n，xi∈{x1,x2,…，xn}，這種條件概率稱為后驗概率。因此，收到一個yj后關(guān)于X的平均不確定性為

(2―3)這是接收到y(tǒng)j后關(guān)于X的后驗熵?？梢?，后驗熵是當信道接收端接收到符號yj后，關(guān)于輸入符號的信息測度。但式（２―３）所考慮的僅是輸出端接收到Y(jié)中一種符號yj，所以這個后驗熵對接收碼Y求統(tǒng)計平均的條件熵為(2―4)式(2―4)表示，在信道輸出端收到輸出Y的全部符號后，對于信道輸入端輸入的X尚存在的不確定性（存在疑義），稱這個條件熵為信道疑義度。對X尚存在的這個不確定性是由于干擾（噪聲）引起的。如果是一一對應(yīng)信道，那么接收到輸出Y后，對X的不確定性將完全消除，則信道疑義度H（X|Y）＝0。由于條件熵小于無條件熵，即有H（X|Y）<H（X）。這正說明接收到Y(jié)的所有符號后，關(guān)于輸入X的平均不確定性將減小，即總能消除一些關(guān)于輸入X的不確定性，從而獲得了一些信息?？梢娦畔㈧豀（X）代表接收到輸出符號以前關(guān)于輸入X的平均不確定性，而H（X|Y）代表接收到所有輸出符號后關(guān)于輸入X的平均不確定性。通過信道傳輸消除了一些不確定性，獲得了一定的信息。所以定義信道輸入X和信道輸出Y之間平均互信息量為I（X；Y）＝H（X）－H（X|Y）

(2―5)式中：I（X；Y）——信道輸入X和信道輸出Y之間的互信息量；H（X）——信道輸入X的信息熵；H（X|Y）——收到所有輸出符號后關(guān)于輸入X的平均不確定性。可見，X和Y之間的互信息代表接收到輸出符號后平均每個符號獲得的關(guān)于X的信息量，也表明了輸入X和輸出Y之間的統(tǒng)計約束程度。根據(jù)H（X）和H（X|Y）定義得：

(2―6)式中，x∈{x1,x2,…，xn}；y∈{y1,y2,…,ym}。若X與Y獨立，則I（X；Y）＝0，這時收不到關(guān)于X的任何信息，說明干擾很大。當收到y(tǒng)（y∈{y1,y2,…,ym}）時給出的關(guān)于x(x∈{x1,x2,…，xn})的信息量I（x；y）定義為

(2―7)互信息量可取正值也可取負值，如果互信息量I（x；y）取負值，說明在未收到消息y以前對消息x是否出現(xiàn)的猜測難疑程度較小。但由于噪聲的存在，接收到消息y后，反而使接收者對消息x是否出現(xiàn)的猜測難疑程度增加了。也就是收到消息y后對x出現(xiàn)的不確定性反而增加，所以獲得的信息量為負值。因為p（xy）＝p（x）p（y|x）＝p（y）p（x|y）這表明一對消息可以互相提供相等的信息量。所以稱I（x；y）為x與y之間的互信息量。平均互信息量I（X；Y）是互信息量I（x；y）的統(tǒng)計平均值，所以平均互信息量I（X；Y）永遠不會取負值。最差情況是I（X；Y）＝0，說明收到Y(jié)后不能獲得任何關(guān)于X的信息量。由式（2―5）可推得：I（X；Y）

＝H（X）-H（X|Y）

＝H（Y）-H（Y|X）＝I（Y；X）

＝H（X）＋H（Y）-H（XY）（2―8）式中：因為H（X）是X所包含的平均信息量，或X中消息（符號）的平均不確定性，或消息集X中某一個消息（或符號）出現(xiàn)所必須提供的信息量，而H（X|Y）是當接收到Y(jié)時給出的關(guān)于X的不確定性。由式H（X|Y）＝H（X）－I（X；Y）可知，當收到Y(jié)時使X的不確定性減小了I（X；Y），這意味著接收到Y(jié)后，所獲得的關(guān)于X的信息量是I（X；Y）。由H（X）＝I（X；Y）＋H（X|Y）可知，X的信息熵等于接收到的信息量I（X；Y）加上損失掉的信息量H（X|Y）。因為條件熵H（X|Y）是由于信道上存在干擾和噪聲而損失掉的平均信息量，也叫損失熵。

由于損失掉這一部分信息量，故再要惟一的確定信源發(fā)出的信息，就顯得信息量不足。條件熵H（X|Y）又可以看作信道上的干擾和噪聲所造成的對信源符號X的平均不確定性。所以互信息量I（X；Y）是有擾離散信道上能傳輸?shù)钠骄畔⒘?，而條件熵H（X|Y）是在收到Y(jié)的條件下要惟一的確定信源發(fā)出符號所需要的平均信息量。式H（Y）＝H（Y|X）＋I（X；Y）表明，接收碼Y的熵H（Y）等于接收到關(guān)于X的信息量I（X；Y）加上H（Y|X）。這完全是由于信道中噪聲引起的，

故稱H（Y|X）表示在已知X條件下，對Y存在不確定性，反映了信道中噪聲源的不確定性。如果X與Y是相互獨立的，因為收到Y(jié)時給出關(guān)于X的條件概率等于無條件概率，又因為熵就是該條件概率的對數(shù)的數(shù)學(xué)期望，所以X的條件熵就等于X的無條件熵，此時I（X；Y）＝0。這可理解為既然X與Y相互獨立，無法從Y中提取關(guān)于X的信息。這可看成信道上噪聲相當大，以至有H（X|Y）＝H（X）。在這種條件下，傳輸?shù)钠骄男畔⒘繛榱?，這說明收到符號y后不能提供有關(guān)信源發(fā)出符號x的任何信息量。對于這種信道，信源發(fā)出的信息量在信道上全部損失掉了，故稱為全損離散信道。當X與Y有一一對應(yīng)關(guān)系時，即X與Y滿足確定函數(shù)關(guān)系時，條件概率必為0，也就是說I（X；Y）＝H（X），可見此時收到Y(jié)就完全解除了關(guān)于X的不確定性，所獲得的信息就是X的不確定性或熵。這可看成無擾離散信道，由于沒有噪聲，所以信道不損失信息量，此時信道疑義度H（X|Y）＝0。于是有I（X；Y）＝H（X）＝H（Y）。在一般情況下，X與Y既非相互獨立，也不是一一對應(yīng)，那么從Y獲得X的信息必在零與H（X）之間，即常小于X的熵。關(guān)于熵和互信息量等的更多知識請參閱有關(guān)文獻。2.2信源編碼定理若接收端信宿要求無失真精確的復(fù)制信源輸出的消息，這時信源編碼是無失真編碼。只有對離散信源可以實現(xiàn)無失真編碼，而對連續(xù)信源由于其輸出量為無限大，因此不可能實現(xiàn)無失真的信源編碼。離散信源的無失真編碼實質(zhì)上是一種統(tǒng)計匹配編碼。統(tǒng)計匹配編碼是根據(jù)信源的不同概率分布而選用與之相匹配的編碼，以便達到在系統(tǒng)中傳送速率最小，且滿足在信宿復(fù)制時無失真或低于某一允許的失真限度值。

2.2.1信源編碼的基本概念信源編碼是指將信源輸出符號，經(jīng)信源編碼器編碼后變換成另外的壓縮符號，然后將壓縮后信息經(jīng)信道傳送給信宿。為了簡化問題，研究無失真編碼時，只考慮信源和信宿兩個主要因素，忽略信道編、譯碼等的影響，這樣通信系統(tǒng)模型變?yōu)閳D2―1所示。圖2―1通信系統(tǒng)模型設(shè)圖2―1編碼器輸入為S＝（s1,…,sl,…,sL）,sl∈{u1,u2,…,un}編碼器輸出的碼字為X=(x1,…,xk,…,xK),xk∈{b1,b2,…,bm}可見，信源編碼就是從信源符號到碼符號的一種映射；譯碼是從碼符號到信源符號的映射。

若要實現(xiàn)無失真編碼，這種映射必須是一一對應(yīng)的，可逆的。下面給出一些碼的定義。若碼集為{0，1}，所得碼字為二元序列，則稱為二元碼(也叫二進制碼)。二元碼是數(shù)字通信和計算機系統(tǒng)中最常用的一種碼。若一組碼中所有碼字的碼長都相同，稱為等長碼。例如，信源符號U＝{u1，u2，u3，u4}，對應(yīng)不同碼字如表2―1所示。表2―1信源U對應(yīng)的不同碼字表2―1中碼1的編碼為等長碼，其他的幾種編碼皆為變長碼。表2―1中的碼3有兩個符號的編碼相同，這樣的編碼叫奇異碼，否則稱為非奇異碼。即奇異碼是有相同碼字的一種編碼；非奇異碼是一組碼中所有碼字都不同的編碼。表2―1中的碼1、碼2和碼4都為非奇異碼。任意有限長的碼元系列，只能被惟一的分割成一個個的碼字，便稱為惟一可譯碼。例如，碼字{0，10，11}是一種惟一可譯碼。因為任意一串有限長碼序列，例如100111000，只能被分割成10，0，11，10，0，0。任何其他分割法都會產(chǎn)生一些非定義的碼字。顯然，奇異碼不是惟一可譯碼，而非奇異碼中有非惟一可譯碼和惟一可譯碼。惟一可譯碼中又分為非即時碼和即時碼；如果接收端收到一個完整的碼字后，不能立即譯碼，還需等收到下一個碼字后才能判斷是否可以譯碼，這樣的碼叫做非即時碼。表2―1中,碼2是非即時碼，而碼4是即時碼。碼4中只要收到符號1就表示該碼字已完整，可以立即譯碼。即時碼又稱為非延長碼。其中任意一個碼字都不是其他碼字的前綴部分，這種碼稱為異前綴碼。表2―1中的碼1和碼4都是異前綴碼。在惟一可譯變長碼中，需要的是在譯碼時無需參考后續(xù)的碼符號就能立即做出判斷的一類即時碼。異前綴碼一定是即時碼，這可以直接從即時碼的定義得出。事實上，如果沒有一個碼字是其他碼字的前綴，則在譯碼過程中，當收到一個完整碼字的碼符號序列時，就能直接把它譯成對應(yīng)的信源符號，無需等待下一個符號到達后才作判斷。反之，非異前綴碼一定不是即時碼。設(shè)碼中有一些碼字，例如碼字Cj是另一碼字Ci的前綴。收到的碼符號序列正好是Cj時，它可能是碼字Cj，也可能是碼字Ci的前綴部分，因此不能立即作出判斷，譯出相應(yīng)的信源符號來，必須等待其后一些符號的到達，才能做出正確判斷。即時碼一定是惟一可譯碼，反之惟一可譯碼不一定是即時碼。因為有些非即時碼（延長碼）也具有惟一可譯性。樹圖法是構(gòu)造即時碼的一種簡單方法。樹是n個結(jié)點的集合，這n個結(jié)點中有且僅有一個作為根的結(jié)點，其余的結(jié)點可分為m個互不相交的子集，每個子集本身又是一棵樹，稱為根的子樹，也叫根的樹枝數(shù)。圖2―2（a）中，結(jié)點A為樹根，它的樹枝數(shù)為2，結(jié)點B的樹枝數(shù)為3。圖2―2樹結(jié)構(gòu)圖一個結(jié)點擁有的子樹的個數(shù)稱為該結(jié)點的度（Degree）；一棵樹的度是指該樹中結(jié)點的最大度數(shù)。度為零的結(jié)點稱為葉子（Leaf）或終端結(jié)點。圖2―2（a）中，結(jié)點A，B，E的度分別為2，3，0；樹的度為3；D，E，F(xiàn)，H，I，J和K均為葉子。度不為零的結(jié)點稱為分支結(jié)點或非終端結(jié)點，除根結(jié)點之外的分支結(jié)點統(tǒng)稱為內(nèi)部結(jié)點，根結(jié)點又稱為開始結(jié)點。從一個結(jié)點到另一個結(jié)點之間的通路叫兩個結(jié)點間的路徑，路徑所經(jīng)過的邊（即連接兩個結(jié)點的線段）的數(shù)目，叫路徑長度。

圖2―2（a）中結(jié)點A到結(jié)點I的路徑是ACGI，路徑長度為3。如果樹中各個結(jié)點有相同的樹枝數(shù)，且每層結(jié)點數(shù)達到最大值，此樹稱為滿樹，否則稱為非滿樹。圖2―2（b）所示為滿樹，（a）和（c）為非滿樹。可用樹圖對信源符號進行編碼。下面給出樹圖與信源符號編碼之間的對應(yīng)關(guān)系：樹根碼字的起點樹的度碼元數(shù)分支結(jié)點碼的符號的一部分終端結(jié)點待編碼符號滿樹等長碼非滿樹變長碼用于編碼時，樹圖又稱為碼樹。用碼樹進行信源符號編碼時，將待編碼的字符作為終端結(jié)點，構(gòu)造碼樹；然后按一定規(guī)則給每個樹枝分配一個標記；最后將從根到終端結(jié)點的路徑上的標號依次相連，作為該終端結(jié)點所表示的字符的編碼。圖2―3給出了幾種碼樹圖。圖（a）對應(yīng)等長二元碼，圖（b）對應(yīng)變長二元碼，圖（c）對應(yīng)變長三元碼。信源各個符號對應(yīng)的碼字如圖2―3所示。利用該圖可以求出信源序列的編碼。若信源序列為bacabd，則對應(yīng)二元變長碼（圖2―3（b）編碼）的碼字序列為100110010111。碼樹既可用于信源符號的編碼，也可用于譯碼。當接收到一串碼符號序列后，首先從樹根出發(fā)，根據(jù)接收到的第一個碼字符號來選擇應(yīng)走的第一條路徑。若沿著所選路徑走到分支結(jié)點，再根據(jù)收到的第二個碼符號來選擇應(yīng)走的第二條路經(jīng)，如此下去，直至走到終端結(jié)點為止。最后，根據(jù)所走路徑，可立即判斷出接收到的碼符號。使系統(tǒng)重新返到樹根，再作下一個接收碼符號的判斷，如此下去，就可以將接收到的一串碼符號序列譯成對應(yīng)的信源符號序列。對圖2―3（b）所示編碼樹，若收到的碼符號序列為100110010111，則按上述方法可譯出信源符號序列為bacabd；若碼符號序列為100111110，可譯出對應(yīng)信源符號序列為badc。圖2―3碼樹圖2.2.2變長碼若要實現(xiàn)無失真編碼，不但要求信源符號與每個符號的碼字是一一對應(yīng)的，而且要求碼符號序列與信源符號序列也是一一對應(yīng)的。也就是說，任意一串有限長的碼符號序列只能被惟一的譯成對應(yīng)的信源符號序列，滿足這種條件的碼稱為惟一可譯碼。如果所編的碼不具有惟一可譯性，就會在譯碼中引起錯誤與失真。對等長碼，要做到無失真，必須取足夠大數(shù)量的符號一起編碼，這顯然是不現(xiàn)實的，如果采用變長碼，情況則完全不一樣。下面先給出定長編碼定理，然后說明為什么研究變長碼及變長碼特點。

定理2―1

（等長信源編碼定理）

一個熵為

的離散無記憶信源，若對信源長為N的符號序列進行等長編碼，設(shè)碼字是從m個字母的碼符號集中選取L個碼元組成。對于任意ε>0，只要滿足：

（2―9）則當N足夠大時，幾乎可實現(xiàn)無失真編碼，即譯碼錯誤概率能為任意小。反之，若（2―10）則不可能實現(xiàn)無失真編碼，而當N足夠大時，譯碼錯誤概率近似等于1。對該定理的嚴格證明請參閱有關(guān)參考文獻。為了衡量編碼效果，定義編碼信息率：

(2―11)式中：L——碼長；m——碼元數(shù)；N——信源序列長度;R′——編碼后平均每個信源符號能載荷的最大信息量。

定義等長編碼效率η：式中：H（U）——信源熵。由定理2―1可知，最佳等長編碼效率η為(2―1２)(2―13)對等長編碼，若要實現(xiàn)幾乎無失真編碼，則信源長度必滿足:（2―14）式中：

σ2——信源方差；H(U)——信源熵；η——編碼效率；

Pe——差錯率。

式（2―14）給出了在已知方差和信源熵條件下，信源序列長度N與最佳編碼效率和允許錯誤率之間的關(guān)系。可見，編碼效率越高，允許錯誤率越小，則信源序列長度N越長。在實際情況下，要實現(xiàn)幾乎無失真的等長編碼，N需要大到難以實現(xiàn)的程度。下面舉例說明。

【例2―1】

設(shè)離散無記憶信源:信源熵：方差：若取差錯率Pe＝10－6，編碼效率為95%，則可計算出等長編碼需聯(lián)合的信源符號數(shù)N應(yīng)滿足：可見，在差錯率和編碼效率要求并不十分苛刻的條件下，就需要近100萬個信源符號進行聯(lián)合編碼，這顯然是很難實現(xiàn)的。若對例2―1用變長碼實現(xiàn)（具體編碼方法及、η公式在后面介紹），則符號u1

u2

u3

u4碼字010110111信源熵：平均碼長：編碼效率：可見，若采用變長碼，其效率可達100％。這雖然是一個特例，但一般情況下變長碼的編碼效率都很高，它優(yōu)于等長編碼。實際上，一般離散無記憶信源輸出的各消息（符號）的概率是不相等的。對出現(xiàn)概率大的信源符號采用較短的碼字；而對出現(xiàn)概率小的信源符號采用較長的碼字。這樣，從整個信源來看，編成的信源碼字的平均碼長最短，它也實現(xiàn)了與信源統(tǒng)計特性相匹配。這就是變長碼的基本思想。那么為什么要使平均碼長最短呢？下面討論此問題。設(shè)信源為編碼后各碼字的碼長分別為：l1,l2,…，ln,則定義碼字的平均碼長度為碼符號/信源符號(2―15)平均碼長是每個信源符號平均需用的碼元數(shù)。信源編碼的目的是為了提高通信系統(tǒng)的有效性，而和編碼后的壓縮效果密切相關(guān)。平均碼長大，則壓縮效果差，系統(tǒng)有效性差；若平均碼長小，則壓縮效果好，系統(tǒng)有效性高。為此，我們感興趣的是平均碼長最短的編碼，這種編碼可使通信系統(tǒng)更經(jīng)濟、簡單，使信息傳輸效率更高。當信源給定時，信源的熵H（U）就確定了，編碼后每個信源符號的平均碼元數(shù)為，那么平均每個碼元攜帶的信息量，即編碼后信道的信息傳輸率為比特/碼符號(2―16)若傳輸一個碼符號平均需要ｔ秒，則編碼后信道每秒鐘傳輸?shù)男畔⒘繛楸忍?秒(2―17)由此可見平均碼長越短，Rt越大，信息傳輸效率就越高，為此我們感興趣的碼是平均碼長最短的碼。另外，變長碼一般不能直接由信道來傳送，為了適應(yīng)信道，必須有緩沖設(shè)備，將碼符號暫存于緩沖設(shè)備中，若平均碼長大，則編碼后需存儲的信息就多，需要的存儲器的容量就大，反之，若平均碼長最短，則需要存儲的信息量就最少，這時可使通信系統(tǒng)更經(jīng)濟。對于某一信源和某一碼符號集來說，若有一個惟一可譯碼，其平均長度小于所有其他惟一可譯碼的平均長度，則該碼稱為緊致碼，或稱最佳碼。無失真信源編碼的基本問題就是要找最佳碼。那么，平均碼長有沒有極限值，如果有，它的值又是多少呢？這個問題將在2.2.4節(jié)中介紹。下面討論變長碼的缺點和需采取的措施。1．使信道復(fù)雜化一般情況下，信源符號以恒速輸出，信源輸出經(jīng)變長編碼后，輸出的每秒比特數(shù)就不是常量，因而不能直接由信道來傳送。為了適應(yīng)信道，必須有緩沖設(shè)備，將編碼輸出暫存在緩沖器中，然后再送到信道去傳送。從理論上說，信道傳送速率應(yīng)等于信源輸出速率S與平均碼長的乘積。就是當存儲器容量為無限時，信源輸出與信道傳送之間取得平衡。在時間趨向于無限時，信源輸出的比特數(shù)和信道上傳送比特數(shù)接近相等。2．容易產(chǎn)生溢出或取空錯誤根據(jù)前面分析，當存儲器容量無限時，信源輸出與信道傳送之間取得平衡。當存儲器容量有限時，這種平衡不一定能保持。如當信源連續(xù)輸出低概率符號時，由于每個符號的碼長較長，輸入到存儲器的比特數(shù)將大于信道能輸出的比特數(shù)，可能使存儲器存不下而溢出；反之，若高概率符號連續(xù)出現(xiàn)，輸入比特數(shù)將小于信道中傳送的比特數(shù)，以致存儲器被取空，信道上將無信息可傳送。這兩種情況都會造成不良后果。前者可使信息由于溢出而丟失，后者由于取空而使信道上出現(xiàn)連0或連1，在譯碼時會誤譯，也造成差錯。所以應(yīng)估計所需存儲器容量，才能使上述現(xiàn)象發(fā)生的概率小至可以容忍。

一般的說，變長碼只適用于有限長的信息傳送，也就是送出一段信息后，信源能停止輸出，如傳真機送出一張紙以上的信息后就停止。對于長信息，在實際使用時可把長信息分段發(fā)送，也可檢測存儲器狀態(tài)，發(fā)現(xiàn)將要溢出就停止信源輸出，發(fā)現(xiàn)將要取空就插入空閑標志在信道上傳送，或加快信源輸出。3．差錯的擴散

因為采用異前綴碼來分解碼字，一旦在傳送中出現(xiàn)誤碼，某個碼字的前綴部分可能成為另一個碼字，因而錯譯為另一符號，而剩下部分又與后面碼字的一部分譯成某一符號。這樣下去，可能要經(jīng)過一段信息被錯譯后，才能正確分離碼字?？朔@種缺點的措施是力求信道不出誤碼，如采用糾錯或檢錯編碼。尤其是檢錯重發(fā)方式，設(shè)計得好可基本上不出差錯或差錯小到可容忍的程度。檢錯可用附加監(jiān)督位的方式,也可在編碼時有意識地不編成滿樹,某些樹葉不用來代表某個符號,一旦這種碼字出現(xiàn)在接收端,說明傳送中有誤碼,可要求發(fā)端重發(fā)。變長編碼具有很高的編碼效率，有時幾乎接近于1，但上述缺點限制了它的應(yīng)用范圍。采用變長碼時,常需有大容量的存儲設(shè)備作為緩沖，這也有利于重發(fā)。近來存儲器發(fā)展很快，不但容量越來越大，價格也越來越低，這會使變長碼應(yīng)用范圍不斷擴大。2.2.3克拉夫特（Kraft）不等式變長碼有很多優(yōu)點，但真正使用時，又會遇到難題，這就是由于編成的碼字是不等長度的，將它傳送至接收端，如何進行辨認。對等長碼，接收端只要根據(jù)約定的碼組長度進行判決即可。對變長碼，由于編成的碼長度是不一樣的，無法根據(jù)碼組長度進行判決。如何克服并解決這一難題，是采用變長碼時應(yīng)解決的主要問題。解決它一般有兩種方法，一種是類似于莫爾斯電報方法，碼字間留空隙，或者加同步信號，但這種方法不經(jīng)濟，直接影響譯碼效率；另一種是采用可分離碼字。

異前綴碼是一種實時的惟一可譯碼，這類碼無需另加同步信息，就能在接收端被分離出來。在信源編碼和數(shù)據(jù)壓縮中這類編碼無論在理論還是在實際中都有很大意義，對較簡單的信源，可以很方便地用碼樹法直接且直觀地構(gòu)造出可分離碼（異前綴碼），但是當信源較復(fù)雜，直接畫碼樹就比較復(fù)雜。針對這一問題，在數(shù)學(xué)上給出一個與碼樹等效的，表達碼字可分離的充要條件，即著名的克拉夫特不等式。定理2―2

對于碼長分別為l1,l2，…，ln的m元碼，若此碼為即時碼，則必定滿足(2―18)反之，若碼長滿足不等式（2―18），則一定存在具有這樣碼長的即時碼。不等式（2―18）是1949年由L.G.Kraft提出的，所以稱克拉夫特（Kraft）不等式?？死蛱夭坏仁街赋黾磿r碼的碼長必須滿足的條件。后來在1956年，麥克米倫（B.McMillan）證明惟一可譯碼也滿足此不等式，1961年卡拉什（J.karuSh)簡化了麥克米倫的證明方法。這說明惟一可譯碼在碼長的選擇上并不比即時碼有什么更寬松的條件，而是惟一可譯碼的碼長也必須滿足克拉夫特不等式，所以在碼長選擇的條件上，即時碼與惟一可譯碼是一致的。下面給出克拉夫特不等式的證明。證明設(shè)任意即時碼C對應(yīng)碼長分別為l1,l2，…，ln。因為任意即時碼都可以用碼樹來描述，則即時碼C一定可以用m元碼樹來表示。從碼樹看，第N階所有可能伸出樹枝數(shù)為mN。當某第i（i＜N）階結(jié)點作為碼字，即碼長li＝i0，它將影響到第N階所伸出樹枝。它使第N階不能伸出的樹枝數(shù)為

。因為共有n個碼字，每個碼字作為樹終端結(jié)點后，都會影響第N階所伸出樹枝。假設(shè)N≥maxli(i＝1,2,3,…,n)，則n個碼字影響第N階總共不能伸出的樹枝為（2―19）這些總共不能伸出樹枝數(shù)必小于或等于第N階所有可能伸出樹枝數(shù)，所以有整理得定理充分性的證明可參見相關(guān)參考文獻?？死蛱夭坏仁浇o出了m元碼字中，信源序列中的消息數(shù)（符號數(shù)）n以及碼字的各個碼長li（i＝1，2，…，n）之間的關(guān)系。如果二者滿足式（2―18），則至少能夠構(gòu)成一種這樣碼長的即時碼，即時碼是惟一可譯碼。否則，無法構(gòu)成惟一可譯碼。如表2―1中，m＝2，n＝4。對碼1有l(wèi)1＝2,l2＝2,l3＝2,l4＝2，則滿足式（2―18），則此碼長的編碼是惟一可譯碼。對碼2有l(wèi)1＝1,l2＝2,l3＝2,l4＝2，則不滿足式（2―18），則此碼長的編碼不能構(gòu)成惟一可譯碼。對碼4有l(wèi)1＝1,l2＝2,l3＝3,l4＝4，則滿足式（2―18），則此碼長的編碼是惟一可譯碼。2.2.4信源編碼定理由前面討論可知，用變長碼實現(xiàn)無失真編碼時，平均碼長越短越好，那么平均碼長的極限是多少？下面的定理將回答這個問題。

定理2―3

若一個離散無記憶信源U的熵為H（U），每個信源符號用m碼元進行變長編碼，則總可找到一種無失真編碼方法，構(gòu)成惟一可譯碼，使其平均碼長滿足：(2―20)此編碼定理給出了最佳變長碼的平均碼長的上限和下限。定理表明碼字的平均長度不能小于極限H(U)/lbm，否則惟一可譯碼不存在；該定理還給出了最佳碼的最短平均碼長，并指出這個最短的平均碼長與信源熵是有關(guān)的。在尚未編出碼字之前就知道平均碼長落在什么范圍，這當然是很重要的。該定理指出，最佳變長碼應(yīng)是與信源熵相匹配的編碼，其下限更重要，因為它是信源壓縮編碼的極限。我們通常稱達到下限的最佳變長碼為熵編碼。定理的證明參見有關(guān)文獻。

定理2―4

無失真變長信源編碼定理（香農(nóng)第一定理）。離散無記憶信源U的N次擴展信源UN＝{α1,α2,…，αNn}，其熵為H(UN)，并有碼符號

X＝{x1,x2，…，xm}，對信源UN進行編碼，總可以找到一種編碼方法，構(gòu)成惟一可譯碼，使信源U中每個信源符號所需的平均碼長滿足：

或者(2―21)(2―22)當N→∞時，則得式中：式中：(2―23)而λi是αi所對應(yīng)的碼字長度，因此，是無記憶擴展信源UN中每個符號αi的平均碼長，可見

仍是信源U中每一單個信源符號所需的平均碼長。的含義是為了得到這個平均值，不是對單個信源符號ui進行編碼，而是對N個信源符號的序列αi進行編碼。定理2―4指出，要做到無失真的信源編碼，對每個信源符號編碼平均所需最少的碼元數(shù)m就是信源的熵值。若編碼的平均碼長小于信源的熵值，則惟一可譯碼不存在。變長編碼后平均每個信源符號能載荷的最大信息量為（2―24）式中：

——N次擴展信源的平均碼長；m——碼元數(shù)。

這時，香農(nóng)第一定理也可陳述為：若R′>H（U），就存在惟一可譯變長編碼；若R′<H（U），惟一可譯變長碼不存在，不能實現(xiàn)無失真的信源編碼。若從信道角度看，當平均碼長達到極限值H（U）/lbm時，根據(jù)式（2-16）可得編碼后的信道的信息傳輸率為R＝lbm,比特/碼符號

由此可見，這時信道的信息傳輸率等于無噪無損信道的信道容量，信息傳輸效率最高。

因此，無失真信源編碼的實質(zhì)就是對離散信源進行適當?shù)淖儞Q，使變換后新的碼符號信源（信道的輸入信源）盡可能為等概率分布，以使新信源的每個碼符號平均所包含的信息量達到最大，從而使信道的信息傳輸率和信道容量相等，實現(xiàn)信源與信道理想的統(tǒng)計匹配，這也是香農(nóng)第一定理的物理意義。無失真信源編碼定理通常又稱為無噪信道編碼定理。此定理可以表述為：若信道的信息傳輸率不大于信道容量，總能對信源的輸出進行適當?shù)木幋a，使得在無噪無損信道上能無差錯地以最大信息傳輸率傳輸信息；但要使信道的信息傳輸率大于信道容量而無差錯的傳輸信息是不可能的。下面討論變長碼達到極限的情況。設(shè)對信源U進行編碼所得到的平均碼長，因為一定大于或者等于Hm(U)，所以定義編碼的效率η為

(2―25)η小于或等于1。對同一信源來說，若碼的平均碼長越短，越接近極限值Hr（U），信道的信息傳輸率就越高，就越接近無噪無損信道容量，這時η也越接近于1，所以可用碼的效率η來衡量各種信源編碼的優(yōu)劣。另外，為了衡量各種編碼與最佳碼的差距，定義碼剩余度為(2―26)在二元無噪無損信道中m＝2，所以Hm(U)＝H(U)，式（2―25）為所以在二元無噪無損信道中信息傳輸率為注意式中R與η數(shù)值相同，單位不同，其中η是個無單位的比值。2.2.5統(tǒng)計匹配碼

從信源編碼定理可以看出，離散無失真編碼實質(zhì)上是一種統(tǒng)計匹配編碼，是根據(jù)信源符號的不同概率分布分配與之相對應(yīng)碼字，對出現(xiàn)概率大的符號分配短的碼字，對出現(xiàn)概率小的符號分配長的碼字，這樣可使信源符號的平均碼長最短，從而保證通信系統(tǒng)的有效性。那么，如果不考慮信源的統(tǒng)計特性，能否做到有效且無失真呢？下面討論這個問題。編碼器輸入為S=（s1,…,sl,…,sL）,sl∈{u1,u2,…,un}編碼器輸出的碼字為X＝(x1,…,xk,…,xK),xk∈{b1,b2,…,bm}

要實現(xiàn)無失真信源編碼，必須同時滿足無失真和有效性兩個條件。如果不考慮信源統(tǒng)計特性，若要滿足無失真，就必須使每個信源輸出的消息（或符號）都能找到一個對應(yīng)的碼字，即滿足：mK≥nL

(2―27)若取m＝n，由式（2―27）得K≥L說明碼序列的長度大于信源序列長度，顯然不滿足有效性。若選K＝L，由式（2―27）得m≥n這顯然不滿足無失真。所以若先考慮有效性，則無失真得不到滿足。要想同時滿足上述兩個基本條件的要求，惟一辦法是從信源統(tǒng)計特性上去考慮。由式（2―27）得

(2―28)式（2―28）中的logan和logam分列是不考慮信源統(tǒng)計特性或等概率條件下消息熵H（U）＝logan與碼熵H（X）＝logam。當考慮信源的統(tǒng)計特性時，信源符號一般是不等概率的，這時消息熵H（U）為將其代入式（2―28）得：(2―29)2.3霍夫曼碼及其他編碼方法無失真的信源編碼定理，既是存在性定理也是構(gòu)造性定理，即它給出了構(gòu)造信源編碼的原理性方法，這樣構(gòu)造出的碼的平均碼長與信源統(tǒng)計特性相匹配。為此，香農(nóng)、費諾、霍夫曼都各自按上述思路設(shè)計出不同的具體編碼方法，其中霍夫曼給出的方法最好。本節(jié)將介紹這些具體的編碼方法。2.3.1霍夫曼(Huffman)碼1952年，霍夫曼提出了一種構(gòu)造最佳碼的方法，它是一種逐個符號的編碼方法。所得的碼字是異前綴碼的變長碼，其平均碼長最短，是最佳變長碼，又稱霍夫曼碼。二元霍夫曼碼編碼步驟如下：(1)將n個信源U的各個符號ui按概率分布p（ui）以遞減次序排列起來。(2)將兩個概率最小的信源符號合并成一個新符號，新符號的值為兩個信源符號值的和，從而得到只包含n－1個符號的新信源，稱為U信源的縮減信源U1。(3)把縮減信源U1的符號仍按概率以遞減次序排列，然后將其中兩個概率最小的符號合并成一個符號，這樣又形成了n－2個符號的縮減信源U2。(4)依次繼續(xù)下去，直至信源最后只剩下１個符號為止。(5)將每次合并的兩個信源符號分別用0和1碼符號表示。(6)從最后一級縮減信源開始，向前返回，就得出各信源符號所對應(yīng)的碼符號序列，即得各信源符號對應(yīng)的碼字?！纠波D２】

離散無記憶信源:對應(yīng)的霍夫曼編碼如圖２―４所示。圖2―4例2―2霍夫曼編碼信源熵:平均碼長：編碼效率：

【例2―3】

離散無記憶信源:的兩種霍夫曼編碼如圖2―5所示。這兩種方法對應(yīng)的霍夫曼樹分別如圖2―6(a)、(b)所示。圖2―5例2―3兩種霍夫曼編碼圖2―5例2―3兩種霍夫曼編碼

圖2―6例2―3對應(yīng)碼樹例2―3中（a）、（b）兩種方案的霍夫曼編碼平均碼長都為信源熵為編碼效率為兩種碼有相同的平均碼長，有相同的編碼效率，但每個信源符號的碼長卻不相同，其均方差也不同。下面分別計算兩種碼的均方差σ2，即：(方法(a)方差)(方法(b)方差)可見，方法（a）的方差比方法（b）的方差要小許多。方法(a）的具體編碼原則是，把合并后的概率總是放在其他相同概率的信源符號之上（或之左），方法（b）的編碼原則是，把合并后的概率放在其他相同概率的信源符號之下（或之右）。從上面的分析可以看出，方法（a）要優(yōu)于方法（b）。2.3.2m元霍夫曼碼前面討論的二元霍夫曼碼的編碼方法可以推廣到m元編碼中。不同的只是每次把概率最小的m個符號合并成一個新的信源符號，并分別用0，1，…，（m－1）等碼元表示。為了使短碼得到充分利用，使平均碼長最短，必須使最后一步的縮減信源有m個信源符號。因此對于m元編碼，信源U符號個數(shù)n必須滿足：n＝（m－1）Q＋m（2―30）式中：n——信源符號個數(shù)；m——進制數(shù)（碼元數(shù)）；Q——縮減次數(shù)。對于二元碼，總能找到一個Q，滿足式（2―30）。但對于m元碼，n為任意正整數(shù)時不一定能找到一個Q滿足式（2―30），此時，可以人為地增加一些概率為零的符號，以滿足式（2―30）。然后取概率最小的m個符號合并成一個新符號（結(jié)點），并把這些符號的概率相加作為該結(jié)點的概率，重新按概率由大到小順序排隊，再取概率最小的m個符號（結(jié)點）合并；如此下去直至樹根。下面給出m元霍夫曼編碼步驟：(1)驗證所給n是否滿足式（2―30），若不滿足該式，可以人為地增加一些概率為零的符號，以使最后一步有m個信源符號；(2)取概率最小的m個符號合并成一個新結(jié)點，并分別用0，1，…，（m－１）給各分支賦值,把這些符號的概率相加作為該新結(jié)點的概率；(3)將新結(jié)點和剩下結(jié)點重新排隊，重復(fù)（2），如此下去直至樹根。(4)取樹根到葉子（信源符號對應(yīng)結(jié)點）的各樹枝上的賦值，得到各符號碼字。后來新加的概率為零的符號，雖也賦予碼字，實際上這是冗余碼字，并未用上，但這樣編成的碼，仍是最佳的，也就是平均碼長最短，如果等概率符號排隊時注意到順序，則碼長的方差也是最小的?！纠?―4】

已知離散無記憶信源其三元霍夫曼編碼如圖2―7所示，四元霍夫曼編碼如圖2―8所示。下面計算例2―4的編碼效率。圖2.7例2―4三元霍夫曼編碼圖2―8例2―4四元霍夫曼編碼信源熵：兩種編碼的平均碼長分別為因為lb3＝1.58bit,lb4＝2bit，所以其編碼效率分別為可見，要發(fā)揮霍夫曼編碼的優(yōu)勢，一般情況下，信源符號集的元數(shù)應(yīng)遠大于碼元數(shù)。對例2―4中，若編五元碼，只能對每個信源符號賦予一個碼數(shù)，等于沒有編碼，當然無壓縮可言。那么，什么樣的編碼能獲得最佳的壓縮效果呢？下面討論這個問題。圖2―92.3.3霍夫曼碼的最佳性設(shè)信源U中每個符號ui(ui∈｛u1，u2，…，un})的頻度為fi，碼長為li，則表示編碼后的信源總長。有時并非每次壓縮都去統(tǒng)計各字符在文件中出現(xiàn)的頻度，而是通過對定義在相同字符集上的大量文件進行統(tǒng)計分析，得出每個字符ui的概率p（ui），此時的表示平均碼長。將使或最小的即時編碼稱為最佳碼。所謂最佳碼，就是指對于某個給定信源，在所有可能的惟一可譯碼中，此碼的平均碼長最短。另外霍夫曼編碼可由霍夫曼樹構(gòu)造，平均碼長（或文件總長）是霍夫曼樹的帶權(quán)路徑長度。由于霍夫曼樹是權(quán)最小的樹，因此霍夫曼編碼的平均碼長亦最小，霍夫曼碼是最佳碼。最優(yōu)的前綴碼對文件的壓縮效果亦最佳?；舴蚵幋a的特點之一是高頻先見?；舴蚵木幋a方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，即

p（uj）>p（uk），有l(wèi)j≤lk。這是現(xiàn)代編碼的基礎(chǔ)，是漢字編碼的簡碼設(shè)計原則，也是動態(tài)高頻優(yōu)選的原則。符號集中的任一字符的碼字都不是其他字符編碼的前綴，可直接用于譯碼，所以霍夫曼碼是即時碼。2.3.4費諾（Fano)編碼費諾編碼屬于統(tǒng)計匹配編碼，但它不是最佳的編碼方法。其編碼步驟如下：(1)將信源消息（符號）按其出現(xiàn)的概率由大到小依次排列；(2)將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組分別賦予一個二進制碼元“0”和“1”。(3)將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之和近于相同，并又分別賦予一個二進制符號“0”和“1”。(4)如此重復(fù)，直至每個組只剩下一個信源符號為止。(5)信源符號所對應(yīng)的碼字即為費諾碼?！纠?―5】

離散無記憶信源的費諾編碼如圖2―9所示。信源熵：平均碼長：【例2―6】

離散無記憶信源編碼效率：的費諾編碼如圖2―10所示。圖2―10例2―6費諾編碼圖信源熵：平均碼長：編碼效率：【例2―7】

已知離散無記憶信源的費諾編碼如圖2―11所示。由上述分析可見，費諾碼考慮了信源的統(tǒng)計特性，使經(jīng)常出現(xiàn)的信源符號能對應(yīng)碼長短的碼字。顯然，費諾碼仍然是一種相當好的編碼方法。但是，這種編碼方法不一定能使短碼得到充分利用。尤其當信源符號較多，并有一些符號概率分布很接近時，分兩大組的組合方法就很多。可能某種分配結(jié)果，會出現(xiàn)后面小組的“概率和”相差較遠，因而使平均碼長增加，所以費諾碼不一定是最佳碼。費諾碼的編碼方法實際上是構(gòu)造碼樹的一種方法，所以費諾碼是一種即時碼。圖2―11例2―7費諾編碼圖

2.3.5香農(nóng)―費諾―埃利斯碼香農(nóng)―費諾―埃利斯碼不是分組碼，它根據(jù)信源符號的積累概率分配碼字，不是最佳碼，但它的編碼和譯碼效率都很高。設(shè)信源為定義信源符號積累概率為(2―31)由信源符號積累概率定義可知，和F(uk)都是小于1的正數(shù)，可將這些小于1的正數(shù)映射到區(qū)間（0，1］內(nèi)，圖2―12描繪了積累概率分布。圖2―12積累概率分布圖可見，符號的積累概率函數(shù)呈級躍形，符號的積累概率的值是上界值，每個臺級的高度（或?qū)挾龋┚褪窃摲柕母怕蕄(uk)值，修正的積累概率對應(yīng)臺級的中點。因為所有的積累概率F(uk)都是正數(shù)，且當ui≠uj時，F(xiàn)(ui)≠F(uj),所以這些積累概率F(ui)將區(qū)間（0，1］分成許多互不重疊的小區(qū)間。若知道了，就能確定其處在哪個小區(qū)間，就能確定相應(yīng)的信源符號uk,所以可采用的數(shù)值作為符號uk的碼字。那么，這樣給出的符號的編碼是即時碼嗎？碼長又如何選取呢？下面討論這些問題。

一般情況下，為一實數(shù)，將其轉(zhuǎn)換成二進制小數(shù)的形式，取小數(shù)點后l(uk)位作為uk的碼字。根據(jù)二進制小數(shù)截去位數(shù)的影響得：（2―33）式中：——取l(uk)位小于等于的最大整數(shù)。若取(2―34)式中：［X］——取大于或等于X的最小整數(shù)。得：

(2―35)(2―36)則這樣編得的碼字在信源符號uk對應(yīng)的區(qū)間內(nèi)。上面證明了將轉(zhuǎn)化為二進制數(shù)的形式，取小數(shù)點后l(uk)位作為符號uk的碼字，此碼字恰好在符uk對應(yīng)的區(qū)間內(nèi)。那么，這樣得到的碼字是即時碼嗎？從F(uk)劃分的區(qū)間看，若每個信源符號uk所對應(yīng)的區(qū)間都沒有重疊，那么，此編碼一定是即時碼。由式（2―34）可得香農(nóng)―費諾―埃利斯碼平均碼長為則：

(2―37)【例2―8】

離散無記憶信源的香農(nóng)―費諾―埃利斯碼編碼如表2―2所示。表2―2例2―8香農(nóng)―費諾―埃利斯碼碼表信源熵：平均碼長：編碼效率：【例2―9】

離散無記憶信源的香農(nóng)―費諾―埃利斯碼編碼如表2―3所示。此編碼比霍夫曼碼每位信源符號多1.2位碼元。表2―3例2―9香農(nóng)―費諾―埃利斯碼碼表前面討論了信源編碼原理及各種編碼方法?；舴蚵a的編碼方法保證了概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，而且所有短碼得到充分利用；且每次縮減信源的最后兩個碼字總是最后一位不同，前面各位相同，這兩個特點保證了所得的霍夫曼碼一定是最佳碼。對信源的N次擴展信源同樣可以采用霍夫曼編碼方法，因為霍夫曼碼是最佳碼，所以編碼后單個信源符號所編得的平均碼長隨N的增加很快接近于極限值——信源的熵。費諾碼不一定是最佳碼，但有時也可獲得最佳的編碼效果。費諾碼也是統(tǒng)計匹配碼，但這種方法不一定能使短碼得到充分利用。用這種編碼方法得到碼字是即時碼。費諾編碼方法同樣適合于m元編碼，只需每次分成m組即可。香農(nóng)―費諾―埃利斯碼不是最佳碼，但由它擴展而得到的算術(shù)編碼，在數(shù)據(jù)壓縮中得到了廣泛的應(yīng)用。2.4算

術(shù)

編

碼用霍夫曼編碼方法對小消息信源進行編碼，要實現(xiàn)統(tǒng)計匹配，提高編碼效率，必須擴展信源，即由一維擴展至多維進行霍夫曼編碼時，才能使平均碼長接近信源的熵,二元序列用二元碼編碼,等于沒有編碼,也無壓縮而言,且編碼效率也不高。例如，設(shè)二元序列中兩個符號概率分別為

p（a）＝0.7,p(b)＝0.3,其信源熵為平均碼長:編碼效率:要想提高二元信源的編碼效率，可以用合并信源符號的辦法擴展符號集，若進行二次擴展,即取2個相鄰符號作為新符號編霍夫曼碼。二次擴展的一種霍夫曼碼如表2―4所示。

表2―4二元信源二次擴展平均碼長：編碼效率:

表2―5二元信源三次擴展若進行三次擴展,即取3個相鄰符號作為新符號編霍夫曼碼。三次擴展的一種霍夫曼碼如表2―5所示。三次擴展的編碼效率η＝96.9%?？梢?合并的信源符號越多，編碼效率越高，但擴展階次越高，系統(tǒng)延時越長、存儲量越大、設(shè)備也越復(fù)雜，合并的符號數(shù)達到一定值時，再增加符號數(shù)所提高的效率將不顯著，所以工程上只能在效率與經(jīng)濟性之間作合理的選擇。另外,算術(shù)編碼就比較適合二元信源，這種方法主要是對信源序列進行編碼,并且可達到很好的壓縮效果。

2.4.1積累概率的遞推公式設(shè)信源：定義信源符號的積累概率：（2―38）由（2―38）式可知：F（uk）∈［0，1)由（2―38）式得:F（u1）＝0，F(xiàn)（u2）＝p（u1），

F（u3）＝p（u1）＋p（u2），…且p（ui）＝F（ui＋1）－F（ui）因為F（ui）和F（ui＋1）都是小于1的正數(shù)，因此可用［0，1）區(qū)間的兩個點來表示，p（ui）就是這兩點間小區(qū)間的長度。不同的符號對應(yīng)不同的小區(qū)間，這些小區(qū)間互不重疊，小區(qū)間內(nèi)的任意的一個點可作為該符號的碼字，且此編碼為即時碼。下面給出信源序列的積累概率的遞推公式，其證明可見相關(guān)的參考文獻。設(shè)獨立信源序列：S=s1s2…sk，…,sn∈{u1,u2,…,um},k＝1，2，…，n則信源序列的積累概率的遞推公式：F(Sur)=F(S)+p(S)F(ur)p(Sur)=p(S)p(ur)式中：F（Sur）——

信源序列S添加一個新的信源符號ur后所得到的新序列Sur的積累概率；（2―39）p（S）——信源序列S的概率；F（ur）——信源符號ur的積累概率；p（Sur）——信源序列S添加一個新的信源符號ur后所得到的新序列Sur的概率；p（ur）——信源符號ur的概率。公式（2―39）對于有相關(guān)性的序列同樣適用，只是需要將公式中的單符號概率改成條件概率。信源序列的積累概率F（S）與信源符號的積累概率一樣，可用［0，1）區(qū)間內(nèi)的一個點來表示，因此積累概率F（S）將區(qū)間［0，1）分成許多不同的小區(qū)間，它們互不重疊，序列S的概率p（S）就是兩點間小區(qū)間的長度。小區(qū)間內(nèi)的一個點可用來表示序列的概率，這就是算術(shù)編碼的基本思想。2.4.2算術(shù)編碼原理由前面的討論可知，信源符號的積累概率將區(qū)間［0，1）分成許多互不重疊的小區(qū)間，每個信源符號對應(yīng)一個不同的小區(qū)間。每個小區(qū)間的長度等于這個信源符號的概率，在此小區(qū)間內(nèi)取一點，該點的取值可作為這個信源符號的碼字。這個原理同樣適用于信源序列。把信源序列的積累概率映射到［0，1）區(qū)間上，使每個序列對應(yīng)該區(qū)間內(nèi)的一個點，這些點把區(qū)間［0，1)分成許多不同的小區(qū)間，這些小區(qū)間的長度等于對應(yīng)序列的概率，在小區(qū)間內(nèi)取一個浮點小數(shù)，使其長度與該序列的概率相匹配，因而達到高效編碼的目的。

算術(shù)編碼的主要任務(wù)是計算信源序列對應(yīng)的小區(qū)間。下面先給出小區(qū)間劃分的遞推計算公式,然后舉例說明如何劃分小區(qū)間。設(shè)小區(qū)間左、右端點的值分別用low和high表示，用range表示小區(qū)間的長度，則小區(qū)間左、右端點的遞推公式：low(Sur)=low(S)+range(S)×low(ur)high(Srr)=low(S)+range(S)×high(ur)（2―40）式中：low（Sur）——

信源序列S添加一個新符號ur后所得到的新序列Sur對應(yīng)區(qū)間的左端點值；high（Sur）——

信源序列S添加一個新信源符號ur后所得到的新序列Sur對應(yīng)區(qū)間的右端點值；low（S）——信源序列S對應(yīng)區(qū)間的左端點值；range（S）——信源序列S對應(yīng)區(qū)間的寬度值；low（ur）——信源符號ur對應(yīng)區(qū)間的左端點值；high（ur）——信源符號ur對應(yīng)區(qū)間的右端點值。使用公式（2―40）計算小區(qū)間端點值的步驟：(1)給出信源符號對應(yīng)的區(qū)間；(2)初始時設(shè)S＝（代表空集），low（）＝0，high（）＝1，range（）＝1；(3)輸入信源序列的一個符號ur，根據(jù)公式（2―40）計算序列Sur的左右端點值。依次下去，直至全部信源序列對應(yīng)的區(qū)間被確定為止?！纠?―10】

設(shè)信源求信源序列S=abda對應(yīng)的小區(qū)間。各個信源符號對應(yīng)的小區(qū)間如表2―6所示。表2―6例2―10信源符號對應(yīng)區(qū)間端點值不同的信源符號分別對應(yīng)不同的小區(qū)間,哪個符號被設(shè)在哪個區(qū)段并不重要,也就是說不需要各符號按概率順序排列,只要編碼和譯碼都以同樣的方式進行就可以。信源序列S=abda對應(yīng)的小區(qū)間的左、右端點的值如表2―7所示。表2―7例2―10信源序列對應(yīng)區(qū)間的端點值表2―7信源序列abda對應(yīng)區(qū)間的端點值的計算：設(shè)low（）＝0，high（）＝1，range（）＝1；輸入信源序列的第1個符號a：

low（a）＝low（）＋range（）×low（a）＝0＋1×0＝0.000high（a）＝low（）＋range（）×high（a）＝0＋1×0.5＝0.500輸入信源序列的第2個符號b：

low（ab）＝low（a）＋range（a）×low（b）＝0.00＋0.5×0.5＝0.250high（ab）＝low（a）＋range（a）×high（b）＝0.00＋0.5×0.75＝0.375輸入信源序列的第3個符號d：

low（abd）＝low（ab）＋range（ab）×low（d）＝0.25＋0.875×0.125＝0.359375high（abd）＝low（ab）＋range（ab）×high（d）＝0.25＋0.125×1＝0.375輸入信源序列的第4個符號a：

low（abda）＝low（abd）＋range（abd）×low（a）＝0.359375high（abda）＝low（abd）＋range（abd）×high（a）＝0.3671875信源序列S=abda對應(yīng)區(qū)間的劃分如圖2―13所示。圖2―13例2―10信源序列對應(yīng)區(qū)間的劃分不同的信源序列分別對應(yīng)不同的互不重疊的小區(qū)間,取小區(qū)間內(nèi)的一個點作為對應(yīng)序列的編碼,此碼是即時碼。根據(jù)上述分析，可取0.359375作為信源序列S=abda的編碼。譯碼是編碼的逆過程，就是根據(jù)接收到的碼字翻譯出對應(yīng)的信源序列。

譯碼步驟：(1)判斷碼字落在哪個符號區(qū)間，翻譯出1個符號；(2)將碼字減去剛翻譯出的符號的左端點值；(3)用剛翻譯出的符號對應(yīng)的區(qū)間的長度去除步驟2的結(jié)果，判斷此值落在哪個符號區(qū)間，翻譯出一個新符號；(4)重復(fù)步驟(2)、(3)直至全部信源序列被翻譯完為止。下面以碼字0.359375為例,說明譯碼過程。碼字0.359375落在［0，0.5）之間,即0.359375∈［0，0.5），于是翻譯出第1個符號為a；用符號a對應(yīng)區(qū)間的長度0.5去除碼字與符號a的左端點值的差得0.71875,即(0.359375－0)/０.5＝0.71875∈［0.5,0.75］,則翻譯出第2個符號為b；用符號b對應(yīng)區(qū)間的長度0.25去除碼字0.71875與符號b的左端點值的差得0.875,于是翻譯出第3個符號為d；用符號d對應(yīng)區(qū)間的長度0.125去除碼字0.875與符號d的左端點值的差得0,碼字0落在［0，0.5）之間,即0∈［0,0.5),于是翻譯出第4個