算術編碼-課件

1計算機應用技術

張志林

算數(shù)編碼無失真編碼1ppt課件算術編碼特點非分組碼，它是從全序列出發(fā)，考慮符號之間的依賴關系。經(jīng)香農(nóng)-費諾-埃利斯編碼推廣而來的，直接對信源符號序列進行編碼輸出。即時碼，信源符號序列對應的累積概率區(qū)間是不重疊的?？隙ㄒ部梢晕ㄒ蛔g碼。不必預先定義概率模型,自適應模式具有獨特的優(yōu)點;信源符號概率接近時,建議使用算術編碼,這種情況下其效率高于Huffman編碼(約5%)。JPEG擴展系統(tǒng)采用。無失真編碼22ppt課件算術編碼特點算術編碼并不是將單個信源符號映射成一個碼字，而是把整個信源表示為實數(shù)線上0到1之間的一個區(qū)間,其長度等于該序列的概率。在該區(qū)間內(nèi)選擇一個代表性的小數(shù)，轉換為二進制作為實際的編碼輸出消息序列中的每個元素都要用來壓縮這個區(qū)間消息序列中元素越多，所得到的區(qū)間就越小，當區(qū)間變小時，就需要更多的位數(shù)來表示這個區(qū)間無失真編碼33ppt課件算術編碼的編碼過程從信源符號全序列出發(fā)，將各信源序列依累積概率分布函數(shù)的大小映射到［０,１］區(qū)間,將［０,１］區(qū)間分成許多互不重疊的小區(qū)間。此時每個符號序列均有一個小區(qū)間與之對應，因而可在小區(qū)間內(nèi)取點來代表該符號序列。無失真編碼44ppt課件無失真編碼5算術編碼應用（1）采用固定模式符號概率分配如下：

字符:

aeiou

概率:0.20.30.10.20.2

范圍:［0,0.2)［0.2,0.5)［0.5,0.6)［0.6,0.8)［0.8,1.0)編碼數(shù)據(jù)串為eai。令high間隔的高端,low為低端，range為間隔的長度,rangelow為編碼字符分配的間隔低端,rangehigh為編碼字符分配的間隔高端。5ppt課件無失真編碼6算術編碼應用（1）初始high=1,low=0,range=high-low,一個字符編碼后新的low和high按下式計算：

low=low+range×rangelow；high=low+range×rangehigh。(1)在第一個字符e被編碼時,e的rangelow=0.2,rangehigh=0.5,因此:

low=0+1×0.2=0.2high=0+1×0.5=0.5range=high-low=0.5-0.2=0.3

此時分配給e的范圍為［0.2,0.5)6ppt課件無失真編碼7(2)第二個字符a編碼時使用新生成范圍[0.2,0.5),a的rangelow=0,rangehigh=0.2,因此:

low=0.2+0.3×0=0.2high=0.2+0.3×0.2=0.26range=0.06

范圍變成[0.2,0.26)7ppt課件無失真編碼8(3)對下一個字符i編號,i的rangelow=0.5，rangehigh=0.6,range=0.06,則：

low=0.2+0.06×0.5=0.23high=0.2+0.06×0.6=0.236結果：用[0.23,0.236)表示數(shù)據(jù)串eai,如果解碼器知道最后范圍是[0.23,0.236),它馬上可解得一個字符為e,然后依次得到唯一解a、i,最終得到eai8ppt課件

算術編碼過程表示91e0.5ea0.260.2360.80.60.50.20uoieauoieauoieauoiea0.20.20.23eai無失真編碼9ppt課件無失真編碼10算術編碼應用（2）10ppt課件無失真編碼算術編碼設定初值high=1.0low=0length=high-low=1.0對符號序列中每一個輸入的信源符號進行編碼，計算high,low及l(fā)ength的新值high=low+length×symbol_high(c)low=low+length×symbol_low(c)1111ppt課件無失真編碼算術編碼符號定義等號右邊的low和length分別為前面已編碼符號序列所對應編碼區(qū)間的下界和區(qū)間長度等號左邊的low和high分別為輸入待編碼符號后所對應的當前區(qū)間的下界和上界symbol_high(c):當前輸入符號c的上界symbol_low(c):當前輸入符號c的下界length:“當前區(qū)間”的區(qū)間長度，length=high-low1212ppt課件無失真編碼13算數(shù)編碼過程表示（圖）13ppt課件無失真編碼算術編碼—編碼過程根據(jù)每個符號出現(xiàn)的概率將半開區(qū)間[0,1)分成四個區(qū)域[0,0.2)[0.2,0.4)[0.4,0.8)[0.8,1)對輸入的第一個符號a1編碼symbol_high(a1)=0.2symbol_low(a1)=0high=0+1.0×0.2=0.2low=0+1.0×0=0輸入第一個符號a1后，編碼區(qū)間由[0,1)變?yōu)閇0,0.2)，當前區(qū)間長度length=0.2-0=0.2對輸入的符號序列a1a2進行編碼symbol_high(a2)=0.4symbol_low(a2)=0.2high=0+0.2×0.4=0.08low=0+0.2×0.2=0.04輸入第二個符號a2后，編碼區(qū)間由[0,0.2)變?yōu)閇0.04,0.08)，當前區(qū)間長度length=0.08-0.04=0.041414ppt課件無失真編碼算術編碼—編碼過程輸入第三個符號a3后，對序列a1a2a3進行編碼,編碼區(qū)間為[0.056,0.072)輸入第四個符號a3后,對序列a1a2a3a3進行編碼,編碼區(qū)間為[0.0624,0.0688)輸入第五個符號a4后,對序列a1a2a3a3a4進行編碼,編碼區(qū)間為[0.06752,0.0688)在區(qū)間[0.06752,0.0688)內(nèi)的任何數(shù)字都可以表示消息a1a2a3a3a4,例0.067521515ppt課件無失真編碼算術編碼—編碼過程1616ppt課件無失真編碼算術編碼—譯碼過程通過查看哪一個信源符號擁有已編碼消息所落入的數(shù)值范圍，找到消息中的第一個信源符號，0.06752在[0,0.2)之間，所以第一個符號為a1從編碼數(shù)值中消去第一個符號a1的影響，即首先減去a1的所在區(qū)間的下界值，然后除以a1對應區(qū)間的寬度，即

(0.06752-0)/0.2=0.3376查表找到該結果0.3376落入哪一個符號對應的數(shù)值范圍，得到第二個符號a2重復上述過程直至解出整個符號流1717ppt課件無失真編碼算術編碼—譯碼過程1818ppt課件無失真編碼算術編碼總結算術編碼對整個消息只產(chǎn)生一個碼字，這個碼字是在間隔[0,1)中的一個實數(shù)，因此譯碼器在接收到這個實數(shù)的所有位之前不能進行譯碼算術編碼是一種對，如果有一位發(fā)生錯誤就會導致錯誤很敏感的編碼方法整個消息譯錯實際編碼是用