电子科技大学电子工程学院信息论课程设计报告<课程名称：信息编码与加密，课程设计报告学生姓名：农瀚学号：20 指导教师：李万春一、课程设计名称：编程实现霍夫曼、费诺、香农编码二、课设原理：1）霍夫曼编码：霍夫曼编码的平均码长最短，是最佳编码。
编码步骤如下：（1）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两幅号分别赋予码元0和1；（3）将概率之和当做一个新符号的概率。
与剩下的概率一起，形成一个缩减信源，再重复上述步骤，直到概率和为1为止；（4）按上述步骤实际上构成了一个码树，从根到端点经过的树枝即为码字。
/2）费诺编码：编码步骤如下：（1）将信源概率从大到小排序；（2）将信源符号分成两组，使两组信源符号的概率之和近似相等，并给两组信源符号分别赋0和1；（3）再把各个小组的信源符号细分为两组并赋码元，方法与第一次分组相同；（4）如此一直下去，直到每一个小组只含一个信源符号为止；（5）由此可构造成一个码树，所有终端节点上的码字组成费诺码。
3）香农编码：编码方法如下：⑴将信源消息符号按其出现的概率大小依次排列@p(u1)≥p(u2)≥…≥ p(un)⑵确定码长Ki (整数) ：Ki= []——取整⑶为了编成唯一可译码，计算第i个消息的累加概率⑷将累加概率Pi变换成二进制数。
⑸取pi二进制数的小数点后Ki位即为该消息符号的二进制数。
三、课设目的：通过编程实现三种方式的编码，掌握三种编码方式的步骤。
四、课设内容：三种编码方式的编程思路：】1、霍夫曼编码：（1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。
（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。
）（2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
（3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。
（4）重复二和三两步，直到集合F中只有一棵二叉树为止。
2、费诺编码的编程思路：（1）先使用冒泡法对信源概率概率排序；（2）依次将按排好序的符号概率进行近似1:1分成两大组；（3）对各组赋予一个二进制码元“0”和“1”；（4）输出符号,符号概率及编码。
3、香农编码：（1）对于一个给定的符号列表，制定了概率相应的列表或频率计数，使每个符号的相对发生频率是已知。
（2）排序根据频率的符号列表，最常出现的符号在左边，最少出现的符号在右边。
（3）清单分为两部分，使左边部分的总频率和尽可能接近右边部分的总频率和。
（4）该列表的左半边分配二进制数字0，右半边是分配的数字1。
这意味着，在第一半符号代都是将所有从0开始，第二半的代码都从1开始。
（（5）对左、右半部分递归应用步骤3和4，细分群体，并添加位的代码，直到每个符号已成为一个相应的代码树的叶。
五、器材（设备、元器件）：计算机、visual studio2017社区版六、设计代码：见附录九、实验数据及结果根据上述实验程序得到的实验数据及结果如下：霍夫曼编码：~费诺编码：香农编码：>十、结论完成了20个非等概随机信源的霍夫曼、费诺和香农编码，并给出了编码效率和码字。
十一、总结及心得体会通过这次课程设计，我掌握了三种编码方式的步骤，并能够利用编程实现编码，提高了自己的编程水平和对该知识点的掌握程度。
附录代码：;eight = 0;HuffNode[i].parent = -1;HuffNode[i].lchild = -1;HuffNode[i].rchild = -1;}for (i = 0; i < n; i++){HuffNode[i].weight = Sp[i];…}for (i = 0; i < n - 1; i++){m1 = m2 = MaxValue;x1 = x2 = 0;for (j = 0; j < n + i; j++){if (HuffNode[j].weight < m1 && HuffNode[j].parent == -1)#{m2 = m1;x2 = x1;m1 = HuffNode[j].weight;x1 = j;}else if (HuffNode[j].weight < m2 && HuffNode[j].parent == -1){m2 = HuffNode[j].weight;x2 = j;/}}HuffNode[x1].parent = n + i;HuffNode[x2].parent = n + i;HuffNode[n + i].weight = HuffNode[x1].weight + HuffNode[x2].weight;HuffNode[n + i].lchild = x1;HuffNode[n + i].rchild = x2;}}double CodEffi()arent;！while (p != -1){if (HuffNode[p].lchild == c)[] = 0;else[] = 1;;c = p;p = HuffNode[c].parent;}~for (j = + 1; j<n; j++){HuffCode[i].bit[j] = [j];}HuffCode[i].start = ;}memset(coder, '\0', sizeof(coder));int temp=0;for (i = 0; i<n; i++){|cout <<"信源"<< i <<"编码为：";for (j = HuffCode[i].start + 1; j < n; j++){cout << HuffCode[i].bit[j];coder[i][temp]= char(HuffCode[i].bit[j]+48);temp++;?}temp = 0;cout <<" 信源概率："<< Sp[i];cout <<" 字长："<< strlen(coder[i]);printf("\n");bitlong[i] = strlen(coder[i]);}CodEffi();cout <<"\n编码效率: "<< CodEffi() * 100 <<"%\n";return 0;}}pp : 定义控制台应用程序的入口点。
= i;s[i].probability = Sp[i];}}/***********用冒泡法排序**********/void code(int low, int mid, int high){！int i;for (i = low; i<high; i++){if (i<mid){s[i].[s[i].] = '0';s[i].++;}else{~s[i].[s[i].] = '1';s[i].++;}}}void sort(int n){double t;char a;int i, j;~for (i = 1; i<n; i++)for (j = 0; j<n - i; j++)if (s[j].probability<s[j + 1].probability){t = s[j].probability;a = s[j].c;s[j].probability = s[j + 1].probability;s[j].c = s[j + 1].c;s[j + 1].probability = t;s[j + 1].c = a;!}}/************分组函数************/void group(int n){int i, pmid, plow, phigh;pmid = phigh = n;plow = 0;for (i = 0; i<n; i++)）s[i]. = 0;group1(plow, pmid, phigh);}void group1(int low, int mid, int high){double d, dmin;d = 0;int i;if (high == low + 1)return;！for (i = low; i<mid; i++)d += s[i].probability;dmin = d - 2 * s[low].probability;for (i = low + 1; i<high; i++){d = fabs(dmin - 2 * s[i].probability);if (d<dmin)dmin = d;elsebreak;】}mid = i;code(low, mid, high);group1(low, mid, mid);group1(mid, high, high);}void output(int n){{int i, j;printf("费诺编码输出信源,概率及编码：\n\n");for (i = 0; i<n; i++){cout<<"信源："<<s[i].c<<" "<<"概率："<<s[i].probability<<" "<<"编码：";for (j = 0; j<s[i].; j++)cout<< s[i].[j];bitlong[i] = s[i].;cout <<" "<<"字长"<< bitlong[i];【printf("\n");}}double CodEffi( ){int AveraLong =0,SumLong=0;double H=0,CE=0;for (int i = 0; i < SourNum; i++){）SumLong = SumLong + bitlong[i];}AveraLong = SumLong / SourNum;for (int j=0; j < SourNum; j++){H = (-Sp[j])*(log(Sp[j]) / log(2)) + H;}CE = H / AveraLong;return CE;}【void main() pp : 定义控制台应用程序的入口点。