《《信息论》课程设计(26页).docx》由会员分享，可在线阅读，更多相关《《信息论》课程设计(26页).docx（26页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-信息论课程设计-第 26 页 成绩： 2016-2017学年第1学期信息论课程设计学院名称： 班级学号： 学生姓名： 教师姓名： 2016年 12 月 一、 判定唯一可译码1. 任务说明 输入：任意的一个码(即已知码字个数及每个具体的码字) 输出：判决结果（是/不是） 输入文件:in1.txt，含至少2组码，每组的结尾为”$”符 输出文件:out1.txt，对每组码的判断结果 说明：为了简化设计，可以假定码字为0，1串2. 实现原理 判断方法：将码C中所有码字可能的尾随后缀组成一个集合F，当且仅当集合F中没有 包含任一码字，则可判断此码C为唯一可译变长码。 构成集合F：首先观察码C中最短的码
2、字是否是其他码字的前缀。若是，将其所有可能 的尾随后缀排列出。就是将其他码字序列中截去与其最短码字相同的前缀 部分，将余下的序列为尾随后缀。而这些尾随后缀又可能是某些码字的前 缀，或者最短码字又仍是这些尾随后缀的前缀，再将由这些尾随后缀产生 的新的尾随后缀列出。然后再观察这些新的尾随后缀是否是某些码字的前 缀，或观察有否其他码字是这些新的尾随后缀的前缀，再将产生的尾随后 缀列出，依次下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随 后缀产生为止。这样，首先获得的是由最短码字能引起的所有尾随后缀。 接着，按照上述步骤将次短的码字、.所有码字可能产生的尾随后缀前部 列出。由此得到由码C的所有可
3、能的尾随后缀组成的集合F。 参考算法伪代码：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 #in
4、clude #include #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的
5、尾随后缀放入f中 for (j = 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) /
6、*查看当前生成的尾随后缀在f集合中 是否存在*/ 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;
7、if (fgetc(file) = ) 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
8、(ci, cj) = 0) flag = 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中的
9、字符串是否与si中一 样 ，重复的则不再添加*/ 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
10、 N; y+) file1 cy ; 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)#de
12、fine N 100#define 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
13、 = j + 2;ycj = 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 游程译
14、码后： jieya endl;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;i
15、nt tag;*p = 0;/叶子节点个数/统计字符出现个数,放入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)i
16、nt i, j;int s1, 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;
17、 /找到第一个双亲为零的结点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 CrtHuffmanNodeCode(Huffman ht, char
18、 ch, HuffmanCode h, WeightNode weight, int m, int n)int i, c, p, start;char *cd;cd = (char *)malloc(n*sizeof(char);cdn - 1 = 0;/末尾置0for (i = 1; i = n; i+)start = n - 1; /cd串每次从末尾开始c = i;p = hti.parent;/p在n+1至2n-1while (p) /沿父亲方向遍历,直到为0start-;/依次向前置值if (htp.LChild = c)/与左子相同,置0cdstart = 0;else /否则置1c
19、dstart = 1;c = p;p = htp.parent;weighti.num = n - start; /二进制码的长度(包含末尾0)hi = (char *)malloc(n - start)*sizeof(char);strcpy(hi, &cdstart);/将二进制字符串拷贝到指针数组h中free(cd);/释放cd内存system(pause);/*所有字符的编码*/void CrtHuffmanCode(char ch, HuffmanCode h, HuffmanCode hc, WeightNode weight, int n, int m)int i, k;for
20、(i = 0; im; i+)for (k = 1; k = n; k+) /*从weightk.c中查找与chi相等的下标K*/if (chi = weightk.c)break;hci = (char *)malloc(weightk.num)*sizeof(char);strcpy(hci, hk); /拷贝二进制编码/*解码*/void TrsHuffmanTree(Huffman ht, WeightNode w, HuffmanCode hc, int n, int m)int i = 0, j, p;while (im)p = 2 * n - 1;/从父亲节点向下遍历直到叶子节点
21、for (j = 0; hcij != 0; j+)if (hcij = 0)p = htp.LChild;elsep = htp.RChild;printf(%c, wp.c); /*打印原信息*/out wp.c;i+;out endl;/*释放huffman编码内存*/void FreeHuffmanCode(HuffmanCode h, HuffmanCode hc, int n, int m)int i;for (i = 1; i = n; i+)/释放叶子结点的编码free(hi);for (i = 0; im; i+) /释放所有结点的编码free(hci);int n; /*n
22、为叶子结点的个数*/int m; /*m为字符串ch的长度*/Huffman ht; /*Huffman二叉数*/HuffmanCode h, hc; /*h存放叶子结点的编码，hc 存放所有结点的编码*/WeightNode weight; /*存放叶子结点的信息*/void huffmanbm(char *ch)n = 0;int i;m = 0;printf(t*HuffmanCoding*n);CreateWeight(ch, &m, weight, &n); /*产生叶子结点信息，m为字符串ch的长度printf(*WeightInformation*n Node );for (i
23、= 1; i = n; i+) /输出叶子结点的字符与权值printf(%c , weighti.c);printf(nWeight );for (i = 1; i = n; i+)printf(%d , weighti.weight);CreateHuffmanTree(ht, weight, n); /*产生Huffman树*/printf(n*HuffamnTreeInformation*n);printf(titweighttparenttLChildtRChildn);for (i = 1; i = 2 * n - 1; i+) /打印Huffman树的信息printf(t%dt%d
24、t%dt%dt%dn, i, hti.weight, hti.parent, hti.LChild, hti.RChild);CrtHuffmanNodeCode(ht, ch, h, weight, m, n); /*叶子结点的编码*/printf( *NodeCode*n); /*打印叶子结点的编码*/for (i = 1; i = n; i+)printf(t%c:, weighti.c);printf(%sn, hi);CrtHuffmanCode(ch, h, hc, weight, n, m); /*所有字符的编码*/printf(Huffman编码后); /*打印字符串的编码*/
25、for (i = 0; i m; i+)printf(%s, hci);strcpy(&yi, hci);system(pause);void huffmanyima()printf(huffman译码后：);TrsHuffmanTree(ht, weight, hc, n, m); /*解码*/FreeHuffmanCode(h, hc, n, m);system(pause);int main()char s100;if (!in.is_open()cout Error opening file; exit(1);while (!in.eof() in.getline(s, 100);co
26、ut s endl;youchengbianma(s);out 游程编码后： x endl;huffmanbm(x);out Huffman编码后： y endl;out huffman译码后：;huffmanyima();youchengyima(x);in.close();out.close();return 0;4. 运行结果输入文件：in2.txt输出文件：out2.txt结果分析：对n个符号序列进行游程编码后输出“0”游程长度和“1”游程长度，再对结果进行霍夫曼编码，得到游程编码结果的霍夫曼码。然后进行译码，首先的是霍夫曼译码，得到游程编码结果，再进行游程译码，得到原符号序列。第二组
27、符号序列编码译码过程相同。5. 设计体会游程编码相对简单，首先计算每次连续相同字符的个数，然后将每次连续相同的字符及个数保存起来，再使用霍夫曼编码。霍夫曼编码用概率匹配方法进行信源编码，有两个明显的特点：一是霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长吗，充分利用了短码；二是缩减信源的最后两个码字总是最后一位不同，从而保证霍夫曼编码是即时码。完成哈夫曼的编码首先建立哈夫曼树，定义当前节点的字符，当前节点的左子、右子和父亲指针，之后对所有字符根据权重进行编码（先在所有可能出现的字符中筛选出当前权重最小的两个字符，将这两个字符分别作为新节点的左子和右子建立一个小的二叉树，并
28、将两个字符的权重之和赋值给新节点，将新二叉树放入筛选字符中，再将筛选过的两个字符从筛选列表中淘汰掉。依次对列表中剩下的字符进行权重最小的筛选，直到根节点），最后再对文件内容进行编码。三、算术编码的编码与译码1. 任务说明要求：输入字符集为a,b,且p(a)=1/4,p(2)=3/4.对长度L=30的序列进行算术编码,并进 反向译码输入文件:in3.txt，含至少两组输入，每组为满足要求的串 输出文件:out3.txt，对每组输入的编码和译码结果2. 实现原理算术编码用到两个基本的参数：符号的概率和它的编码间隔。信源符号的概率决定压缩编码的效率，也决定编码过程中信源符号的间隔，而这些间隔包含在0
29、到1之间。编码过程中的间隔决定了符号压缩后的输出。给定事件序列的算术编码步骤如下：（1）编码器在开始时将“当前间隔” L， H) 设置为0，1)。（2）对每一事件，编码器按步骤（a）和（b）进行处理 （a）编码器将“当前间隔”分为子间隔，每一个事件一个。 （b）一个子间隔的大小与下一个将出现的事件的概率成比例，编码器选择子间隔 对应于下一个确切发生的事件相对应，并使它成为新的“当前间隔”。（3）最后输出的“当前间隔”的下边界就是该给定事件序列的算术编码。3. 实现源码#include#include#pragma warning(disable:4996)using namespace std
30、;#includemath.hchar S100, A10; /用户的码字、保存输入字符float P10, f10, gFs; /字符概率char bm100, jm100;fstream in(in3.txt);fstream out(out3.txt);/编码程序void bianma(int a, int h)int i, j;float fr;float ps = 1;float Fs = 0;float Sp100; /以待编码的个数和字符个数为循环周期将待编码的字符所对应的概率存入到Fs中for (i = 0; ih; i+)for (j = 0; ja; j+)if (Si =
31、 Aj)Spi = Pj;fr = fj;/将划分好的0,1)区间的对应点赋值给frFs = Fs + ps*fr;/从选择的子区间中继续进行下一轮的分割。不断的进行这个过程直到所有符号编码完毕。ps *= Spi; /求Pscout Fs= Fs endl;/显示最终的算术编码gFs = Fs;out 算术编码结果： endl;out Fs= Fs (int)l)l = (int)l + 1;else l = int(l);/将Fs转换成二进制的形式int d20;int m = 0;while (lm)Fs = 2 * Fs;if (Fs1)Fs = Fs - 1;dm = 1;else if (Fs= l)while (1)dm - 1 = (dm - 1 + 1) % 2;/最后位加if (dm - 1 = 1)break;else m-;