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

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

M={mi},mi∈S,i=0..N-1符號(hào)表

S={sk}，k=0..K-1符號(hào)sk出現(xiàn)的概率為pk，k=0..K-1符號(hào)sk的信息量為h(sk)=-log2(pk)信息熵理論符號(hào)出現(xiàn)的概率越小，所包含的信息量越大。經(jīng)過理論分析和實(shí)踐檢驗(yàn)，證明概率的倒數(shù)的對(duì)數(shù)是最符合概率和信息量之間關(guān)系的（2.26，9.58）信息源的信息量是構(gòu)成它的所有符號(hào)的信息量的和，即?(M)=h(m0)+…+h(mN-1)信息熵理論信息源的熵是構(gòu)成它的所有符號(hào)的平均信息量H(M)=(h(m0)+…+h(mN-1))/N=Σ(-pklog(pk))當(dāng)所有符號(hào)出現(xiàn)的概率相同時(shí)，信息源的熵最大當(dāng)對(duì)數(shù)以2為底時(shí)，?(M)是編碼信息源所需的最小位數(shù)，而H(M)是每個(gè)符號(hào)的平均位數(shù)信息熵理論M={AAAAAAAAAAAAAAABBBBBBBCCCCCCDDDDDDEEEEE}huffman編碼Shannon-Fano算法根據(jù)出現(xiàn)概率從大到小將符號(hào)排成一列將符號(hào)列分成上下兩部分，使兩部分的概率之和盡量接近上半部分標(biāo)0，下半部分標(biāo)1對(duì)所分的兩部分重復(fù)上述步驟，直到所有分組都只包含一個(gè)符號(hào)huffman編碼huffman算法尋找概率最小的兩個(gè)符號(hào)將概率最小的兩個(gè)符號(hào)連接成一個(gè)新符號(hào)，新符號(hào)的概率為原來的兩個(gè)符號(hào)的概率之和用新符號(hào)替換原來的兩個(gè)符號(hào)重復(fù)上述步驟，直到符號(hào)集中只剩下一個(gè)符號(hào)哈夫曼編碼過程演示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碼的局限只適用于有限符號(hào)集需要傳送或保存碼表指數(shù)哥倫布碼的優(yōu)點(diǎn)可以對(duì)無限符號(hào)集編碼不需要傳送或保存碼表指數(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)的，只有概率分布合適的時(shí)候是0階指數(shù)哥倫布碼總共用了109位1階指數(shù)哥倫布碼總共用了112位需要根據(jù)符號(hào)的概率分布選擇合適的階數(shù)算數(shù)編碼的由來Huffman碼和指數(shù)哥倫布碼的碼字必須是整數(shù)個(gè)bit，這就造成了大多數(shù)情況下huffman碼無法達(dá)到理論極限，甚至距離理論極限很遠(yuǎn)。例如，如果一個(gè)符號(hào)的概率是1/3，則該符號(hào)的編碼位數(shù)最優(yōu)是1.6左右，而huffman碼卻只能為其設(shè)計(jì)1位或2位的碼字。當(dāng)一個(gè)符號(hào)的概率特別高時(shí)，例如大于0.9，則最優(yōu)碼長是0.15位，而huffman碼只能是1位，比最優(yōu)碼長長6倍當(dāng)符號(hào)集中只有兩個(gè)符號(hào)時(shí)（例如二值圖像），huffman碼幾乎失去作用。解決這個(gè)問題的方法是將若干個(gè)相連的符號(hào)打包，從而產(chǎn)生一個(gè)較大的符號(hào)集，然后再應(yīng)用huffman編碼。算數(shù)編碼的基本思想一個(gè)由服從已知概率分布的符號(hào)集中的符號(hào)組成的符號(hào)串（假設(shè)長度為N）實(shí)際上是一個(gè)事件，這個(gè)事件發(fā)生的概率可以計(jì)算出來。假設(shè)所有長度為N的事件共有K個(gè)，它們的概率之和為1。把這些事件按照某種規(guī)則排成一列，在[0，1）上為每個(gè)事件分配一個(gè)區(qū)間[Lk,Hk），區(qū)間長度等于第k個(gè)事件的概率，那么得到一個(gè)[0，1）的分割用一個(gè)落入某區(qū)間的值，就可以指示該區(qū)間對(duì)應(yīng)的事件發(fā)生了，這就是算術(shù)編碼的基本思想算數(shù)編碼的編碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..KI(m)是符號(hào)m在符號(hào)集中的索引Low=0;High=1;range=High–Low;for(n=0;n<N;n++)//有N個(gè)符號(hào)需要編碼{High=Low+C[I(mn)+1]*range;Low=Low+C[I(mn)]*range;range=High–Low;}尋找一個(gè)值v，使得Low<=v且v+d<=High且用二進(jìn)制表示時(shí)v的有效位數(shù)最少。其中d是v的最低有效位表示的值。例如v為8位時(shí)d就是1/256算數(shù)編碼的解碼算法pi是第i個(gè)符號(hào)的概率，i=0..K-1C[0]=0,C[k]=p0+..+pk-1,k=1..K{b0,b1,…}是待解碼bit串D[i]=C[i];//動(dòng)態(tài)區(qū)間For(n=0;n<N;n++)//已知有N個(gè)符號(hào)需要解碼{

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

解碼得到符號(hào)集中索引為k的符號(hào)

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