信息论课程设计报告

成绩：

2016-2017学年第1学期

《信息论》课程设计

学院名称： 班级学号： 学生姓名： 教师姓名：

2016年 12 月 一、判定唯一可译码

1. 任务说明

输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是） 输入文件:in1.txt，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt，对每组码的判断结果 说明：为了简化设计，可以假定码字为0，1串

2. 实现原理

判断方法：将码C中所有码字可能的尾随后缀组成一个集合F，当且仅当集合F中没有 包含任一码字，则可判断此码C为唯一可译变长码。 构成集合F：首先观察码C中最短的码字是否是其他码字的前缀。若是，将其所有可能 的尾随后缀排列出。就是将其他码字序列中截去与其最短码字相同的前缀 部分，将余下的序列为尾随后缀。而这些尾随后缀又可能是某些码字的前 缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生 的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某些码字的前 缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后 缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随 后缀产生为止。这样，首先获得的是由最短码字能引起的所有尾随后缀。 接着，按照上述步骤将次短的码字、......所有码字可能产生的尾随后缀前部 列出。由此得到由码C的所有可能的尾随后缀组成的集合F。 参考算法伪代码： For all do C?W,WjiWW的前缀if then 是jiF中 将相应的后缀作为一个尾随后缀放入集合0End if End for

Loop W?C do

For all iW?F do For all njWW的前缀是if then jiF中 将相应的后缀作为一个尾随后缀放入集合1n?WW的前缀Else if then

是jiF中 将相应的后缀作为一个尾随后缀放入集合1?nEnd if End for End for F?UF ii?W?F,W?C then

If iiReturn false Else if F 中未出现新的元素 then Return true End if

中有新的元素出现，需继续//能走到这里，说明F End loop实现源码3. #include #include #include #include std; using namespace :4996) #pragma disablewarning( 保存码字char c[100][50]; // char f[300][50]; //保存尾随后缀 //N为码字的个数，为尾随后缀个数sum int N, sum = 0; // 判断是否唯一可译标志位 flag; int

//检测尾随后缀 d[]) c[], char patterson( voidchar{ i, j, k; int (i = 0;; i++) for { // (c[i] == '\0'&&d[i] == '\0') 两字符串一样长，跳出 If; break 中 f dc//d ) (c[i] == if'\0' 比长，将的尾随后缀放入{

; j++) '\0' for (j = i; d[j] != f[sum][j - i] = d[j]; ; '\0' f[sum][j - i] = (k = 0; k{ f集合中 /* if (strcmp(f[sum], f[k]) == 0) 查看当前生成的尾随后缀在 */ 是否存在 { ; sum--; break}

} sum++; ; break }

中 长，将c的尾随后缀放入fd if (d[i] == '\0') //c比{ ; j++) '\0' (j = i; c[j] != forf[sum][j - i] = c[j];

; f[sum][j - i] = '\0' (k = 0; k集合中 /*查看当前生成的尾随后缀在fif (strcmp(f[sum], f[k]) == 0) 是否存在*/ { ; breaksum--; }

} sum++; ; break }

// 字符不一样了也退出（前缀不同）if (c[i] != d[i]); break }

} main(){ void k = 0, N = 0, m = 0, a[50], z = 0; int a[m] = N; m++; fstream file1; ); 潜瑵?硴屴 file1.open( 码字读取 // FILE *file;

); , 牜尫 file = fopen(楜?琮瑸 num = fgetc(file) - 48; int n = 0; n < num; n++){ int for ( i = 0, j; int ) ' 'if (fgetc(file) == N += (fgetc(file) - 48);

N += (fgetc(file) - 48); else a[m] = N; m++;

fgetc(file); (k; k < N; k++){ for q = 0;; q++){ for (int temp = fgetc(file); char c[k][q] = temp;

){ if '$'' ' || temp == (temp == ; '\0' c[k][q] = ; break }

} } 生成尾随后缀 // flag = 0;

(i = a[z]; i{ (strcmp(c[i], c[j]) == 0) if { ; break flag = 1; }

} 如果码本身有重复，就可以断定它不是唯一可译码 if (flag == 1)//{ y = a[z]; y < N; y++) int (for ; ' 'file1 << c[y] << ; 不是唯一可译码。屜屮 file1 << } else { f 放入将原始码字生成的尾随后缀集合s[1] /* for (i = a[z]; i中 */ { (j = i + 1; j{ patterson(c[i], c[j]);

} } f[i] 生成s[i+1] 也放入 //根据原始码与s[i] for (i = 0;; i++) { s = 0; int /*判断 s[i+1] 中的字符串是否与s[i]中一 for (j = a[z]; j，重复的则不再添加*/ 样 { (i == sum) if { ; break s = 1; } else patterson(f[i], c[j]);

} ; if (s == 1)break }

判断尾随后缀与原始码字是否相同， /* for (i = 0; i*/相同则不是唯一可译码 { (j = a[z]; j{ (strcmp(f[i], c[j]) == 0) if { flag = 1; ; break }

} } (flag == 1) if{ y = a[z]; y < N; y++) for (int ; file1 << c[y] << ' '; file1 << 不是唯一可译码。屜屮 } { else y = a[z]; y < N; y++) (intfor ; ' ' file1 << c[y] << ; 屜屮是唯一可译码。file1 << }

} ; file1 << 尾随后缀集合为： (i = 0; i < sum; i++) for ; file1 << f[i] << ' ' file1 << 屜湜; z++; sum = 0;

} }

4. 运行结果

in1.txt输入文件： 说明：输入文件中第一个数字表示码的组数，第二个数字表示一组码码字的个数，一组码结束以“$”符号结尾；“$”符号后的数字表示下一组码的码字个数。此例以两组码输入为例，多组码判断同上。