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

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

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ù)是最符合概率和信息量之間關(guān)系的（2.26，9.58）信息源的信息量是構(gòu)成它的所有符號的信息量的和，即?(M)=h(m0)+…+h(mN-1)信息熵理論信息源的熵是構(gòu)成它的所有符號的平均信息量H(M)=(h(m0)+…+h(mN-1))/N=Σ(-pklog(pk))當(dāng)所有符號出現(xiàn)的概率相同時，信息源的熵最大當(dāng)對數(shù)以2為底時，?(M)是編碼信息源所需的最小位數(shù)，而H(M)是每個符號的平均位數(shù)信息熵理論M={AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE}huffman編碼Shannon-Fano算法根據(jù)出現(xiàn)概率從大到小將符號排成一列將符號列分成上下兩部分，使兩部分的概率之和盡量接近上半部分標0，下半部分標1對所分的兩部分重復(fù)上述步驟，直到所有分組都只包含一個符號huffman編碼huffman算法尋找概率最小的兩個符號將概率最小的兩個符號連接成一個新符號，新符號的概率為原來的兩個符號的概率之和用新符號替換原來的兩個符號重復(fù)上述步驟，直到符號集中只剩下一個符號哈夫曼編碼過程演示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ù)碼字結(jié)構(gòu)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碼卻只能為其設(shè)計1位或2位的碼字。當(dāng)一個符號的概率特別高時，例如大于0.9，則最優(yōu)碼長是0.15位，而huffman碼只能是1位，比最優(yōu)碼長長6倍當(dāng)符號集中只有兩個符號時（例如二值圖像），huffman碼幾乎失去作用。解決這個問題的方法是將若干個相連的符號打包，從而產(chǎn)生一個較大的符號集，然后再應(yīng)用huffman編碼。算數(shù)編碼的基本思想一個由服從已知概率分布的符號集中的符號組成的符號串（假設(shè)長度為N）實際上是一個事件，這個事件發(fā)生的概率可以計算出來。假設(shè)所有長度為N的事件共有K個，它們的概率之和為1。把這些事件按照某種規(guī)則排成一列，在[0，1）上為每個事件分配一個區(qū)間[Lk,Hk），區(qū)間長度等于第k個事件的概率，那么得到一個[0，1）的分割用一個落入某區(qū)間的值，就可以指示該區(qū)間對應(yīng)的事件發(fā)生了，這就是算術(shù)編碼的基本思想算數(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ù)編碼的終止碼流的終止因為算術(shù)編碼器輸出的比特串是作為一個很長的碼流的一部分，為了不受后續(xù)bit的影響，必須要求low<=vandv+d<=high解碼過程的終止已知要解碼的符號的個數(shù)在符號集中增加結(jié)束符號EOB算數(shù)編碼的區(qū)間放大浮點數(shù)的精度是有限的，當(dāng)待編碼的符號串很長時，會出現(xiàn)range過小的情況解決的方法是每編碼一個符號都對區(qū)間進行放大解碼過程也進行同樣的放大，以保證編解碼所得的區(qū)間一致算數(shù)編碼的整數(shù)實現(xiàn)浮點數(shù)運算復(fù)雜，為了降低復(fù)雜度，發(fā)明了用定點運算實現(xiàn)的算術(shù)編碼器和解碼器定點的算術(shù)編碼器和解碼器一定包含區(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)的概率基于上下文的熵編碼可以有效的提高編碼效率，具體提高多少和符號的相關(guān)性有關(guān)基于上下文的熵編碼可以和huffman、指數(shù)哥倫布、算術(shù)編碼等結(jié)合使用自適應(yīng)熵編碼在事先不知道符號的概率分布的情況下，或者不愿意使用固定的碼表和概率表的時候，可以使用自適應(yīng)熵編碼技術(shù)自適應(yīng)熵編碼就是一邊編碼一邊統(tǒng)計，根據(jù)統(tǒng)計結(jié)果動態(tài)生成概率表和變長碼表自適應(yīng)熵編碼可以和huffmann、指數(shù)哥倫布、算術(shù)編碼等結(jié)合自適應(yīng)熵編碼和基于上下文的熵編