視頻壓縮

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

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

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

圖 6-3 算術編碼過程示意圖

若將符號序列S3S3S2S4進行算術編碼， 序列的第一個符號為S3， 我們用指向圖6-3中第3個子區間的指針來代表這個符號， 由此得到碼字0.011。 后續的編碼將在前面編碼指向的子區間內進行。 將［0.011， 0.111)區間再按符號的概率值劃分成4份， 對第二個符號S3， 指針指向0.1001,碼 字串變為0.1001。 然后S3所對應的子區間又被劃分為4份， 開始對第3個符號進行編碼……。

算術編碼的基本法則如下：
(1) 初始狀態： 編碼點(指針所指處)C0=0， 區間寬度A0=1。
(2) 新編碼點： Ci= Ci-1 + Ai-1×Pi。
式中, Ci-1是原編碼點；　Ai-1是原區間寬度；　
Pi所編符號對應的累積概率。
新區間寬度Ai= Ai-1×pi
式中， pi為所編符號對應的概率。

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