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

构成集合F ：首先观察码C 中最短的码字是否是其他码字的前缀。

若是，将其所有可能 的尾随后缀排列出。

就是将其他码字序列中截去与其最短码字相同的前缀 部分，将余下的序列为尾随后缀。

而这些尾随后缀又可能是某些码字的前 缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生 的新的尾随后缀列出。

然后再观察这些新的尾随后缀是否是某些码字的前 缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后 缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随 后缀产生为止。

这样，首先获得的是由最短码字能引起的所有尾随后缀。

接着，按照上述步骤将次短的码字、......所有码字可能产生的尾随后缀前部 列出。

由此得到由码C 的所有可能的尾随后缀组成的集合F 。

参考算法伪代码：For all ,i j W W C ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合0F 中 End if End for LoopFor all i W C ∈ doFor all j n W F ∈ doif i W 是j W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中 Else if j W 是i W 的前缀 then将相应的后缀作为一个尾随后缀放入集合1n F +中End if End for End for i i F F ←If ,i i W F W C ∃∈∈ thenReturn falseElse if F 中未出现新的元素thenReturn trueEnd if//能走到这里，说明F中有新的元素出现，需继续End loop3. 实现源码#include<iostream>#include<fstream>#include<stdio.h>#include<string.h>using namespace std;#pragma warning(disable:4996)char c[100][50]; //保存码字char f[300][50]; //保存尾随后缀int N, sum = 0; //N为码字的个数，sum为尾随后缀个数int flag; //判断是否唯一可译标志位//检测尾随后缀void patterson(char c[], char d[]){int i, j, k;for (i = 0;; i++){If (c[i] == '\0'&&d[i] == '\0')//两字符串一样长，跳出break;if (c[i] == '\0') //d比c长，将d的尾随后缀放入f中{for (j = i; d[j] != '\0'; j++)f[sum][j - i] = d[j];f[sum][j - i] = '\0';for (k = 0; k<sum; k++){if (strcmp(f[sum], f[k]) == 0) /*查看当前生成的尾随后缀在f集合中是否存在*/{sum--; break;}}sum++;break;}if (d[i] == '\0') //c比d长，将c的尾随后缀放入f中{for (j = i; c[j] != '\0'; j++)f[sum][j - i] = c[j];f[sum][j - i] = '\0';for (k = 0; k<sum; k++){if (strcmp(f[sum], f[k]) == 0) /*查看当前生成的尾随后缀在f集合中是否存在*/{sum--; break;}}sum++;break;}if (c[i] != d[i])//字符不一样了也退出（前缀不同）break;}}void main(){int k = 0, N = 0, m = 0, a[50], z = 0;a[m] = N; m++;fstream file1;file1.open("out1.txt");//码字读取FILE *file;file = fopen("in1.txt", "r+");int num = fgetc(file) - 48;for (int n = 0; n < num; n++){int i = 0, j;if (fgetc(file) == ' ')N += (fgetc(file) - 48);else N += (fgetc(file) - 48);a[m] = N; m++;fgetc(file);for (k; k < N; k++){for (int q = 0;; q++){char temp = fgetc(file);c[k][q] = temp;if (temp == ' ' || temp == '$'){c[k][q] = '\0';break;}}}//生成尾随后缀flag = 0;for (i = a[z]; i<N - 1; i++)//判断码本身是否重复for (j = i + 1; j<N; j++){if (strcmp(c[i], c[j]) == 0){flag = 1; break;}}if (flag == 1)//如果码本身有重复，就可以断定它不是唯一可译码{for (int y = a[z]; y < N; y++)file1 << c[y] << ' ';file1 << "不是唯一可译码。

\n";}else{for (i = a[z]; i<N - 1; i++) /*将原始码字生成的尾随后缀集合s[1]放入f中*/{for (j = i + 1; j<N; j++){patterson(c[i], c[j]);}}for (i = 0;; i++) //根据原始码与s[i]生成s[i+1]也放入f[i]{int s = 0;for (j = a[z]; j<N; j++) /*判断s[i+1]中的字符串是否与s[i]中一样，重复的则不再添加*/{if (i == sum){s = 1; break;}elsepatterson(f[i], c[j]);}if (s == 1)break;}for (i = 0; i<sum; i++) /*判断尾随后缀与原始码字是否相同，相同则不是唯一可译码*/ {for (j = a[z]; j<N; j++){if (strcmp(f[i], c[j]) == 0){flag = 1;break;}}}if (flag == 1){for (int y = a[z]; y < N; y++)file1 << c[y] << ' ';file1 << "不是唯一可译码。

\n";}else{for (int y = a[z]; y < N; y++)file1 << c[y] << ' ';file1 << "是唯一可译码。

\n";}}file1 << "尾随后缀集合为：";for (i = 0; i < sum; i++)file1 << f[i] << ' ';file1 << "\n";z++;sum = 0;}}4. 运行结果输入文件：in1.txt说明：输入文件中第一个数字表示码的组数，第二个数字表示一组码码字的个数，一组码结束以“$”符号结尾；“$”符号后的数字表示下一组码的码字个数。

此例以两组码输入为例，多组码判断同上。

输出文件：out1.txt结果分析：程序首先读取第一组码，进行是否唯一可译码的判断，在输出文件第一行输出判断结果，在第二行输出该码字产生的尾随后缀集合（若只是输出是否唯一可译码的判断结果，不能完全说明程序的正确性，可能存在偶然性；若是输出的尾随后缀集合是正确的，则能说明程序的正确性，由于选取的两组数据来自课本，可以准确的知道尾随后缀集合是否正确，则可验证此程序的正确性，即可用于判断码是否为唯一可译码）。

5. 设计体会通过此实验的设计，进一步加深了我对唯一可译码判别方法的理解。

此实验在设计完成的过程中出现两大难点，第一点就是，作为此程序的核心，两个码字生成尾随后缀的函数编写，选取两个字符数组保存码字和后缀，通过码字长度和单个字符比较来生成尾随后缀；第二个难点是码字的文件读取，起初考虑的是整个码字一起读取，发现实现过程较为复杂，经过修改，改为单个字符读取能简化程序的设计。

其他部分按照唯一可译码的判断方法进行设计，关键部分调用尾随后缀生成函数即可，再将判断结果输出到输出文件。

此实验总体而言较为简单，实现时注意细节、没有逻辑误区即可。

二、游程编码+Huffman码1. 任务说明要求：一无记忆二元信源，0符号的出现概率为1/4, 1符号的出现概率为3/4。

现要求对该信源连续出现的n个符号序列，先进行游程编码，再对结果进行Huffman编码。

然后，再进行Huffman译码和游程译码。

假定，连续出现的0或1序列的长度不超过16，n不小于256。

输入：长为n的0/1串输出：1. 游程编码结果，2. Huffman编码结果，3. Huffman译码结果4. 游程译码结果输入文件:in2.txt，含至少两组输入输出文件:out2.txt，对每组输入的处理结果2. 实现原理游程编码：信源输出的字符序列中各种字符连续地重复出现而形成一段一段的字符串，这种字符串的长度称为游程。