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

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