关于信源的tunstall编码方法

《关于信源的tunstall编码方法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、1介绍Tunstall编码是一类重要的信源(变长一定长)编码方法.众所周知，随着扩展次数趋于无穷，Tunstall码的码率趋于信源嫡;并且Tunstall码具有许多与Hufman码相类似的性质.关于Tunstall码渐进最优性的讨论，Fabris等人【1]对于离散无记忆信源给出了当Tunstall码的扩展次数给定时，它的码率的上界和下界.Gallager等人冈证明了广义的Tunstall码对于有记忆信源的渐进最优性，因而从另一方面说明了自适应Tunstall编码的可行性.本文进一步研究了Tunstall码的性质，给出了Tunstall码的码率的新的上界，这些新的上界要优于【1]文给出的上界.

2、本文进一步刻划了Tunstall树和扩展次数之间的一些较深刻的内在联系，在实际应用上，如果已知信源的概率分布，我们用Tunstall码进行编码时，非常想知道需要扩展几步就可以使码率接近信源嫡，为此作者设计了一个在一定条件下求:一最优的扩展步的算法.2关于'Install码的基本知识设离散平稳无记忆信源的信源字母表A二{a,,a2,.，,ax},K>2，我们由A可以建立一棵扩展树，它的生成步骤如下:伪以A中的所有字母作为叶结点形成一棵深度为1的树则共有K个叶结点和一个根结点.J)在前面7一1步形成的树中选择一个叶结点作为扩展点，把第0步生成的树贴上去，保证根结点和扩展点重合.则扩展i步之后，扩

3、展树的叶结点个数记为T(j)二K+j(K一1)如果A的概率分布为P={P1,P2,⋯,P对，这里。

4、母的词序为a,>。:>一>a们选择词序最靠前的叶结点作为扩展点.我们把除叶结点之外的其余结点称为内结点(包括根结点)如果内结点的个数为。，则叶结点的个数也可记为M=a(K一1)+1，这种表示法与T(7)是等价的，且。二少十1如果码字符号集是B={b,户。，⋯，与}，D>2(一般D=2).经过，步扩展的Tunstall树一共有T(j)个长度不相等的消息串，把它们编为定长码字，则最恰当的码长为L(7)=1109DT(7)]，这种码就称为Tunstall码;为了保证编码的有效性，最大限度的使用每一个码字，Tunstall扩展树的叶结点的个数必须满足D”一(K一2)<到力

5、stall编码的有效性条件.例如果A={a,b},F=10}6,0.4}，取B={0,11，下图是经过3步扩展的Tunstall码0.216旧几几一0000(1.)60.144住0014aababo.010ba24root0(2.b4)<一0110.16bb一100图1.P=(0.6,0.4),j=3的Tunstall树这棵Tunstall树有4个内结点(root,a,b,aa，5个叶结点(aaa,aab,ab,ba,bb),即‘a=3,a=4,M=5,码长L=1109251=3，所以我们进行以下的变长一定长编码:aaa升000，aab开001,ab--+010,ba-011,品--}100

6、定义2.2:经过7步扩展的Tunstall树，记洲力是叶结点a对应的概率，-,(j)是叶结点i的深度，则编码的平均消息长度T(j)。(，)=艺p+(7)-a(i)留=]在上例中，n份)=0.216x3+0.144x3+0.24x2+0.24x2+0.16x2=2.36定义2.3:经过7步扩展的Tunstall码的码率L，R2Jl-一，--J一n?︺在上例中，R(j)一赢、1.27下面这个性质与Hufman码的平均码长等于Hufman树中所有内结点的概率之和是一致的.命题2.1(6J:如果毛阴)表示Tunsta“树中所有内结点的集合，则Turislall编码的平均消息长度等于所有内结点的概率之

7、和，即n(j)=艺p+.(?)-ETj(P)这里p.(7)是每个内结点对应的概率.在上例中，创力=1+0.6+0.4+0.36二2.36，这与定义2.2计算的结果一致.3Tunstall码的码率的上界和下界在信源概率分布P={pl,P2,.二，pi'}中，记p=min{p;:pieP,1