（概率論與數(shù)理統(tǒng)計專業(yè)論文）關(guān)于信源的tunstall編碼方法.pdf

致謝 作者首先要感謝兩位導(dǎo)師沈世錳教授和符方偉教授，他們那淵 博的知識和嚴謹?shù)闹螌W(xué)精神深深地影響了我，令我終身難忘。三年 以來，作者在兩位導(dǎo)師的關(guān)懷和培育下，學(xué)到了更為深刻而系統(tǒng)的 專業(yè)知識，正是由于他們的精心教誨和耐心指導(dǎo)，才使得本文能夠 順利地完成。他們那科學(xué)的治學(xué)方法、敏銳的洞察力以及平易近人 的工作作風，使我領(lǐng)悟到了正確的求學(xué)態(tài)度和做人準則，所有這些 是我在這幾年學(xué)習(xí)生活中獲得的最為寶貴的財富。 在本文寫作過程中，概率和信息教研室的各位老師以及本專業(yè) 信息論方向討論班的諸位同學(xué)給予我許多啟發(fā)和幫助，對此表示衷 心的感謝。 最后感謝我最親愛的父母多年來為我所做的一切，我的哥哥對 我的關(guān)心、鼓勵和支持。 關(guān) 于ip i vi i 的t u n s t a ll 場 _4 ;u- 方 迭 楊軍 ( 南 開 大 學(xué) 數(shù) 學(xué) 科 學(xué) 學(xué) 院 ， 天 津3 0 0 0 7 1 ) 中 文 摘 要 在信源編碼理論中，具有定長消息申 一 變長碼字的信源碼比 具有變長消息申 一 定 長 碼 字 的 信 源 碼 研 究 地 更 為 廣 泛 . 眾 所 周 知，h u ff m a n 碼 是 最 優(yōu) 的b - v碼( b代 表 定 長 消 息 ，v代表 變長 碼字 ) ， 有許 多 文 章 研 究 它的 冗 余 度的 上 界 和下 界 ， 詳見 3 、 4 和同等 文 . 事 實 上 ，h u ff m a n 碼 的 理 論 最 優(yōu) 性 是 在 信 源 為 平 穩(wěn) 無 記 憶 型 ， 這 一 非 常強的條件下得到的.實際應(yīng)用中的信源不一定為平穩(wěn)無記憶的，但經(jīng)驗證明它在理論 框架外的性能還比較令人滿意. h u ff m a n 碼 在v - b碼( v代表 變 長消 息 ，b代 表 定 長 碼 字 ) 中 的 配 對 碼 是t u n - s t a l l 碼， 它是漸近 最優(yōu)的， 它的冗余度隨著t u n s t a l l 樹擴展次數(shù)的增加趨于零. t u n s t a l l 碼在某種程度上比h u ff m a n碼更能探索信源字符串 之間的統(tǒng)計相關(guān)性， 從而為實際生 活 中 的 信 源 提 供 了 一 種 新 的 編 碼 方 法. 本 文 在【 1 文 的 基 礎(chǔ) 上 進 一 步 研 究 了t u n s t a l l 碼 的 性質(zhì)， 給出了t u n s t a l l 碼的碼率的 新的上界， 刻劃了t u n s t a l l 樹和擴展次數(shù)之間的 一些較深刻的內(nèi)在聯(lián)系， 并且給出了一個尋找 一最優(yōu)的t u n s 七 a l ! 碼的擴展次數(shù)的 算 法. o n t h e t u n s t a l l c o d e s i n s o u r c e c o d i n g y a n g j u n s c h o o l o f ma t h e ma t i c a l s c i e n c e s , n a n k a i u n i v e r s i t y t i a n j i n 3 0 0 0 7 1 , p . r . c h i n a abs t r a c t i n t h e t h e o r y o f s o u r c e c o d i n g , c o d e s w i t h b l o c k l e n g t h m e s s a g e s a n d v a r i a b l e - l e n g t h c o d e w o r d s i s i n v e s t i g a t e d m u c h m o r e e x t e n s i v e l y t h a n c o d e s w i t h v a r i a b l e - l e n g t h m e s s a g e s a n d b l o c k l e n g t h c o d e w o r d s . i t i s w e l l k n o w n t h a t h u ff m a n c o d e s i s t h e o p t i m a l b - v c o d e s ( b r e p r e s e n t s b l o c k l e n g t h m e s s a g e s , v r e p r e s e n t s v a r i a b l e - l e n g t h c o d e w o r d s ) . t h e r e a r e m u c h l i t e r a t u r e s t u d y i n g t h e u p p e r b o u n d a n d l o w e r b o u n d o f i t s r e d u n d a n c y , s u c h a s 3 , 4 a n d 5 . a c t u a l ly , t h e t h e o r e t i c a l o p t i m a l i t y o f h u ff m a n c o d e s r e q u i r e s a v e r y s t r o n g a s s u m p t i o n o n t h e n a t u r e o f t h e s o u r c e ; n a m e l y , t h a t t h e s o u r c e o u t p u t s l e t t e r s i n a s t a t i o n a r y a n d m e m o r y l e s s w a y . r e a l - l i f e s o u r c e s a r e n o t o f t h a t k i n d , b u t e m p i r i c a l e v - i d e n c e s h o w s t h a t h u ff ma n c o d e s w o r k f a i r l y w e l l o u t s i d e t h e t h e o r i t i c a l f r a me . t h e c o u n t e r p a r t t o h u ff m a n c o d e s f o r v - b c o d e s ( v r e p r e s e n t s v a r i a b l e - l e n g t h m e s s a g e s , b r e p r e s e n t s b l o c k l e n g t h c o d e w o r d s ) i s t u n - s t a l l c o d e , w h i c h i s a s y m p t o t i c a l l y o p t i m a l a n d w h o s e r e d u n d a n c y g o e s t o z e r o a s t u n s t a l l t r e e s e x t e n s i o n n u m b e r g o e s t o i n fi n i t y . t o s o m e d e g r e e , t u n s t a l l c o d e s h a v e a m o r e p o t e n t i a l f o r e x p l o i t i n g t h e s t a t i s t i - c a l d e p e n d e n c i e s o f s o u r c e o u t p u t s t h a n h u ff m a n c o d e s . s o i t p r o v i d e s a f r u i t f u l c o d i n g m e t h o d s f o r r e a l - l i f e s o u r c e s . i n t h i s p a p e r , w e f u r - t h e r s t u d y t h e p r o p e r t i e s o f t u n s t a l l c o d e s o n t h e b a s is o f 1 . t w o n e w u p p e r b o u n d s f o r t h e r a t e o f t u n s t a l l c o d e s a r e o b t a i n e d . s o m e d e e p r e l a t i o n s h i p s b e t w e e n t h e t u n s t a l l t r e e a n d i t s e x t e n s i o n n u m b e r a r e e s t a b l i s h e d . f i n a l l y w e p r e s e n t a n a l g o r i t h m f o r c a l c u l a t i n g t h e e - o p t i m a l e x t e n s i o n n u m b e r . 2 1 介紹 t u n s t a l l 編 碼 是 一 類 重 要的 信 源( 變 長一 定 長 ) 編 碼 方法 . 眾 所 周知 ， 隨 著 擴展次數(shù)趨于無窮，t u n s t a l l 碼的碼率趨于信源嫡; 并且t u n s t a l l 碼具有許 多與h u ff m a n 碼相類似的 性質(zhì). 關(guān)于t u n s t a l l 碼漸進最優(yōu)性的討論，f a b r i s 等人【 1 對于離散無記憶信源給出了當t u n s t a l l 碼的擴展次數(shù)給定時， 它的碼 率的上界和下界.g a l l a g e r 等人岡證明了廣義的t u n s t a l l 碼對于有記憶信 源的漸進最優(yōu)性，因 而從另一方面說明了自 適應(yīng)t u n s t a l l 編碼的可行性. 本 文進一步研究了t u n s t a l l 碼的性質(zhì)， 給出了t u n s t a l l 碼的碼率的新的上界， 這些新的 上界要優(yōu)于【 1 文給出 的上界. 本文進一步刻劃了t u n s t a l l 樹和擴展 次數(shù)之間的一些較深刻的內(nèi)在聯(lián)系，在實際應(yīng)用上，如果已知信源的概率分 布， 我們用t u n s t a l l 碼進行編碼時， 非常想知道需要擴展幾步就可以使碼率 接近信源嫡， 為此作者設(shè)計了一個在一定條件下求: 一最優(yōu)的擴展步的算法. 2關(guān)于in s t a l l 碼的基本知識 設(shè)離散平穩(wěn)無記憶信源的信源字母表a二 a , , a 2 , . ， 由a可以建立一棵擴展樹，它的生成步驟如下: 偽以a中的 所有字母作為葉 結(jié)點形成一棵深度為1 的樹 點和一個根結(jié)點. , a x , k 2 ， 我們 則共有 k個葉結(jié) j ) 在前面 貼上去， 則擴展i 7 一1 步形成的 樹中 選擇一個葉 結(jié)點 作為擴展點， 把第0 步生成的 樹 保證根結(jié)點和擴展點重合. 步之后， 擴展 樹的葉 結(jié)點 個 數(shù)記為t ( j ) 二k+ j ( k一1 ) 如果a的概率分布為p= p 1 , p 2 , , p 對， 這里。 一 a 們 選擇詞序最靠前的葉結(jié)點作為擴展點. 我們 把除葉 結(jié)點之外的 其余結(jié)點稱為內(nèi) 結(jié)點( 包括根結(jié)點 )如果內(nèi) 結(jié)點 的個數(shù)為。 ， 則葉 結(jié)點的個數(shù)也可記為m=a ( k一1 ) +1 ， 這種表示法與t ( 7 ) 是等價的， 且。 二少 十1 如果 碼字 符號集 是b= b , 戶 。 ， ， 與 ， d2 ( 一般d=2 ) . 經(jīng) 過， 步擴 展的t u n s t a l l 樹一 共有t ( j ) 個 長度 不相 等的消 息串 ， 把它們 編為定 長碼字， 則最 恰當 的 碼長為l ( 7 ) = 1 1 0 9 d t ( 7 ) ， 這種碼就稱為t u n s t a l l 碼; 為了 保證 編碼的有效性， 最大限度的使用每一個碼字，t u n s t a l l 擴展樹的葉結(jié)點的個 數(shù)必須滿 足d ” 一( k一2 ) 到力 d 0 ， 這個條件稱為t u n s t a l l 編碼的 有效 性條件. 例如果a = a , b , f = 1 0 6 , 0 .4 ， 取 b= 0 , 1 1 ， 下圖是經(jīng)過3 步擴 展的t u n s t a l l 碼 0 . 2 1 6 舊 幾 幾一0 0 0 (1)0 . 6 0 . 1 4 4 4 a a b 0 0 1 01 0 (2)0.4b 2 4 一0 1 1 住abo.ba r o o t 0 . 1 6 b b 一1 0 0 圖1 . p = ( 0 . 6 , 0 . 4 ) , j = 3 的 t u n s t a l l 樹 這棵 即a t u n s t a l l 樹有 4 個內(nèi) 結(jié)點( r o o t , a ,b , a a =3 , a=4 , m= 長編碼: a a a升 0 0 0 5 , 碼長 ， a a b 開 l =1 10 9 2 5 1 = ， 5 個葉結(jié)點( a a a , a a b , a b ,b a ,b b ) , 3 ， 所以我們進行以下的變長一 定 0 0 1 , a b - -+ 0 1 0 , b a - 0 1 1 , 品- - 1 0 0 定 義2 . 2: 經(jīng) 過7 步擴展的t u n s t a l l 樹， 記洲力是葉 結(jié)點a 對應(yīng)的 概率， - , ( j ) 是葉結(jié)點i 的 深度， 則編碼的平均消息 長度 t ( j ) 。 (， ) =藝 p+(7)-a(i) 留 = 在 上例中 ，n 份 ) =0 . 2 1 6 x 3 + 0 . 1 4 4 x 3 + 0 .2 4 x 2 + 0 .2 4 x 2 + 0 . 1 6 x 2 =2 .3 6 定義2 . 3: 經(jīng)過7 步擴展的 t u n s t a l l 碼的碼率 ，j-? l-一n -一 ，j 2l r 在 上 例中 ，r (j ) 一贏 、 1 .2 7 下面這個性質(zhì)與 h u ff m a n碼的平均碼長等于h u ff m a n樹中所有內(nèi) 結(jié)點 的概率之和是一致的. 命 題2 . 1 (6 j : 如 果毛 陰) 表 示t u n s t a “ 樹 中 所 有內(nèi) 結(jié) 點 的 集 合 ， 則t u ris l a l l 編碼的平均消息長度等于所有內(nèi) 結(jié)點的概率之和，即 n (j ) = 藝 p +. ( ? ) - e t j ( p ) 這里p.(7 ) 是每個內(nèi)結(jié)點對應(yīng)的概率. 在上例中 ，創(chuàng) 力=1 + 0 .6 + 0 .4 + 0 .3 6 二2 . 3 6 ， 這與定義2 .2 計算的結(jié)果一致. 3 t u n s t a l l 碼的碼率的上界和下界 在 信 源 概 率 分 布p = p l , p 2 , . 二 ， p i 中 ， 記 p =m i n p ; : p i ep , 1 i k ) p + 二 m a x p ; : p ; e 只1 “ k ) 分別表示最小和最大的信源概率 f a b r i s 等人【 1 給出了t u n s t a l l 碼的碼率的一個上界和下界. 對于經(jīng)過j 步擴 展的 t u n s t a l l 樹，定義一個參數(shù) lo g t ( j ) 1 / p - 一k 77 + ( i ) l o g t ( 力+l o g p - k 一 1 +00 ， jr1尹1 一一 本文的l o g 如不特別說明， 都以d為底. 定 理3 . 1 il l : 以 概率分布p建立的 t u n s t a l l 碼的 碼率滿足 h ( p ) r ( j ) il + ( j ) h ( p ) , 這里h( 尸 ) 為信源分布 尸的嫡. 容易 發(fā)現(xiàn)li m j i + - t7 + ( 力=1 ， 可見 這 個定 理充 分 說明 了t u n s t a l l 碼的 漸 進 最 優(yōu)性. 我們運用t u n s t a l l 碼的一些性質(zhì)， 可以得到一些新的上界， 這些上界要 優(yōu)于定理 3 . 1 給出的上界 經(jīng)過j 步擴展的t u n s t a l l 樹， 用p ( 力表示雙力個葉 結(jié)點對應(yīng)的概率分 布 ，p ( j ) 二 p i ( j ) , p 2 ( j ) , ， ; : ，(， ) ( : ) ， h ( p ( j ) ) 表 示 概 率 分 布p ( j ) 的 嫡 ， 即 t u n s t a l l 樹的嫡.同 樣地， 記 p 一 ( j ) = 尹 + ( 力= m i n p ; ( j ) : p i ( j ) e p ( j ) , 1 三x 三t ( j ) m a x p t ( j ) : p i ( j ) e p ( j ) , 1 i pp + ( 力 很容易由數(shù)學(xué)歸納法加以證明由t u n s t a l l 樹的這個性質(zhì)容易得出下面這個 引理 引理 3 . 1: 經(jīng)過歹步擴展的 t u n s t a “ 樹，有 p 一 ( j +1 ) =p 一 p + ( j ) 通過這個式子可推出t u n s t a l l 樹的嫡的上界和下界，以及其它一些性質(zhì). 引理3 . 2: 經(jīng)過7 步擴展的 t u n s t a l l 樹， 有 h ( p ( j ) ) =h ( p ( j 一 1 ) ) + p + ( j 一 1 ) h ( p ) 證明:一棵經(jīng)過7 一1 步擴展的t u n s t a l l 樹， 在進行第7 步擴展時， 一定選 擇概率為p + ( i ) 的葉 結(jié)點為擴展點， 而其余的葉 結(jié)點保持不變， 所以 t ( i ) h ( p ( j ) )=一 又a u ) lo g p i u ) =土 一z , p i ( j ) lo g p i ( 7 ) + ， + (， 一 1 ) l o g p + ( .7 一 1 ) i- 1k + 一 e p + (， 一 1 )p i lo g p + (， 一 1 )p i = h ( p ( ， 一1 ) ) + p + ( j 一1 ) l o g p + ( j 一1 ) 一 e p + (， 一 1 )p i lo g p + (: 一 ) + lo g p i = h ( p ( j 一1 ) ) + p + ( j 一 1 ) l o g p + ( 7 一1 ) 一 p + ( j 一1 ) l o g p + ， 一 1 ) 藝: 、 一 。 + ( : 一 1 ) 藝， lo g ; : i =1 i =1 h ( p ( j 一1 ) ) + p + ( j 一1 ) h ( p ) 注: 根據(jù) 約以 由 這個引理可以看出每擴展一次，t u n s 七 a l l 樹的嫡就增加p + ( j ) h ( p ) , p + ( 7 ) - v 二 興i p - 命可 ， 可 知 擴 展 次 數(shù) ， 每 增 加 一 次 ， h ( p (j ) ) 的幅度向上增長并趨于 十 。 1-丫7-t 一了去一rj 引理 3 . 3: h( p 仃 ) ) =n 汀 ) h( p ) 證明:這個引理是參考文獻i l l 中引 理2 的一個特例， 下面我們給出一個新 的證明， 根據(jù)引理3 .2 ， 我們有 h ( 尸 ( 7 ) )=h ( p ( ， 一1 ) ) + p + ( 一1 ) h ( p ) h ( p ( j 一 2 ) ) + p + ( ， 一 2 ) h ( p ) + p + ( 7 一1 ) h ( p ) ( 1 + p + ( o ) + p + ( 1 ) +一+ p + u一1 ) ) h ( p ) 在t u n s t a l l 樹的擴展過程中 內(nèi)結(jié)點， t u n s t a l l 故l , p + ( o ) ( p + ( o ) = 每擴展一次后概率最大的葉結(jié)點就變?yōu)橄鄳?yīng)的 p + ) , p + ( 1 ) , ， p + (一1 ) 就是經(jīng)過 ? 次擴展的 樹對應(yīng)的j +1 個內(nèi) 結(jié)點的概率，由 命題2 . 1 ， 知引理成立. 口 注: 引 理3 .3 反映了 經(jīng)過7 步擴展的t u n s t a l l 樹的 嫡、 信源嫡和平均消息長 度三者之間的關(guān)系.更進一步， 以表示如下: h ( p ( j ) ) 以 上兩個引 理說明了h ( p ( j ) ) 的漸進性質(zhì)可 。 (9-1o (ee=o 命 ) h( 尸 ) 這里o ( ) 表示同階無窮大或無窮小. 下面兩個定理給出了t u n s t a l l 樹的嫡的上界和下界. 定理 3 . 2: l o g t ( j +1 ) +l o g p - h ( p ( j ) ) lo g t ( j 一1 ) 一l o g p - 上界可以進一步加強:有 l o g t ( j +1 ) +l o g e 5 h ( p ( j ) ) g l o g t ( j ) 證明:對任意p ; ( j ) , 1 -! t ( j ) ， 有 p t ( j 一1 ) 臼(j 幾幾 對上面兩個不等式兩邊取對數(shù)后乘以一 p ; ( 力并求和， 第一個不等式成立. 由 最大嫡原理可得h ( p ( j ) ) lo g t ( j ) ， 因而第二個不等式成立.我們可以證 明對任何了 ， l o g t ( j ) 。 p k ( k ( ， 一1 ) ( k一1 ) ) -一 件一舟 定理 3 . 3 l o g t ( j ) +l o g p + h( p ) t ( j 一1 ) h ( p ( j ) ) l o g t ( j 一1 ) + h( 尸 ) p - t ( 力 上界可以進一步加強，有 log t (j ) + log ; 一 + 器 : h (p (7 ) 、 m in lo g t (j),log t ， 一 1)+ 黯 證明:根據(jù)引理3 .2 , h ( p ( j ) ) 二h ( p ( j 一1 ) ) +p + ( : 一1 ) 1 3 ( p ) ， 再根據(jù)定理 3 . 2 ， 我們 有 l o g t ( j ) +l o g e s h ( p ( j 一1 ) ) lo g t ( ， 一1 ) 加上1 1 t ( j 一1 ) _ p + ( .9 一1 ) 二p - ( j ) / p - l l p - t ( j ) ， 第一個不等式成立. 由 最大炳原理可得h ( p ( 力 ) k 一 1 t ( j ) i n d 蔽(p )(k - 1 ) in d 且 p 擊 1n (1 + 1 )x l o g t ( j 一1 ) + h( p ) p 一 t ( j ) 當p 一 不在這個范圍時， 這兩個上界無確定的大小關(guān)系. 由 碼率的定義和引理3 .3 , 經(jīng)過j 步擴展的t u n s t a l l 碼的碼率 r (j ) = 黯一 弩 轟 爵 h (p ) 由 定理3 . 2 和3 . 3 ， 很容易 得出t u n s t a l l 碼的 碼率的上界和下界 設(shè)兩個參數(shù) f l o g t ( j ) 7 1 / p - 一2 k+1 l o g t ( j +1 ) +l o g p - l o g t ( j ) ( 1 十 昌命) h ( p ) k 一 1 否則 矛!于、.月1、 一- 、，了 ，j 廠t飛 + 科 f l o g t ( j ) ) lo g t (j ) -f lo g 二 十 摧溉 a d - t v -n p / p - - k k 一 1 v + ( j ) f l o g t ( 力 飛 。 十 云 e3 - fe .- o 命) 州 尸 ) 否則 十矛、.吸氣 一- 定理 3 . 4: 以概率分布 尸建立的 t u n s t a l l 碼的碼率滿足 h ( p ) c h( p ) r ( j ) 。 因 此了 的范圍 有一定的要求， 即? 必須大于某個值. 當j 不在這個范圍內(nèi) 時， 根 據(jù)引 理3 .3 , h ( p ( a)= ( 1 + p + ( 0 ) + p + ( l ) +。 (l + t 1(0) 十 1t (1) + +p + j 一1 x ( p 十 蒸 李下 ) 州 尸 ) l f .9 一 土 ) 這可以 作為當j 小于這個值時t u r s t a ll 樹嫡的下界 口 注: 顯 然， 對 任何， ， w + ( 7 ) 刀 + ( ， ) ， 。 + ( ， ) 刀 + ( ， ) ， 界要優(yōu)于定理3 . 1 給出的 上界 當擴展次數(shù)， 較小時， 綜上所述，定理成立. 因此定理3 .4給出的上 碼率的上界仍然是存在 的 ， 不 能 簡 單 地 看 作 + 00 . 。 + (， ) 和 。 + (; ) 大 小 關(guān) 系 取 決 于 lo g 興 毛 興 一 群 興 資 的正負， 根據(jù)不等式 牛 、 ln ( 1 + 與 、 1 可得 k 一i， _k 一i 、k 一1 雙 j+1刃ii d 1 .當 了 2 k -s -i ( k- z ) ( ， 一1 ) 2 ， 可 得h ( p ) 10 9 d k揣 時 ， 有t j + 1t ti - t) h( 尸 ) t ( ; 一1 ) 所以當 _ 1 / p -一2 k+1 a 夕 m axi 一、找一 1 d 一 t p 粉 / p - k k 一 1 2 k - s - 匕、 ( h一1 ) ( s 一1 ) 時， 有iu + ( 力。 +( 力 我們 換一個角度。 經(jīng)過j 步擴展的t u n s t a l l 樹， 如果用d 切 表示葉結(jié) 點 的 概 率 分 布p (j ) 和 均 勻 分 布q 一 4 = = 命， = 1 , 2 ， 一t (j ) 之 間 的 信 息散度，即 t ( i ) d ( 1 ) =藝p i ( 力lo g 可知d ( j ) = 的變化范圍， l o g t ( 力一h ( p ( j ) ) ， 由h ( p ( j ) ) 的 上界 和下界很容易 得出d ( ) 即 +1 ) t f l 5l o gt ( j _l o g p 或者 0 三d ( j ) 0 d ( j ) h ( 尸 ) t ( j 一1 ) _l o g p 側(cè)力的變化情況刻畫了t u n s t a l l 樹葉 結(jié)點的概率分布偏離均勻 分布的遠近程 度 ， 當7 增大時，d ( j ) 并 不一定 趨于 零、 它的 變 化與 信源分布尸 ， 具體地 說 主要是和p 一 有密切的關(guān)系. 例: 當 信源分布尸為均勻分布時， 設(shè)想t u n s t a ll 樹隨著j 的增加由 一棵完 全 樹 變?yōu)?另 一 棵 完 全 樹 的 過程 中 ，d ( 力由 零 開 始 遞增 然 后又 遞 減為 零， 它 就 這一直往復(fù)下去， 可見當j 丹十 、時，d ( j ) 不一定有極限. 我們可以 這么認為，t u n s t a l l 擴展樹具有某種平衡能力， 它能把葉 結(jié)點 的 概率分布p ( ? ) 平 衡在 均勻 分布q的 周圍( 從編碼的 角 度講，t u n s t a l l 碼把 出 現(xiàn)概率最接近的消息串 映射成定長碼字) ， 因 此d ( 力隨， 的 變化反映在圖形 上就是在一定的范圍內(nèi) 上下波動. 下面這個定理說明了d ( 力波動的幅度越來 越平緩. 定理 3 . 5: 經(jīng)過7 步擴展的 t u n s t a l l 樹，隨著7的不斷增大，相鄰 d 川 的 變 化 幅 值 以命 的 速 度 趨 于 零 ， 即 一d (j + 1 ) 一 d (川一 。 t (j )一 證明: 由引理 3 .2 ， 我們有 d ( j +1 )=l o g t ( j +1 ) 一h ( p ( j +1 ) ) l o g t ( j +1 ) 一h ( p ( j ) ) 一 p + ( ) h ( p ) 所以 d ( j +1 ) 一d ( j )= l o g t ( j +1 ) 一 l o g t ( j ) 一 p + ( j ) h ( p ) 一 ，og (1 + 號) - 。 (; ) h (p ) 根據(jù)不等式 x+ 1 in ( 1 + 與 1 以及 1 /、一 、 p - ( j +1 ) / 不不 ， 戈 泛 p kj少= 匕 1 l 71 p 1 p - t ( j +1 ) 可得 k 一 1 不 下甲甲不 一 不 - 不 二 l o g ( 1 + i kj 十 1 ) 1 1 1 州 k一1 、 二二 二 ，二-1 1( 了 ) k 一 1 t ( j ) 1 n d hf 尸、._ _ 萬 訪 _ p t u ) 月 仁 尸 ， 三 f l ( p ) p t ( j +1 ) 所以 k - 1_ f且 i n d p - t ( j +1 ) 當i 丹+ co 時， p t ( .j 一1 ) 對上面兩個不等式兩邊取對數(shù)后，可得 l o g t ( j +1 ) +l o g p - 一 l o g 二 ( ， ) l o g t ( : 一1 ) 一l o g p - 由l ( j ) =t o g o t ( j ) ) 知定 理成立. 5 t u n s t a l l 碼的碼率和擴展次數(shù)的關(guān)系 如果已 知信源的概率分布尸 ， 需要擴展多少步才能使 t u n s t a l l 碼的冗余 度達到預(yù)先指定的標準呢? 這是我們應(yīng)用t u n s t a l l 碼進行編碼時首先必須解 決的問題.雖然 t u n s t a l l 碼的碼率在擴展次數(shù)趨于無窮時逼近信源嫡，但在 實際應(yīng)用中必須明確指明t u n s t a l l 樹的擴展次數(shù). 我們已經(jīng)知道，t u n s t a l l 樹的結(jié)點由內(nèi)結(jié)點和葉結(jié)點組成，它滿足有序 性川. 如果我們把內(nèi) 結(jié)點 和葉 結(jié)點的 概率按照遞減的順序排列， 則這個列表 可分為前后兩個部分， 前一部分( 記作z j ( p ) ) 包括所有的內(nèi) 結(jié)點， 且它的順 序和擴展點的先后順序一樣; 后一部分( 記作 j ( p ) ) 包括所有的葉結(jié)點. 例:在圖1 所示的t u n s t a l l 樹中，將所有結(jié)點按概率遞減的順序排列，為 1 ( r o o t ) , 0 .6 ( a ) , 0 .4 ( b ) , 0 . 3 6 ( a a ) 0 . 2 4 ( a b ) , 0 .2 4 ( b a ) , 0 .2 1 6 ( a a a ) , 0 . 1 6 ( b b ) , 0 . 1 4 4 ( a a b ) 可見前 4 個點為內(nèi)結(jié)點，它的順序和這棵t u n s t a l l 樹的擴展點的先后順序一 樣，后5 個點為葉結(jié)點. 在 有 效 性的 條 件下， 即葉 結(jié)點 個 數(shù)m滿 足d ” 一 ( k一 2 ) md 0 , n 為 碼 長 ; 其 內(nèi) 結(jié) 點 個 數(shù)a =鬢 注 告 ， 擴 展 次 數(shù); = 。 一 1 . 換 句 話 說 ，壽 滬) 有 。 個 元， ， ( 尸 ) 有m個 元 我們先給出k叉完全概率樹的定義. 定義 5 . 1: 如果一裸 k叉樹按照以下步驟生成: 1 ) 由p= p i , p 2 , ， 二 ， p it 生成一棵深度為1 的k叉樹， 喲把第1 步生成的樹貼在由 前面d 一1 步形成的 樹的每一個葉 結(jié)點上. 那么我們稱這樣的概率樹為 k叉完全概率樹. 在t u n s t a l l 樹中，任何結(jié)點: 的概率都可以表示為 p i ( 7 ) 一 討 12p 1l, p 2二 、 ixh 的形式，其中 1 1 +1 2 +一+l k =n i ( 力 n i ( 力為結(jié)點 的深度. 如果把下面的 多項 式展開， 同 時不 合并同 類項( 即 每一 項系 數(shù)為1 ) 1 + ( p ， 十 p 2 + ， 二 + p 動+ ( p i + p 2 + p k ) 2 + + ( p ; 十 p 2 + 十 p h ) d 則這個多項式的每一項都對應(yīng)k叉完全概率樹中某個結(jié)點的概率. 因 為每一 項 都 具有p i ( 力的 形式， 所以 可 能 是某棵t u n s t a l l 樹的 結(jié)點. 這樣一 來， 結(jié)點 的概率就和多項式聯(lián)系起來. 定理5 . 1: 一棵t u n s t a l l 樹的結(jié)點總數(shù)泡括內(nèi) 外結(jié)點 夕 不大于d + d ( k一 1 ) + 1 個， 則它必是由p=i p 1 , p 2 , , p 對 生成的 深度為d 的 k叉完全概率樹的 子樹. 證明: 考慮最大深度為 d的t u n s t a l l 樹.從第一次擴展開始，如果每擴展一 次 t u n s t a l l 樹的最大深度就加 1 ， 則擴展 d 一1 次后 t u n s t a l l 樹的最大深度 為d ， 這種t u n s t a l l 樹的內(nèi) 結(jié)點數(shù)為d ， 葉 結(jié)點數(shù)為d ( k一1 ) +1 ， 結(jié)點總數(shù)為 d 十 d ( k一 1 ) +1 . 但t u n s t a l l 樹每擴展一次后不一 定 最大深 度就加1 ， 所以 擴 展d 一1 次后其 最大深 度小于 等于d ， 但結(jié)點總 數(shù)仍為d + d ( k一1 ) +1 . 由 此 可 見， 結(jié)點總 數(shù)不大于d 十 武 k一1 ) +1 個的t u n s t a l l 樹的 深度一定不 超過 d ， 引 理成立口 這個定理說明了如果把深度為d 的k叉完全概率樹的所有結(jié)點依概率 遞減的 順序排列， 則列表中的前d 個結(jié)點一定是由p生成的t u n s t a l l 樹的內(nèi) 結(jié)點. 定義5 . 2: 在給定的冗余度 :下，稱 t u n s t a l l 碼是 。 一最優(yōu)的， 如果這個 t u n s t a l l 碼的碼率 r ( 力 h( p ) +e 定義 5 . 3: 在所有的: 一最優(yōu)的 t u n s t a l l 碼中，定義最小的擴展次數(shù) j=m i n j : r ( j ) h ( p ) +: 如果已知信源概率分布 尸和冗余度: ， 下面給出一個尋找j的算法， ( 0 ) 選擇 碼長的初 值n o ， 一 般取二 。 =r l ogd i ,1 0 9 d深度的 初值d =。 。 . ( 1 ) 根據(jù)深度為d 的k叉完全概率樹的每一結(jié)點的概率對應(yīng)多項式 1 + ( p i + p 2 + + p 司+ ( p i + p 2 + + p k ) 2 + + (p i + p 2 + + p k ) d 的 展開 式的每 一項( 注 意展 開時 不合并同 類項 ) ， 數(shù)是 1 +k+k2 + +kd 二 把每一項存入數(shù)組b . b k d + 1 一1 k 一 飛 ( 2 ) 對數(shù)組b按照從大到小的順序進行排序，只需排出 最大的前d 個元. ( 3 ) 令 碼 長n = n o . ( 4 ) 根據(jù)有效性的 條件 d ” 一( k一 2 ) md ， 則a - -+ d , n - 3 n o , g o t o ( 1 ) ; 否則，由 命題2 . 1 計算碼率 的維 確定 n 藝 幾 1 h a ( 6 ) 如果r h ( p ) 十: ， 則找到j(luò) =a 一1 ， 退出; 否則，。 +l - 。 ， g o t o ( 4 ) . 我們可以根據(jù)這個算法很快地確定: 一最優(yōu)的t u n s t a l l 碼的最小擴展次 從而建立 t u n s t a l l 樹來進行編碼. 對 概 率 分 布p = 。 6 , 0 .3 , 0 . 1 的 信 源， 信 源 字 母 表為a= 。 ， b , c , k= 3 , 數(shù)例 采用二 元 碼進行編 碼( d=2 ) ， 信源 嫡h 護) =1 .2 9 5 如果: =0 . 2 ， 通過算法計算知當。 二4 , a =7 時， 4 1 +0 . 6 +0 . 3 6+0 . 3 +0 .2 1 6 +0 . 1 8+0 . 1 8、1 . 4 1 0 h ( p ) +0 .2 所以可以確定最小的擴展次數(shù) i 如果: =0 .1 ， 通過算法計算知當 所以可以確定最小的擴展次數(shù)j = 。 一 1= 二5 , a= = a 一 1= 6 . 1 5 時，r、1 . 3 8 5 h ( p ) +0 . 1 , 1 4. re f e r e nc e s 1 f . f a b r i s , a .s g a r r o a n d r . p a u le t t i , “ t u n s t a ll a d a p t i v e c o d i n g a n d m i s - c o d i n g ” ，i e e e t r a n s . i n f o r m . t h e o r y , v o l . i t - 4 2 , n o . 6 , p p . 2 1 6 7 - 2 1 8 0 , 1 9 9 6 . 2 s . a .s a v a r i a n d r . g .g a l l a g e r ,“ g e n e r a l i z e d t u n s t a l l c o d e s f o r w i t h me m o r y” ， i e e e t r a n s . i n f o r m. t h e o r y , v o l . i t - 4 3 , n o 6 5 8 - 6 6 8 , 1 9 9 7 . s o u r c e s 2 , p p . 3 r . g . g a l l a g e r ,“ v a r i a t i o n s o n a t h e m e b y h u ff m a n” ， i e e e t r a n s i n