linux上用c實現算術編碼（三）--算術編碼理論講解

1、算術編碼定義

它是1種非分組編碼算法。它是從全序列動身，采取遞推情勢的連續編碼。它不是將單個的信源符號映照成1個碼字，而是將全部輸入序列的符號根據它們的幾率映照為實數軸上區間[0 1)內的1個小區間，再在該小區間內選擇1個代表性的2進制小數，作為實際的編碼輸出。

算術編碼不同于霍夫曼碼，它是非分組（非塊）碼。它從全序列動身，斟酌符號之間的關系來進行編碼。

算術編碼利用了積累幾率的概念。

算術碼主要的編碼方法是計算輸入信源符號序列所對應的區間。

由于在編碼進程中，每輸入1個符號要進行乘法和加法運算，所以稱此編碼方法為算術編碼。

2、算術編碼的編碼

設輸入符號串s取自符號集S={a1,a2,a3,…,am}，p(ai)={p1,p2,p3,…,pm}，s后跟符號ai擴大成符號串sai，算術編碼的迭代關系為: 

1)碼字刷新：C(sai)=C(s)+P(ai)A(s)

2)區間刷新：A(sai)=p(ai)A(s) 

符號積累幾率：

初始條件：

通過關于信源符號序列的積累散布函數的計算，把區間分割成許多小區間，不同的信源符號序列對應不同的區間為[F(s),F(s)+P(s)) 。可取小區間內的1點來代表這序列。

編碼方法：將符號序列的積累散布函數寫成2進位的小數，取小數點后k位，若后面有尾數，就進位到第k位，這樣得到的1個數C，并使k滿足：

舉例:

4、例題

[例]假定信源符號為{a,b, c, d}，這些符號的幾率分別為{ 0.1, 0.4, 0.2, 0.3 }，對輸入消息序列cadacdb進行算術編碼。

解：根據這些幾率可把間隔[0, 1)分成4個子間  隔：[0, 0.1), [0.1, 0.5), [0.5, 0.7), [0.7, 1)。信息可綜合在表中：

編碼時首先輸入的符號是c，找到它的編碼范圍是[0.5, 0.7)。由于消息中第2個符號a的編碼范圍是[0, 0.1)，因此它的間隔就取[0.5, 0.7)的第1個10分之1作為新間隔[0.5, 0.52)。依此類推，編碼第3個符號d時取新間隔為[0.514, 0.52)，… 。消息的編碼輸出可以是最后1個間隔中的任意數。

我們可以根據碼字計算求出：K取17。

進而將終究輸出的小數0.5143876轉換為2進制：0.10000011101011110

進而終究的結果為：10000011101011110

具體的實現可以參考我的代碼，謝謝！！！

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈