1、第5章 信源編碼技術5.1 最佳變長編碼最佳變長編碼回顧：1、根據信源編碼理論，將能夠荷載一定信息量，且碼字的平均長度最短，可分離的變長碼字集合稱為最佳變長碼。2、最佳變長碼編碼的基本原則是：概率大的信源符號分配短的碼字，而概率小的信源符號分配長碼字，從而使得平均碼長最短。具有代表性變長編碼方法有：香農碼，費諾碼和哈夫曼碼等。 5.1.1 香農碼香農碼香農碼的根據：離散無記憶信源的自信息量設離散無記憶信源所對應的概率空間為1212()()()( )rraaaXp ap ap ap x對應碼字的長度Li應該滿足下列關系 ()()1iiiI xlI xi這樣就可以保證對于每個信源符號而言，碼字長度

2、是最佳的 。符號自信息量香農碼編碼方法香農碼編碼方法 (1)將信源消息符號按其出現的概率大小依次排列為12nppp(2)確定每個信源符號的碼長，同時保證碼長為滿足下列不等式的整數( )( ) 1iiilbp allbp a (3)為了編成唯一可譯碼，計算第i個消息的累加概率 11()iikkPp a(4)將累加概率Pi表示為二進制形式；(5)取二進制數的小數點后li位作為該消息符號的二進制碼字。總結：1、由于每個信源符號碼長是根據信源符號的信息量選擇，從局部來看每個碼長的取值都是最佳的。所以從局部看，香農碼是最佳碼。 但是香農碼構造碼字時沒有綜合使用信源統計特性，所以碼長并非最短的。2、香農碼

3、編碼采用累計概率小數部分的二進制表示作為碼字，從而保證了碼字是唯一可譯碼的。 5.1.2費諾碼費諾碼費諾碼的基本思想：1、按照累加概率盡可能相等的原則對信源符號進行分組： 對于二元碼，則每次分為兩組; 對于d元碼，則每次分為d個組。 并且給不同的組分配一個不同的碼元符號。2、對其中的每組按照累計概率盡可能相等的原則再次進行分組，并指定碼元符號，直到不能再分類為止。3、然后將每個符號指定的碼元符號排列起來就得到相應的碼字。費諾二元碼的編碼步驟1、將源消息符號按概率大小排序：2、將依次排列的信源符號分為兩大組，使每組的概率和盡可能相等，且每組賦與二進制碼元“0”和“1”。3、將每一大組的信源符號再

4、分為兩組，使每組的概率和盡可能相等，且每組賦與二進制碼元“0”和“1”。4、如此重復，直至每組只剩下一個符號。信源符號所對應的碼字即費諾碼。npppp321例5.2對例5.1的信源進行費諾編碼,，具體編碼過程參見表5.2 根據每個信源符號的碼長，得到每個符號的平均碼長為 71( )2.74iiiLp a l碼元/符號 721,aaa321,aaa7654,aaaa1a32,aa4a765,aaa2a3a5a76,aa6a7a010000011111000100111011011101111用樹碼表示的費諾碼編碼過程總結：1、費諾碼要比上述香農碼的平均碼長小，編碼效率高。 2、從上面的例子可以看

5、出，p(a4)p(a2)，而碼長L4p(a2),那么當n1n2時，平均常常最短。假如n1 n1 p(a1)+n2 p(a2)所以，定理的第部分成立。關于含義：二元Huffman碼不可能出現單分支。對信源且假定對aK-1和aK的碼字最后一位分別指定0、1，然后合并，產生輔助符號ak-1,做一輔助集排序后KKpppaaaX.2121Kppp.21121121.KKpppaaaX21.Kpppak-1 ak-1 ak01對剩下的符號重復合并最小概率符號，分配碼元0、1，到最后對兩個符號重復上述操作，編碼完成。定理定理2 2 編碼對輔助集最佳，對原始集也最佳。（平編碼對輔助集最佳，對原始集也最佳。（平

6、均碼長最短）均碼長最短）)()()1)(111111211KKKKkKkkKKKkKkkkKkkppnppnpnppnppnn原始集平均碼長輔助集平均碼長合并一次二元碼的哈夫曼編碼步驟二元碼的哈夫曼編碼步驟(1)將信源消息符號按其出現的概率大小依次排列為 (2)取兩個概率最小的兩個信源符號分別分配碼元0和1，并將這兩個概率相加作為一個新符號的概率，與未分配的二進符號的符號一起重新進行概率排序。(3)對重排后的兩個概率最小符號重復步驟（2）的 過程。(4)不斷繼續上述過程，直到最后兩個符號配以0和1 為止。(5)從最后一級開始，反向搜索參與編碼的符號，得 到各個信源符號所對應的碼元序列，即相應的

7、碼 字。12nppp例5.3 對例5.1的信源符號進行哈夫曼編碼，給出編碼過程，每個信源符號的碼字，碼長，求平均碼長、編碼效率。7654321aaaaaaa01. 010. 015. 017. 018. 019. 020. 0信源符號 概率0.110.150.170.180.190.200.260.200.190.180.170.350.260.200.190.390.6100000111111010 211 2000 3001 3010 30110 40111 4碼字 碼長li0.350.260.391.0哈夫曼編碼過程平均碼長編碼效率符號比特 /72. 2)(71iiilapL96. 07

8、2. 261. 2)(LXH關于哈夫曼編碼的討論1、每次對信源縮減時，賦予信源最后兩個概率最小的符號，分配碼元0和1是可以任意的，即大概率符號或者合并后的符號集合可以分配碼元0也可以是1，這種選擇任意性可以得到不同的哈夫曼碼，但不會影響碼字的長度。2、對信源進行縮減時，如果兩個概率最小的符號合并后的概率與其它信源符號的概率相同, 應當放在上面，以便減少更多符號分配更長碼的可能。 例例5.4 設有離散無記憶信源的概率空間為123450.40.20.20.10.1Xaaaaap方法1方法2合并后的概率盡量往上根據兩種方法的編碼結果，計算兩種哈夫曼碼的平均碼長，相等，即 71( ) =2.2iiiL

9、p a l碼元碼元/符號符號 編碼效率也相等，都為( )=0.965H XL兩種碼的質量不完全相同，用碼方差衡量，即 2221()()()rliiiiElLp alL211.36l220.16l， 由于方法2的碼方差比方法1的碼方差小許多，所以方法2編碼質量好。哈夫曼碼的主要特點1、哈夫曼碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；2、縮減信源的兩個碼字的最后一位總是不同，可以保證構造的碼字為即時碼。3、哈夫曼碼的效率是相當高的，既可以使用單個信源符號編碼，也可以對信源序列編碼。4、要得到更高的編碼效率，可以使用較長的序列進行編碼。算術編碼適用于JPEG2

10、000,H.263等圖像壓縮標準。特點：1、隨著序列的輸入，就可對序列進行編碼2、平均符號碼長 滿足3、需要知道信源符號的概率是對shanno-Fanno-Elias編碼的改進。NXHLXH1)()(L（最佳編碼）累計分布函數的定義設信源輸出累計分布函數定義為算術編碼是累計函數的二進制表示加截短。0)(,.,21kkapaaaA0)()()(111aFapaFKiiK算術編碼的定義算術編碼是計算序列的累計分布，用累計分布值表示序列，所以稱為算術編碼。例如，對輸出的二元序列 01110進行編碼，將0,1)區間分為25=32個區段，每個序列對應一個區段，這個區段的每個數值可用來表示這個序列，一般用

11、區段的最左邊的值來表示序列。算術編碼對于長為n的符號序列序列個數共有 個(若每個符號可取2個值，比如0,1)分別是對應概率序列k的累計分布函數),.,(21nXXXn2nXXXXk221,.,.,)(),.(),.(),(221nXpXpXpXpk)(kXF累計分布函數的計算)()()()()()()(apupaupaFupuFauFu遞推公式a：已輸入序列：當前輸入符號算術編碼將0,1)分割成小區間，如長為n的二元序列，分為2n個區間，用區間F(u),F(u)+p(u)）表示序列u,實際取F(u)。將F(u)截短，截斷長度為每個區間的寬度等于序列的概率。)(1logupl序列u的自信息量)

12、0.00(0u) 1.11(2nu算術碼的截短規則假如累計函數表示為只要第L位后面的小數不為0，就要向第L位進位，進位后得數值C。. 0)(121LLLccccuF例5.7 離散無記憶信源X的概率空間為信源輸出符號序列 ，描述算術編碼過程。解：首先計算條件累計概率令 ，然后編碼。81814121)(4321aaaaxpX2132aaaa875. 0125. 025. 05 . 075. 025. 05 . 05 . 003213213121pppPppPpPP1,000AC)(F)(p（1）對第一個符號 進行編碼，得到（2）對第二個符號 進行編碼，得到（3）對第三個符號 進行編碼，得到（4）對

13、四個符號 進行編碼，得到21ax 32ax13ax24ax 25.05.02012001pAAPACC31231126875. 075. 0*25. 05 . 0pAAPACC012625. 05 . 0*03125. 06875. 00*03125. 06875. 01231223pAAPACC00390625. 025. 0*015625. 06953125. 05 . 0*015625. 06875. 02342334pAAPACC)()(22aFaF)()(22apap)(32aaF)(32aap)(132aaaF)(132aaap)(2132aaaaF)(2132aaaap將 用 位

14、二進制表示將小數點后8位作為碼字輸出，得編碼圖4C8)(4Alb10110010. 04C10110010W算術碼譯碼2a193125.05 .0693125.0去掉累計概率P2，3a1a2a)75. 0 , 5 . 05 . 0) 2/ 1/(25. 025. 0025. 0) 5 . 0 , 025. 0) 8/1/(03125. 003125. 075. 078125. 0)75. 0 , 5 . 06953125. 0)10110010. 04BC)875. 0 ,75. 078125. 0) 4/ 1/(1953125. 0碼字,得符號放大到0,1),去掉累計概率P3，去掉累計概率P

15、1，放大到0,1),放大到0,1),得符號,得符號,得符號算術編碼的特點1、能夠任意擴展序列長度，而又不重復構造碼表，然后再進行編碼，算術編碼能夠實現這樣的編碼要求。2、平均符號碼長滿足并且唯一可譯，因此最佳。NXHLXH1)()(5.2 編碼的實現編碼的實現 上面介紹了幾種變長編碼方法，相對于等長編碼，變長碼可以有效提高編碼效率。即使采用長度較短的擴展信源進行編碼，也能夠取得好的編碼效果，這是因為變長碼利用了信源統計冗余指導編碼的結果。 實際上，上述的幾種變長編碼只是產生編碼使用的碼表，并不是真正意義上的編碼實現。 信源編碼目的是為了更有效地傳輸信息，即提高通信系統的有效性。為了實現信息傳輸

16、，信源編碼產生的碼流傳輸到信宿之前應當首先進行譯碼，以便按照先后順序再現或者重現信源發送的消息符號。 對于譯碼器而言，必須知道信源編碼使用的碼表和每個碼字對應的長度等相關信息，才能夠實現正確譯碼，以便重建信源發送的消息符號序列。信源變長碼編碼原理框圖 具體步驟如下：u分析給定信源統計特性，得到信源統計規律。對于離散無記憶信源，得到各個符號的概率分布；對于記憶信源，則得到序列的聯合概率分布。 u根據統計特性，碼表產生器進行編碼，得到每個信源符號或者符號序列對應的碼字和碼長，即產生碼表。對于離散無記憶信源，每個符號都對應一個碼字并有一個碼長；而對于記憶信源，每個序列對應一個碼字和碼長。u 將序列符

17、號、序列長度、碼字及碼長等信息按照約定規則經過信道傳輸給譯碼器，譯碼器才能夠根據這些信息進行正確譯碼。u信源編碼器根據碼表產生器產生的碼表，對給定信源輸出符號序列按照先后順序進行編碼，產生碼流（碼字序列），并經過信道將碼流傳輸給譯碼器。u信源譯碼器根據接收到的序列符號、序列長度、碼字和碼長，對接收到的碼流進行譯碼，再現或者重建信源發送的消息。 實際應用中，信源編碼使用的碼表是根據一類信源的統計特性事先產生的，通過對大量同類信源的分布特性進行分析，在此基礎上根據統計得到的分布特性產生碼表。 對于編碼、譯碼器而言，輔助信息是編譯碼雙方約定的，這些輔助信息不需要再經過信道傳輸，這樣編碼器不需要分析信

18、源統計特性，也無需產生和傳輸碼表，從而減輕了編碼復雜度 采用算法約定碼表對給定信源進行編碼，這就意味著編碼建立碼表對應的概率統計特性與給定信源的概率統計特性并不相同，這樣就可能會導致編碼效率下降。下面對實際信源編碼進行分析。不失一般性，首先討論離散無記憶信源情況。假設碼表產生使用的編碼概率空間（也稱為碼表概率空間）為 1212()()()( )rraaaZq aq aq aq z 每個消息符號對應碼字的長度為 li. 對于給定的離散無記憶信源，實際的概率空間為 1212()()()( )rraaaXp ap ap ap x 如果采用碼表概率空間編碼，那么信源編碼的實際平均碼長 1()riiiL

19、p al 只有當兩種統計特性相近時，采用約定碼表進行編碼是一種有效的編碼方法。 反之，如果兩種信源統計模型相差甚遠，則實際編碼的平均碼長與理論值相差甚遠，此時編碼冗余度就會增加，編碼效率下降。此外，信源編碼的模型與實際的信源模型是否相符，也是影響編碼效率的因素之一。如果實際信源模型與編碼采用的模型不一致，實際編碼的效率也會下降，比如，如果有記憶信源的記憶長度與實際給定信源的長度不一樣，則編碼效率就會下降。但是在實際應用中，首先需要考慮的是系統編碼復雜度，如果實際模型特別復雜，難以實現；而如果采用相對較簡單的模型也能夠取得好的效果，則就可以簡化系統模型，得到有意義的結果。 盡管上述討論是針對平穩

20、離散信源進行的無失真編碼，但是得到的結論可以推廣到非平穩信源，包括馬爾可夫信源等。此外，該結論也適合限失真編碼，當統計特性不相符時，限失真編碼的信息率失真曲線會向右邊移動，在給定碼率的情況下，編碼產生的失真會增加。 由于信源輸出符號長度是有限的，而且許多信源是非平穩性、關聯性長度也各有差異，直接對數據進行編碼并取得好的編碼效果十分困難。為了減少這些因素的影響，得到簡單的信源模型和統計規律，信源編碼大多在變換域進行，而且實際信源編碼大多采用混合編碼算法以提高編碼效率。5.3 編碼方法簡介編碼方法簡介 前面闡述了無失真編碼使用的變長編碼方法，共同點在于都是采用組碼對信源進行編碼。對于信源符號數量較

21、少的無記憶信源編碼而言，組碼是一種簡單有效的編碼方法，此時可以直接傳輸碼表，當信源輸出的長度足夠大時，碼表的附加信息可以不加考慮。為了提高編碼效率，應當對信源進行擴展，使用序列進行編碼，而隨著序列長度的增加，序列種類也就增加，系統編碼復雜度也相應增加。而且使用擴展信源進行編碼，效率的提高也是有限的，對記憶信源更是如此。 在實際應用中，信源類型眾多，統計特性各不相同，特別是大多數信源并不是離散無記憶的、許多信源甚至是非平穩的，而且信源輸出的長度也是有限的，所以使用的編碼方法需要根據信源的具體特點而設計或者選擇。 在信源編碼理論的指導下，先后出現了許多性能優良的編碼方法，這里簡單介紹常用編碼算法的

22、基本原理。5.3.1 游程編碼游程編碼 游程編碼是經常使用的編碼方法之一，當信源游程編碼是經常使用的編碼方法之一，當信源出現連續相同符號，或者連續出現的符號在允出現連續相同符號，或者連續出現的符號在允許失真范圍內時，游程編碼是一種有效的描述許失真范圍內時，游程編碼是一種有效的描述方法。方法。 游程編碼是利用先后符號之間的關聯性進行編游程編碼是利用先后符號之間的關聯性進行編碼，從而提高編碼效率。碼，從而提高編碼效率。 游程編碼實際上是一種特殊的序列編碼方式，利用了符號（或者是數據）之間的相關性進行編碼，從而減少了數據描述長度，提高了編碼效率。 但是一般情況下，并不單獨使用游程編碼對數據進行壓縮，

23、總是將其作為整體編碼算法中的一種編碼單元加以使用。 游程編碼算法在圖像壓縮中得到廣泛應用，連續色調靜態圖像壓縮標準JPEG-LS中就采用了這種游程編碼算法，以提高數據壓縮效率。 游程編碼有二進制和非二進制之分，取決于具體編碼要求。對于二進制編碼，就是統計連續0或者1的個數。由于其特殊性，游程編碼可以不輸出再現符號，數據長度的交替就是符號0和1之間的交替，這樣只需要約定或者在開始時給出再現符號即可。 二進制游程編碼在信源編碼中得到廣泛應用，但是經常使用的是上述算法的改進算法。 如果信源輸出的二進制符號中，符號0的數量很多，而且連續出現的概率也很大，游程編碼算法就可以簡化。 比如，首先約定二進制序

24、列的長度N，如果連續個二進制符號都為0，則輸出0；否則輸出1，并對序列符號進一步處理。 許多實際應用中取N=4，下面以此為例介紹游程編碼算法。5.3.2 算術編碼算術編碼 從信源編碼角度來看，非常希望設計一種有效編碼算法對信源符號進行擴展，從而構成盡可能長的序列。 盡管哈夫曼編碼是一種有效的編碼算法，但并不滿足這種要求，因為它采用自下而上的編碼方法，要求計算特定長度的所有信源序列的概率，并且構造完整的碼表。理想編碼方法是：能夠任意擴展序列長度，而又不重復構造碼表，然后再進行編碼，算術編碼能夠實現這樣的編碼要求。 與變長編碼算法一樣，算術編碼是以信源的概率分布作為編碼的依據。 其基本思想是： 綜

25、合上述，算術編碼過程如下：5.4 變換編碼變換編碼 在許多情況下，信源輸出符號之間具有很強的相關性，如果按照前面介紹的哈夫曼、算術編碼等編碼算法來實現高效數據壓縮，需要使用擴展信源進行編碼，因此需要知道序列之間的聯合概率分布。 當信源符號數量較多，編碼算法已經比較復雜，如果采用較長的序列進行編碼，會進一步增加編碼系統的復雜度。 為了提高編碼效率，同時降低編碼復雜度，可以對信源輸出的數據進行變換，以去除數據之間的相關性，即將數據之間的相關冗余變換為系數之間的統計冗余，由于變換后的系數相關性減弱，可以使用簡單編碼算法實現高效率的數據壓縮。 原則上講，正交變換可以保持熵的不變性，所以，如果變換后的系數是整型的，不會損失任何信息。 但是一般情況下，變換后的系數是浮點的，這就需要對系數進行量化，得到整型系數，然后再進行編碼。量化過程可能會造成信息損失，而且系數量化涉及到信息率失真函數的輸出符號取值問題，是信息率失真函數研究內容之一，這里不進行討論。 總之，變換的目的是為了去除信源輸出數據之間的相關性，或者說是將數據之間的相關冗余映射為系數之間的統計冗余，從而降低系統編碼復雜度，提高編碼效率。 5.4.1 變換基本原理變換基本原理 設時間函數f(t)在觀測時間內，滿足下列條件 20|( ) |Tftd t 設有一完備正交規一化函數系( )it，即滿足00( )