对于紧致码在三种编码方法下的编码特性研究

开篇：润墨网以专业的文秘视角，为您筛选了一篇对于紧致码在三种编码方法下的编码特性研究范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘 要：本文针对一种被称为紧致码的特殊的信源空间分布，基于Shannon，Fano和Huffman三种编码方法，并分别对其进行了证明，发现对于某种特殊的信源分布的紧致码，平均码长与其信源概率分布有关。同时通过引入Huffman tree构造方法证明了Huffman编码方法的情况，简化了对于这种特殊的信源分布的紧致码编码过程。

关键词：紧致码；Shannon；Fano；Huffman；Huffman tree

DOI：10.16640/ki.37-1222/t.2015.24.247

1 引言

21世纪，国际社会已进入信息化时代。信息论作为信息科学和技术的基本理论，犹如信息科学大厦的地基，在信息社会中占据越来越重要的地位。信息论的创始人Shannon，他在 1949 年发表了《保密通信的信息理论》，是每一位研究信息学者必读的一篇文章[1]。随着信息技术的发展， 编码技术已经在媒体技术、网络技术、无线通信技术、数字电视技术等方面得到广泛应用[2]。信息论、错误控制编码和密码学是现在数字通信系统中的三大支柱。信息论基础是应用概率论、随机过程和近世代数等方法研究信息的存储、传输和处理中一般规律的学科，主要解决通信过程中信息传输的有效性、可靠性与安全性的问题，是信息科学和通信科学领域中的一门基础理论[3，4]。

信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的方法。信息传输和信息压缩是信息论研究中的两大领域。紧致码在信息论的研究中有着至关重要的作用，并且具有重大实际意义。

本文的目的是用信息论观点对紧致码进行若干研究，以Shannon，Fano和Huffman三种编码方法为例，分别介绍它们的编码原理以及相关证明，进一步得出结论。

2 紧致码

这里我们介绍一种特殊的信源分布，如果其中各消息概率满足pi

其中hi为任意正整数，对信源进行二进制编码，该编码为最佳编码，或者说获得码是紧致码[5]。

编码效率

。

式中H（X）=-∑pilog2pi为信源熵，r为码符号数，这里考虑二进制编码，r=2，为编码后平均码长，定义表达式为。

从平均码长的角度出发，对于给定信源，使平均码长达到最小的编码方法，称为最佳编码，得到的码称为最佳码，即紧致码。

本文考虑信源的每个消息的概率满足，信源消息编码后的码长为ni=hi，则编码效率为

下面我们将对上述结论进行证明。

3 三种编码法及其证明

3.1 对于Shannon编码的证明

首先介绍Shannon编码方法。步骤如下：

（1）将信源发出的M个消息，按其概率递减顺序进行排列，得

P（x1）≥p（x2）≥…≥p（xM）

（2）计算出各消息的-logp（xm）值，m=1，2，…M；

（3）根据-logp（xm）≤nm

（4）为得到唯一可译码，计算出第m个消息的累加概率，再将pm变换成二进制小数，取小数点后面nm位作为第m个消息的代码组（码字）。

然后我们考虑上面介绍的紧致码。记离散信源，其中满足，对其进行Shannon编码[6]，由第三步可知，任一信源xi其对应的二进制代码长度nm=-logp（xm）=hi，这就是我们要证明的对紧致码进行Shannon编码后每个信源对应的码长为hi。

3.2 对于Fano编码的证明

对Fano编码的思路与Shannon编码类似。首先介绍Fano编码方法[7]。步骤如下：

（1）信源发出的M个消息，按其概率递减顺序排列，得

P（x1）≥p（x2）≥…≥p（xM）

把消息集{x1，x2，…xM}按其概率大小分解成两个子集，使两个子集的概率之和尽可能相等，把第一个子集编码为0，第二个子集编码为1，作为代码组的第一个码元；

（2）对子集做第二次分解，同样分解成两个子集，并使两个子集概率之和尽可能接近相等，再把第一个子集编码为0，第二个子集编码为1，作为第二个代码组的码元；

（3）如此一直进行下去，直到各子集仅含一个消息为止；

（4）将逐次分解过程中得到的码元排列起来就是各消息代码。

下面证明作上述操作后得到的每个消息对应的码长为hi。

由上述步骤可知，经过n次分解后得到的消息xi其对应的码长一定为n，于是问题转为证明对应概率为的消息需要hi次分解后得到的子集仅含该消息。为简便，以下将把某个消息经过分解后得到的子集仅含该消息简称为将该消息分出来。

由Fano编码步骤可知，进行第n次分解，会得到2n个子集，其中每个子集中所包含消息概率和为2-n，现在考虑第hi次分解，将会得到个子集，其中每个子集中所包含的消息概率和为，可知概率为的消息将会在本次分解中被分出来。也即概率为的消息将在第hi次分解中被分出来。

由上述可知对于紧致码用Fano编码法进行编码后每个信源对应的码长也为hi。

3.3 对于Huffman编码的证明

同样首先引出Huffman编码[8]。将信源符号按概率递减的次序排列；

（1）将概率最小的两个符号连在一起。将这两个符号的概率之和写在他们的结合节点上。将这两个分别标记为0和1；

（2）将这两个概率和看作一个新符号的概率。重新排列信源符号，并将概率最小的两个信源符号，将他们绑定在一起构成一个新的概率。每一次我们把两个符号结合在一起是符号总数减1。每当把两个概率结合在一起时，总是把两个分支标记为0和1；

（3）将此过程继续下去直至只剩一个概率，就完成了Huffman树的构造；

（4）对于任意符号的码字，找到从最后节点到该符号的一个路径，反向追踪路径并读出分支的码字，即为该符号的码字。

下面开始证明。

首先我们考虑最特殊也是最理想的一种情况，信源概率分布如表1所示，

对于这种信源分布显然每个信源编码后的码长为hi。

上述讨论的概率分布是对于的概率分布最特殊也是最基本的情况，一切其他的情况都是有此种情况转化而来。换句话说任何概率分布为的概率均可以转化为从2-1，2-2，一直排到2-M+1，2-M+1的排列。下面我们考虑这种序列所具有的特性，可得出如下结论：

对于一个信源空间X，其概率分布为

其中hi为任意正整数。将其按概率降序排列为

p1≥p2≥…≥pM

其中M为消息个数。那么其最小的两个概率和必定是相等的。举个简单例子，概率从大到小为1/2，1/4，1/8，1/16，1/16。如果只有一个1/16，那么前三项加起来应该是15/16，但前面三项中最小的也是1/8，怎么相加都不会加到15/16。

下面用反证法进行证明。

假设有pM-1>pM即hM-1

现在回到Huffman方法。由上面的结论可知，对于上述的一个信源空间进行Huffman编码，每一次合并重排后，最下面的两个信源符号，也就是概率最小的两个信源的概率一定是相等的。因为每一次合并重排后，原信源空间会形成一个新的信源空间，原来概率最小的两个信源符号合并成一个新的信源符号，也就是说形成一个新的概率分布，由于相加的两个概率相等，则相加得到的新的概率仍然满足p=2-h，也就是说新的概率分布仍然满足，则同样满足结论。这个结论当我们引入Huffman tree的概念后对证明就会变得极其有用。

下面先介绍一些树的基本概念，然后引出Huffman tree的概念。

（1）路径和路径长度。在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

（2）结点的权及带权路径长度。若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

（3）树的带权路径长度。树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

然后是Huffman tree的构造。

假设有n个权值，则构造出的Huffman tree有n个叶子结点。n个权值分别设为w1w2……wn，则Huffman tree的构造规则为：

（1） 将w1w2……wn看成是有n棵树的森林（每棵树仅有一个结点）；

（2）在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

（3）从森林中删除选取的两棵树，并将新树加入森林；

（4）重复（2）、（3）步，直到森林中只剩一棵树为止，该树即为所求得的Huffman tree。

此时在看结论2我们会发现，在Hufuman tree中每个节点的两个子节点权值，在这里也就是信源符号对应的概率一定是相等的，举个例子就是如图1所示。

也就是说，从根结点开始进行分支，每i次分支得到的两个子节点概率为2-i，反之概率为的节点一定是经过第hi次分支得到。由于Human tree的定义，某一结点的路径长度就等于得到该节点所需的分支次数，因此对于紧致码每个概率为的信源进行Huffman编码后其码长一定为hi。

4 结论

本文针对一种被称为紧致码的特殊的信源空间分布，分别用Shannon，Fano和Huffman三种编码方法对其进行了证明，发现对于某种特殊的信源分布的紧致码，平均码长与其信源概率分布有关。我们引入Huffman tree构造方法证明了Huffman编码方法的情况，简化了对于这种特殊的信源分布的紧致码编码过程，具有重要的实际意义。

参考文献：

[1]王鹤鸣.从信息化发展历程看密码学发展――专访西安电子科技大学通信工程学院王育民教授[J].信息安全与通信保密，2011（11）：13-19.

[2]邓家先.与编码课程教学改革探讨[J].电子教学学报，2007（02）：111-114

[3]陈运.信息论与编码[M].北京：电子工业出版社，2007.

[4]D CMacKay.Information Theory，Inference，and Learning Algorithms[M].Cambridge： Cambridge University Press，2000.

[5]曹雪虹，张宗橙.信息论与编码[M].北京：清华大学出版社，2004（03）.

[6]曲炜，朱诗兵.信息论基础及应用[M].北京：清华大学出版社，2005（01）.

[7]沈世镒，吴忠华.信息论基础与应用[M].北京：高等教育出版社，2004.

[8]傅祖芸.信息论――基础理论与应用[M].北京：电子工业出版社，2001.

[9]马秋芳.关于离散无记忆信源的最佳编码问题[J].江汉石油学院学报，1987.

项目：江西省省级教改项目（编号：JXJG-12-1-17） 和南昌大学学位与研究生教育教学改革研究项目（编号：YJG2012002）资助的课题。

*为通讯作者