信息论课程设计报告.docx

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

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

3、考算法伪代码：For all do if 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中End ifEnd forLoopFor all do For all doif 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中Else if 是的前缀 then将相应的后缀作为一个尾随后缀放入集合中End ifEnd for End forIf thenReturn falseElse if F 中未出现新的元素 thenReturn trueEnd if/能走到这里，说明F中有新的元素出现，需继续 End loop3. 实现源码 #include #include #include

4、#include using namespace std; #pragma warning(disable:4996) char c10050; /保存码字 char f30050; /保存尾随后缀 int N, sum = 0; /N为码字的个数，sum为尾随后缀个数 int flag; /判断是否唯一可译标志位 /检测尾随后缀 void patterson(char c, char d) int i, j, k; for (i = 0; i+) If (ci = 0&di = 0)/两字符串一样长，跳出 break; if (ci = 0) /d比c长，将d的尾随后缀放入f中 for (j

5、 = i; dj != 0; j+) fsumj - i = dj; fsumj - i = 0; for (k = 0; ksum; k+) if (strcmp(fsum, fk) = 0) /*查看当前生成的尾随后缀在f集合中 是否存在*/ sum-; break; sum+; break; if (di = 0) /c比d长，将c的尾随后缀放入f中 for (j = i; cj != 0; j+) fsumj - i = cj; fsumj - i = 0; for (k = 0; ksum; k+) if (strcmp(fsum, fk) = 0) /*查看当前生成的尾随后缀在f集

6、合中 是否存在*/ sum-; break; sum+; break; if (ci != di)/字符不一样了也退出（前缀不同） break; void main() int k = 0, N = 0, m = 0, a50, z = 0; am = 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)

7、 = ) N += (fgetc(file) - 48); else N += (fgetc(file) - 48); am = N; m+; fgetc(file); for (k; k N; k+) for (int q = 0; q+) char temp = fgetc(file); ckq = temp; if (temp = | temp = $) ckq = 0; break; /生成尾随后缀 flag = 0; for (i = az; iN - 1; i+)/判断码本身是否重复 for (j = i + 1; jN; j+) if (strcmp(ci, cj) = 0) f

8、lag = 1; break; if (flag = 1)/如果码本身有重复，就可以断定它不是唯一可译码 for (int y = az; y N; y+) file1 cy ; file1 不是唯一可译码。n; else for (i = az; iN - 1; i+) /*将原始码字生成的尾随后缀集合s1放入f 中*/ for (j = i + 1; jN; j+) patterson(ci, cj); for (i = 0; i+) /根据原始码与si生成si+1也放入fi int s = 0; for (j = az; jN; j+) /*判断si+1中的字符串是否与si中一 样 ，重

9、复的则不再添加*/ if (i = sum) s = 1; break; else patterson(fi, cj); if (s = 1)break; for (i = 0; isum; i+) /*判断尾随后缀与原始码字是否相同， 相同则不是唯一可译码*/ for (j = az; jN; j+) if (strcmp(fi, cj) = 0) flag = 1; break; if (flag = 1) for (int y = az; y N; y+) file1 cy ; file1 不是唯一可译码。n; else for (int y = az; y N; y+) file1 c

10、y ; file1 是唯一可译码。n; file1 尾随后缀集合为：; for (i = 0; i sum; i+) file1 fi ; file1 =p2=p3=.=pq （2）用0和1码符号分别分配给概率最小的两个信源符号，并将这两个 概率最小的信源符号合并成一个信服好，并用这两个最小概率之和 作为新符号的概率，从而得到只包含q-1个服啊后的新信源，称为 S信源的缩减信源S1。 （3）把缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两 个概率最小的符号合并成一个新符号，并分别用0和1码符号表示， 这样又形成了q-2个符号的缩减信源S2。 （4）依次继续下去，直至缩减信源最后只剩

11、两个符号为止。将这最后两 个符号分别用0和1码符号表示。最后这两个符号的概率之和必为 1。然后从最后一级缩减信源开始，依编码路径由后向前返回，就得 出各信源符号所对应的码符号序列，即得对应的码字。Huffman码参考算法伪代码：if q=2 then Return Else降序排序缩减信源：创建一个符号以取代，其概率递归调用Huffman算法以得到的编码（相应的概率分布为）Return End if3. 实现源码#include #include #include #include #include #pragma warning(disable:4996)#define N 100#defi

12、ne M 2*N-1typedef char * HuffmanCode2 * M;/haffman编码using namespace std;char x100;char y100;fstream in(in2.txt);fstream out(out2.txt);void youchengbianma(char a100)char yc100;int i = 0, j = 0, jishu = 1;yc0 = a0;for (i = 0; ai != 0; i+)if (ai = ai + 1)jishu+;elseycj + 1 = jishu + 48;j = j + 2;ycj =

13、ai + 1;jishu = 1;ycj = 0;cout 游程编码后： yc endl;strcpy_s(x, yc);void youchengyima(char a100)char bz = 0, jieya100, j, jishu;for (int i = 0; ai != 0; i = i + 2)jieyabz = ai;for (j = bz, jishu = 1; jishu = ai + 1 - 48; jishu+, j+)jieyaj = ai;bz = j;jieyaj = 0;cout 游程译码后： jieya endl;out 游程译码后： jieya endl;

14、typedef structint weight;/权值int parent;/父节节点int LChild;/左子节点int RChild;/右子节点HTNode, HuffmanM + 1;/huffman树typedef struct Nodeint weight; /叶子结点的权值char c; /叶子结点int num; /叶子结点的二进制码的长度WNode, WeightNodeN;/*产生叶子结点的字符和权值*/void CreateWeight(char ch, int *s, WeightNode CW, int *p)int i, j, k;int tag;*p = 0;/

15、叶子节点个数/统计字符出现个数,放入CWfor (i = 0; chi != 0; i+)tag = 1;for (j = 0; ji; j+)if (chj = chi)tag = 0;break;if (tag)CW+*p.c = chi;CW*p.weight = 1;for (k = i + 1; chk != 0; k+)if (chi = chk)CW*p.weight+;/权值累加*s = i;/字符串长度/*创建HuffmanTree*/void CreateHuffmanTree(Huffman ht, WeightNode w, int n)int i, j;int s1,

16、 s2;/初始化哈夫曼树for (i = 1; i = n; i+)hti.weight = wi.weight;hti.parent = 0;hti.LChild = 0;hti.RChild = 0;for (i = n + 1; i = 2 * n - 1; i+)hti.weight = 0;hti.parent = 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.parent)break;s1 = j; /找到第一个双亲为零的结点for (; j htj.weight ? j : s1;hts1.parent = i;hti.LChild = s1;for (j = 1; j = i - 1; j+)if (!htj.parent)break;s2 = j; /找到第二个双亲为零的结点for (; j htj.weight ? j : s2;hts2.parent = i;hti.RChild = s2;hti.weight = hts1.weight + hts2.weight;/权值累加/*叶子结点的编码*/void CrtHuffm