信息论专业课程设计.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 <algorithm>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
using namespace std;
#define SourNum 20
#define MAXBIT 100
#define MaxValue 10000
#define MAXLEAF 30
#define MAXNODE MAXLEAF*2 -1

double Sp[SourNum];
char coder[100][100];
int bitlong[100];
void ProSource()//产生非等概信源函数
{
int n = 0;
srand((unsigned)time(0));
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;
} HCode;
typedef 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 / SourNum;
for (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 + SourNum);
HNodeType HuffNode[MAXNODE];
HCode HuffCode[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 = HuffNode[c].parent;
while (p != -1)
{
if (HuffNode[p].lchild == c)
cd.bit[cd.start] = 0;
else
cd.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];

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;
}

// 费诺编码.cpp ：定义控制台应用程序入口点。
//

#include "stdafx.h"
#include <algorithm>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<cstring>
#define Bmax 10
#define Smax 20
using namespace std;
#define SourNum 20
double Sp[SourNum];
int bitlong[100];
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)
{

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;

}
struct Bit
{
char b[Bmax]； //定义码长度数组数据类型 字符型 构成成员
int last;
};
typedef struct symbol
{
int c；
double probability；
struct Bit bit；
}sbl;
sbl s[Smax]；
/********输入符号符号概率********/
void input(int n)
{
int i；
int c；

for (i = 0；i<n；i++)
{
s[i].c = 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].bit.b[s[i].bit.last] = '0'；
s[i].bit.last++;
}
else
{
s[i].bit.b[s[i].bit.last] = '1'；
s[i].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++)
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].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；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;
else
break;
}
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].bit.last；j++)
cout<< s[i].bit.b[j]；
bitlong[i] = s[i].bit.last;
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() //主函数
{
int n = SourNum； //定义变量
ProSource();
input(n)； //分别调用输入、排序、分组、输出函数，并执行
sort(n);
group(n);
output(n);
cout << "\n编码效率： " << CodEffi() * 100 << "%\n";

}
// 香农编码.cpp ：定义控制台应用程序入口点。
//

#include "stdafx.h"
#include <algorithm>
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<time.h>
#include<cstring>
#include<iomanip>
#define Bmax 10 //最长码长度
#define Smax 20
using namespace std;
#define SourNum 20
double Sp[SourNum];
int bitlong[100];

struct shan
{
int s;
double p;
double padd;
double l_f;
int l;
char w[20];
};
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((unsigned)time(0));
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;

}
int i，j，n，k，b;
double addp;
char bitw[20];

void sequ(struct shan x[]，int n)
{
struct shan temp;
for (i = 0；i<n；i++)
for (j = i；j<n；j++)
{
if (x[i].p<x[j].p)
{
temp = x[j];
x[j] = x[i];
x[i] = temp;
}
}
}

void countpadd(struct shan x[]，int n)
{
addp = 0;
x[0].padd = 0;
for (i = 0；i<n；i++)
{
addp += x[i].p;
x[i + 1].padd = addp;
}
}
void count_l(struct shan x[]，int n)
{
for (i = 0；i<n；i++)
{
x[i].l_f = -log(x[i].p) / log(2);
if ((x[i].l_f - (int)x[i].l_f)>0)
x[i].l = (int)x[i].l_f + 1;
else x[i].l = (int)x[i].l_f;
}
}
void covbit(double a，int lc)
{
for (j = 0；j<lc；j++)
{
b = (int)(a * 2);
bitw[j] = 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 + 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;
}
int main()
{
n = SourNum;
ProSource();
for (i = 0；i<n；i++)
{
SourData[i].s= i;
}
/*获取信源概率*/
for (i = 0；i<n；i++)
{

SourData[i].p=Sp[i];
}
sequ(SourData，n);
countpadd(SourData，n);
count_l(SourData，n);

for (i = 0；i<n；i++)
{
covbit(SourData[i].padd，SourData[i].l);
strcpy(SourData[i].w，bitw);
}
/*输出数据*/

cout.fill(' ');
for (i = 0；i<n；i++)
cout << left << setw(6) <<"信源符号： "<< SourData[i].s<<" 信源概率： "<<SourData[i].p<<" 累加概率"<<SourData[i].padd<<" 字长："<<SourData[i].l<<" 码字："<< SourData[i].w<<"\n";
for (i = 0；i < SourNum；i++)
{
bitlong[i] = SourData[i].l;
}
cout << "\n编码效率： " << CodEffi() * 100 << "%\n";
return 0;
}