信息论专业课程设计.doc

电子科技大学电子工程学院信息论课程设计报告课程名称：信息编码与加密课 程 设 计 报 告学生姓名：农瀚 学号： 指引教师：李万春一、课程设计名称：编程实现霍夫曼、费诺、香农编码二、课设原理： 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 studio社区版六、设计代码：见附录九、实验数据及成果依照上述实验程序得到实验数据及成果如下：霍夫曼编码： 费诺编码： 香农编码：十、结论 完毕了20个非等概随机信源霍夫曼、费诺和香农编码，并给出了编码效率和码字。十一、总结及心得体会通过这次课程设计，我掌握了三种编码方式环节，并可以运用编程实现编码，提高了自己编程水平和对该知识点掌握限度。附录代码：/ ConsoleApplication1.cpp ：定义控制台应用程序入口点。/*霍夫曼编码*/#include stdafx.h#include #include#include#include#include #include using namespace std;#define SourNum 20#define MAXBIT 100#define MaxValue 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1double SpSourNum;char coder100100;int bitlong100;void ProSource()/产生非等概信源函数int n = 0;srand(unsigned)time(0);double sum = 0;while (1)Spn = (double)rand() / (RAND_MAX);/产生随机浮点数sum = sum + Spn;if (sum 1 & Spn 19)break;else continue;elsesum = sum - Spn;Spn = 0;continue;SpSourNum = 1 - sum;/*霍夫曼编码*/typedef structint bitMAXBIT;int start; HCode;typedef structdouble weight;double parent;double lchild;double rchild;int last; HNodeType;void HuffmanTree(HNodeType HuffNodeMAXNODE，int n)int i，j，x1，x2;double m1，m2;for (i = 0；i 2 * n - 1；i+)HuffNodei.weight = 0;HuffNodei.parent = -1;HuffNodei.lchild = -1;HuffNodei.rchild = -1;for (i = 0；i n；i+)HuffNodei.weight = Spi;for (i = 0；i n - 1；i+)m1 = m2 = MaxValue;x1 = x2 = 0;for (j = 0；j n + i；j+)if (HuffNodej.weight m1 & HuffNodej.parent = -1)m2 = m1;x2 = x1;m1 = HuffNodej.weight;x1 = j;else if (HuffNodej.weight m2 & HuffNodej.parent = -1)m2 = HuffNodej.weight;x2 = j;HuffNodex1.parent = n + i;HuffNodex2.parent = n + i;HuffNoden + i.weight = HuffNodex1.weight + HuffNodex2.weight;HuffNoden + i.lchild = x1;HuffNoden + i.rchild = x2;double CodEffi()/求编码效率int AveraLong = 0，SumLong = 0;double H = 0，CE = 0;for (int i = 0；i SourNum；i+)SumLong = SumLong + bitlongi;AveraLong = SumLong / SourNum;for (int j = 0；j SourNum；j+)H = (-Spj)*(log(Spj) / log(2) + H;CE = H / AveraLong;return CE;int main()ProSource();sort(Sp，Sp + SourNum);HNodeType HuffNodeMAXNODE;HCode HuffCodeMAXLEAF，cd;int i，j，c，p，n;n = SourNum;HuffmanTree(HuffNode，SourNum + 1);for (i = 0；i n；i+)cd.start = n - 1;c = i;p = HuffNodec.parent;while (p != -1)if (HuffNodep.lchild = c)cd.bitcd.start = 0;elsecd.bitcd.start = 1;cd.start-;c = p;p = HuffNodec.parent;for (j = cd.start + 1；jn；j+)HuffCodei.bitj = cd.bitj;HuffCodei.start = cd.start;memset(coder，0，sizeof(coder);int temp=0;for (i = 0；in；i+)cout 信源 i 编码为：;for (j = HuffCodei.start + 1；j n；j+)cout HuffCodei.bitj;coderitemp= char(HuffCodei.bitj+48);temp+;temp = 0;cout 信源概率： Spi;cout 字长： strlen(coderi);printf(n);bitlongi = strlen(coderi);CodEffi();cout n编码效率： CodEffi() * 100 %n;return 0;/ 费诺编码.cpp ：定义控制台应用程序入口点。/#include stdafx.h#include #include#include#include#include #include #include#define Bmax 10 #define Smax 20 using namespace std;#define SourNum 20double SpSourNum;int bitlong100;void group1(int low，int mid，int high);void code(int low，int mid，int high);void ProSource()/产生非等概信源函数int n = 0;srand(unsigned)time(0);double sum = 0;while (1)Spn = (double)rand() / (RAND_MAX);/产生随机浮点数sum = sum + Spn;if (sum 1 & Spn 19)break;else continue;elsesum = sum - Spn;Spn = 0;continue;SpSourNum = 1 - sum;struct Bitchar bBmax； /定义码长度数组数据类型 字符型 构成成员int last;typedef struct symbol int c； double probability； struct Bit bit； sbl;sbl sSmax； /*输入符号符号概率*/void input(int n)int i； int c； for (i = 0；in；i+) si.c = i； si.probability = Spi； /*用冒泡法排序*/void code(int low，int mid，int high) int i； for (i = low；ihigh；i+) if (imid) si.bit.bsi.bit.last = 0； si.bit.last+;elsesi.bit.bsi.bit.last = 1； si.bit.last+;void sort(int n)double t； char a； int i，j； for (i = 1；in；i+) for (j = 0；jn - i；j+) if (sj.probabilitysj + 1.probability) t = sj.probability;a = sj.c;sj.probability = sj + 1.probability;sj.c = sj + 1.c;sj + 1.probability = t;sj + 1.c = a; /*分组函数*/void group(int n) int i，pmid，plow，phigh； pmid = phigh = n； plow = 0； for (i = 0；in；i+) si.bit.last = 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；imid；i+) d += si.probability； dmin = d - 2 * slow.probability； for (i = low + 1；ihigh；i+) d = fabs(dmin - 2 * si.probability)； if (ddmin) dmin = d;else break;mid = i； code(low，mid，high);group1(low，mid，mid)； group1(mid，high，high);void output(int n) int i，j； printf(费诺编码输出信源,概率及编码：nn)； for (i = 0；in；i+) cout 信源：si.c 概率：si.probability 编码：； for (j = 0；jsi.bit.last；j+)cout si.bit.bj； bitlongi = si.bit.last;cout 字长 bitlongi;printf(n);double CodEffi( )int AveraLong =0,SumLong=0;double H=0,CE=0;for (int i = 0；i SourNum；i+)SumLong = SumLong + bitlongi;AveraLong = SumLong / SourNum;for (int j=0；j SourNum；j+)H = (-Spj)*(log(Spj) / log(2) + H;CE = H / AveraLong;return CE;void main() /主函数int n = SourNum； /定义变量ProSource();input(n)； /分别调用输入、排序、分组、输出函数，并执行sort(n);group(n);output(n);cout n编码效率： CodEffi() * 100 %n; / 香农编码.cpp ：定义控制台应用程序入口点。/#include stdafx.h#include #include#include#include#include #include #include#include#define Bmax 10 /最长码长度#define Smax 20 using namespace std;#define SourNum 20double SpSourNum;int bitlong100;struct shanint s;double p;double padd;double l_f;int l;char w20;shan SourDataSourNum;void group1(int low，int mid，int high);void code(int low，int mid，int high);void ProSource()/产生非等概信源函数int n = 0;srand(unsigned)time(0);double sum = 0;while (1)Spn = (double)rand() / (RAND_MAX);/产生随机浮点数sum = sum + Spn;if (sum 1 & Spn 19)break;else continue;elsesum = sum - Spn;Spn = 0;continue;SpSourNum = 1 - sum;int i，j，n，k，b;double addp;char bitw20;void sequ(struct shan x，int n)struct shan temp;for (i = 0；in；i+)for (j = i；jn；j+)if (xi.pxj.p)temp = xj;xj = xi;xi = temp;void countpadd(struct shan x，int n)addp = 0;x0.padd = 0;for (i = 0；in；i+)addp += xi.p;xi + 1.padd = addp;void count_l(struct shan x，int n)for (i = 0；i0)xi.l = (int)xi.l_f + 1;else xi.l = (int)xi.l_f;void covbit(double a，int lc)for (j = 0；jlc；j+)b = (int)(a * 2);bitwj = b + 48;a = 2 * a - int(a * 2);double CodEffi()int AveraLong = 0，SumLong = 0;double H = 0，CE = 0;for (int i = 0；i SourNum；i+)SumLong = SumLong + bitlongi;AveraLong = SumLong / SourNum;for (int j = 0；j SourNum；j+)H = (-Spj)*(log(Spj) / log(2) + H;CE = H / AveraLong;return CE;int main()n = SourNum;ProSource();for (i = 0；in；i+)SourDatai.s= i;/*获取信源概率*/for (i = 0；in；i+)SourDatai.p=Spi;sequ(SourData，n);countpadd(SourData，n);count_l(SourData，n);for (i = 0；in；i+)covbit(SourDatai.padd，SourDatai.l);strcpy(SourDatai.w，bitw);/*输出数据*/cout.fill( );for (i = 0；in；i+)cout left setw(6) 信源符号： SourDatai.s 信源概率： SourDatai.p 累加概率SourDatai.padd 字长：SourDatai.l 码字： SourDatai.wn;for (i = 0；i SourNum；i+)bitlongi = SourDatai.l;cout n编码效率： CodEffi() * 100 %n;return 0;