第四章：算術(shù)編碼

第四章：算術(shù)編碼算術(shù)編碼：越來越流行（在很多標(biāo)準(zhǔn)中被采用）適合的場合：小字母表：如二進制信源概率分布不均衡建模與編碼分開內(nèi)容：算術(shù)編碼的基本思想一些性質(zhì)實現(xiàn)有限精度：區(qū)間縮放（浮點數(shù)/整數(shù)實現(xiàn)）計算復(fù)雜度：用移位代替乘法二進制編碼自適應(yīng)模型QM編碼器：自適應(yīng)二進制編碼回顧：Huffman編碼例1：信源的符號數(shù)目很少

0ab1a=0,b=1回顧：擴展的Huffman編碼例2：信源的符號的概率嚴(yán)重不對稱：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335

bits/symbolHuffman編碼：a 0b 11c 10l=1.05

bits/symbol冗余（Redundancy）=l-H=0.715bits/sym(213%!)問題：能做得更好嗎？10abc01回顧：擴展的Huffman編碼基本思想：考慮對兩個字母序列而不是單個字母編碼LetterProbabilityCodeaa0.90250ab0.0190111ac0.0285100ba0.01901101bb0.0004110011bc0.0006110001ca0.0285101cb0.0006110010cc0.0009110000l=1.222/2=0.611冗余=0.276bits/symbol（27%）回顧：擴展的Huffman編碼該思想還可以繼續(xù)擴展考慮長度為n的所有可能的mn序列(已做了32)理論上：考慮更長的序列能提高編碼性能實際上：字母表的指數(shù)增長將使得這不現(xiàn)實例如：對長度為3的ASCII序列：2563=224=16M需要對長度為n的所有序列產(chǎn)生碼本很多序列的概率可能為0分布嚴(yán)重不對稱是真正的大問題：A={a,b,c},P(a)=0.95,P(b)=0.02,P(c)=0.03H=0.335

bits/symboll1=1.05,l2=0.611,…當(dāng)n=8時編碼性能才變得可接受但此時|alphabet|=38=6561!!!算術(shù)編碼（ArithmeticCoding）算術(shù)編碼：從另一種角度對很長的信源符號序列進行有效編碼對整個序列信源符號串產(chǎn)生一個唯一的標(biāo)識（tag）直接對序列進行編碼（不是碼字的串聯(lián)）：非分組碼不用對該長度所有可能的序列編碼標(biāo)識是[0,1)之間的一個數(shù)（二進制小數(shù)，可作為序列的二進制編碼）概率復(fù)習(xí)隨機變量：將試驗的輸出映射到實數(shù)用數(shù)字代替符號X(ai)=i,其中ai

A(A={ai},i=1..n)給定信源的概率模型P概率密度函數(shù)（probabilitydensityfunction,pdf）累積密度函數(shù)（cumulativedensityfunction,cdf）產(chǎn)生標(biāo)識定義一一映射：ak

[FX(k-1),FX(k)],k=1..m,FX(0)=0[FX(k-1),FX(k)]區(qū)間內(nèi)的任何數(shù)字表示ak對2字母序列akaj編碼對ak，選擇[FX(k-1),FX(k)]然后將該區(qū)間按比例分割并選取第j個區(qū)間：將[0,1)分為m個區(qū)間：產(chǎn)生標(biāo)識：例考慮對a1a2a3編碼：A={a1,a2,a3},P={0.7,0.1,0.2)映射：a11,a22,a33cdf:FX(1)=0.7,FX(2)=0.8,FX(3)=1 .0映射成實數(shù)A={a1,a2,…,am}對公平擲骰子的例子：{1,2,3,4,5,6}詞典順序（Lexicographicorder）字符串的詞典順序：其中表示“在字母順序中，y在x的前面”n為序列的長度詞典順序：例考慮兩輪連續(xù)的骰子：輸出={11,12,…,16,21,22,…,26,…,61,62,…,66}注意：為了產(chǎn)生13的標(biāo)識，我們不必對產(chǎn)生其他標(biāo)識但是，為了產(chǎn)生長度為n的字符串的標(biāo)識，我們必須知道比其短的字符串的概率這與產(chǎn)生所有的碼字一樣繁重！應(yīng)該想辦法來避免此事區(qū)間構(gòu)造觀察包含某個標(biāo)識的區(qū)間與所有其他標(biāo)識的區(qū)間不相交基本思想遞歸：將序列的下/上界視為更短序列的界的函數(shù)上述骰子的例子：考慮序列：322

令u(n),l(n)為長度為n序列的上界和下界，則 u(1)=FX(3),l(1)=FX(2) u(2)=FX(2)(32),l(2)=FX(2)(31)區(qū)間構(gòu)造區(qū)間構(gòu)造產(chǎn)生標(biāo)識通常，對任意序列x=x1x2…xn只需知道信源的cdf，即信源的概率模型算術(shù)編碼：編碼和解碼過程都只涉及算術(shù)運算（加、減、乘、除）產(chǎn)生標(biāo)識：例考慮隨機變量X(ai)=i

對序列1321編碼：1131321321解碼標(biāo)識AlgorithmInitializel(0)=0,u(0)=1.Foreachi,i=1..nComputet*=(tag-l(k-1))/(u(k-1)-l(k-1)).Findthexk:FX(xk-1)t*FX(xk).Updateu(n),l(n)Ifdone--exit,otherwisegoto1.解碼：例AlgorithmInitializel(0)=0,u(0)=1.Computet*=(tag-l(k-1))/(u(k-1)-l(k-1)).Findthexk:FX(xk-1)t*FX(xk).Updateu(k),l(k)Ifdone--exit,otherwisegoto1.1131321321算術(shù)編碼的唯一性和效率上述產(chǎn)生的標(biāo)識可以唯一表示一個序列，這意味著該標(biāo)識的二進制表示為序列的唯一二進制編碼但二進制表示的精度可以是無限長：保證唯一性但不夠有效為了保證有效性，可以截斷二進制表示，但如何保證唯一性？答案：為了保證唯一性和有效性，需取小數(shù)點后l位數(shù)字作為信源序列的碼字，其中注意：P(x)為最后區(qū)間的寬度，也是該符號串的概率符合概率匹配原則：出現(xiàn)概率較大的符號取較短的碼字，而對出現(xiàn)概率較小的符號取較長的碼字算術(shù)編碼的唯一性和效率長度為n的序列的算術(shù)編碼的平均碼長為：算術(shù)編碼的效率高：當(dāng)信源符號序列很長，平均碼長接近信源的熵實現(xiàn)迄今為止已有能工作的編碼/解碼算法假設(shè)實數(shù)（無限精度）最終l(n)

和u(n)

將集中到一起我們需要對字符串增量式編碼觀測：當(dāng)區(qū)間變窄時[l(n),u(n)][0,0.5),或[l(n),u(n)][0.5,1),或l(n)[0,0.5),u(n)[0.5,1).先集中處理1.&2，稍后再討論3實現(xiàn)編碼器：一旦我們到達1.或2.，就可以忽略[0,1)的另一半還需要告知解碼器標(biāo)識所在的半?yún)^(qū)間：發(fā)送0/1比特用來指示下上界所在區(qū)間將標(biāo)識區(qū)間縮放到[0,1):E1:[0,0.5)=>[0,1); E1(x)=2xE2:[0.5,1)=>[0,1); E2(x)=2(x-0.5)注意：在縮放過程中我們丟失了最高位但這不成問題—我們已經(jīng)發(fā)送出去了解碼器根據(jù)0/1比特并相應(yīng)縮放與編碼器保持同步標(biāo)識產(chǎn)生：帶縮放的例子考慮隨機變量X(ai)=i

對序列1321編碼：Input:1321Output:

Input:-321Output:

1標(biāo)識產(chǎn)生：帶縮放的例子Input:--21Output:11Input:---1Output:110Input:---1Output:1100Input:---1Output:11000標(biāo)識產(chǎn)生：帶縮放的例子EOT:[l(n),u(n)]區(qū)間內(nèi)的任何一個數(shù)字在此選0.510=0.12Input:---1Output:110001Input:---1Output:110001Input:---1Output:110001Output:11000110…注意：0.1100011=2-1+2-2+2-6+2-7=0.7734375[0.7712,0.77408]增量式標(biāo)識解碼我們需要增量式解碼如：網(wǎng)絡(luò)傳輸問題如何開始？必須有足夠的信息，可以對第一個字符無歧義解碼接收到的比特數(shù)應(yīng)比最小標(biāo)識對應(yīng)的區(qū)間更小怎樣繼續(xù)？一旦有一個非歧義的開始，只要模擬編碼器即可如何結(jié)束？標(biāo)識解碼：例假設(shè)碼字長為6輸入：1100011000000.1100012=0.76562510第1位：1Output:1Input:110001100000Output:13Input:-10001100000(左移)Input:-10001100000(0.546875)Output:132Input:---001100000(左移)Input:--0001100000(左移)此時解碼最后一個符號標(biāo)識解碼：例Input:----01100000(左移)Input:-----1100000(左移)Input:-----100000

(左移)Input:-----100000Output:1321第三種情況：E3回憶三種情況[l(n),u(n)][0,0.5):E1:[0,0.5)=>[0,1);E1(x)=2x[l(n),u(n)][0.5,1):E2:[0.5,1)=>[0,1);E2(x)=2(x-0.5)l(n)[0,0.5),u(n)[0.5,1):E3(x)=???E3

縮放E3:[0.25,0.75)=>[0,1);E3(x)=2(x-0.25)編碼E1=0,E2=1,E3=???注意：

E3…E3E1=E1E2…E2

E3…E3E2=E2E1…E1

規(guī)則：記錄E3

連續(xù)的次數(shù)，并在輸出下一個E2/E1

之后發(fā)送該次數(shù)證明請見文獻：Witten,Radford,Neal,Cleary,“ArithmeticCodingforDataCompression”CommunicationsoftheACM,vol.30,no.6,pp.520-540,June1987.第三種情況：E3整數(shù)實現(xiàn)假設(shè)碼字長度為n，則ni=長度為TotalCount（TC）的序列中字符i出現(xiàn)的次數(shù)累積計數(shù)：CC

整數(shù)實現(xiàn)MSB(x)=MostSignificantBitofxLSB(x)=LeastSignificantBitofxSB(x,i)=ithSignificantBitofxMSB(x)=SB(x,1);LSB(x)=SB(x,m)E3(l,u)=(SB(l,2)==1&&SB(u,2)==0)l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

//lowerboundupdateu=l+(u-l+1)CC(x)/TC-1//upperboundupdatewhile(MSB(u)==MSB(l)ORE3(u,l))//MSB(u)=MSB(l)=0E1rescalingif(MSB(u)==MSB(l))//MSB(u)=MSB(l)=1E2rescalingsend(MSB(u))l=(l<<1)+0//shiftleft,setLSBto0u=(u<<1)+1//shiftleft,setLSBto1while(e3_count>0)send(!MSB(u))//encodeaccumulatedE3rescalingse3_count--endwhileendif

if(E3(u,l))//performE3rescaling&rememberl=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildone整數(shù)編碼器整數(shù)編碼器：例序列：1321Count{1,2,3}={40,1,9}TotalcountTC=50CumulativecountCC{0,1,2,3}={0,40,41,50}記?。簠^(qū)間的終點不會重疊n=?最小的[l(n),u(n)]=整個范圍內(nèi)的1/4，仍能區(qū)分0..TC的最小區(qū)間：=>28x?>50/1=>最小n=8(28=256)l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildone整數(shù)編碼器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:1321Output:

Input:-321Output:1

整數(shù)編碼器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:--21Output:110

e3_count=1整數(shù)編碼器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:---1Output:1100

Input:---1Output:11000

Input:---1Output:110001

整數(shù)編碼器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:---1Output:1100010

Input:---1e3_count=1整數(shù)編碼器：例l=00…0,u=11…1,e3_count=0repeatx=get_symboll=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))send(MSB(u))l=(l<<1)+0u=(u<<1)+1while(e3_count>0)send(!MSB(u))e3_count--endwhileendif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1complementMSB(u)andMSB(l)e3_count++endifendwhileuntildoneInput:---1Output:1100010結(jié)束通常，發(fā)送l(4):(00000000)2但是

e3_count=1，因此在發(fā)送l(4)的第一個‘0’后發(fā)送‘1’最后output:1100010010000000

Initializel,u,t

//t=firstnbitsrepeatk=0while(((t-l+1)TC-1)/(u-l+1)CC(k)

k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))//PerformE1/E2rescalingofl,u,tl=(l<<1)+0 //add0totherightoflu=(u<<1)+1//add1totherightofut=(t<<1)+next_bit

endif

if(E3(u,l))//PerformE3rescalingofl,u,tl=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

complementMSB(u),MSB(l),MSB(t)endifendwhileuntildone整數(shù)解碼器整數(shù)解碼器：例Initializel,u,t

repeatk=0while((t-l+1)CC(x-1)/TCCC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

endif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

complementMSB(u),MSB(l),MSB(t)endifendwhileuntildoneInput:1100010010000000

Output:1Output:13整數(shù)解碼器：例Input:1100010010000000

Input:1100010010000000

Input:1100010010000000

Initializel,u,t

repeatk=0while((t-l+1)CC(x-1)/TCCC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

endif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

complementMSB(u),MSB(l),MSB(t)endifendwhileuntildone整數(shù)解碼器：例Output:132結(jié)束已解碼接收到了預(yù)定數(shù)目的字符，或接收到EOTInitializel,u,t

repeatk=0while((t-l+1)CC(x-1)/TCCC(k)k++x=decode_symbol(k)l=l+(u-l+1)CC(x-1)/TC

u=l+(u-l+1)CC(x)/TC-1while(MSB(u)==MSB(l)ORE3(u,l))if(MSB(u)==MSB(l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

endif

if(E3(u,l))l=(l<<1)+0u=(u<<1)+1t=(t<<1)+next_bit

complementMSB(u),MSB(l),MSB(t)endifendwhileuntildoneOutput:1321算術(shù)編碼vs.Huffman編碼n=序列長度平均碼長：算術(shù)：擴展Huffman：觀察二者的積漸近性質(zhì)相同Huffman有一個微小的邊際擴展的Huffman要求巨大數(shù)量的存儲和編碼mn而算術(shù)編碼不用實際應(yīng)用中可以對算術(shù)編碼假設(shè)較大的長度n但Huffman不可我們期望算術(shù)編碼表現(xiàn)更好（除了當(dāng)概率為2的整數(shù)次冪的情況）算術(shù)編碼vs.Huffman編碼增益為字母表大小和分布的函數(shù)較大的字母表（通常）較適合Huffman不均衡的分布更適合算術(shù)編碼很容易將算術(shù)編碼擴展到多個編碼器QM編碼器很容易將算術(shù)編碼適應(yīng)到統(tǒng)計變化模型（自適應(yīng)模型、上下文模型）不必對樹重新排序可以將建模與編碼分開應(yīng)用：圖像壓縮ImageBits/pixelRatioArithmeticRatioHuffmanSena6.521.231.16Sensin7Earth4.671.711.67Omaha6.841.171.14ImageBits/pixelRatioArithmeticRatioHuffmanSena3.892.062.08Sensin4.561.751.73Earth3.922.042.04Omaha6.271.281.26自適應(yīng)算術(shù)編碼：對像素值自適應(yīng)算術(shù)編碼：對像素差分自適應(yīng)算術(shù)編碼統(tǒng)計編碼技術(shù)需要利用信源符號的概率，獲得這個概率的過程稱為建模。不同準(zhǔn)確度（通常也是不同復(fù)雜度）的模型會影響算術(shù)編碼的效率。建模的方式：靜態(tài)建模：在編碼過程中信源符號的概率不變。但一般來說事先知道精確的信源概率是很難的，而且是不切實際的。自適應(yīng)動態(tài)建模：信源符號的概率根據(jù)編碼時符號出現(xiàn)的頻繁程度動態(tài)地進行修改。當(dāng)壓縮消息時，我們不能期待一個算術(shù)編碼器獲得最大的效率，所能做的最有效的方法是在編碼過程中估算概率。算術(shù)編碼很容易與自適應(yīng)建模相結(jié)合。自適應(yīng)算術(shù)編碼自適應(yīng)算術(shù)編碼：在編碼之前，假設(shè)每個信源符號的頻率相等（如都等于1），并計算累積頻率從輸入流中讀入一個字符，并對該符號進行算術(shù)編碼更新該符號的頻率，并更新累積頻率由于在解碼之前，解碼器不知道是哪個信源符號，所以概率更新應(yīng)該在解碼之后進行對應(yīng)的，編碼器也應(yīng)在編碼后進行概率更新自適應(yīng)算術(shù)編碼為了提高解碼器的搜索效率，信源符號的頻率、累積頻率表按符號出現(xiàn)頻率降序排列在自適應(yīng)算術(shù)編碼中，可以用平衡二叉樹來快速實現(xiàn)對頻率和累積頻率的更新平衡二叉樹可用數(shù)組實現(xiàn)（類似Huffman編碼中的堆）最可能出現(xiàn)的符號安排在根附近，從而平均搜索的次數(shù)最小詳見《數(shù)據(jù)壓縮原理與應(yīng)用》第2.15節(jié)自適應(yīng)算術(shù)編碼例：信源符號及其出現(xiàn)頻率為：數(shù)組下標(biāo)：12345678910信源符號：頻率：輔助變量：輔助變量為該節(jié)點左子樹的總計數(shù)，用于計算累積頻率例：計算a6的累積頻率得到從節(jié)點10（a6）到根節(jié)點的路徑：

10521

a6a1a2a8

2.令af=0,沿樹枝從根節(jié)點向節(jié)點10（a6）

1)取根節(jié)點的左分支到子節(jié)點a2，af不變

2)取節(jié)點a2的右分支到到節(jié)點a1

， 將該節(jié)點的兩個數(shù)值加到af

af=af+12+16=282)取節(jié)點a1的左分支到到節(jié)點a6后，將其左子樹計數(shù)0加至af，最后af=28為累積頻率區(qū)間的起點自適應(yīng)算術(shù)編碼

數(shù)組下標(biāo)：12345678910信源符號：頻率：輔助變量：頻率、累積頻率表：a42[0,2)a912[2,14)a72[14,16)a212[16,28)a61[28,29)a111[29,40)a819[40,59)a108[59,67)a312[67,79)a55[79,84)自適應(yīng)算術(shù)編碼在平衡二叉樹上更新頻率：例：讀進符號a9，將其頻率計數(shù)從12變?yōu)?3在數(shù)組中尋找符號a9的左邊、離a9最遠的、頻率小于a9的元素，同時更新左子樹計數(shù)值總結(jié)直接對序列進行編碼（不是碼字的串聯(lián)）：非分組碼可證明是唯一可譯碼漸近接近熵界對不均衡的分布，比Huffman更有效只產(chǎn)生必要的碼字但是實現(xiàn)更復(fù)雜允許將建模和編碼分開，容易與自適應(yīng)模型和上下文模型結(jié)合對錯誤很敏感，如果有一位發(fā)生錯誤就會導(dǎo)致整個消息譯碼錯誤下節(jié)課內(nèi)容作業(yè)：Sayood3rd,pp.114-115必做：5,6,7,8下節(jié)課內(nèi)容：JPEG、JPEG2000和JBIG中的算術(shù)編碼：QM編碼器HistoryTheideaofencodingbyusingcumulativeprobabilityinsomeordering,anddecodingbycomparisonofmagnitudeofbinaryfractionwasintroducedinShannon’scelebratedpaper[1948].TherecursiveimplementationofarithmeticcodingwasdevisedbyElias(anothermemberinFano’sfirstinformationtheoryclassatMIT).

ThisunpublishedresultwasfirstintroducedbyAbramsonasanoteinhisbookoninformationtheoryandcoding[1963].TheresultwasfurtherdevelopedbyJelinekinhisbookoninformationtheory[1968].Thegrowingprecisionproblempreventedarithmeticcodingfrompracticalusage,however.TheproposalofusingfiniteprecisionarithmeticwasmadeindependentlybyPasco[1976]andRissanen[1976].HistoryPracticalarithmeticcodingwasdevelopedbyseveralindependentgroups[Rissane