視頻壓縮

2. 算術(shù)編碼
霍夫曼編碼的每個(gè)代碼都要使用一個(gè)整數(shù)位， 如果一個(gè)符號只需要用2.5位就能表示， 但在霍夫曼編碼中卻必須用3個(gè)符號來表示， 因此它的效率較低。 與其相比， 算術(shù)編碼并不是為每個(gè)符號產(chǎn)生一個(gè)單獨(dú)的代碼， 而是使整條信息共用一個(gè)代碼， 增加到信息上的每個(gè)新符號都遞增地修改輸出代碼。

假設(shè)信源由4個(gè)符號S1、 S2、 S3和S4組成， 其概率模型如表6-1所示。 把各符號出現(xiàn)的概率表示在如圖6-3所示的單位概率區(qū)間之中， 區(qū)間的寬度代表概率值的大小， 各符號所對應(yīng)的子區(qū)間的邊界值， 實(shí)際上是從左到右各符號的累積概率。 在算術(shù)編碼中通常采用二進(jìn)制的小數(shù)來表示概率， 每個(gè)符號所對應(yīng)的概率區(qū)間都是半開區(qū)間， 如S1對應(yīng)［0， 0.001)， S2對應(yīng)［0.001， 0.011)。 算術(shù)編碼所產(chǎn)生的碼字實(shí)際上是一個(gè)二進(jìn)制小數(shù)值的指針， 該指針指向所編的符號所對應(yīng)的概率區(qū)間。

表6-1 信源概率模型和算術(shù)編碼過程

圖 6-3 算術(shù)編碼過程示意圖

若將符號序列S3S3S2S4進(jìn)行算術(shù)編碼， 序列的第一個(gè)符號為S3， 我們用指向圖6-3中第3個(gè)子區(qū)間的指針來代表這個(gè)符號， 由此得到碼字0.011。 后續(xù)的編碼將在前面編碼指向的子區(qū)間內(nèi)進(jìn)行。 將［0.011， 0.111)區(qū)間再按符號的概率值劃分成4份， 對第二個(gè)符號S3， 指針指向0.1001,碼 字串變?yōu)?.1001。 然后S3所對應(yīng)的子區(qū)間又被劃分為4份， 開始對第3個(gè)符號進(jìn)行編碼……。

算術(shù)編碼的基本法則如下：
(1) 初始狀態(tài)： 編碼點(diǎn)(指針?biāo)柑?C0=0， 區(qū)間寬度A0=1。
(2) 新編碼點(diǎn)： Ci= Ci-1 + Ai-1×Pi。
式中, Ci-1是原編碼點(diǎn)；　Ai-1是原區(qū)間寬度；　
Pi所編符號對應(yīng)的累積概率。
新區(qū)間寬度Ai= Ai-1×pi
式中， pi為所編符號對應(yīng)的概率。

根據(jù)上述法則， 對序列S3S3S2S4進(jìn)行算術(shù)編碼的過程如下：
第一個(gè)符號S3：
C1=C0+A0×P1=0+1×0.011=0.011
A1=A0×p1=1×0.1=0.1
［0.011,0.111］