- 1 -
Tunstall编码与自适应编码算法
王东昊
北京邮电大学，北京 （100876）
摘 要：Tunstall码是 Tunstall在 1968年提出的一种 V-B码，其使用前提是信源的静态特性
和无记忆特性，但在实际中，信源多是动态变化的，此时就需要对 Tunstall码进行修改。传
统的方法是根据新的信源概率分布构造新的 Tunstall 码，但在很多情况下，只需要对原
Tunstall 码进行适当的修改即可，这种方法被称作是自适应的 Tunstall 编码。由于该算法可
以在一定程度上避免重新编码，因此对 Tunstall码来说是一种优化，对 Tunstall码的应用有
很重要的作用。
关键词：Tunstall，误编码，自适应编码
中图分类号：
1. 引言
对于无失真信源编码，现今的大部分文献都将其分为两大类：一类是 B-V 编码，即将等长
的消息序列编为变长的码序列；另一类是 V-B 编码，即将变长的消息序列编为等长的码序
列。Huffman 编码是一种典型的 B-V 编码[1]，它的一个重要的理论前提是信源的静态和无记
忆特性。但研究表明，即使不满足上述假设前提（实际的信源多是此类），Huffman 编码也
可以很好的执行其编码功能[2]。与 Huffman 编码相对应的是 Tunstall 编码，这也是本篇论文
讨论的主要内容。
Tunstall 码是 Tunstall 在 1968 年提出的一种 V-B 码，与 Huffman 一样，它适用于静态
无记忆的信源[4]，但在实际应用中，大部分信源都是动态且有记忆的，因此当信源的概率分
布出现变化时，就会随之产生误编码(miscoding)问题[3]，而解决这类问题的办法之一就是使
用自适应的 Tunstall 码，根据信源的概率分布的变化来对 Tunstall 码进行适当的调整。
本论文的第一部分介绍了 Tunstall 码的基本原理和具体步骤，在引入了几个辅助引理之
后，第二部分我们讨论了误编码问题。针对出现的这种问题，第三部分给出了解决的方案----
自适应 Tunstall 编码。第四部分对全文进行了总结。
2. Tunstall 码原理与编码步骤
对于一个给定的信源符号集合 1 2{ , ,... }, 2kA a a a K= ≥ ,我们可以使用下面的算法得到
A 的扩展树。
扩展树算法：
1） 将 A 集合中的符号作为叶节点构造一个深度为 1 的树
………
j） 从第 j-1 步构造得到的树中选择一个叶节点，并用第一步的方法对其进行扩展
使用扩展树算法，经过 j 步扩展之后，树的叶节点的总数为 T(j)=K+j(K-1)（j 为扩展次
数）。而当信源符号集合 A 的每个符号的产生概率 ip 都已知时，我们就可以在上述算法的
基础上产生一个 Tunstall 树，具体方法如下：
1） 将 A 集合中的符号作为叶节点构造一个深度为 1 的树
2） 选择一个概率最大的叶节点进行扩展，且扩展后的叶节点的概率为从根节点到该叶
节点的所有节点的概率之积
- 2 -
3） 如果扩展后的树已满足编码要求，则算法结束，否则回到步骤 2。
在产生了 Tunstall 树之后，就可以用它来对消息序列进行编码了。对任意给定的消息序
列，首先，按照其字母排列顺序在 Tunstall 树中寻找相应的叶节点，然后将该叶节点对应的
码字写出，如此循环进行，直到该消息序列被编码完毕。
为了确保 Tunstall 算法的正确执行，就必须要保证，对每一个字母组合，都能在 Tunstall
树中找到对应的节点，这可以被称作是符号集合的完整性，而同时也要保证任意一个符号组
合都不是其他符号组合的前缀，以避免译码的延迟，我们将这个特性称为异前置性。同时具
有这两个特性的符号集合可以被看作是一个完备的集合[5]，而上述 Tunstall 树算法所得到的
符号集合即是一个完备的集合。
对于 Tunstall 码来说，衡量其性能的一个很重要的参数就是它的编码速率。如果定义
L(j)是编码后的码长，
( )
1
( ) ( ) ( )
T j
i i
i
n j p j n j
=
= ∑ 是消息序列的平均长度，那么 Tunstall 码的编码
速率 R(j)可以表示为 R(j)=L(j)/n(j)。由编码速率的定义可以得到：R(j)越小，数据压缩的程
度就越高。另外，为了更好的描述 Tunstall 码，我们将给出以下的性质：
性质 1：对每一个 Tunstall 编码树 Tj，任意一个内部节点α 的概率都要大于等于任意一
个叶节点β 的概率
证明：如果存在Pr( ) Pr( )α β< ，那在前面的扩展步骤中我们就可以用 β 来代替α 作为
扩展节点，这与给定条件矛盾，所以假设错误，即命题成立。
性质 2：对一个扩展次数为 j 的 Tunstall 树，如果我们在扩展完之前对所有等概率的节
点进行排序的话，那最终得到的 Tunstall 树将是不变的。
证明：假设在一个扩展次数为 j 的 Tunstall 树中存在两个等概率的节点α 和 β 。如果在
某次扩展中我们选择α 作为扩展节点，那接下来的扩展中 β 将会被作为扩展节点，因为它
的概率将会是最大的，所以在两次扩展过后 Tunstall 树的形状是一样的。对于多个节点概率
相同的情况也可以用类似的方法得到相同的 Tunstall 树，因此命题是成立的。
为了方便讨论，本篇论文对 Tunstall 树中的节点按如下的方法进行排序：
设α 与β 是任意两个节点，且它们的概率分别为Pr( )α ，Pr( )β 。那么，
Pr( ) Pr( )
:
Pr( ) Pr( )
α βα β α β α β
<⎧ ⎫∠ ⎨ ⎬< <⎩ ⎭
或者
且 （<表示符号序列在字典中出现的前后顺序）
根据这个假设，在某次扩展中，总能找到一个概率最大的节点，因此对于信源的每一个
概率分布，都可以产生一个独一无二的 Tunstall 树。
3. Tunstall 码的误编码现象
一些引理
设 1 2{ , ,... }kP p p p= ， 1 2{ , ,... }kQ q q q= 为信源符号集合 1 2{ , ,... }kA a a a= 的两个概率
分布向量。 p−， p+分别为向量 P 中的最小值和最大值。
引理 1：设 p pα− +≥ （0 1α< ≤ ），则
log log log log logK p Kα α+ ≤ − ≤ −
证明：由已知条件可得， 1/p K p− +≤ ≤ ，所以
- 3 -
(1/ ) 1/p p p Kα α+ −≤ ≤ ≤
(1/ )p p p Kα α− +≥ ≥ ≥
即 (1/ ) 1/K p Kα α≤ ≤
对上面的不等式取对数，则命题得证。
引理 2：设 ( )p j− 和 ( )p j+ 分别表示叶节点的最小概率和最大概率， p−为符号概率集
合中的最小值，则 ( ) ( )p j p p j− − +≥ 。
证明：当 j=0 时结论显然是成立的。设 j=k 时成立，则当 j=k+1 时，存在两种情况：
（1） ( 1) ( )p k p k− −+ =
（2） ( 1) ( )p k p p k− − ++ =
对这两种情况，都有 ( 1) ( )p k p p k− − ++ ≥ ，由于 ( ) ( 1)p k p k+ +≥ + ，因此可以
得到 ( 1) ( 1)p k p p k− − ++ ≥ + ，即对 j=k+1 时结论仍然成立，所以命题得证。
引理 3 ( ( ) // ( )) ( ) ( // )H Q j P j n j H Q P=
引理 4 设 ( )n j− 和 ( )n j+ 分别表示 Tunstall 树的最小深度和最大深度，并定义一个
Tunstall 树的斜度为 ( )n j+ / ( )n j− ，那么，
( ) log ( )
( ) 1 log ( ) 1
n j p n j
n j p n j
+ − +
− + −≤ ≤+ −
证明：设 ( )jπ 和 ( )jω 为任意两个叶节点的概率，容易得到
( ) ( ) 1
( ) ( )
j p j
j p j p
π
ω
+
− −≤ ≤ （1）
而在一个 Tunstall 树中，长的分支代表了概率较大的节点，短的分支代表了概率
较小的节点，因此可以假设 ( )( ) n jj pπ ++⎡ ⎤= ⎣ ⎦ ，
( )
( )
n j
j pω −−⎡ ⎤= ⎣ ⎦ ，或者
( )
( )
n j
j pω ++⎡ ⎤= ⎣ ⎦ ，
( )
( )
n j
j pπ −−⎡ ⎤= ⎣ ⎦ ，代入不等式（1），从而可以得到结论不
等式。
Tunstall 误编码
在实际中，信源的概率分布都是动态变化的，设信源的初始概率分布为 P，并由此建立
一个 Tunstall 树 T。当信源的概率分布发生变化时（设变为 Q）,利用 T 进行编码就会产生误
编码现象(miscoding)。
有文献证明，当出现误编码现象时，随着扩展次数 j 的增大，编码速率会逐渐逼近
H(Q//P),，另外，根据上述结论也可以得到，当使用两个分别按照概率分布为 P 和 Q 建立的
Tunstall 树对概率分布为 Q 的信源进行编码时，随着扩展次数 j 的增大，它们的速率之差会
逼近 D(Q//P)，我们可以将其看作是不了解信源概率分布而需要付出的代价。
4. 自适应 Tunstall 编码
对 Tunstall 树的检测
误编码对 Tunstall 编码的影响主要分为以下两种：（1）新的概率分布 Q 与初始概率分
- 4 -
布 P 相差不大。在这种情况下，原来的 Tunstall 码仍然是最优的，不需要对它做任何改动。
（2）Q 与 P 差距比较大，此时就需要对原 Tunstall 树进行修改。由此可以看出，需要得到
Tunstall 码的一种检测方法，来确定是否需要对原 Tunstall 树进行修改。
检测的原理
设信源的初始概率分布为 1 2 3 1 2{ , , ,..... }, ......k kP p p p p p p p= > > > 。根据 P 可以构造
相应的 Tunstall 树 T。在构造过程中，按照节点的扩展次序能够得到扩展节点集合
1 2( ) { ( ), ( ),... ( )}j jI P m P m P m P= ， 而 且 可 以 按 以 下 方 法 得 到 集 合
(1) (2) ( )( ) { ( ), ( ),... ( )}j j j jL P P P P
µλ λ λ= ：对每次扩展得到的新节点，取其中概率最大的一个。
当信源的概率分布变为 Q 之后，我们可以通过比较两次扩展中的集合 ( )jI P 与 ( )jL P 来决
定是否需要改动原 Tunstall 树。
检测的步骤
设 P 为初始概率分布，j 为扩展次数，T 为根据 P 得到的 Tunstall 树
（1） 根据 1 中的方法，我们可以得到集合 ( )jI P 与 ( )jL P
（2） 当信源概率分布变为 Q 时，可以类似的得到 ( )jI Q 与 ( )jL Q
（3） 如果(2)中得到的 ( )jI Q 的节点次序与 ( )jI P 相同，且对所有的1 i µ≤ ≤ ，都有
( ) ( ) ( )ij jQ m Qλ ∠ ，那么原 Tunstall 树 T 对于 Q 也是适用的，反之则需要对 T 进行修改。
二进制自适应 Tunstall 算法
在检测的基础上，这一部分将主要讨论实际中比较常见的二进制编码的情况。文献 1
已经证明，对二进制情况的研究可以推广到多进制的情况。在此，假设信源符号集合为
{ , }A a b= （ a b∠ ），可知 { , } { ,1 }a bP p p p p= = − (p 为信源符号 a 的概率，<p<1)。
我们可以根据 p 的大小在（，1）区间内划分若干个 Tunstall 区域。对于两个不同的
概率分布 P 和 Q，如果 Q 与 P 的差距不大，那么根据 P 得到的 Tunstall 编码对于 Q 来说也
是最优的，这就意味着二者在同一个 Tunstall 区域内。反之，如果 P 与 Q 差距比较大，那么
二者处于不同的 Tunstall 区域，就需要对原 Tunstall 编码进行修改[3]。另外，每一个 Tunstall
区域又可以划分成若干个 Tunstall 树区域，其中的所有概率分布所得到的 Tunstall 树是一样
的。二进制自适应 Tunstall 算法的基本原理就是确定不同的 Tunstall 区域，并得到每个区域
的最优的 Tunstall 树。
消息序列的分析
由上面对信源符号的假设可以很容易的看出，每一个信源序列都是下面的三种情况之
一：
a. 序列只由符号 a 组成。对于由 t 个 a 组成的信源序列可以表示为 ta ，概率= tp
b. 序列只由符号 a 组成。对于由 t 个 a 组成的信源序列可以表示为 tb ，概率= (1 )tp−
c. 序列同时包含符号 a 和符号 b。如果序列中有 s 个 a 和 t 个 b，那么它的概率为
(1 )s tp p−
- 5 -
算法的原理
对于某一个固定的概率分布 P，我们总是可以得到它的最优的 Tunstall 码树，并根据前
面提到的方法得到集合 ( )jI P 与 ( )jL P 。当符号 a 的概率逐渐变化时，会存在两个结点的概
率逐渐接近并相等，这就会引起结点次序的变化，并有可能改变 Tunstall 树和 Tunstall 区域。
下面，根据不同的情况进行讨论：
a 如果两个概率接近的结点都属于集合 ( )jI P ，那么随着两个结点概率的接近会使得
内部结点之间发生位置上的变化，从而导致 Tunstall 树区域的变化，但这种情况不会影
响树的结构和码字。
b 两个结点，一个属于集合 ( )jI P ，另一个属于集合 ( )jL P 。随着两个结点概率的接
近会导致叶结点与内部结点位置的交换，这必然会导致树区域的变化，而由于树的结构也发
生了变化， Tunstall 区域也会发生变化，我们就需要对旧的码字进行更新。
c 两个结点都属于集合 ( )jL P 。文献 1 证明，在这种情况下，如果结点是单纯由 a
或者单纯由 b 构成的，那么树区域不会变化；如果结点是由 a 和 b 混合构成的，树区
域会发生改变。但树的结构和码字保持不变。
由上面的分析可以看出，二进制 Tunstall 自适应算法的核心是寻找每一个 Tunstall 树区
域的边界和每一个 Tunstall 区域的边界，下面，我们根据参考文献，直接给出这两个区域的
搜索算法
Tunstall 树区域搜索算法：
1α ， 1β ，……. hα ， hβ 为一个 Tunstall 树中的 h 对全部由 a 和全部由 b 组成的结点，
且每一对结点的概率都比较接近。设 iα 和 iβ 不全是集合 ( )jL P 中的元素，并有
( ) ( )i iPb Pbβ α> 。如果 is+是等式Pr( ) Pr( )i iβ α= 在区间（,1）上的解（p 逐渐增大），
S + 是所有的 is+组成的集合，那么该 Tunstall 树的上界为 min{ , }t i iP s s S+ + + += ∈ 。同理，令
p 逐渐减小，可以得到该 Tunstall 树的下界。
Tunstall 区域搜索算法[3]：
a) 根据上面的 Tunstall 树区域搜索算法求得 Tunstall 树的上界。
b) 如果根据(a)中求得的上界能够使得两个分别属于集合 ( )jI P 和 ( )jL P 的结点位置
互换，那么 Tunstall 区域的上界 TP+ = tP+
c) 如果(b)中的情况不成立，那么寻找两个结点α 和 β ，使得等式Pr( ) Pr( )β α= 的
解为 tP+，并互换这两个结点的位置
d) 使用(c)中得到的 Tunstall 树，回到步骤(a)。
5. 总结
Tunstall 码是一种典型的 V-B 码，该码的优点是输出速率恒定，不存在 Huffman 码的差
错传播问题，但它的一个很重要的假设前提是信源概率分布的不变性，当信源的概率分布随
时间变化而变化时，便很容易产生误编码现象。
本篇论文详细阐述了 Tunstall 码的编码原理，并说明了误编码现象产生的原因。针对这
个问题，在论文的第三部分讨论了基于信源概率分布的自适应编码算法,该算法的主要目的
- 6 -
是根据信源概率分布的变化来调整 Tunstall 树的结构，通过划分 Tunstall 树区域和 Tunstall
区域，可以根据 p 的变化调整 Tunstall 树，以避免重新编码，达到优化编码的目的。
参考文献
[1] and ,Elements of Information Theory. New York:
[2] and ,”Data Compression”,ACM Comput Surv.,,no 3,-294,
[3] Francesco Fabris and Rudy Pauletti,”Tunstall adaptive coding and miscoding,”IEEE Information
Theory,,,November,1996
[4] Frederick Jelinek and Kenneth ,”On variable-length-to-block coding”, IEEE
Information Theory,-18,,November 1972
[5] and ,”Algorithm for source coding”,in Coding and Complexity,,Ed New
York:Springer-Verlag,1976
Tunstall Coding and Adaptive Coding Algorithm
Wang Donghao
Beijing university of posts and telecommunications，Beijing （100876）
Abstract
The Tunstall code is a V-B code that invented by Tunstall in 1968, whose premises is the static identity
and memoryless identity of the source. However, the source in practical are more likely to be dynamic,
so it is necessary to modify the code. The traditional method is constructing new code with the source
that has changed, but in many cases, we only need to modify the former code, which we can call it the
adaptive method. As this method can avoid re-coding in some extent, it is an optimization to the
Tunstall code, and will play an important role in the use of the Tunstall code.
Keywords：Tunstall，miscoding，adaptive coding
