电子科技大学电子工程学院信息论课程设计报告课程名称：信息编码与加密课程设计报告学生姓名：农瀚学号：21 指导教师：李万春一、课程设计名称：编程实现霍夫曼、费诺、香农编码二、课设原理：1）霍夫曼编码：霍夫曼编码的平均码长最短，是最佳编码。

编码步骤如下：（1 ）将信源符号按概率大小排序；（2）对概率最小的两个符号求其概率之和，同时给两幅号分别赋予码元0和1 ；（3）将概率之和当做一个新符号的概率。

与剩下的概率一起，形成一个缩减信源，再重复上述步骤，直到概率和为1为止；（4）按上述步骤实际上构成了一个码树，从根到端点经过的树枝即为码字。

2）费诺编码：编码步骤如下：（1）将信源概率从大到小排序；（2）将信源符号分成两组，使两组信源符号的概率之和近似相等，并给两组信源符号分别赋0和1；（3）再把各个小组的信源符号细分为两组并赋码元，方法与第一次分组相同；（4）如此一直下去，直到每一个小组只含一个信源符号为止；（5）由此可构造成一个码树，所有终端节点上的码字组成费诺码。

3)香农编码：编码方法如下：⑴将信源消息符号按其出现的概率大小依次排列p(u1) > p(u2)》p(un)⑵确定码长Ki (整数)：1»S —Ki=[ ]——取整⑶ 为了编成唯一可译码，计算第i个消息的累加概率Pi=工>(・Ju⑷ 将累加概率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社区版六、 设计代码：见附录 九、实验数据及结果根据上述实验程序得到的实验数据及结果如下: 霍夫曼编码：ows\&yst&e 3 2、,匚 IT □ .ese扁码效率：90. 9645% 青按任意键继缜...费诺编码:1001000言源1编码沏 講2编玛为: 言源3编码为;言源5編码为: 盲源6编码为= 言源7编码均: 言源g 编码^ = 言凉9編码为. 詬换10^码为 莒源谕码关 言源1臨码共 言源1錮码均 言源1味帀软 言源谕砌 言源丘肃码为 言原1褊码共 謫1牆趾 諦19编話* 1001001010100 010101100101 OlOOOOlOOlulOU 10011 QOQO 1O1 O V -I X ■ - ■- o o :I'...:1000 :11001101:£f n F孵孵孵幣幣审率気率障率曇$:审棘陞率 鮒翎棘腮槪噸觥紀胪酰貯號噸W 概概概辟 討討割源源源源麻派源源源源' 湖源、>源瀕 信信肓宿訣信信信信信信信信信(0. 006<35822 =0,00753SC70. 0104®4 0.01440470.01568&5(X 0233161 C-. 0235258 C. 0297砧5 0. 0424512.0432447 C. 043305S 0. 0447707 C. 0464492 0. 0E5269 6 0555庇 Q. 0^357010. 0陀£氐40. 0505^94 0. aS 15760. 0354213长#8左怜I ・・ A - R w5 5 E -E 4 4 4 4 4 4 4 4444 s 4F ■■■■ti i ■申 s s i 长长檢长口长长长口长长长长 字字字字护字字字齐字宇宇31679-3o152-■TM-■-■-■OKr1Jiu7r-tsni1■■■-■-■£M-■-w嘛圍W.1II痢為w.囲漏販線遍囲诵iEI诵瓯w.怖师.1r^-F--=1--!:』=i'l」一—一1」-」』—」=」』—'--I4」_iD■I4一-11■I9科;辭.柢名寿;0.0.3355^7山06覇4410,<33102300■帧541“.G743431O.CW1520.0E融硏工行珈?G.CaQKlO.C45^H(I.fl4f3810.胡34俯Q r QQ203440*0211798Q+M5此和0.0141134XL32 価0.0C7S7J780.00753807 FFr-：襦彳F M r 觀CD'昴碍I 010和无011Q0111 需咼1000編码"：皿1 编五101J 希不nji1011 编祐1100編础：:K J W編码11011 畲码；「】1皿罰勺mon111011 筍％uubo 却 K1111GL0 編码1 11 11111 苗礼111MQ nun&&145-55-F*w诵汨'障:H.40 肓持总衽磁録飯*・，香农编码:-」一一匚一4三二一匸•一一」•-三一-■一一■-■---■.怦龄J：脖4：胯時能胖律膀符硏符笛將询斑癡疥ife翊麋媳W嚟穩頫漏诟盪漏碾屢测=门兰口亠一一旨一|7二==|•言-Hwtpa-.2口亠口士I-J二C.亠一」.=2一曰=1亠一n亠=金J^1—Jn.pf—..I'diI■up■1・I■■I-■I-r—1・I■■■11dIIInpp!—.>8I4i1751671410154111813信awBi 信棕册率借痺擴率，措课棣幸;信蹄率：信潭概率|恬裤機車：仁原嘅率:疳砺播I率1仁谛堀％信暁糰率.肓蓿概率’信■凉探率I 信诵撮鞋蓿凉棵率.0.083315& 累和概率Q -L：.0.082333^ 累加槪率0.0B33155 CL0S056S9 宝加擁率［.H5G54I：. C T S402L 羞麵槪率山1452230. OE64S92 累加槪李H 左圧0L0626444 里祐槪車0, 3S10BS D”052M6I 景加概率0. 433729L. U489S17 禀畑稱率D. 40S8240.04E5244 第加用率匚5：477FOL M32L42 玺加概率D, 5片益0. 0405896 累血瞬0. 6265M010396215 霖知糅率D,朋FL04 0L理獗听髯负愉皋0, ?06626 r.02&^647 舉扪飯主0.73^626Q. 0245^79 累加恼丰Q. 763390. 0L8S9L 至H槪卞山?S?9SSD.iX T437: *加棣率「.方亦产C CUO222 累加薇率乩沁66C. C0^21 需9 寧tn 熾丰0.P1OFP8 Q+ WBO2MT S 加海車Q,曰496C5宇456&&7756-E-=■I66:pE卷聖1宇0001码孚=C0G1 裡字.ODLQ4：C11码字:OJ010畤,01100码孚:OJ101 两卒.C1L11 逼乎，19001 字：10DL0凸卒，10100 衬辛士10101 网宇，101101 玛电101111 咼字，11QDOO F)4：Iiieoio玛宇 1 110011 與字I 110100 码字1 1101011 码黑11C11Q0謁就芒率：72. 9O97X十、结论完成了20个非等概随机信源的霍夫曼、费诺和香农编码，并给出了编码效率和码字。

十^一、总结及心得体会通过这次课程设计，我掌握了三种编码方式的步骤，并能够利用编程实现编码，提高了自己的编程水平和对该知识点的掌握程度。

附录代码:// ConsoleApplicationl.cpp : 定义控制台应用程序的入口点。

//霍夫曼编^码*************/*******#include "stdafx.h"#include 《algorithm〉#include <iostream>#include <math.h>#include <stdlib.h>#include <stdio.h>#include <time.h>using namespace std;#define SourNum20#define MAXBIT 100#define MaxValue 10000#define MAXLEAF 30#define MAXNODE MAXLEAF! -1double Sp[ SourNunj；char coder[100][100];int bitlong[100];void ProSource() //产生非等概信源的函数{int n = 0;srand(( unsigned )time(O)); double sum = 0;while (1){Sp[n] = ( double )rand() / ( RAND_MAX〃产生随机浮点数sum = sum + Sp[n];if (sum < 1 && Sp[n] <0.086){n++;if (n >19)break;else continue ;}else{sum = sum - Sp[n];Sp[n] = 0;continue ;}}Sp[SourNum = 1 - sum;霍夫曼编码***********typedef struct{int bit[ MAXBIT； int start;} HCodetypedef struct{double weight; double parent;double lchild;double rchild;int last;} HNodeType void HuffmanTree( HNodeType HuffNode [ MAXNODE int n) { int i, j, x1, x2;;double m1, m2;for (i = 0; i < 2 * n - 1; i++){HuffNode [i].weight = 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() // 求编码效率{int AveraLong = 0, SumLong = 0; double H = 0, CE = 0;for ( int i = 0; i < SourNum i++){SumLong = SumLong + bitlong[i];}AveraLong = SumLong / SourNumfor ( int j = 0; j < SourNum j++){H = (-Sp[j])*(log(Sp[j]) / log(2)) + H;}CE = H / AveraLong;return CE;}int main(){ProSource();sort(Sp, Sp + SourNun);HNodeTypeHuffNode[ MAXNODEHCodeHuffCode[ MAXLEAFcd;int i, j, c, p, n;n = SourNumHuffmanTree(HuffNode, SourNum+ 1);for (i = 0; i < n; i++){cd.start = n - 1;c = i;p = HuffNode[c].parent;while (p != -1){if (HuffNode[p].lchild == c)cd.bit[cd.start] = 0;elsecd.bit[cd.start] = 1; cd.start--;c = p;p = HuffNode[c].parent;}for (j = cd.start + 1; j<n; j++)HuffCode[i].bit[j] = cd.bit[j];}HuffCode[i].start = cd.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];char (HuffCode[i].bit[j]+48);temp++; temp = 0;bitlong[i] = strlen(coder[i]);CodEffi(); return 0; //费诺编码.cpp :定义控制台应用程序的入口点。