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

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

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

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

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

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

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

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

(2―7)互信息量可取正值也可取負值，如果互信息量I（x；y）取負值，說明在未收到消息y以前對消息x是否出現的猜測難疑程度較小。但由于噪聲的存在，接收到消息y后，反而使接收者對消息x是否出現的猜測難疑程度增加了。也就是收到消息y后對x出現的不確定性反而增加，所以獲得的信息量為負值。因為p（xy）＝p（x）p（y|x）＝p（y）p（x|y）這表明一對消息可以互相提供相等的信息量。所以稱I（x；y）為x與y之間的互信息量。平均互信息量I（X；Y）是互信息量I（x；y）的統計平均值，所以平均互信息量I（X；Y）永遠不會取負值。最差情況是I（X；Y）＝0，說明收到Y后不能獲得任何關于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中某一個消息（或符號）出現所必須提供的信息量，而H（X|Y）是當接收到Y時給出的關于X的不確定性。由式H（X|Y）＝H（X）－I（X；Y）可知，當收到Y時使X的不確定性減小了I（X；Y），這意味著接收到Y后，所獲得的關于X的信息量是I（X；Y）。由H（X）＝I（X；Y）＋H（X|Y）可知，X的信息熵等于接收到的信息量I（X；Y）加上損失掉的信息量H（X|Y）。因為條件熵H（X|Y）是由于信道上存在干擾和噪聲而損失掉的平均信息量，也叫損失熵。

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

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

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

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

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

定理2―1

（等長信源編碼定理）

一個熵為

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

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

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

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

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

Pe——差錯率。

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

【例2―1】

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

u2

u3

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

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

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

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

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

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

定理2―3

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

定理2―4

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【例2―3】

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

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

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

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

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

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

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

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

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

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

(2―37)【例2―8】

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

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

術

編

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

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

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

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

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

F（u3）＝p（u1）＋p（u2），…且p（ui）＝F（ui＋1）－F（ui）因為F（ui）和F（ui＋1）都是小于1的正數，因此可用［0，1）區間的兩個點來表示，p（ui）就是這兩點間小區間的長度。不同的符號對應不同的小區間，這些小區間互不重疊，小區間內的任意的一個點可作為該符號的碼字，且此編碼為即時碼。下面給出信源序列的積累概率的遞推公式，其證明可見相關的參考文獻。設獨立信源序列：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）對于有相關性的序列同樣適用，只是需要將公式中的單符號概率改成條件概率。信源序列的積累概率F（S）與信源符號的積累概率一樣，可用［0，1）區間內的一個點來表示，因此積累概率F（S）將區間［0，1）分成許多不同的小區間，它們互不重疊，序列S的概率p（S）就是兩點間小區間的長度。小區間內的一個點可用來表示序列的概率，這就是算術編碼的基本思想。2.4.2算術編碼原理由前面的討論可知，信源符號的積累概率將區間［0，1）分成許多互不重疊的小區間，每個信源符號對應一個不同的小區間。每個小區間的長度等于這個信源符號的概率，在此小區間內取一點，該點的取值可作為這個信源符號的碼字。這個原理同樣適用于信源序列。把信源序列的積累概率映射到［0，1）區間上，使每個序列對應該區間內的一個點，這些點把區間［0，1)分成許多不同的小區間，這些小區間的長度等于對應序列的概率，在小區間內取一個浮點小數，使其長度與該序列的概率相匹配，因而達到高效編碼的目的。

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

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

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

設信源求信源序列S=abda對應的小區間。各個信源符號對應的小區間如表2―6所示。表2―6例2―10信源符號對應區間端點值不同的信源符號分別對應不同的小區間,哪個符號被設在哪個區段并不重要,也就是說不需要各符號按概率順序排列,只要編碼和譯碼都以同樣的方式進行就可以。信源序列S=abda對應的小區間的左、右端點的值如表2―7所示。表2―7例2―10信源序列對應區間的端點值表2―7信源序列abda對應區間的端點值的計算：設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對應區間的劃分如圖2―13所示。圖2―13例2―10信源序列對應區間的劃分不同的信源序列分別對應不同的互不重疊的小區間,取小區間內的一個點作為對應序列的編碼,此碼是即時碼。根據上述分析，可取0.359375作為信源序列S=abda的編碼。譯碼是編碼的逆過程，就是根據接收到的碼字翻譯出對應的信源序列。

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