信息论课程设计报告

1、成绩：2016-2017 学年第 1 学期信息论课程设计学院名称：班级学号：学生姓名：教师姓名：2016 年 12 月一、判定唯一可译码1. 任务说明输入：任意的一个码 （ 即已知码字个数及每个具体的码字 ）输出：判决结果（是 / 不是）输入文件 : ，含至少 2 组码，每组的结尾为” $”符输出文件 : ，对每组码的判断结果说明：为了简化设计，可以假定码字为 0，1 串2. 实现原理判断方法：将码 C中所有码字可能的尾随后缀组成一个集合F,当且仅当集合F中没有包含任一码字，则可判断此码 C为唯一可译变长码。构成集合F:首先观察码C中最短的码字是否是其他码字的前缀。若是，将其所有可能的尾随后缀

2、排列出。就是将其他码字序列中截去与其最短码字相同的前缀部分，将余下的序列为尾随后缀。而这些尾随后缀又可能是某些码字的前缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某些码字的前缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随 后缀产生为止。这样，首先获得的是由最短码字能引起的所有尾随后缀。接着，按照上述步骤将次短的码字、 所有码字可能产生的尾随后缀前部 列出。由此得到由码 C的所有可能的尾随后缀组成的集合F。参考算法伪代码:For all Wi,

3、Wj C doif W、是Wj的前缀then将相应的后缀作为一个尾随后缀放入集合F0中End ifEnd forLoopFor all Wi C doFor all Wj Fn doif Wi 是 Wj 的前缀 then将相应的后缀作为一个尾随后缀放入集合Fn 1中Else if Wj 是 W 的前缀 then将相应的后缀作为一个尾随后缀放入集合Fn 1中End ifEnd forEnd forIfWiF,Wi C thenReturn falseElse if F中未出现新的元素 the nRetur n trueEnd if实现源码#inelude <iostream>#inc

4、lude <fstream>#include <>#include <>using namespace std;#pragma warning (disable :4996)char c10050;运行结果输入文件：说明：输入文件中第一个数字表示码的组数，第二个数字表示一组码码字的个数，一组 码结束以“ $”符号结尾；“$”符号后的数字表示下一组码的码字个数。此例以两组码输入 为例，多组码判断同上。输出文件：结果分析：程序首先读取第一组码，进行是否唯一可译码的判断，在输出文件第一行输 出判断结果，在第二行输出该码字产生的尾随后缀集合(若只是输出是否唯一可译码

5、的判断结果，不能完全说明程序的正确性，可能存在偶然性；若是输出的尾随后缀集合是正确的， 则能说明程序的正确性，由于选取的两组数据来自课本，可以准确的知道尾随后缀集合是否正确，则可验证此程序的正确性，即可用于判断码是否为唯一可译码)。5.设计体会通过此实验的设计，进一步加深了我对唯一可译码判别方法的理解。此实验在设计完成 的过程中出现两大难点， 第一点就是， 作为此程序的核心， 两个码字生成尾随后缀的函数编 写，选取两个字符数组保存码字和后缀， 通过码字长度和单个字符比较来生成尾随后缀； 第 二个难点是码字的文件读取， 起初考虑的是整个码字一起读取， 发现实现过程较为复杂， 经 过修改， 改为单

6、个字符读取能简化程序的设计。 其他部分按照唯一可译码的判断方法进行设 计，关键部分调用尾随后缀生成函数即可， 再将判断结果输出到输出文件。 此实验总体而言 较为简单，实现时注意细节、没有逻辑误区即可。二、游程编码 +Huffman 码1. 任务说明要求：一无记忆二元信源， 0 符号的出现概率为 1/4, 1 符号的出现概率为 3/4 。现要求 对该信源连续出现的 n 个符号序列，先进行游程编码，再对结果进行 Huffman 编码。然后，再进行 Huffman 译码和游程译码。假定，连续出现的 0或 1 序列 的长度不超过 16，n 不小于 256。输入：长为 n 的 0/1 串输出： 1. 游

7、程编码结果， 2. Huffman 编码结果， 3. Huffman 译码结果 4. 游程译码结 果输入文件 : ，含至少两组输入输出文件 : ，对每组输入的处理结果2. 实现原理游程编码：信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串，这种字符串的长度称为游程。游程编码（RLC就是将信源输出的这种字符序列映射成由串的字符， 串的长度和串的位置三个标志组成的标志序列。 知 道了串的字符、 串的长度和串的位置的标志序列， 就可以完全恢复出原来的 字符序列。在二元序列中，只有两种符号，即“ 0”和“ 1”，这些符号可连续出现，连“ 0”这一段称为“ 0”游程，连“ 1”这一段称为

8、“ 1”游程。它们的长度分 别称为游程长度 L(0) 和 L(l) 。“ 0”游程和“ l ”游程总是交替出现的。如 果规定二元序列是以“ 0”开始，第一个游程是“ 0”游程，第二个必为“ 1”游 程，第三个又是“ 0”游程等等。对于随机的二元序列，各游程长度将是随 机变量，其取值可为 1，2，3， ?，直到无限。Huffman码：(1 )将q个信源符号按概率分布 P (si )的大小，以递减次序排列起来，设 p1>=p2>=p3>=.>=p q( 2)用 0 和 1 码符号分别分配给概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个信服好，并用这两个最小概

9、率之和 作为新符号的概率，从而得到只包含 q-1 个服啊后的新信源，称为 S信源的缩减信源 S1。(3)把缩减信源Si的符号仍按概率大小以递减次序排列，再将其最后两 个概率最小的符号合并成一个新符号， 并分别用 0和 1 码符号表示， 这样又形成了 q-2 个符号的缩减信源 S2。( 4)依次继续下去，直至缩减信源最后只剩两个符号为止。将这最后两 个符号分别用 0 和 1 码符号表示。最后这两个符号的概率之和必为1。然后从最后一级缩减信源开始， 依编码路径由后向前返回， 就得出各信源符号所对应的码符号序列，即得对应的码字。Huffman 码参考算法伪代码：if q=2 thenReturns0

10、0,s11Else降序排序 pi缩减信源：创建一个符号s'以取代Sq 1,Sq 2，其概率P' Pq 2 Pq 1递归调用Huffman算法以得到恥3，$ 3,s的编码WoW.Wq 3,w (相应的概率分 布为 p0， p1 ,，pq 3 , p)ReturnSoWo,S,Wi,.,Sq3Wq3,Sq2w'0,Sq1w'1End if3. 实现源码#include <iostream>#include <string>#include <>#include <>#include <fstream>#pr

11、agma warning (disable :4996)#define N 100#define M 2*N-1typedef char * HuffmanCode2 * M; = chi; |CW*p.weight = 1;for (k = i + 1; chk !='0' k+)if (chi = chk)CW*p.weight+;eight = wi.weight;hti.pare nt = 0;hti. LChild = 0;hti.RChild = 0;for (i = n + 1; i <= 2 * n - 1; i+)hti.weight = 0;hti.p

12、are nt = 0;hti. LChild = 0;hti.RChild = 0;for (i = n + 1; i <= 2 * n - 1; i+)for (j = 1; j <= i - 1; j+)if (!htj.pare nt)break ;s1 = j; arent)s1 = hts1.weight>htj.weight j : s1; |hts1.pare nt = i;hti. LChild = s1;for (j = 1; j <= i - 1; j+)if (!htj.pare nt)break ;s2 = j; arent)s2 = hts2.

13、weight>htj.weight j : s2;|hts2.pare nt = i;hti.RChild = s2;hti.weight = hts1.weight + hts2.weight;are nt;Child = c)are nt;weighty.num = n - start; 中查找与 chi相等的下标 K*/if (chi = weightk.c)break ;hci = ( char *)malloc(weightk.num)*sizeof (char);strcpy(hci, hk); Child;elsep = htp.RChild;printf( "%

14、c", wp.c); /*打印原信息 */out << wp.c;i+;out << en dl;/* 释放 huffman 编码内存 */void FreeHuffma nCode(Huffma nCode h, Huffma nCode hc, int n, int m) int i;for (i = 1; i <= n; i+);printf("nWeight ");for (i = 1; i <= n; i+)printf( "%d ", weighti.weight);CreateHuffmanTr

15、ee(ht, weight, n);/*产生 Huffman 树*/printf( "n*HuffamnTreelnformation*n");printf( "titweighttparenttLChildtRChildn");for (i = 1; i <= 2 * n - 1; i+) eight, hti.parent, hti.LChild,hti .RChild);CrtHuffmanNodeCode(ht, ch, h, weight, m, n);/*叶子结点的编码 */printf(” *NodeCode*n" ); /

16、* 打印叶子结点的编码 */for (i = 1; i <= n; i+)printf( "t%c:" , weighti.c);printf( "%sn" , hi);CrtHuffmanCode(ch, h, hc, weight, n, m);/*所有字符的编码 */printf( "Huffman编码后");/*打印字符串的编码 */for (i = 0; i < m; i+)printf( "%s", hci);strcpy(&y i, hci);system( "pause

17、");void huffma nyi ma()printf( "huffman 译码后：");TrsHuffmanTree(ht, weight, hc, n, m);/*解码 */FreeHuffma nCode(h, hc, n, m);system( "pause");int mai n() char s100;if (!()cout << "Error opening file" ; exit(1);while (!() (s, 100);cout << s << en dl;yo

18、uche ngbia nm a(s);out << "游程编码后："<< x << endl;huffma nbm(x);out << "Huffman 编码后：” << y << endl;out << "huffman 译码后：”；huffma nyima();youche ngyima(x);();();return 0;4. 运行结果输入文件：结果分析：对 n 个符号序列进行游程编码后输出“ 0”游程长度和“ 1”游程长度，再对 结果进行霍夫曼编码， 得到游程编码

19、结果的霍夫曼码。 然后进行译码， 首先的是霍夫曼译码， 得到游程编码结果， 再进行游程译码， 得到原符号序列。 第二组符号序列编码译码过程相同。5. 设计体会游程编码相对简单， 首先计算每次连续相同字符的个数， 然后将每次连续相同的字符及 个数保存起来， 再使用霍夫曼编码。 霍夫曼编码用概率匹配方法进行信源编码， 有两个明显 的特点： 一是霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码； 二是缩减信源的最后两个码字总是最后一位不同， 从而保证霍夫曼编 码是即时码。 完成哈夫曼的编码首先建立哈夫曼树， 定义当前节点的字符， 当前节点的左子、 右子和父亲指针

20、， 之后对所有字符根据权重进行编码 （先在所有可能出现的字符中筛选出当 前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树， 并将两个字符的权重之和赋值给新节点， 将新二叉树放入筛选字符中， 再将筛选过的两个字 符从筛选列表中淘汰掉。 依次对列表中剩下的字符进行权重最小的筛选，直到根节点） ，最 后再对文件内容进行编码。三、算术编码的编码与译码1. 任务说明要求：输入字符集为 a,b, 且 p（a）=1/4,p（2）=3/4. 对长度 L<=30 的序列进行算术编码 , 并进 反向译码输入文件 : ，含至少两组输入，每组为满足要求的串输出文件 : ，对每组输入的编码和译码结果2. 实现原理算术编码用到两个基本的参数： 符号的概率和它的编码间隔。 信源符号的概率决定压缩 编码的效率， 也决定编码过程中信源符号的间隔， 而这些间隔包含在 0到 1 之间。编码过程 中的间隔决定了符号压缩后的输出。给定事件序列的算术编码步骤如下：（1）编码器在开始时将“当前间隔” L ， H） 设置为0 ，1）。（2）对每一事件，编码器按步骤（a）和（b）进行处理(a) 编码器将“当前间隔”分为子间隔，每一个事件一个。(b) 一