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

1、爛編碼變長編碼&算術(shù)編碼III利用信源的統(tǒng)計(jì)特性進(jìn)行碼率壓縮的編碼就稱為 爛編碼,也叫統(tǒng)計(jì)編碼。視頻編碼常用的兩種:變長編碼（也稱哈夫曼編 碼）及算術(shù)編碼?，F(xiàn)分別討論其基本原理。變長編碼1952年，哈夫曼提出變長編碼方法。其重要的編碼原則即：對(duì)出現(xiàn)概率大的符號(hào)分配短字長的二進(jìn)制碼,對(duì)出現(xiàn)概率小的符號(hào)分配長字長二進(jìn)制碼,得到符號(hào)平均 碼長最短的碼。變長編碼也稱最佳編碼。具體編碼方法如下所示例子。哈夫曼編碼舉例:信源符號(hào)出現(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結(jié)果可X?X-4&k222344H'i00101101001100111_ 6則平均碼長w=p./. = 2.326因此我們可以看出哈夫曼編碼的步驟:第一步，將信息符號(hào)按其出現(xiàn)概率從大到小排列;第二步，將兩個(gè)最小概率組成一組,劃成2個(gè)分支域,并 坯以0和1 ；再把2個(gè)分支域合并成1個(gè)支域,標(biāo)以兩個(gè)概 率之和；第三步，依次類推,直到概率之和等于1.0 ；第四步，找出概率和1.0到各信息符號(hào)的戦至，記下各路 徑從看型廷各分支域的0和1,即得到信息符號(hào)相應(yīng)的碼字 o （皮向倫碼）丄理論上，這種編碼是最佳的。實(shí)際上,利用硬件實(shí)現(xiàn)時(shí),出現(xiàn)概率

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

4、）區(qū)間內(nèi),每個(gè)字符根據(jù)其概率選定范圍 ,如上表所示（3）開始時(shí)，浮點(diǎn)范圍： R0 = HO LO = 1 , HO = 1 , LO = 0o（4 ）當(dāng)?shù)谝粋€(gè)字符"a"被傳送時(shí),其范圍為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對(duì)a編碼后,編碼范圍從0, 1 ）變?yōu)?.00,0.50）o （5）當(dāng)?shù)诙€(gè)字符被傳送時(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于是對(duì)"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。由上述過程可以總結(jié)出來：若已知的字符范圍【L,H），則第i個(gè)字符傳送時(shí): Li = Li-1 + Ri-1 * L ; Hi= Li-1 + Ri-1 *H; Ri = Hi - Li;碼結(jié)果:表3.4算術(shù)編碼結(jié)果序列范圍L范圍H初始01a0.000.50b0.250375a0.2503125c0.29

7、68750.3125a0.2968750.3046875(1)接受到浮點(diǎn)數(shù)0.3046875 ,對(duì)照表1 ,在范圍中查得 第一個(gè)字符為“才,其概率為0.5。(2)從接收值減去的概率范圍L ,并除以p(a), (0.3046875 - 0.00 ) /0.5 = 0.609375該值為下一字符范圍內(nèi)的值，查得為“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"。解碼結(jié)果：表3 5尊術(shù)解碼結(jié)果