信息論與編碼第5章信源編碼技術(shù)

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

(1)將信源消息符號按其出現(xiàn)的概率大小依次排列為(2)確定每個信源符號的碼長，同時保證碼長為滿足下列不等式的整數(shù)(3)為了編成唯一可譯碼，計算第i個消息的累加概率

(4)將累加概率Pi表示為二進制形式；(5)取二進制數(shù)的小數(shù)點后li位作為該消息符號的二進制碼字?？偨Y(jié)：1、由于每個信源符號碼長是根據(jù)信源符號的信息量選擇，從局部來看每個碼長的取值都是最佳的。所以從局部看，香農(nóng)碼是最佳碼。但是香農(nóng)碼構(gòu)造碼字時沒有綜合使用信源統(tǒng)計特性，所以碼長并非最短的。2、香農(nóng)碼編碼采用累計概率小數(shù)部分的二進制表示作為碼字，從而保證了碼字是唯一可譯碼的。

5.1.2費諾碼費諾碼的基本思想：1、按照累加概率盡可能相等的原則對信源符號進行分組：對于二元碼，則每次分為兩組;對于d元碼，則每次分為d個組。并且給不同的組分配一個不同的碼元符號。2、對其中的每組按照累計概率盡可能相等的原則再次進行分組，并指定碼元符號，直到不能再分類為止。3、然后將每個符號指定的碼元符號排列起來就得到相應的碼字。費諾二元碼的編碼步驟

1、將源消息符號按概率大小排序：2、將依次排列的信源符號分為兩大組，使每組的概率和盡可能相等，且每組賦與二進制碼元“0”和“1”。3、將每一大組的信源符號再分為兩組，使每組的概率和盡可能相等，且每組賦與二進制碼元“0”和“1”。4、如此重復，直至每組只剩下一個符號。信源符號所對應的碼字即費諾碼。例5.2對例5.1的信源進行費諾編碼,，具體編碼過程參見表5.2根據(jù)每個信源符號的碼長，得到每個符號的平均碼長為碼元/符號010000011111000100111011011101111用樹碼表示的費諾碼編碼過程總結(jié)：1、費諾碼要比上述香農(nóng)碼的平均碼長小，編碼效率高。2、從上面的例子可以看出，p(a4)<p(a2)，而碼長L4<L2，從統(tǒng)計角度來看，平均碼長一定不是最短的;

如果將兩個符號對應的碼字互換，這樣編碼得到的平均碼長肯定小于原來的平均碼長。3、費諾碼的平均碼長滿足編碼效率為費諾碼的最佳性1、保證每個集合概率和近似相等，保證d個碼元近似等概率，每個碼字承載的信息量最大，碼長近似最短。2、是次最佳的編碼方法，只在當信源符號概率滿足：時達最佳。012012012012a1a2a3a4a5a6a7a8a9p(a1)=3-1p(a2)=p(a3)=p(a4)=3-2p(a7)=p(a8)=p(a9)=3-3滿足Kraft不等式取1，此時費諾碼最佳。信源符號概率5.1.3哈夫曼碼基本思想：1、概率大的符號分配短碼字，而概率小的信源符號分配長碼字2、首先為小概率符號分配碼元3、分配碼元后的符號進行概率合并4、然后按照大小順序重排概率，并對概率小的符號或者符號集合分配碼元，直到概率合并結(jié)束為止。5、然后逆向搜索參與概率合并時分配的碼元符號，形成對應的碼字。Huffman碼的最佳性最佳性：所有可能的編碼方法中，平均碼長最短。定理1對于給定的信源，有最佳唯一可譯二元碼，其最小概率的兩個碼字Ck-1和Ck的長度最長并且相等①，它們之間僅最后一位碼元的取值不同②（一個為0、一個為1）。關(guān)于含義①：對于符號a1,a2，碼長分別為n1,n2如果p(a1)>p(a2),那么當n1<n2時，平均常常最短。假如n1<n2，則有n2p(a1)+n1p(a2)>n1p(a1)+n2p(a2)所以，定理的第①部分成立。關(guān)于含義②：二元Huffman碼不可能出現(xiàn)單分支。對信源且假定對aK-1和aK的碼字最后一位分別指定0、1，然后合并，產(chǎn)生輔助符號a’k-1,做一輔助集排序后ak-1ak-1‘

ak01對剩下的符號重復合并最小概率符號，分配碼元0、1，到最后對兩個符號重復上述操作，編碼完成。定理2編碼對輔助集最佳，對原始集也最佳。（平均碼長最短）原始集平均碼長輔助集平均碼長合并一次二元碼的哈夫曼編碼步驟

(1)將信源消息符號按其出現(xiàn)的概率大小依次排列為(2)取兩個概率最小的兩個信源符號分別分配碼元0和1，并將這兩個概率相加作為一個新符號的概率，與未分配的二進符號的符號一起重新進行概率排序。(3)對重排后的兩個概率最小符號重復步驟（2）的過程。(4)不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。(5)從最后一級開始，反向搜索參與編碼的符號，得到各個信源符號所對應的碼元序列，即相應的碼字。例5.3對例5.1的信源符號進行哈夫曼編碼，給出編碼過程，每個信源符號的碼字，碼長，求平均碼長、編碼效率。信源符號概率0.110.150.170.180.190.200.260.200.190.180.170.350.260.200.190.390.610000011111101021120003001301030110401114碼字碼長li0.350.260.391.0哈夫曼編碼過程平均碼長編碼效率關(guān)于哈夫曼編碼的討論1、每次對信源縮減時，賦予信源最后兩個概率最小的符號，分配碼元0和1是可以任意的，即大概率符號或者合并后的符號集合可以分配碼元0也可以是1，這種選擇任意性可以得到不同的哈夫曼碼，但不會影響碼字的長度。2、對信源進行縮減時，如果兩個概率最小的符號合并后的概率與其它信源符號的概率相同,應當放在上面，以便減少更多符號分配更長碼的可能。例5.4設有離散無記憶信源的概率空間為方法1方法2合并后的概率盡量往上根據(jù)兩種方法的編碼結(jié)果，計算兩種哈夫曼碼的平均碼長，相等，即

碼元/符號編碼效率也相等，都為兩種碼的質(zhì)量不完全相同，用碼方差衡量，即

，由于方法2的碼方差比方法1的碼方差小許多，所以方法2編碼質(zhì)量好。哈夫曼碼的主要特點1、哈夫曼碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；2、縮減信源的兩個碼字的最后一位總是不同，可以保證構(gòu)造的碼字為即時碼。3、哈夫曼碼的效率是相當高的，既可以使用單個信源符號編碼，也可以對信源序列編碼。4、要得到更高的編碼效率，可以使用較長的序列進行編碼。算術(shù)編碼適用于JPEG2000,H.263等圖像壓縮標準。特點：1、隨著序列的輸入，就可對序列進行編碼2、平均符號碼長滿足3、需要知道信源符號的概率是對shanno-Fanno-Elias編碼的改進。（最佳編碼）累計分布函數(shù)的定義設信源輸出累計分布函數(shù)定義為算術(shù)編碼是累計函數(shù)的二進制表示加截短。算術(shù)編碼的定義算術(shù)編碼是計算序列的累計分布，用累計分布值表示序列，所以稱為算術(shù)編碼。例如，對輸出的二元序列01110進行編碼，將[0,1)區(qū)間分為25=32個區(qū)段，每個序列對應一個區(qū)段，這個區(qū)段的每個數(shù)值可用來表示這個序列，一般用區(qū)段的最左邊的值來表示序列。算術(shù)編碼對于長為n的符號序列序列個數(shù)共有個(若每個符號可取2個值，比如0,1)分別是對應概率序列k的累計分布函數(shù)累計分布函數(shù)的計算遞推公式：已輸入序列：當前輸入符號算術(shù)編碼將[0,1)分割成小區(qū)間，如長為n的二元序列，分為2n個區(qū)間，用區(qū)間[F(u),F(u)+p(u)）表示序列u,實際取F(u)。將F(u)截短，截斷長度為每個區(qū)間的寬度等于序列的概率。序列u的自信息量算術(shù)碼的截短規(guī)則假如累計函數(shù)表示為只要第L位后面的小數(shù)不為0，就要向第L位進位，進位后得數(shù)值C。例5.7離散無記憶信源X的概率空間為信源輸出符號序列，描述算術(shù)編碼過程。解：首先計算條件累計概率令，然后編碼。（1）對第一個符號進行編碼，得到（2）對第二個符號進行編碼，得到（3）對第三個符號進行編碼，得到（4）對四個符號進行編碼，得到將用位二進制表示將小數(shù)點后8位作為碼字輸出，得編碼圖算術(shù)碼譯碼去掉累計概率P2，碼字,得符號放大到[0,1),去掉累計概率P3，去掉累計概率P1，放大到[0,1),放大到[0,1),,得符號,得符號,得符號算術(shù)編碼的特點1、能夠任意擴展序列長度，而又不重復構(gòu)造碼表，然后再進行編碼，算術(shù)編碼能夠?qū)崿F(xiàn)這樣的編碼要求。2、平均符號碼長滿足并且唯一可譯，因此最佳。5.2編碼的實現(xiàn)上面介紹了幾種變長編碼方法，相對于等長編碼，變長碼可以有效提高編碼效率。即使采用長度較短的擴展信源進行編碼，也能夠取得好的編碼效果，這是因為變長碼利用了信源統(tǒng)計冗余指導編碼的結(jié)果。實際上，上述的幾種變長編碼只是產(chǎn)生編碼使用的碼表，并不是真正意義上的編碼實現(xiàn)。信源編碼目的是為了更有效地傳輸信息，即提高通信系統(tǒng)的有效性。為了實現(xiàn)信息傳輸，信源編碼產(chǎn)生的碼流傳輸?shù)叫潘拗皯斒紫冗M行譯碼，以便按照先后順序再現(xiàn)或者重現(xiàn)信源發(fā)送的消息符號。對于譯碼器而言，必須知道信源編碼使用的碼表和每個碼字對應的長度等相關(guān)信息，才能夠?qū)崿F(xiàn)正確譯碼，以便重建信源發(fā)送的消息符號序列。信源變長碼編碼原理框圖具體步驟如下：分析給定信源統(tǒng)計特性，得到信源統(tǒng)計規(guī)律。對于離散無記憶信源，得到各個符號的概率分布；對于記憶信源，則得到序列的聯(lián)合概率分布。根據(jù)統(tǒng)計特性，碼表產(chǎn)生器進行編碼，得到每個信源符號或者符號序列對應的碼字和碼長，即產(chǎn)生碼表。對于離散無記憶信源，每個符號都對應一個碼字并有一個碼長；而對于記憶信源，每個序列對應一個碼字和碼長。

將序列符號、序列長度、碼字及碼長等信息按照約定規(guī)則經(jīng)過信道傳輸給譯碼器，譯碼器才能夠根據(jù)這些信息進行正確譯碼。信源編碼器根據(jù)碼表產(chǎn)生器產(chǎn)生的碼表，對給定信源輸出符號序列按照先后順序進行編碼，產(chǎn)生碼流（碼字序列），并經(jīng)過信道將碼流傳輸給譯碼器。信源譯碼器根據(jù)接收到的序列符號、序列長度、碼字和碼長，對接收到的碼流進行譯碼，再現(xiàn)或者重建信源發(fā)送的消息。實際應用中，信源編碼使用的碼表是根據(jù)一類信源的統(tǒng)計特性事先產(chǎn)生的，通過對大量同類信源的分布特性進行分析，在此基礎上根據(jù)統(tǒng)計得到的分布特性產(chǎn)生碼表。對于編碼、譯碼器而言，輔助信息是編譯碼雙方約定的，這些輔助信息不需要再經(jīng)過信道傳輸，這樣編碼器不需要分析信源統(tǒng)計特性，也無需產(chǎn)生和傳輸碼表，從而減輕了編碼復雜度采用算法約定碼表對給定信源進行編碼，這就意味著編碼建立碼表對應的概率統(tǒng)計特性與給定信源的概率統(tǒng)計特性并不相同，這樣就可能會導致編碼效率下降。下面對實際信源編碼進行分析。不失一般性，首先討論離散無記憶信源情況。假設碼表產(chǎn)生使用的編碼概率空間（也稱為碼表概率空間）為每個消息符號對應碼字的長度為li.對于給定的離散無記憶信源，實際的概率空間為如果采用碼表概率空間編碼，那么信源編碼的實際平均碼長只有當兩種統(tǒng)計特性相近時，采用約定碼表進行編碼是一種有效的編碼方法。反之，如果兩種信源統(tǒng)計模型相差甚遠，則實際編碼的平均碼長與理論值相差甚遠，此時編碼冗余度就會增加，編碼效率下降。此外，信源編碼的模型與實際的信源模型是否相符，也是影響編碼效率的因素之一。如果實際信源模型與編碼采用的模型不一致，實際編碼的效率也會下降，比如，如果有記憶信源的記憶長度與實際給定信源的長度不一樣，則編碼效率就會下降。但是在實際應用中，首先需要考慮的是系統(tǒng)編碼復雜度，如果實際模型特別復雜，難以實現(xiàn)；而如果采用相對較簡單的模型也能夠取得好的效果，則就可以簡化系統(tǒng)模型，得到有意義的結(jié)果。盡管上述討論是針對平穩(wěn)離散信源進行的無失真編碼，但是得到的結(jié)論可以推廣到非平穩(wěn)信源，包括馬爾可夫信源等。此外，該結(jié)論也適合限失真編碼，當統(tǒng)計特性不相符時，限失真編碼的信息率失真曲線會向右邊移動，在給定碼率的情況下，編碼產(chǎn)生的失真會增加。由于信源輸出符號長度是有限的，而且許多信源是非平穩(wěn)性、關(guān)聯(lián)性長度也各有差異，直接對數(shù)據(jù)進行編碼并取得好的編碼效果十分困難。為了減少這些因素的影響，得到簡單的信源模型和統(tǒng)計規(guī)律，信源編碼大多在變換域進行，而且實際信源編碼大多采用混合編碼算法以提高編碼效率。5.3編碼方法簡介前面闡述了無失真編碼使用的變長編碼方法，共同點在于都是采用組碼對信源進行編碼。對于信源符號數(shù)量較少的無記憶信源編碼而言，組碼是一種簡單有效的編碼方法，此時可以直接傳輸碼表，當信源輸出的長度足夠大時，碼表的附加信息可以不加考慮。為了提高編碼效率，應當對信源進行擴展，使用序列進行編碼，而隨著序列長度的增加，序列種類也就增加，系統(tǒng)編碼復雜度也相應增加。而且使用擴展信源進行編碼，效率的提高也是有限的，對記憶信源更是如此。在實際應用中，信源類型眾多，統(tǒng)計特性各不相同，特別是大多數(shù)信源并不是離散無記憶的、許多信源甚至是非平穩(wěn)的，而且信源輸出的長度也是有限的，所以使用的編碼方法需要根據(jù)信源的具體特點而設計或者選擇。在信源編碼理論的指導下，先后出現(xiàn)了許多性能優(yōu)良的編碼方法，這里簡單介紹常用編碼算法的基本原理。5.3.1游程編碼游程編碼是經(jīng)常使用的編碼方法之一，當信源出現(xiàn)連續(xù)相同符號，或者連續(xù)出現(xiàn)的符號在允許失真范圍內(nèi)時，游程編碼是一種有效的描述方法。游程編碼是利用先后符號之間的關(guān)聯(lián)性進行編碼，從而提高編碼效率。游程編碼實際上是一種特殊的序列編碼方式，利用了符號（或者是數(shù)據(jù)）之間的相關(guān)性進行編碼，從而減少了數(shù)據(jù)描述長度，提高了編碼效率。但是一般情況下，并不單獨使用游程編碼對數(shù)據(jù)進行壓縮，總是將其作為整體編碼算法中的一種編碼單元加以使用。游程編碼算法在圖像壓縮中得到廣泛應用，連續(xù)色調(diào)靜態(tài)圖像壓縮標準JPEG-LS中就采用了這種游程編碼算法，以提高數(shù)據(jù)壓縮效率。游程編碼有二進制和非二進制之分，取決于具體編碼要求。對于二進制編碼，就是統(tǒng)計連續(xù)0或者1的個數(shù)。由于其特殊性，游程編碼可以不輸出再現(xiàn)符號，數(shù)據(jù)長度的交替就是符號0和1之間的交替，這樣只需要約定或者在開始時給出再現(xiàn)符號即可。二進制游程編碼在信源編碼中得到廣泛應用，但是經(jīng)常使用的是上述算法的改進算法。如果信源輸出的二進制符號中，符號0的數(shù)量很多，而且連續(xù)出現(xiàn)的概率也很大，游程編碼算法就可以簡化。比如，首先約定二進制序列的長度N，如果連續(xù)個二進制符號都為0，則輸出0；否則輸出1，并對序列符號進一步處理。許多實際應用中取N=4，下面以此為例介紹游程編碼算法。5.3.2算術(shù)編碼從信源編碼角度來看，非常希望設計一種有效編碼算法對信源符號進行擴展，從而構(gòu)成盡可能長的序列。盡管哈夫曼編碼是一種有效的編碼算法，但并不滿足這種要求，因為它采用自下而上的編碼方法，要求計算特定長度的所有信源序列的概率，并且構(gòu)造完整的碼表。

理想編碼方法是：能夠任意擴展序列長度，而又不重復構(gòu)造碼表，然后再進行編碼，算術(shù)編碼能夠?qū)崿F(xiàn)這樣的編碼要求。與變長編碼算法一樣，算術(shù)編碼是以信源的概率分布作為編碼的依據(jù)。其基本思想是：綜合上述，算術(shù)編碼過程如下：5.4變換編碼

在許多情況下，信源輸出符號之間具有很強的相關(guān)性，如果按照前面介紹的哈夫曼、算術(shù)編碼等編碼算法來實現(xiàn)高效數(shù)據(jù)壓縮，需要使用擴展信源進行編碼，因此需要知道序列之間的聯(lián)合概率分布。當信源符號數(shù)量較多，編碼算法已經(jīng)比較復雜，如果采用較長的序列進行編碼，會進一步增加編碼系統(tǒng)的復雜度。為了提高編碼效率，同時降低編碼復雜度，可以對信源輸出的數(shù)據(jù)進行變換，