多媒體編碼與通信-熵編碼

多媒體編碼與通信趙海武上海大學通信學院networkmultimedia@126.com111111第二章熵編碼技術熵編碼概述信息熵理論Huffman編碼指數(shù)哥倫布編碼算術編碼基于上下文的熵編碼自適應熵編碼其他無損編碼方法熵編碼概述熵編碼是針對統(tǒng)計冗余的壓縮編碼方法熵編碼的理論基礎是shannon的信息熵理論，所以被叫做熵編碼熵編碼是無損編碼熵編碼是壓縮編碼中最重要的一種編碼方法，是各種編解碼方案中都要采用的編碼方法信息熵理論假設無記憶信息源

M={mi},mi∈S,i=0..N-1符號表

S={sk}，k=0..K-1符號sk出現(xiàn)的概率為pk，k=0..K-1符號sk的信息量為h(sk)=-log2(pk)信息熵理論符號出現(xiàn)的概率越小，所包含的信息量越大。經(jīng)過理論分析和實踐檢驗，證明概率的倒數(shù)的對數(shù)是最符合概率和信息量之間關系的（2.26，9.58）信息源的信息量是構成它的所有符號的信息量的和，即?(M)=h(m0)+…+h(mN-1)信息熵理論信息源的熵是構成它的所有符號的平均信息量H(M)=(h(m0)+…+h(mN-1))/N=Σ(-pklog(pk))當所有符號出現(xiàn)的概率相同時，信息源的熵最大當對數(shù)以2為底時，?(M)是編碼信息源所需的最小位數(shù)，而H(M)是每個符號的平均位數(shù)信息熵理論M={AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE}huffman編碼Shannon-Fano算法根據(jù)出現(xiàn)概率從大到小將符號排成一列將符號列分成上下兩部分，使兩部分的概率之和盡量接近上半部分標0，下半部分標1對所分的兩部分重復上述步驟，直到所有分組都只包含一個符號huffman編碼huffman算法尋找概率最小的兩個符號將概率最小的兩個符號連接成一個新符號，新符號的概率為原來的兩個符號的概率之和用新符號替換原來的兩個符號重復上述步驟，直到符號集中只剩下一個符號哈夫曼編碼過程演示A1A2A3A4A5A6A70.03100.10100.23100.33100.44

1

00.56011編碼010011111010110011000huffman編碼ASCII碼(定長碼)39x8=312Shannon-Fano算法15x2+7x2+6x2+6x3+5x3=89huffmann算法15x1+7x3+6x3+6x3+5x3=87理論最小值85.25指數(shù)哥倫布碼Exponential-Golombcode=Exp-GolombcodeHuffmann碼的局限只適用于有限符號集需要傳送或保存碼表指數(shù)哥倫布碼的優(yōu)點可以對無限符號集編碼不需要傳送或保存碼表指數(shù)哥倫布碼階數(shù)碼字結構CodeNum取值范圍k=01001x01～2001x1x03～60001x2x1x07～14............k=11x00～101x1x02～5001x2x1x06～130001x3x2x1x014～29............k=21x1x00～301x2x1x04～11001x3x2x1x012～270001x4x3x2x1x028～59............指數(shù)哥倫布碼指數(shù)哥倫布碼的局限通常不是最優(yōu)的，只有概率分布合適的時候是0階指數(shù)哥倫布碼總共用了109位1階指數(shù)哥倫布碼總共用了112位需要根據(jù)符號的概率分布選擇合適的階數(shù)算數(shù)編碼的由來Huffman碼和指數(shù)哥倫布碼的碼字必須是整數(shù)個bit，這就造成了大多數(shù)情況下huffman碼無法達到理論極限，甚至距離理論極限很遠。例如，如果一個符號的概率是1/3，則該符號的編碼位數(shù)最優(yōu)是1.6左右，而huffman碼卻只能為其設計1位或2位的碼字。當一個符號的概率特別高時，例如大于0.9，則最優(yōu)碼長是0.15位，而huffman碼只能是1位，比最優(yōu)碼長長6倍當符號集中只有兩個符號時（例如二值圖像），huffman碼幾乎失去作用。解決這個問題的方法是將若干個相連的符號打包，從而產(chǎn)生一個較大的符號集，然后再應用huffman編碼。算數(shù)編碼的基本思想一個由服從已知概率分布的符號集中的符號組成的符號串（假設長度為N）實際上是一個事件，這個事件發(fā)生的概率可以計算出來。假設所有長度為N的事件共有K個，它們的概率之和為1。把這些事件按照某種規(guī)則排成一列，在[0，1）上為每個事件分配一個區(qū)間[Lk,Hk），區(qū)間長度等于第k個事件的概率，那么得到一個[0，1）的分割用一個落入某區(qū)間的值，就可以指示該區(qū)間對應的事件發(fā)生了，這就是算術編碼的基本思想算數(shù)編碼的編碼算法pi是第i個符號的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..KI(m)是符號m在符號集中的索引Low=0;High=1;range=High–Low;for(n=0;n<N;n++)//有N個符號需要編碼{High=Low+C[I(mn)+1]*range;Low=Low+C[I(mn)]*range;range=High–Low;}尋找一個值v，使得Low<=v且v+d<=High且用二進制表示時v的有效位數(shù)最少。其中d是v的最低有效位表示的值。例如v為8位時d就是1/256算數(shù)編碼的解碼算法pi是第i個符號的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..K{b0,b1,…}是待解碼bit串D[i]=C[i];//動態(tài)區(qū)間For(n=0;n<N;n++)//已知有N個符號需要解碼{

讀入碼流，直到[v,v+d)落入某個區(qū)間[D[k],D[k+1])

解碼得到符號集中索引為k的符號

range=D[k+1]–D[k];D[0]=D[k];D[i]=D[0]+C[i]*range;}其中d是v的最低有效位表示的值。算數(shù)編碼的終止碼流的終止因為算術編碼器輸出的比特串是作為一個很長的碼流的一部分，為了不受后續(xù)bit的影響，必須要求low<=vandv+d<=high解碼過程的終止已知要解碼的符號的個數(shù)在符號集中增加結束符號EOB算數(shù)編碼的區(qū)間放大浮點數(shù)的精度是有限的，當待編碼的符號串很長時，會出現(xiàn)range過小的情況解決的方法是每編碼一個符號都對區(qū)間進行放大解碼過程也進行同樣的放大，以保證編解碼所得的區(qū)間一致算數(shù)編碼的整數(shù)實現(xiàn)浮點數(shù)運算復雜，為了降低復雜度，發(fā)明了用定點運算實現(xiàn)的算術編碼器和解碼器定點的算術編碼器和解碼器一定包含區(qū)間放大算數(shù)編碼舉例符號集{A,B,C}，概率{0.8,0.1,0.1}，分割{0,0.8,0.9,1}符號串AAAAAAAABC符號十進制low十進制high二進制low二進制high輸出bitA00.801100110011001100A00.6401010001111010111A00.51201000001100010010A00.409600110100011011011A00.3276800101001111100010A00.26214400100001100011011A00.209715200011010110101111A00.1677721600010101011110011B0.1342177280.15099499400100010010111000010011010100111C0150994994001001100011100100100110101001110010011001基于上下文的熵編碼考慮了符號的條件概率，即根據(jù)已經(jīng)出現(xiàn)的符號調(diào)整下一個符號出現(xiàn)的概率基于上下文的熵編碼可以有效的提高編碼效率，具體提高多少和符號的相關性有關基于上下文的熵編碼可以和huffman、指數(shù)哥倫布、算術編碼等結合使用自適應熵編碼在事先不知道符號的概率分布的情況下，或者不愿意使用固定的碼表和概率表的時候，可以使用自適應熵編碼技術自適應熵編碼就是一邊編碼一邊統(tǒng)計，根據(jù)統(tǒng)計結果動態(tài)生成概率表和變長碼表自適應熵編碼可以和huffmann、指數(shù)哥倫布、算術編碼等結合自適應熵編碼和基于上下文的熵編