（概率论与数理统计专业论文）关于信源的tunstall编码方法.pdf

致谢 作者首先要感谢两位导师沈世锰教授和符方伟教授，他们那渊 博的知识和严谨的治学精神深深地影响了我，令我终身难忘。三年 以来，作者在两位导师的关怀和培育下，学到了更为深刻而系统的 专业知识，正是由于他们的精心教诲和耐心指导，才使得本文能够 顺利地完成。他们那科学的治学方法、敏锐的洞察力以及平易近人 的工作作风，使我领悟到了正确的求学态度和做人准则，所有这些 是我在这几年学习生活中获得的最为宝贵的财富。 在本文写作过程中，概率和信息教研室的各位老师以及本专业 信息论方向讨论班的诸位同学给予我许多启发和帮助，对此表示衷 心的感谢。 最后感谢我最亲爱的父母多年来为我所做的一切，我的哥哥对 我的关心、鼓励和支持。 关 于ip i vi i 的t u n s t a ll 场 _4 ;u- 方 迭 杨军 ( 南 开 大 学 数 学 科 学 学 院 ， 天 津3 0 0 0 7 1 ) 中 文 摘 要 在信源编码理论中，具有定长消息申 一 变长码字的信源码比 具有变长消息申 一 定 长 码 字 的 信 源 码 研 究 地 更 为 广 泛 . 众 所 周 知，h u ff m a n 码 是 最 优 的b - v码( b代 表 定 长 消 息 ，v代表 变长 码字 ) ， 有许 多 文 章 研 究 它的 冗 余 度的 上 界 和下 界 ， 详见 3 、 4 和同等 文 . 事 实 上 ，h u ff m a n 码 的 理 论 最 优 性 是 在 信 源 为 平 稳 无 记 忆 型 ， 这 一 非 常强的条件下得到的.实际应用中的信源不一定为平稳无记忆的，但经验证明它在理论 框架外的性能还比较令人满意. h u ff m a n 码 在v - b码( v代表 变 长消 息 ，b代 表 定 长 码 字 ) 中 的 配 对 码 是t u n - s t a l l 码， 它是渐近 最优的， 它的冗余度随着t u n s t a l l 树扩展次数的增加趋于零. t u n s t a l l 码在某种程度上比h u ff m a n码更能探索信源字符串 之间的统计相关性， 从而为实际生 活 中 的 信 源 提 供 了 一 种 新 的 编 码 方 法. 本 文 在【 1 文 的 基 础 上 进 一 步 研 究 了t u n s t a l l 码 的 性质， 给出了t u n s t a l l 码的码率的 新的上界， 刻划了t u n s t a l l 树和扩展次数之间的 一些较深刻的内在联系， 并且给出了一个寻找 一最优的t u n s 七 a l ! 码的扩展次数的 算 法. 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 编 码 是 一 类 重 要的 信 源( 变 长一 定 长 ) 编 码 方法 . 众 所 周知 ， 随 着 扩展次数趋于无穷，t u n s t a l l 码的码率趋于信源嫡; 并且t u n s t a l l 码具有许 多与h u ff m a n 码相类似的 性质. 关于t u n s t a l l 码渐进最优性的讨论，f a b r i s 等人【 1 对于离散无记忆信源给出了当t u n s t a l l 码的扩展次数给定时， 它的码 率的上界和下界.g a l l a g e r 等人冈证明了广义的t u n s t a l l 码对于有记忆信 源的渐进最优性，因 而从另一方面说明了自 适应t u n s t a l l 编码的可行性. 本 文进一步研究了t u n s t a l l 码的性质， 给出了t u n s t a l l 码的码率的新的上界， 这些新的 上界要优于【 1 文给出 的上界. 本文进一步刻划了t u n s t a l l 树和扩展 次数之间的一些较深刻的内在联系，在实际应用上，如果已知信源的概率分 布， 我们用t u n s t a l l 码进行编码时， 非常想知道需要扩展几步就可以使码率 接近信源嫡， 为此作者设计了一个在一定条件下求: 一最优的扩展步的算法. 2关于in s t a l l 码的基本知识 设离散平稳无记忆信源的信源字母表a二 a , , a 2 , . ， 由a可以建立一棵扩展树，它的生成步骤如下: 伪以a中的 所有字母作为叶 结点形成一棵深度为1 的树 点和一个根结点. , a x , k 2 ， 我们 则共有 k个叶结 j ) 在前面 贴上去， 则扩展i 7 一1 步形成的 树中 选择一个叶 结点 作为扩展点， 把第0 步生成的 树 保证根结点和扩展点重合. 步之后， 扩展 树的叶 结点 个 数记为t ( j ) 二k+ j ( k一1 ) 如果a的概率分布为p= p 1 , p 2 , , p 对， 这里。 一 a 们 选择词序最靠前的叶结点作为扩展点. 我们 把除叶 结点之外的 其余结点称为内 结点( 包括根结点 )如果内 结点 的个数为。 ， 则叶 结点的个数也可记为m=a ( k一1 ) +1 ， 这种表示法与t ( 7 ) 是等价的， 且。 二少 十1 如果 码字 符号集 是b= b , 户 。 ， ， 与 ， d2 ( 一般d=2 ) . 经 过， 步扩 展的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 扩展树的叶结点的个 数必须满 足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 ， 下图是经过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 个内 结点( 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 个叶结点( 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: 经 过7 步扩展的t u n s t a l l 树， 记洲力是叶 结点a 对应的 概率， - , ( j ) 是叶结点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: 经过7 步扩展的 t u n s t a l l 码的码率 ，j-? l-一n -一 ，j 2l r 在 上 例中 ，r (j ) 一赢 、 1 .2 7 下面这个性质与 h u ff m a n码的平均码长等于h u ff m a n树中所有内 结点 的概率之和是一致的. 命 题2 . 1 (6 j : 如 果毛 阴) 表 示t u n s t a “ 树 中 所 有内 结 点 的 集 合 ， 则t u ris l a l l 编码的平均消息长度等于所有内 结点的概率之和，即 n (j ) = 艺 p +. ( ? ) - e t j ( p ) 这里p.(7 ) 是每个内结点对应的概率. 在上例中 ，创 力=1 + 0 .6 + 0 .4 + 0 .3 6 二2 . 3 6 ， 这与定义2 .2 计算的结果一致. 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 步扩 展的 t u n s t a l l 树，定义一个参数 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( 尸 ) 为信源分布 尸的嫡. 容易 发现li m j i + - t7 + ( 力=1 ， 可见 这 个定 理充 分 说明 了t u n s t a l l 码的 渐 进 最 优性. 我们运用t u n s t a l l 码的一些性质， 可以得到一些新的上界， 这些上界要 优于定理 3 . 1 给出的上界 经过j 步扩展的t u n s t a l l 树， 用p ( 力表示双力个叶 结点对应的概率分 布 ，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 + ( 力 很容易由数学归纳法加以证明由t u n s t a l l 树的这个性质容易得出下面这个 引理 引理 3 . 1: 经过歹步扩展的 t u n s t a “ 树，有 p 一 ( j +1 ) =p 一 p + ( j ) 通过这个式子可推出t u n s t a l l 树的嫡的上界和下界，以及其它一些性质. 引理3 . 2: 经过7 步扩展的 t u n s t a l l 树， 有 h ( p ( j ) ) =h ( p ( j 一 1 ) ) + p + ( j 一 1 ) h ( p ) 证明:一棵经过7 一1 步扩展的t u n s t a l l 树， 在进行第7 步扩展时， 一定选 择概率为p + ( i ) 的叶 结点为扩展点， 而其余的叶 结点保持不变， 所以 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 ) 注: 根据 约以 由 这个引理可以看出每扩展一次，t u n s 七 a l l 树的嫡就增加p + ( j ) h ( p ) , p + ( 7 ) - v 二 兴i p - 命可 ， 可 知 扩 展 次 数 ， 每 增 加 一 次 ， h ( p (j ) ) 的幅度向上增长并趋于 十 。 1-丫7-t 一了去一rj 引理 3 . 3: h( p 仃 ) ) =n 汀 ) h( p ) 证明:这个引理是参考文献i l l 中引 理2 的一个特例， 下面我们给出一个新 的证明， 根据引理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 树的扩展过程中 内结点， t u n s t a l l 故l , p + ( o ) ( p + ( o ) = 每扩展一次后概率最大的叶结点就变为相应的 p + ) , p + ( 1 ) , ， p + (一1 ) 就是经过 ? 次扩展的 树对应的j +1 个内 结点的概率，由 命题2 . 1 ， 知引理成立. 口 注: 引 理3 .3 反映了 经过7 步扩展的t u n s t a l l 树的 嫡、 信源嫡和平均消息长 度三者之间的关系.更进一步， 以表示如下: h ( p ( j ) ) 以 上两个引 理说明了h ( p ( j ) ) 的渐进性质可 。 (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 几几 对上面两个不等式两边取对数后乘以一 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)+ 黯 证明:根据引理3 .2 , h ( p ( j ) ) 二h ( p ( j 一1 ) ) +p + ( : 一1 ) 1 3 ( p ) ， 再根据定理 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 一 不在这个范围时， 这两个上界无确定的大小关系. 由 码率的定义和引理3 .3 , 经过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 码的 码率的上界和下界 设两个参数 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 不在这个范围内 时， 根 据引 理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 ) 刀 + ( ， ) ， 。 + ( ， ) 刀 + ( ， ) ， 界要优于定理3 . 1 给出的 上界 当扩展次数， 较小时， 综上所述，定理成立. 因此定理3 .4给出的上 码率的上界仍然是存在 的 ， 不 能 简 单 地 看 作 + 00 . 。 + (， ) 和 。 + (; ) 大 小 关 系 取 决 于 lo g 兴 毛 兴 一 群 兴 资 的正负， 根据不等式 牛 、 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 步扩展的t u n s t a l l 树， 如果用d 切 表示叶结 点 的 概 率 分 布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 侧力的变化情况刻画了t u n s t a l l 树叶 结点的概率分布偏离均匀 分布的远近程 度 ， 当7 增大时，d ( j ) 并 不一定 趋于 零、 它的 变 化与 信源分布尸 ， 具体地 说 主要是和p 一 有密切的关系. 例: 当 信源分布尸为均匀分布时， 设想t u n s t a ll 树随着j 的增加由 一棵完 全 树 变为 另 一 棵 完 全 树 的 过程 中 ，d ( 力由 零 开 始 递增 然 后又 递 减为 零， 它 就 这一直往复下去， 可见当j 丹十 、时，d ( j ) 不一定有极限. 我们可以 这么认为，t u n s t a l l 扩展树具有某种平衡能力， 它能把叶 结点 的 概率分布p ( ? ) 平 衡在 均匀 分布q的 周围( 从编码的 角 度讲，t u n s t a l l 码把 出 现概率最接近的消息串 映射成定长码字) ， 因 此d ( 力随， 的 变化反映在图形 上就是在一定的范围内 上下波动. 下面这个定理说明了d ( 力波动的幅度越来 越平缓. 定理 3 . 5: 经过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 ) 根据不等式 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 ) 对上面两个不等式两边取对数后，可得 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 码的码率和扩展次数的关系 如果已 知信源的概率分布尸 ， 需要扩展多少步才能使 t u n s t a l l 码的冗余 度达到预先指定的标准呢? 这是我们应用t u n s t a l l 码进行编码时首先必须解 决的问题.虽然 t u n s t a l l 码的码率在扩展次数趋于无穷时逼近信源嫡，但在 实际应用中必须明确指明t u n s t a l l 树的扩展次数. 我们已经知道，t u n s t a l l 树的结点由内结点和叶结点组成，它满足有序 性川. 如果我们把内 结点 和叶 结点的 概率按照递减的顺序排列， 则这个列表 可分为前后两个部分， 前一部分( 记作z j ( p ) ) 包括所有的内 结点， 且它的顺 序和扩展点的先后顺序一样; 后一部分( 记作 j ( p ) ) 包括所有的叶结点. 例:在图1 所示的t u n s t a l l 树中，将所有结点按概率递减的顺序排列，为 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 个点为内结点，它的顺序和这棵t u n s t a l l 树的扩展点的先后顺序一 样，后5 个点为叶结点. 在 有 效 性的 条 件下， 即叶 结点 个 数m满 足d ” 一 ( k一 2 ) md 0 , n 为 码 长 ; 其 内 结 点 个 数a =鬓 注 告 ， 扩 展 次 数; = 。 一 1 . 换 句 话 说 ，寿 沪) 有 。 个 元， ， ( 尸 ) 有m个 元 我们先给出k叉完全概率树的定义. 定义 5 . 1: 如果一裸 k叉树按照以下步骤生成: 1 ) 由p= p i , p 2 , ， 二 ， p it 生成一棵深度为1 的k叉树， 哟把第1 步生成的树贴在由 前面d 一1 步形成的 树的每一个叶 结点上. 那么我们称这样的概率树为 k叉完全概率树. 在t u n s t a l l 树中，任何结点: 的概率都可以表示为 p i ( 7 ) 一 讨 12p 1l, p 2二 、 ixh 的形式，其中 1 1 +1 2 +一+l k =n i ( 力 n i ( 力为结点 的深度. 如果把下面的 多项 式展开， 同 时不 合并同 类项( 即 每一 项系 数为1 ) 1 + ( p ， 十 p 2 + ， 二 + p 动+ ( p i + p 2 + p k ) 2 + + ( p ; 十 p 2 + 十 p h ) d 则这个多项式的每一项都对应k叉完全概率树中某个结点的概率. 因 为每一 项 都 具有p i ( 力的 形式， 所以 可 能 是某棵t u n s t a l l 树的 结点. 这样一 来， 结点 的概率就和多项式联系起来. 定理5 . 1: 一棵t u n s t a l l 树的结点总数泡括内 外结点 夕 不大于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 树的内 结点数为d ， 叶 结点数为d ( k一1 ) +1 ， 结点总数为 d 十 d ( k一 1 ) +1 . 但t u n s t a l l 树每扩展一次后不一 定 最大深 度就加1 ， 所以 扩 展d 一1 次后其 最大深 度小于 等于d ， 但结点总 数仍为d + d ( k一1 ) +1 . 由 此 可 见， 结点总 数不大于d 十 武 k一1 ) +1 个的t u n s t a l l 树的 深度一定不 超过 d ， 引 理成立口 这个定理说明了如果把深度为d 的k叉完全概率树的所有结点依概率 递减的 顺序排列， 则列表中的前d 个结点一定是由p生成的t u n s t a l l 树的内 结点. 定义5 . 2: 在给定的冗余度 :下，称 t u n s t a l l 码是 。 一最优的， 如果这个 t u n s t a l l 码的码率 r ( 力 h( p ) +e 定义 5 . 3: 在所有的: 一最优的 t u n s t a l l 码中，定义最小的扩展次数 j=m i n j : r ( j ) h ( p ) +: 如果已知信源概率分布 尸和冗余度: ， 下面给出一个寻找j的算法， ( 0 ) 选择 码长的初 值n o ， 一 般取二 。 =r l ogd i ,1 0 9 d深度的 初值d =。 。 . ( 1 ) 根据深度为d 的k叉完全概率树的每一结点的概率对应多项式 1 + ( p i + p 2 + + p 司+ ( p i + p 2 + + p k ) 2 + + (p i + p 2 + + p k ) d 的 展开 式的每 一项( 注 意展 开时 不合并同 类项 ) ， 数是 1 +k+k2 + +kd 二 把每一项存入数组b . b k d + 1 一1 k 一 飞 ( 2 ) 对数组b按照从大到小的顺序进行排序，只需排出 最大的前d 个元. ( 3 ) 令 码 长n = n o . ( 4 ) 根据有效性的 条件 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 =a 一1 ， 退出; 否则，。 +l - 。 ， g o t o ( 4 ) . 我们可以根据这个算法很快地确定: 一最优的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 , 数例 采用二 元 码进行编 码( 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 所以可以确定最小的扩展次数 i 如果: =0 .1 ， 通过算法计算知当 所以可以确定最小的扩展次数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