1、信源編碼徐偉業(yè)電子信息工程教研室25.2無失真信源編碼無失真信源編碼的研究內(nèi)容 若信源輸出符號序列的長度L1，即變換成由KL個符號組成的碼序列35.21無失真信源編碼變換的要求能夠無失真或無差錯地從Y恢復X，也就是能正確地進行反變換或譯碼傳送Y時所需要的信息率最小由于Yk可取m種可能值，即平均每個符號輸出的最大信息量為logm，KL長碼序列傳輸?shù)淖畲笮畔⒘繛镵Llogm。用該碼序列表示L長的信源序列,則送出一個信源符號所需要的信息率平均為45.2無失真信源編碼無失真信源編碼的研究內(nèi)容就是就是找到一種編碼方式使 最小那么：（1）最小信息率為多少時，才能得到無失真的譯碼？（2）若小于這個信息率是否

2、還能無失真地譯碼？55.2無失真信源編碼一、定長編碼若要實現(xiàn)無失真編碼，所編碼的碼必須是唯一可譯碼定長碼的每個碼字長度相等，所以只要定長碼是非奇異碼，則必為唯一可譯碼研究定長編碼時所需的碼長65.2失真信源編碼單符號信源X若對信源X進行定長編碼，則必須滿足n為信源符號數(shù)mK為用碼符號集，可編出的碼長為K的碼字個數(shù)m為碼元符號數(shù)K為定長碼的碼長例：4個信源符號的二元編碼75.2無失真信源編碼L次擴展信源XL如果將信源X的L次擴展信源進行定長編碼，即將長度為L的信源序列變換為長度為KL的碼符號序列。L長的信源序列數(shù)nLKL長的碼符號序列數(shù)mKL85.2失真信源編碼L次擴展信源XL滿足 條件的定長編

3、碼雖然可以保證無失真編碼，但是平均碼長較長，編碼效率偏低例：第二章p38頁，27個符號的定長二元編碼即傳輸一個英文符號至少需要5個二元符號95.2失真信源編碼L次擴展信源XL由第2章的計算結(jié)果可知，在考慮了符號出現(xiàn)的概率以及符號之間的相關(guān)性后，平均每個符號所提供的信息量約等于1.4bit，因此定長編碼后，每個長度為5的碼字只載荷約1.4bit的信息量由第3章可知，對于無噪無損的二元信道，信道容量為1bit/符號，即每個二元碼最大能載荷1bit的信息量每個長度為5的二元碼字最大能載荷5bit的信息量由此可以看出，上述的定長編碼的效率很低能否縮短定長編碼的碼長來提高傳輸效率？105.2無失真信源編

4、碼縮短碼長的方法在前面的討論中沒有考慮符號出現(xiàn)的概率以及符號之間的相關(guān)性。如果考慮到以上兩個因素，定長編碼中每個符號所需的平均碼長可以減少。例:考慮符號出現(xiàn)的概率設(shè)離散無記憶信源概率空間為115.2無失真信源編碼若不考慮符號的概率分布，二元定長編碼的碼長若考慮符號的概率分布，對L長的無記憶信源序列進行編碼，會出現(xiàn)小概率事件對小概率事件不進行編碼，擴展信源序列數(shù)小于nL，平均每個信源符號所需的碼長會減小。當然，這就會引入一定的誤差。但是，當L足夠長時，這種誤差概率可以任意小，即可做到幾乎無失真地編碼。 125.2無失真信源編碼:考慮符號之間的相關(guān)性設(shè)離散無記憶信源概率空間為符號間的依賴關(guān)系為其余

5、135.1無失真信源編碼縮短碼長的方法若不考慮符號之間的相關(guān)性，二元定長編碼的碼長若考慮符號之間的相關(guān)性，對此信源的二次擴展信源進行編碼。根據(jù)已知條件，除 不等于0外，其余145.2無失真信源編碼 因此，二次擴展信源X2的信源序列數(shù)由n2=16，縮減到4個此時對X2進行定長編碼，所需碼長KL=2,平均每個符號所需碼長K=KL/2=1由此可見，當考慮符號之間的依賴關(guān)系后，有些信源符號序列不會出現(xiàn)，這樣信源符號序列個數(shù)會減少，再進行編碼時，所需平均碼長就可以縮短 碼長的極限是多少？155.2無失真信源編碼定長編碼定理 由L個符號組成的、每個符號的熵為HL(X)的無記憶平穩(wěn)信源符號序列 ，可用KL個

6、符號 （每個符號有m種可能值）進行定長編碼。對任意 ，只要 則當L足夠大時，必可使譯碼差錯小于 ；反之，當 時，譯碼差錯一定是有限值，而當L足夠大時，譯碼幾乎必定出錯。 165.2無失真信源編碼定長編碼定理的說明(1)KL:信源L次擴展后，每個信源序列對應的碼元數(shù)K= KL/L:平均每個信源符號對應的碼元數(shù) ，表示KL/L的碼符號序列所能攜帶的最大信息量HL(X) ，表示信源序列中平均每個符號的熵，對于無記憶平穩(wěn)信源HL(X)=H(X)175.1無失真信源編碼定長編碼定理的說明(2)信源經(jīng)過定長編碼后，每個碼字攜帶的最大信息量大于信源序列中每個符號的熵， 則可以使傳輸幾乎無失真，當然條件是L足

7、夠大當 時，不可能構(gòu)成無失真的編碼，也就是不可能做一種編碼器，能使收端譯碼時差錯概率趨于零當 時，則為臨界狀態(tài)，可能無失真，也可能有失真185.2無失真信源編碼定長編碼定理的說明(3)適用范圍定長編碼定理是在離散平穩(wěn)無記憶信源的條件下得到證明的，但它同樣適用于平穩(wěn)有記憶信源，只是要求平穩(wěn)有記憶信源的極限熵 和極限方差 存在即可對于平穩(wěn)有記憶信源，定理中應改為極限熵195.2無失真信源編碼定長編碼定理的說明(4)比較表達式 和 可知，當信源具有等概分布時，兩式一致。一般情況下，信源符號并非等概分布，而且符號之間有很強的關(guān)聯(lián)性，故信源熵 或 將遠遠小于logn這時，在定長編碼中每個信源符號平均所需

8、的碼符號數(shù)將大大減少，從而提高編碼效率 205.2無失真信源編碼差錯概率與信源序列長度L的關(guān)系信源X的L次擴展信源XL，共有nL個樣本序列對 中的樣本不編碼，此時差錯概率為 中元素出現(xiàn)的概率215.2無失真信源編碼差錯概率與信源序列長度L的關(guān)系如果允許一定的差錯概率， 。所以， 中的樣本都應該是小概率事件。當L足夠大時，小概率事件的出現(xiàn)概率會更小，即差錯概率會更小式中 為自信息方差，為一正數(shù)。當 和 均為定值時，只要L足夠大，Pe可以小于任一正數(shù)。 225.2無失真信源編碼差錯概率與信源序列長度L的關(guān)系當信源序列長度L滿足 時，能達到差錯率要求 235.2無失真信源編碼相關(guān)概念編碼信息率：平均

9、每個碼字所能攜帶的最大信息量編碼效率 為了衡量編碼效果，定義編碼效率為編碼信息率大于信源的熵，才能實現(xiàn)無失真編碼245.2無失真信源編碼相關(guān)概念最佳編碼效率 由定長編碼定理可知最佳編碼效率由上式可知，若要譯碼差錯概率越小，編碼效率越高，則信源序列長度L必須越長。在實際情況下，要幾乎無失真的定長編碼，L需要大到難以實現(xiàn)的程度255.2無失真信源編碼例設(shè)離散無記憶信源概率空間為265.2無失真信源編碼對信源符號采用定長二元編碼，要求編碼效率為 90若取L1，則可算出2.55/0.9=2.83碼元/符號即每個符號用2.83個二元碼進行定長編碼，共有22.83=7.11種可能，按7種可能性計算，信源符

10、號中就有一種符號沒有對應的碼字，取概率最小的a8, 則Pe0.04 太大275.2無失真信源編碼 L取多大時，由此可見，在對編碼效率和譯碼錯誤概率的要求不是十分苛刻的情況下，就需要108個信源符號一起進行編碼，這對存儲和處理技術(shù)的要求太高，在實際應用中很難實現(xiàn)。285.2 無失真信源編碼 如果用3比特來對上述信源的8個符號進行定長二元編碼，L=1，此時可實現(xiàn)譯碼無差錯，但編碼效率只有2.55/3=85%。 因此，一般來說，當L有限時，高傳輸效率的定長碼往往要引入一定的失真和譯碼錯誤。解決的辦法是可以采用變長編碼，真正實現(xiàn)無失真。295.2 無失真信源編碼二、變長編碼定理在變長編碼中，碼長KL是

11、變化的問題：對同一信源，其即時碼或唯一可譯碼可以有許多種。究竟哪一種好呢？從高速傳輸信息的觀點來考慮，當然 希望選擇由短的碼符號組成的碼字，就是用碼長來作為選擇準則根據(jù)信源各個符號的統(tǒng)計特性，如概率大的符號用短碼，概率小的用較長的碼，使得編碼后平均碼長降低，從而提高編碼效率。（統(tǒng)計匹配）305.2 無失真信源編碼變長編碼定理平均碼長設(shè)信源編碼后的碼字為：碼長為：則這個碼的平均碼長為：315.2無失真信源編碼變長編碼定理碼率：平均每個碼元攜帶的信息量即編碼后的信息傳輸率為最佳碼：若有一個唯一可譯碼，它的平均碼長小于其他唯一可譯碼的長度，則稱此碼為緊致碼或最佳碼，無失真信源編碼的基本問題就是尋找最

12、佳碼325.2無失真信源編碼變長編碼定理設(shè)離散無記憶信源為其信源熵為H(X)，它的L次擴展信源為XL335.2無失真信源編碼變長編碼定理現(xiàn)用碼符號集Y=b1,b2, ,bm對XL進行編碼，則總可以找到一種編碼方法，構(gòu)成唯一可譯碼，使信源X中平均每個符號所需的平均碼長，滿足其中，表示離散無記憶L擴展信源XL中每個信源序列i所對應的平均碼長345.2無失真信源編碼變長編碼定理 表示離散無記憶信源X中平均每個信源符號所需的平均碼長 是每個信源符號所需的平均碼長，為了得到這個平均值，不是直接對單個信源符號進行編碼，而是對L長的信源序列進行編碼若從信道的角度看，當平均碼長達到極限值 時，編碼后信道的信息

13、傳輸率355.2無失真信源編碼變長編碼定理由此可見，這時信道的信息傳輸率等于無噪無損信道的信道容量C，信息傳輸效率最高。因此，無失真信源編碼的實質(zhì)是對信源進行適當?shù)淖儞Q，使變換后新的碼符號盡可能為等概分布，以使每個碼符號攜帶的信息量達到最大，從而使信道的信息傳輸率R達到信道容量C，實現(xiàn)信源與信道理想的統(tǒng)計匹配365.1無失真信源編碼相關(guān)概念編碼信息率：編碼效率碼的剩余度：編碼信息率大于信源的熵，才能實現(xiàn)無失真編碼375.2無失真信源編碼例設(shè)離散無記憶信源的概率空間為若用二元定長編碼(0，1)來構(gòu)造一個即時碼： 平均碼長 1二元碼符號/信源符號385.2無失真信源編碼編碼效率為：輸出的信息效率為

14、：395.2無失真信源編碼L=2的信源序列進行變長編碼（編碼方法后面介紹），其即時碼如下表aip(ai)即時碼a1a19/160a1a23/1610a2a13/16110a2a21/16111405.2無失真信源編碼二元碼符號/信源符號二元碼符號/2個信源符號415.2無失真信源編碼編碼效率為：輸出的信息效率為：425.2無失真信源編碼L3： R30.985比特/二元碼符號 L4： R40.991比特/二元碼符號 變長編碼，L不需要很大就可以達到相當高的編碼效率，而且可以實現(xiàn)無失真編碼435.2無失真信源編碼定長二元碼編碼，要求編碼效率達到96時，允許譯碼錯誤概率 445.2無失真信源編碼說明

15、：（）定長碼需要的信源序列長，使碼表很大，且總存在譯碼差錯。而用變長碼編碼時，L不需要很大就可達到相當高的編碼效率，而且可實現(xiàn)無失真編碼。（）隨著信源序列長度的增加，編碼的效率越來越接近于1。編碼后的傳輸率R也越來越接近于無噪無損二元對稱信道的信道容量，達到信源與信道的匹配。455.2無失真信源編碼最佳碼的定義凡是能載荷一定的信息量，且碼字的平均長度最短，可分離的變長碼的碼字集合都可稱為最佳碼最佳編碼思想將概率大的信息符號編以短的碼字，概率小的符號編以長的碼字，使得平均碼字長度最短最佳碼的編碼主要方法香農(nóng)（Shannon）、費諾（Fano）、哈夫曼（Huffman）編碼465.2無失真信源編碼

16、香農(nóng)編碼Shanon編碼算法是一種簡單的按概率編碼的方法，對于一個離散無記憶信源，如果其某一符號ai的先驗概率為p(ai)，則就取其碼長為475.2無失真信源編碼香農(nóng)編碼（1）將信源消息符號按其出現(xiàn)的概率大小依次排列（2）確定滿足下列不等式的整數(shù)碼長Ki485.2無失真信源編碼香農(nóng)編碼（3）為了編成唯一可譯碼，計算第i個消息的累加概率（4）將累加概率Pi變換成二進制數(shù)（乘2取整，順序排列）（5）取Pi二進數(shù)的小數(shù)點后Ki位即為該消息符號的二進制碼字495.2無失真信源編碼例 設(shè)信源共7個符號消息，其概率和累加概率如下表所示信源消息符號ai符號概率(ai)累加概率Pi-log p(ai)碼字長度

17、Ki碼字a10.2002.323000a20.190.22.393001a30.180.392.473011a40.170.572.563100a50.150.742.743101a60.100.893.3241110a70.010.996.6471111110505.2無失真信源編碼碼元/符號比特/碼元 515.2無失真信源編碼費諾編碼（1）將信源消息符號按其出現(xiàn)的概率大小依次排列（2）將依次排列的信源符號按概率值分為兩大組，使兩個組的概率之和近于相同，并對各組賦予一個二進制碼元“0”和“1”525.2無失真信源編碼費諾編碼（3）將每一大組的信源符號進一步再分成兩組，使劃分后的兩個組的概率之

18、和近于相同，并又賦予兩個組一個二進制符號“0”和“1”（4）如此重復，直至每個組只剩下一個信源符號為止（5）信源符號所對應的碼字即為費諾碼535.2無失真信源編碼消息符號ai各個消息概率 p(ai)第一次分組第二次分組第三次分組第四次分組二元碼字碼長Kia10.2000002a20.19100103a30.1810113a40.1710102a50.15101103a60.101011104a70.01111114545.2無失真信源編碼 碼元/符號 bit/符號 555.2無失真信源編碼費諾編碼的基本特點費諾編碼在構(gòu)造碼樹時，是從樹根開始到終端節(jié)點結(jié)束由于賦碼元時的任意性，因此編出的碼字不是

19、唯一的費諾編碼雖屬于概率匹配范疇，但并未嚴格遵守匹配規(guī)則，有時出現(xiàn)概率小的碼長反而小。因此平均碼長一般不會最小費諾碼比較適合于每次分組概率都很接近的信源。特別是對每次分組概率都相等的信源進行編碼時，可達到理想的編碼效率565.2無失真信源編碼20110.25a24111110.0625a841110010.0625a741101010.0625a6411000.0625a5310110.125a43100000.125a3200010.25a1碼長Ki二元碼字第四次分組第三次分組第二次分組第一次分組各個消息概率 p(ai)消息符號ai001575.2無失真信源編碼 碼元/符號 bit/符號 b

20、it/符號 585.2無失真信源編碼哈夫曼編碼（1）將信源消息符號按其出現(xiàn)的概率大小依次排列（2）取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊595.2無失真信源編碼哈夫曼編碼（3）對重排后的兩個概率最小符號重復步驟(2)的過程（4）不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止（5）從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字605.2無失真信源編碼哈夫曼編碼信源符號ai概率p(ai)碼字Wi碼長Kia10.20102a20.19112a30.180003a40.170013a50.15010

21、3a60.1001104a70.0101114615.2無失真信源編碼哈夫曼編碼0.20 0.20 0.26 0.35 0.39 0.61 1.00.19 0.19 0.20 0.26 0.35 0.390.18 0.18 0.19 0.20 0.260.17 0.17 0.18 0.190.15 0.15 0.170.10 0.110.01010101010101625.2無失真信源編碼 碼元/符號 bit/符號 哈夫曼編碼效率最高，費諾編碼效率次之，香農(nóng)編碼效率最低635.2無失真信源編碼哈夫曼編碼方法得到的碼并非唯一每次對信源縮減時，賦予信源最后兩個概率最小的符號，用0和1是可以任意的，

22、所以可以得到不同的哈夫曼碼，但不會影響碼字的長度645.2無失真信源編碼哈夫曼編碼方法得到的碼并非唯一對信源進行縮減時，兩個概率最小的符號合并后的概率與其它信源符號的概率相同時，這兩者在縮減信源中進行概率排序，其位置放置次序是可以任意的，故會得到不同的哈夫曼碼。此時將影響碼字的長度，一般將合并的概率放在上面，這樣可獲得較小的碼方差655.2無失真信源編碼哈夫曼編碼例 設(shè)有離散無記憶信源5.2無失真信源編碼0.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.2 0.10.4 0.4 0.4 0.6 1.0 0.2 0.2 0.4 0.40.2 0.2 0.20.1 0.20.10101010101010101675.2無失真信源編碼685.2無失真信源編碼信源符號ai概率p(ai)碼字Wi1碼長Ki1碼字Wi2碼長Ki2a10.411002a20.2012102a30.20003112a40.1001040103a50.1001140113695.2無失真信源編碼705.2無失真信源編碼哈夫曼編碼的特點哈夫曼編碼實際上構(gòu)造了一個碼樹，碼樹從端點開始構(gòu)造，直到樹根結(jié)束，因此編出的碼是非延長碼哈