熵編碼詳解-huffman和變長編碼

1、爛編碼變長編碼&算術編碼III利用信源的統(tǒng)計特性進行碼率壓縮的編碼就稱為 爛編碼,也叫統(tǒng)計編碼。視頻編碼常用的兩種:變長編碼（也稱哈夫曼編 碼）及算術編碼?，F(xiàn)分別討論其基本原理。變長編碼1952年，哈夫曼提出變長編碼方法。其重要的編碼原則即：對出現(xiàn)概率大的符號分配短字長的二進制碼,對出現(xiàn)概率小的符號分配長字長二進制碼,得到符號平均 碼長最短的碼。變長編碼也稱最佳編碼。具體編碼方法如下所示例子。哈夫曼編碼舉例:信源符號出現(xiàn)概率 島=0,320o. 60 nX2p廠 0.22 0.40£po.18r小 jfTi f /C()-P4-U.1OP5=008十0. 280, 121p0

2、,04 圖3.36哈夫曼編碼舉例可得：表3.2結果可X?X-4&k222344H'i00101101001100111_ 6則平均碼長w=p./. = 2.326因此我們可以看出哈夫曼編碼的步驟:第一步，將信息符號按其出現(xiàn)概率從大到小排列;第二步，將兩個最小概率組成一組,劃成2個分支域,并 坯以0和1 ；再把2個分支域合并成1個支域,標以兩個概 率之和；第三步，依次類推,直到概率之和等于1.0 ；第四步，找出概率和1.0到各信息符號的戦至，記下各路 徑從看型廷各分支域的0和1,即得到信息符號相應的碼字 o （皮向倫碼）丄理論上，這種編碼是最佳的。實際上,利用硬件實現(xiàn)時,出現(xiàn)概率

3、不可能精確到小數(shù)后 多少位，而最小存儲單元為lbit,會引起概率匹配不準確及編碼效率的下降。算術編碼算術編碼和哈夫曼編碼不同,不采用一個碼字代表一個輸 入信息符號的辦法,而采用一個浮點數(shù)來代替一串輸入符 號,經(jīng)算術編碼后輸出一個小于1 ,大于或等于0的浮點數(shù) ,在解碼端被正確地唯一的解碼,恢復原符號序列。舉例如下。設：輸入序歹I為abaca , p(a)=l/2 , p(b)= p(c)=l/4 ,求算術 編碼輸出序列。解：編碼：(1 )列出各符號出現(xiàn)概率值衣3付虧出現(xiàn)槻爭字符概率范a0.50 00Q50)b0.250.50,0.75)c0.250.75,1.00)0 （ 2）在（0 , 1

4、）區(qū)間內,每個字符根據(jù)其概率選定范圍 ,如上表所示（3）開始時，浮點范圍： R0 = HO LO = 1 , HO = 1 , LO = 0o（4 ）當?shù)谝粋€字符"a"被傳送時,其范圍為0.00,0.50） ,H = 0.05 , L = 0.00 ,可得發(fā)“a“字符的范圍H和L : LI = LO + ROx L = 0+1*0 = 0.00 Hl = L0 + R0xH = 0+1*0.05 = 0.50范圍R1 二 Hl - LI = 0.50對a編碼后,編碼范圍從0, 1 ）變?yōu)?.00,0.50）o （5）當?shù)诙€字符被傳送時z范圍為0.50,0.75） z H=

5、 0.75 , L = 0.50o L2 = LI + R1 x L = 0+0.50*0.50=0.25 H2 = LI + RlxH = 0+0.50*0.75=0.375 R2 = H2 - L2 = 0.125于是對"ab"編碼后,編碼范圍從0.00,0.50）變?yōu)?.25,0.375）o （6）依次類推:"a": L3 = 0.25+ 0.125x0 = 0.25H3 = 0.25 + 0.125x0.50 = 0.3125R3 = 0.0625工 :L4 = 0.25 + 0.0625x0.75 = 0.296875H4 = 0.25 + 0

6、.0625 x 1.00 = 0.3125R4 = 0.015625V : L5 = 0.296875 + 0.015625x0 = 0.296875H5 = 0.296875 + 0.015625x0.50 = 0.3046875R5 = 0.0078125最后輸出碼字為：0.3046875。由上述過程可以總結出來：若已知的字符范圍【L,H），則第i個字符傳送時: Li = Li-1 + Ri-1 * L ; Hi= Li-1 + Ri-1 *H; Ri = Hi - Li;碼結果:表3.4算術編碼結果序列范圍L范圍H初始01a0.000.50b0.250375a0.2503125c0.29

7、68750.3125a0.2968750.3046875(1)接受到浮點數(shù)0.3046875 ,對照表1 ,在范圍中查得 第一個字符為“才,其概率為0.5。(2)從接收值減去的概率范圍L ,并除以p(a), (0.3046875 - 0.00 ) /0.5 = 0.609375該值為下一字符范圍內的值，查得為“b”依此類推 (0.609375 - 0.50 ) /0.25 = 0.4375"a" (0.4375 - 0.00 ) /0.5 = 0.875 一"c" (0.875 - 0.75 ) /0.25 = 0.5 一一"a"解碼出序列"abaca"。解碼結果：表3 5尊術解碼結果