对于紧致码在三种编码方法下的编码特性研究2600字
对于紧致码在三种编码方法下的编码特性研究2600字 本文针对一种被称为紧致码的特殊的信源空间分布，基于Shannon，Fano和 Huffman三种编码方法，并分别对其进行了证明，发现对于某种特殊的信源分布 的紧致码，平均码长与其信源概率分布有关。同时通过引入Huffman tree构造方 法证明了Huffman编码方法的情况，简化了对于这种特殊的信源分布的紧致码编 码过程。摘要：
一、引言 21世纪，国际社会已进入信息化时代。信息论作为信息科学和技术的基本理 论，犹如信息科学大厦的地基，在信息社会中占据越来越重要的地位。信息论的 创始人Shannon，他在 1949 年发表了《保密通信的信息理论》，是每一位研究 信息学者必读的一篇文章[1]。随着信息技术的发展， 编码技术已经在媒体技术、 网络技术、无线通信技术、数字电视技术等方面得到广泛应用[2]。信息论、错 误控制编码和密码学是现在数字通信系统中的三大支柱。信息论基础是应用概率 论、随机过程和近世代数等方法研究信息的存储、传输和处理中一般规律的学科， 主要解决通信过程中信息传输的有效性、可靠性与安全性的问题，是信息科学和 通信科学领域中的一门基础理论[3，4]。
信息论将信息的传递作为一种统计现象来考虑，给出了估算通信信道容量的 方法。信息传输和信息压缩是信息论研究中的两大领域。紧致码在信息论的研究 中有着至关重要的作用，并且具有重大实际意义。
本文的目的是用信息论观点对紧致码进行若干研究，以Shannon，Fano和 Huffman三种编码方法为例，分别介绍它们的编码原理以及相关证明，进一步得 出结论。
二、紧致码 这里我们介绍一种特殊的信源分布，如果其中各消息概率满足pi 其中hi为任意正整数，对信源进行二进制编码，该编码为最佳编码，或者说 获得码是紧致码[5]。编码效率。
式中H(X)=-∑pilog2pi为信源熵，r为码符号数，这里考虑二进制编码，r=2， 为编码后平均码长，定义表达式为。
从平均码长的角度出发，对于给定信源，使平均码长达到最小的编码方法， 称为最佳编码，得到的码称为最佳码，即紧致码。
本文考虑信源的每个消息的概率满足，信源消息编码后的码长为ni=hi，则 编码效率为 下面我们将对上述结论进行证明。
三、三种编码法及其证明 3.1 对于Shannon编码的证明 首先介绍Shannon编码方法。步骤如下：
(1)将信源发出的M个消息，按其概率递减顺序进行排列，得 P(x1)≥p(x2)≥…≥p(xM) (2)计算出各消息的-logp(xm)值，m=1，2，…M;
(3)根据-logp(xm)≤nm<-logp(xm)+1。(-logp(xm)为整数时取等号)，计算 出每个消息的二进制代码的长度nm(m=1，2，…，M)，nm，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的排列。下面我们考虑这种序列所具有的特 性，可得出如下结论：