信息论实习报告

1、信 息 论 实 习 报 告一、 香农编码1. 程序设计题目：对某一个信源y用香农编码编成二元变长唯一可译码。例如：取信源y=(y0,y1,y2,y3,y4,y5,y6,y7,y8).相应的概率为 p=（0.49,0.14,0.14,0.07,0.07,0.04,0.02,0.02,0.01）。2. 程序设计方法：第一步：按概率从大到小的顺序输出信源y。第二步：利用公式li=-p(yi)(取上整)确定码长。第三步：为编成唯一可译码求p（yi）的累加概率pi。第四步：把pi化为二进制数，乘2取整。第五步：根据码长li确定第四步中for循环的次数，最终得到码字。3. 程序的设计中遇到的问题及解决办法

2、：本程序设计最关键在于码长公式的c语言编码实现和如何在编程中实现小数向二进制数的转换。在一开始意识到-p(yi)= -p(yi)/ (2)的问题后，我在编程中首先遇到的问题是如何取整的问题。一开始因为对c语言编程的不熟悉在 这句代码中没有对int加括号。4. 程序中的主要函数： （1） 主函数main().且香农编码的实现比较简单所以没有用到子函数。 （2） 求码长的编程实现：（3）利用累加概率pi求的码字的编程实现： 5. 流程图：6. 源程序如下：7.运行结果截图：二、费诺码1.程序设计题目：对某一个信源x用香农编码编成二元变长唯一可译码。例如：取信源x=(x0,x1,x2,x3,x4,x

3、5,x6,x7,x8).相应的概率为 p=（0.14, 0.49, 0.07, 0.04, 0.14,0.02, 0.07,0.02,0.01）。2. 程序设计方法：第一步：将信源x发出的n个消息符号按其概率的递减次序依次排列。第二步：将依次排列的信源符号依概率分成两组，使两个组的概率和近于相同，并对各组赋予一个二进制代码符号“0”和“1”（编m进制 码就分成m组）。第三步：将每一个大组的信源符号进一步再分成两组，使划分后的两个组的概率和近于相同，并又分别赋予两组一个二进制符号“0”和“1”第四步：如此重复，直至每组值只剩下一个信源符号为止第五步：信源符号所对应的码符号序列即为费诺码3. 程序

4、的设计中遇到的问题及解决办法：在进行费诺编码的过程中首先遇到的问题是如何进行分组，利用变量i从的值把信源符号分为两组，前i个信源符号序列为一组进行概率求和s1,剩下的信源符号为一组进行概率求和s2。当s1和s2之差的绝对值为最小的时候确定分组。前i个信源符号相应的码字在这一列上赋值为0，剩下的信源符号相应的码字在这一列上赋值为1。在进行费诺编码的过程中遇到的最大的问题就是递归，在最初分为两组后，调用子函数bianma（），确定第一组每个信源符号对应的二元变长码字第一位上是“0” ，并且确定第二组每个信源符号对应的二元变长码字第一位上是“1”。再对两个大组分别进行分组，重复前面的步骤，直到每一组

5、只剩一个信源符号进行赋值后，输出每个信源符号对应的二元符号序列。从而得到相应的费诺码。4. 程序中的主要函数：（1） main()本函数实现的主要功能有：实现需要编码符号的个数和相应概率的的输入；对输入的概率进行降序排序；调用bianma（）函数对排序后的概率进行编码并输出编码结果。（2） bianma（）本函数实现对相应的信源符号的分组，并且根据分组得到相应的二元变长的编码符号序列，在此函数中还会递归的用到bianma（）本身，直到每组只剩下一个信源符号，从而完成编码。5. 源程序运行结果截图：6. 流程图：7. 源程序如下：三、 尾随后缀的唯一可译码1. 程序设计题目：利用sardinas

6、-patterson算法将码c中所有可能的尾随后缀组成一个集合f，当且仅当集合f中没有包含任一码字，便可判断码c为唯一可译码。反之，码c不是唯一可译码。2. 程序设计思想方法：a.a.sardinas和g.w.patterson于1957年提出下述算法用于判断码c的唯一可译性此算法的原理如下所示： 其中ai,bi都是码字。可知，当且仅当某个有限长的码符号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时b1一定是a1的前缀，而a1的尾随后缀一定是另一码字b2的前缀；而b2的尾随后缀又是其他码字的前缀最后，码符号序列的尾部一定是一个码字。设c为码字集合，按以下步骤构造此码的尾随后缀集合f：

7、 (1) 考查c中所有的码字，若wi是wj的前缀，则将相应的后缀作为一个尾随后缀放入集合f0中； (2) 考查c和fi两个集合，若wjc是wifi的前缀或wifi 是wjc的前缀，则将相应的后缀作为尾随后缀码放入集合fi+1中； (3)f=fi即为码c的尾随后缀集合； (4) 若f中出现了c中的元素，则算法终止，返回假(c不是唯一可译码)；否则若f中没有出现新的元素，则返回真。3. 程序中的主要函数:(1)main()本函数实现的主要功能有：实现需要码字的个数和码字集合的输入；码字集合本身是否含有重复码字的检验，调用houzhui（）函数后缀集合fi。判断fi和源码字集合是否有相同元素，从而判断原码字集合是否为唯一可译码。(2)houzhui（）本函数实现对两个码字是否存在后缀的判断，并且生成fi中的元素。4.流程图：5.源程序如下：6. 程序的设计中遇到的问题及解决办法：在设计本程序的过程中遇到的最大的问题是尾随后缀的截断问