算術(shù)編碼-課件

1計(jì)算機(jī)應(yīng)用技術(shù)

張志林

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

字符:

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算術(shù)編碼應(yīng)用（1）初始high=1,low=0,range=high-low,一個(gè)字符編碼后新的low和high按下式計(jì)算：

low=low+range×rangelow；high=low+range×rangehigh。(1)在第一個(gè)字符e被編碼時(shí),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

此時(shí)分配給e的范圍為［0.2,0.5)6ppt課件無失真編碼7(2)第二個(gè)字符a編碼時(shí)使用新生成范圍[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)對(duì)下一個(gè)字符i編號(hào),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結(jié)果：用[0.23,0.236)表示數(shù)據(jù)串eai,如果解碼器知道最后范圍是[0.23,0.236),它馬上可解得一個(gè)字符為e,然后依次得到唯一解a、i,最終得到eai8ppt課件

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

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