信息论基础第三章~第七章

《信息论基础第三章~第七章》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、3.4算术码香农一费诺码在3.2节中我们证明了码长取为/(X)=时满足克莱夫特不等式，因此可用来构造唯一可译码。本节要介绍一种利用累积分布函数来分配码字的构造编码方法，通常称为香农一费诺方法。设信源随机变量X取值于字符集/={1,2，...，m}，不失一般性，设对所有xe义有/?(x)〉0定义累积分布函数a

2、这就提示我们可以用F(x)作为的碍字，比如用F(x)的二进小数表示。但通常戸(x)是实数，它未必能用有限多位二进制小数来表出，那么能否用近似表示呢？如用F(x)的二进制小数表示中前/(%)位来近似表示,我们把它记为F(^)L」/(x)则它和F(x)的差距应满足以下不等式.比如取/(%)=log+1时有—r-v-r

3、度为2_/u)^

4、+l)

5、积概率F㈦穆£累积概率F(x)P川的u进表示码w㈤二10.25(1/1)0.250,125(1/3)0.00132叫1/2)0.750,5(1/210.1230325(1/8)■50.8125(13/16)(L110110.0655(1/16)0,93750.90625(29/32)0.11101550▼叫1/16)L00,96^5(31/32)O.illll5平均码长-1111L=3--4-2•-b4»—}2•5—2.87542810而信源熵为1111^(Ar)•=-log4+-log2+-lag8+2—log16=L87542o丄b所以

6、，L=H(X)1v例3.4.2当F(.t)的二进小数表示是无穷循环小数时，我们把无穷懈环小数0.01010101…雕记为0.UT,我们只需第一个循环节的数字就够丁.rF(r)M的二进表示Z(2)=[lo十1码字10J50.250,1250,001300120:25L50.3750.0113OilD：2f).70.6ojooTT,1100110.150.E50.775〔)•1lOOOH411()0u0.151.0OJiioTio411)0平均码长L==3.3比特倍源熵H(X)=2/28比特，平均码长比信源熵多L22比特与例3.3.1的哈夫曼码

7、相比，这里的平均码长多1.2比特。在3.3节中讨论哈夫曼码时，我们曾提到要进一步提髙编码效率，需对长的信源序列来编码，这对香农…费诺码也是对的，即对信源输出的n长符号列V=(6，易，…，)用香农…费诺方法进行编码，这种编码称算术码。其基本方法是要找一个计算％”的概率分布p(x")和累积分布函数厂(^)的快速算法，然后用香农…费诺方法对Z进行编码。实际上就是用区间(F(x,?)-p(xnF(X，?)］中的一个数的二进制数字表示作为x"的码字。由于对不同的这样的区间是不相交的，因此它们对应的码字也不同，但这样选取的碍字集不能保证一定是即时码

8、。如果利用四舍五入到+1比特来表示Z,可以保证得到即时码。以下我们介绍一个简化的计算程序来理解算木码编译码的基本要点，不失一般性，我们仅考虑二进信源，即信源字母集为义={0，1}。我们要对n长的信源字母列=($，易，…，进行编码。1)先对所有又"e，计算概率P(xn)=/?(%,,x2,.;1)在上建立一个字典序，对分二以，々，…，称/?nx>y，如果在第一个满足A*y,.的第/个分量上人=1,乂=0,这个条件等价于2'>^/2_，,也等价于它们对应的二进小数0;又2..人〉0u2…凡。ii我们用xi)表示义"中在字典序下第Z’个n长向量

9、。2)用一个二叉树来表示(见图3.4.2)A为根结点，每个Y对应第n层上一个结点，从根结点到该结点的路上经过的边上的符号就是$易...',如图中B代表4=(0011),C代表<=