《信息论课程设计样本.doc》由会员分享，可在线阅读，更多相关《信息论课程设计样本.doc（31页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、资料内容仅供您学习参考，如有不当之处，请联系改正或者删除。电子科技大学电子工程学院信息论课程设计报告课程名称: 信息编码与加密课 程 设 计 报 告学生姓名: 农瀚 学号: 指导教师: 李万春一、 课程设计名称: 编程实现霍夫曼、 费诺、 香农编码二、 课设原理: 1) 霍夫曼编码: 霍夫曼编码的平均码长最短, 是最佳编码。编码步骤如下: ( 1) 将信源符号按概率大小排序; ( 2) 对概率最小的两个符号求其概率之和, 同时给两幅 号分别赋予码元0和1; （3） 将概率之和当做一个新符号的概率。与剩下的概率 一起, 形成一个缩减信源, 再重复上述步骤, 直到概率和为1为止; （4） 按上述步
2、骤实际上构成了一个码树, 从根到端点经过的树枝即为码字。 2) 费诺编码: 编码步骤如下: （1） 将信源概率从大到小排序; （2） 将信源符号分成两组, 使两组信源符号的概率之和近似相等, 并给两组信源符号分别赋0和1; （3） 再把各个小组的信源符号细分为两组并赋码元, 方法与第一次分组相同; （4） 如此一直下去, 直到每一个小组只含一个信源符号为止; （5） 由此可构造成一个码树, 所有终端节点上的码字组成费诺码。 3) 香农编码: 编码方法如下: 将信源消息符号按其出现的概率大小依次排列p(u1)p(u2)p(un)确定码长Ki(整数): Ki= 取整为了编成唯一可译码, 计算第i个
3、消息的累加概率将累加概率Pi变换成二进制数。取pi二进制数的小数点后Ki位即为该消息符号的二进制数。三、 课设目的: 经过编程实现三种方式的编码, 掌握三种编 码方式的步骤。四、 课设内容: 三种编码方式的编程思路: 1、 霍夫曼编码: ( 1) 对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F= T1,T2,T3,.,Ti,.,Tn, 其中每棵二叉树Ti中只有一个权值为Wi的根结点, 它的左右子树均为空。( 为方便在计算机上实现算 法, 一般还要求以Ti的权值Wi的升序排列。) ( 2) 在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树, 新二叉树的
4、根结点的权值为其左右子树的根结点的权值之和。( 3) 从F中删除这两棵树, 并把这棵新的二叉树同样以升序排列加入到集合F中。( 4) 重复二和三两步, 直到集合F中只有一棵二叉树为止。2、 费诺编码的编程思路: ( 1) 先使用冒泡法对信源概率概率排序; ( 2) 依次将按排好序的符号概率进行近似1:1分成两大组; ( 3) 对各组赋予一个二进制码元”0”和”1”; ( 4) 输出符号,符号概率及编码。3、 香农编码: ( 1) 对于一个给定的符号列表, 制定了概率相应的列表或频率计数, 使每个符号的相对发生频率是已知。( 2) 排序根据频率的符号列表, 最常出现的符号在左边, 最少出现的符号
5、在右边。( 3) 清单分为两部分, 使左边部分的总频率和尽可能接近右边部分的总频率和。( 4) 该列表的左半边分配二进制数字0, 右半边是分配的数字1。这意味着, 在第一半符号代都是将所有从0开始, 第二半的代码都从1开始。( 5) 对左、 右半部分递归应用步骤3和4, 细分群体, 并添加位的代码, 直到每个符号已成为一个相应的代码树的叶。五、 器材( 设备、 元器件) : 计算机、 visual studio 社区版六、 设计代码: 见附录九、 实验数据及结果根据上述实验程序得到的实验数据及结果如下: 霍夫曼编码: 费诺编码: 香农编码: 十、 结论 完成了20个非等概随机信源的霍夫曼、 费
6、诺和香农编码, 并给出了编码效率和码字。十一、 总结及心得体会经过这次课程设计, 我掌握了三种编码方式的步骤, 并能够利用编程实现编码, 提高了自己的编程水平和对该知识点的掌握程度。附录代码: / ConsoleApplication1.cpp : 定义控制台应用程序的入口点。/*霍夫曼编码*/#include stdafx.h#include #include#include#include#include #include using namespace std;#define SourNum 20#define MAXBIT 100#define MaxValue 10000#defin
7、e 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;co
8、ntinue;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
9、;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
10、.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 =
11、 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;
12、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
13、 = 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编码效率: CodEf
14、fi() * 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
15、 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;ty
16、pedef 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
17、+;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
18、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.probab
19、ility; 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
20、 (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) +
21、 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 Bma
22、x 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;sra
23、nd(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;
24、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)
25、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 =
26、 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;