信息论与编码实验报告
20##年12月29日
实验目的:
1.进一步熟悉唯一可译码判别准则;
2.掌握C语言字符串处理程序的设计和调试技术。
实验内容:
1.已知:信源符号数和码字集合C;
2.输入:任意的一个码,码字的个数和每个具体的码字在运行时从键盘输入;
3.输出:判决(是唯一可译码/不是唯一可译码);循环(若继续判决则输入1循环判决,否则输入0结束运行)。
实验原理:
根据唯一可译码的判别方法,利用数据结构所学的知识,定义字符串数据类型并利用指针进行编程来实现算法。
算法:1、考察C 中所有的码字,若Wi是 Wj的前缀,则将对应的后缀作为一个尾随后缀码放入集合Fi+1中;
2、考察C和Fi俩个集合,若Wi ∈C是 Wj∈F的前缀或Wi ∈F是 Wj∈C的前缀,则将相应的后缀作为尾随后缀码放入集合Fi+1中;
3、F=∪Fi即为码C的尾随后缀集合;
4、若F中出现了C中的元素,算法终止,返回假(C不是唯一可译码);否则若F中没有出现新的元素,则返回真。
实验环境及实验文件存档名:
1.实验环境:visual C++ 6.0
2.文件名 :weiyikeyi.cpp
实验结果及分析:
1.源代码:
#include<stdio.h>
#include<string.h>
char c[100][50];
char f[300][50];
int N,sum=0; //N为输入码字的个数,sum为尾随后缀集合中码字的个数
int flag;//判断是否唯一可译标志位
void patterson(char c[],char d[]) //检测尾随后缀
{
int i,j,k;
for(i=0;;i++)
{
if(c[i]=='\0'&&d[i]=='\0')//2字符串一样,跳出
break;
if(c[i]=='\0') //d比c长,将d的尾随后缀放入f中
{
for(j=i;d[j]!='\0';j++) f[sum][j-i]=d[j];
f[sum][j-i]='\0';
for(k=0;k<sum;k++)
{
if(strcmp(f[sum],f[k])==0) //查看当前生成的尾随后缀在f集合中是否存在
{
sum--;break;
}
}
sum++;
break;
}
if(d[i]=='\0') //c比d长,将c的尾随后缀放入f中
{
for(j=i;c[j]!='\0';j++) f[sum][j-i]=c[j];
f[sum][j-i]='\0';
for(k=0;k<sum;k++)
{
if(strcmp(f[sum],f[k])==0) //查看当前生成的尾随后缀在 f集合中是否存在
{
sum--;break;
}
}
sum++;
break;
}
if(c[i]!=d[i])//字符不一样了也退出
break;
}
}
void yima()
{
int i,j;
printf(" ********唯一可译码判别********\n");
printf("请输入码字的个数:");//输入码得个数
scanf("%d",&N);
while(N>100)
{
printf("输入码字个数过大,请输入小于100的数\n");
printf("请输入码字的个数:");
scanf("%d",&N);
}
flag=0;
printf("请分别输入码字:\n");
for(i=0;i<N;i++)
{
scanf("%s",&c[i]);
}
for(i=0;i<N-1;i++)//判断如果码本身是否重复
for(j=i+1;j<N;j++)
{
if(strcmp(c[i],c[j])==0)
{flag=1;break;}
}
if(flag==1)//如果码本身有重复,就可以断定它不是唯一可译码
{
printf("这不是唯一可译码。\n");
}
else
{
for(i=0;i<N-1;i++) //此处是根据原始编码生成的尾随后缀集合s[1]放 入f中
{
for(j=i+1;j<N;j++)
{
patterson(c[i],c[j]);
}
}
for(i=0;;i++) //根据原始码与s[i]生成s[i+1]也放入f[i]
{
int s=0;
for(j=0;j<N;j++)//判断s[i+1]中的字符串是否与s[i]中一样 , 重复的则不再添加
{
if(i==sum)
{ s=1;break;}
else
patterson(f[i],c[j]);
}
if(s==1)break;
}
for(i=0;i<sum;i++) //判断p里的字符串是否与s 中重复, 重复则不是唯一的
{
for(j=0;j<N;j++)
{
if(strcmp(f[i],c[j])==0)
{
flag=1;
break;
}
}
}
if(flag==1)
{
printf("这不是唯一可译码!\n");
}
else
printf("这是唯一可译码!\n");
}
}
void main()
{
int flag=1;
while(flag){
yima();
printf("是否继续判别?1/0\n");
scanf("%d",&flag);
}
}
2.运行结果
(1)输入0,01,001时:
(2)继续执行,输入1,01,10,1010
(3)结束执行
实验目的:
1.进一步熟悉Huffman编码过程;
2.掌握C语言递归程序的设计和调试技术。
实验内容:
1. 输入:信源符号个数r、信源的概率分布P;
2. 输出:每个信源符号对应的Huffman编码的码字。
实验原理:
1.将q个信源符合按概率大小递减排列;
2.用“0,1”码符号分别代表概率最小的两个信源符号,并将这两个概率最小的信源符号合并成一个,从而得到只包含q-1个符号的新信源,称为缩减信源;
3.把缩减信源的符号仍按概率大小递减次序排列,再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示,并且合并成一个符号,这样又形成了q-2个信源符号的缩减信源;
4.依次继续下去,直至信源符号最后只剩下两个信源符号为止,将这最后两个信源符号分别用二元码符号“0”和“1”表示;
5.然后从最后一级缩减信源开始,进行回溯,就得到各信源符号所对应的码符号序列,即对应的码字。
实验环境及实验文件存档名:
1.实验环境:visual C++ 6.0
2.文件名 :Huffman.cpp
实验结果及分析:
1.程序源代码:
#include<stdio.h>
#define N 50
#define maxval 10000.0
#define maxsize 100
typedef struct
{
char ch;
float weight;
int lchild,rchild,parent;
}hufmtree;
typedef struct
{
char bits[N]; //位串
int start; //编码在位串中的起始位置
char ch; //字符
}codetype;
void huffman(hufmtree tree[]);//建立哈夫曼树
void huffmancode(codetype code[],hufmtree tree[]);//根据哈夫曼树求出哈夫曼编码
int n;
int m;
void main()
{
printf("输入信源符号个数\n");
scanf("%d",&n);
getchar();
m = 2*n-1;
printf(" *****霍夫曼哈夫曼编码*****\n");
printf("总共有%d个字符\n",n);
hufmtree tree[2*N-1];
codetype code[N];
int i,j;//循环变量
huffman(tree);//建立哈夫曼树
huffmancode(code,tree);//根据哈夫曼树求出哈夫曼编码
printf("输出每个字符的哈夫曼编码\n");
for(i=0;i<n;i++)
{
printf("%c: ",code[i].ch);
for(j=code[i].start;j<n;j++)
printf("%c ",code[i].bits[j]);
printf("\n");
}
}
void huffman(hufmtree tree[])//建立哈夫曼树
{
int i,j,p1,p2;//p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标
float small1,small2,f;
char c;
for(i=0;i<m;i++) //初始化
{
tree[i].parent=0;
tree[i].lchild=-1;
tree[i].rchild=-1;
tree[i].weight=0.0;
}
printf("依次读入前%d个结点的字符及权值(中间用空格隔开)\n",n);
for(i=0;i<n;i++) //读入前n个结点的字符及权值
{
printf("输入第%d个字符为和权值",i+1);
scanf("%c %f",&c,&f);
getchar();
tree[i].ch=c;
tree[i].weight=f;
}
for(i=n;i<m;i++) //进行n-1次合并,产生n-1个新结点
{
p1=0;p2=0;
small1=maxval;small2=maxval; //maxval是float类型的最大值
for(j=0;j<i;j++) //选出两个权值最小的根结点
if(tree[j].parent==0)
if(tree[j].weight<small1)
{
small2=small1; //改变最小权、次小权及对应的位置
small1=tree[j].weight;
p2=p1;
p1=j;
}
else
if(tree[j].weight<small2)
{
small2=tree[j].weight; //改变次小权及位置
p2=j;
}
tree[p1].parent=i;
tree[p2].parent=i;
tree[i].lchild=p1; //最小权根结点是新结点的左孩子
tree[i].rchild=p2; //次小权根结点是新结点的右孩子
tree[i].weight=tree[p1].weight+tree[p2].weight;
}
}//huffman
void huffmancode(codetype code[],hufmtree tree[])//根据哈夫曼树求出哈夫曼编码
//codetype code[]为求出的哈夫曼编码
//hufmtree tree[]为已知的哈夫曼树
{
int i,c,p;
codetype cd; //缓冲变量
for(i=0;i<n;i++)
{
cd.start=n;
cd.ch=tree[i].ch;
c=i; //从叶结点出发向上回溯
p=tree[i].parent; //tree[p]是tree[i]的双亲
while(p!=0)
{
cd.start--;
if(tree[p].lchild==c)
cd.bits[cd.start]='0'; //tree[i]是左子树,生成代码'0'
else
cd.bits[cd.start]='1'; //tree[i]是右子树,生成代码'1'
c=p;
p=tree[p].parent;
}
code[i]=cd; //第i+1个字符的编码存入code[i]
}
}
2.运行结果
信息论与编码理论课程实验报告
实验:无失真信源编码技术在数据压缩中的应用
实验1绘制二进熵函数曲线串联信道容量曲线一实验内容用Excel或Matlab软件制作二进熵函数曲线串联信道容量曲线二实验环境1计算…
信息论实验实验一哈夫曼编码HuffmanCoding是一种编码方式哈夫曼编码是可变字长编码VLC的一种Huffman于19xx年提…
信息论与编码上机实验报告实验名称信息论与编码学院计算机与通信工程学院专业班级计算机1004姓名李春醒学号4105034920xx年…
实验一唯一可译码的判决准则实验目的1进一步熟悉唯一可译码的判决准则2掌握程序字符处理程序的设计和调试技术实验要求已知信源个数r码字…
中南大学信息论与编码实验报告姓名xxxxx学号xxxxxxxx专业电子信息工程班级电子信息xxxx班指导老师xx实验一关于信源熵的…
课程名称姓名系专业年级学号指导教师职称实验报告信息论与编码年月日目录实验一信源熵值的计算1实验二Huffman信源编码5实验三Sh…
课程名称姓名系专业年级学号指导教师职称实验报告信息论与编码年月日1实验三Shannon编码一实验目的1熟悉离散信源的特点2学习仿真…
中南大学信息论与编码题目关于编码的实验学生姓名杨家骏指导教师赵颖学院信息科学与工程学院学号0909101123专业班级电子信息10…
信息论与编码编码部分实验报告课程名称信息论与编码实验名称关于香农码费诺码Huffman码的实验学院信息科学与工程学院班级电子信息工…
计算机与信息工程学院综合性实验报告一实验目的根据霍夫曼编码的原理用MATLAB设计进行霍夫曼编码的程序并得出正确的结果二实验仪器或…
中北大学数据结构课程设计说明书20xx年12月20日目录1问题描述错误未定义书签2需求分析错误未定义书签3概要设计131抽象数据类…