信息论课程设计

1、电子科技大学电子工程学院信息论课程设计报告课程名称：信息编码与加密课程设计报告学生姓名： 农瀚学号： 2014020908021 指导教师： 李万春一、课程设计名称： 编程实现霍夫曼、费诺、香农编码二、课设原理：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 (整数)：log Ki=取整 为了编成唯一可译码，计算第i个消息的累加概率U 将累加概率Pi变换成二进

3、制数。 取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 中删除这两棵树，并把这棵新的二

4、叉树同样以升序排列加 入到集合 F 中。（4）重复二和三两步，直到集合 F 中只有一棵二叉树为止。2、费诺编码的编程思路：（ 1）先使用冒泡法对信源概率概率排序；（2）依次将按排好序的符号概率进行近似 1:1 分成两大组；（3）对各组赋予一个二进制码元“ 0”和“ 1”；（ 4）输出符号 ,符号概率及编码。3、香农编码：（ 1）对于一个给定的符号列表， 制定了概率相应的列表或频率计数， 使每个符号的相对发生频率是已知。（2）排序根据频率的符号列表，最常出现的符号在左边，最少出现 的符号在右边。（3）清单分为两部分，使左边部分的总频率和尽可能接近右边部分 的总频率和。（ 4）该列表的左半边分配二

5、进制数字 0，右半边是分配的数字 1。这 意味着，在第一半符号代都是将所有从 0 开始，第二半的代码都从 1 开始。（ 5）对左、右半部分递归应用步骤 3 和 4，细分群体，并添加位的 代码，直到每个符号已成为一个相应的代码树的叶。五、器材（设备、元器件）：计算机、visual studio2017社区版六、设计代码：见附录九、实验数据及结果根据上述实验程序得到的实验数据及结果如下:霍夫曼编码：型 !|/!:Tm32'r.exe信源1编码为: 信源2编码为； 言澹瑚码九信源鑼码为:. 信源5编码为I 害源6编码为: 信源F编码为: 信源名編码为; 信源g编码为10编码为: 11编希为1

6、 1龙编码为 编码为:1鑫码为I 15编码为I16编码为; 折编码为r18编码为* M编码为2信源 信源 肓源信源 信源 信源信源 信污 信糠信源10010001001001010100 010101 100101 01000 01001 01011 10011 0000000100100011 0110 0111 1000 1100 1101 1110 1111信源率 o. 00695S22 彳言嘛概率：0. 00753807 信源範率】Q.Q1049呂4 彳言源概車：0. 0144047 彳言源概率0. 0156865 信源概率 信源概率 信源概率 信源概率 信源概率：信源概率 信源概率

7、信源概率 信源概率 信源概率 信源概率 信源概率 信源概率 信源概率 信源概率0,02331610. 02352980. 02975550, 04245116 04324470. 04330550. 04477070. 04644920. 0552696 05551320. 06357010. 07565540. 08059940.0815760. 08542137 74a HM氐/只 5555 444 4444 4 字字誌#*怜恰怜怜島怜仪论后恰恰怜怜島怜 字亠子字字孚字字丼字字字齐字字字字井字90. 9645%青®e意雇继续.费诺编码:赛诺削瑚岀信涼原舉原屎原舉原原県專甲原原原舉

8、第東原果昂 .Ju- J.£ .-IL- ?.IJU >.-lv .-SL- >.JV .-Sv r.vjv .-.V .H.JV .-u 1.1% .L .it .It .ijb 兰口亠-_2_旨七H±旨七宵亠一旨土一冃亠一-口亠二=亠=口亠二口亠= ui一日亠-a 4二口亠一一口±-口±一R±一口 I JI JI 1 JI jl JI JI JI JI JI 1J1 JI JI JI JI JI ijl I JI JI !J1133 M165 1 GO7 9 8 O 4 5 24171921101611概率:概率：槪率:砥率，孵

9、：概率，概率:概率: 槪率| 踣：罐率:槪率:砥率；槪率:孵;0.083&5970.0E26441EL OBlOGfifi0.07675410.07434310.060LS20.05389570.0524&130.05038610.04555140.0453810.03344a30.02203440.021179S0.01516770.01461S40.01321450.0078737S0.007538070.00375378编玛：000编码：001窮玛：010编祐0110编岔：0111 编码,1000编码：1001 塲码m编码：1011 编咼1100 媳码：11QL0 编码n

10、on 塢码1HQ0爲 111010编咼：111011编码 111100 编码HLWIO 编码；1111011 编码：11111。 塢码：1111117 7 6 66 6'<3 3 0 4 4 4 .M 4tE老 宇字宇字 长C3长长e4底长斗也斗耳-.L 字誌字字字袂字抖字抖字字字香农编码: '' C:-U s-ersh0scedainjmentsvisual studio 201 APTojectsS.ZcsSDebugVSSrfire-xeW符符第符符符符符符符符符符特符符符符 'ut耳好总廉st康u&-果麻原黙 咖屎u&-廉显原环 &

11、#171; - IL也J1JU 5.Jt J十 J七 J右?lv .J右 .喘 PJV IL14U ?lv 一口兰冃七西亠百=S-B兰£石兰口亠言亠一吏一一冃士Q亠一一曰亠二口兰口亠_口吉5一更-旨 J . .1'HU 1111 J.J., 丄4-广 1J;丄鼻；号号号号号号号号号号号号号号号号号号号号516714 0196ZD1512324111B131言洱概率: 信源概率信源槪率: 信源概率信漁概率; 信潺概率:信源概率| 信源概率：信源概率; 信源概率：信源槪率,信源概率:信淵概率, 倍源概率 唁裤概率! 信源髀信源概率:信源概率'信源概率:0. 0833155

12、0. 03233390. 0E056E90. 07840210.05645920.05264440.05209S10. 04S95170.04352440. 04321420.04058960. D3952150. 0299997Q, 02676470. 02459790l 0138 逍0.01748710. 01602220. 009216590. 00802637茶加概率D字氐累如概率0, 0333155 累加概率0.165654 第负概0. 2462S3累加概率D. 324625 黑加概率0. 3810S5累加概率0. 433729 勒槪率0. 4E5824 累加概率Q. 534776

13、累加槪率0. 5833第如概率0. 626514 黒加概率0. 667104 臺加概0. 706626 累加概率丄736625累加概率D. 76339 宝加概0. 7379S8累加概率D. 806879 累加槪率0. S24366 累加概率0. 840388 眈概0. 8496054 码字*字總4字怜4字吐：4字长.5字铠5字长5字铠5字长：5字怜5字也：5 字怜5 字#： 6 字怜6 字亀6 字艮6字怅.6 字£： 6字怜7字锂70000码字：0001 码字r 0010码字：0011 0101D码字：011005 帑 01101初字；01111 时；10001 码字.10010 帀

14、爭字：10100码字s 101D1玛字：101101玛字，101111 码字 I 110000 玛字 2 110010110011码字：110100可静 I 11D1D11 码字：1101100编码效率：73. 9Q97S十、结论完成了 20个非等概随机信源的霍夫曼、 费诺和香农编码， 并给出 了编码效率和码字。十一、总结及心得体会通过这次课程设计， 我掌握了三种编码方式的步骤， 并能够利用编程 实现编码，提高了自己的编程水平和对该知识点的掌握程度。附录代码：/ ConsoleApplication1.cpp : 定义控制台应用程序的入口点。 /*霍夫曼编码 */#include"s

15、tdafx.h"#include<algorithm>#include<iostream>#include<math.h>#include<stdlib.h>#include<stdio.h>#include<time.h>using namespace std;#defineSourNum20#defineMAXBIT 100#defineMaxValue 10000#defineMAXLEAF 30#defineMAXNODE MAXLEA*F2 -1double Sp SourNum;char coder1

16、00100;int bitlong100;void ProSource() / 产生非等概信源的函数int n = 0;srand( unsigned )time(0); double sum = 0;while (1)Spn = ( double )rand() / ( RAND_MA);X/ 产生随机浮点数 sum = sum + Spn;if (sum < 1 && Spn <0.086)n+;if (n >19)break ;else continue ;elsesum = sum - Spn;Spn = 0;continue ;SpSourNum =

17、 1 - sum;霍夫曼编码 */typedef structint bit MAXBIT; int start; HCode;typedef structdouble weight; double parent; double lchild; double rchild;int last; HNodeType; void HuffmanTree( HNodeType HuffNode MAXNOD,E int n)int i, j, x1, x2;double m1, m2;for (i = 0; i < 2 *n - 1; i+)HuffNode i.weight = 0;HuffN

18、ode i.parent = -1;HuffNode i.lchild = -1;HuffNode i.rchild = -1;for (i = 0; i <n; i+)HuffNode i.weight = Spi;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.weig

19、ht;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() / 求编

20、码效率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);HNodeT

21、ypeHuffNode MAXNOD;EHCodeHuffCode MAXLEAF, 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

22、;for (j = cd.start + 1; j<n; j+)HuffCodei.bitj = cd.bitj;HuffCodei.start = cd.start;memset(coder, '0' , sizeof (coder); int temp=0;for (i = 0; i<n; i+)cout << "信源 " << i <<" 编码为： " for (j = HuffCodei.start + 1; j < n; j+)cout << HuffCodei.

23、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

24、;/ 费诺编码 .cpp : 定义控制台应用程序的入口点。/#include"stdafx.h"#include<algorithm>#include<iostream>#include<math.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#include<cstring>#defineBmax10#define Smax20using namespace std;#define SourNum20 double Sp Sour

25、Num;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() / ( sum = sum + Spn;if (sum < 1 && Spn <0.086)RAND_MA);X/ 产生随机浮点数/n+

26、;if (n >19) break ;else continue elsesum = sum - Spn;Spn = 0;continueSpSourNum = 1 - sum;struct Bit/ 定义码长度数组的数据类型 字符型组成成员char b Bmax;int last;typedef struct symbolint c;double probability;struct Bit bit;sbl ; sbl s Smax;/* 输入符号的符号概率*void input( int n)int i;int c;for (i = 0; i<n; i+)si.c = i; s

27、bability = Spi;用冒泡法排序*void code( int low, int mid, int high )int i;for (i = low; i< high ; i+)if (i< mid)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; i<n; i+)for (j = 0; j<n - i; j

28、+)if (bability<sj + 1.probability) t = bability;a = sj.c;bability = 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; i< n; i+)si.bit.last = 0;group1(plow, pmid, phi

29、gh);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 += bability;dmin = d - 2 * slow .probability;for (i = low + 1; i< high ; i+) d = fabs(dmin - 2 * bability);if (d<dmin)dmin = d;elsebreak ;mid = i;code(

30、 low, mid, high );group1( low , mid, mid);group1( mid, high , high );void output( int n)int i, j;printf( " 费诺编码输出信源 , 概率及编码： nn" );for (i = 0; i< n; i+)cout << "信源： " <<si.c <<" " << "概率： " <<bability <<" "

31、; <<"编码：I!.Jfor (j = 0; j<si.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

32、= SumLong + bitlongi;AveraLong = SumLong / SourNum;for ( int j=0; j <SourNum; j+)H = (-Spj)*(log(Spj) / log(2) + H;CE = H / AveraLong;return CE;/ 主函数/ 定义变量/ 分别调用输入、排序、分组、<< "%n" ;void main()int n = SourNum;ProSource();input(n);输出函数，并执行sort(n);group(n);output(n);cout << "

33、;n 编码效率 : " << CodEffi() * 100/ 最长码长度/ 香农编码 .cpp : 定义控制台应用程序的入口点。 /#include"stdafx.h"#include<algorithm>#include<iostream>#include<math.h>#include<stdlib.h>#include<stdio.h>#include<time.h>#include<cstring>#include<iomanip>#defineB

34、max10#defineSmax20using namespace std;#defineSourNum20double Sp SourNum;int bitlong100;structshanint s; double p;double padd;double l_f;int l; char w20;shan SourData SourNum;void group1( int low, int mid, int high );void code( int low, int mid, int high );void ProSource() / 产生非等概信源的函数int n = 0;srand

35、( unsigned )time(0); double sum = 0;while (1)Spn = ( double )rand() / ( RAND_MA);X/ 产生随机浮点数 sum = sum + Spn;if (sum < 1 && Spn <0.086)/n+;if (n >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( st

36、ruct shan x, int struct shantemp;for (i = 0; i<n; i+)for (j =i; j<n; j+)if( xi.p< xj.p)temp = xj;xj = xi;xi = temp;void countpadd( struct shan x,addp = 0;x0.padd = 0;for (i = 0; i< n; i+)addp += xi.p;n)int n)xi + 1.padd = addp;void count_l( struct shan x, int n)for (i = 0; i< n; i+)xi.l_f = -log( xi.p) / log(2);int )xi.l_f)>0) int ) xi