信息论与编码.docx
《信息论与编码.docx》由会员分享，可在线阅读，更多相关《信息论与编码.docx（17页珍藏版）》请在冰点文库上搜索。
信息论与编码
《信息论与编码》实验报告
学生姓名：
李俊
班号：
116111—25
班号：
20111003660
指导教师：
黄鹰
中国地质大学（武汉）信息工程学院
2013年7月
]
实验1Huffman编码
Huffman编码原理：
①将信源符号按概率从大到小的顺序排列，令
p（x1）≥p（x2）≥…≥p（xn）
②给两个概率最小的信源符号p（xn-1）和p（xn）各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，
结果得到一个只包含（n－1）个信源符号的新信源。
称为信源的第一次缩减信源，
用S1表示。
③将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含（n－2）个符号的缩减信源S2。
④重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。
然后从最后一级缩减信源开始，依编码路径向前返回，就得到各
信源符号所对应的码字。
Huffman树的编码步骤：
步骤1：
将各个符号及其出现频率分别作为不同的小二叉树（目前每棵树只有根节点）
步骤2：
在步骤1中得到的树林里找出频率值最小的两棵树，将他们分别作为左、右子树连成一棵大一些的二叉树，该二叉树的频率值设为两棵子树频率值
之和。
步骤3：
对上面得到的树林重复步骤2的做法，直到所有符号都连入树中为止。
数据结构定义
typedefstruct
{
unsignedlongweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;//指向存放数组指针的数组即二维数组
包含的函数：
（1）voidSelect（HuffmanTree&HT,intn,int*s1,int*s2），实现从HT[1..n]中选出权值最小的两个节点
（2）voidCreateHuffmanTree（HuffmanTree&HT,float*w,intn），创造huffman树
（3）voidHuffmanCoding（HuffmanTreeHT,HuffmanCode&HC,intn），对信源符号进行编码
（4）voidOutputHuffCode（HuffmanCodeHC,char*ch,float*w,intn），输出编码
函数的实现：
voidSelect（HuffmanTree&HT,intn,int*s1,int*s2）
{
inti;
floatp,q;
p=q=1.0;
for（i=1;i<=n;i++）
{
if（HT[i].parent==0&&（HT[i].weightif（p{
q=HT[i].weight;
*s2=i;
}
else
{
p=HT[i].weight;
*s1=i;
}
}
if（*s2<*s1）//指针s1存放权值较小的节点
{
i=*s1;
*s1=*s2;
*s2=i;
}
}
voidCreateHuffmanTree（HuffmanTree&HT,float*w,intn）
{
inti,m;
ints1,s2;
HuffmanTreet;
if（n<=1）
return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
for（t=HT,i=1;i<=n;++i,++w）//给每个叶节点赋值
{
++t;
t->weight=*w;
t->parent=0;
t->lchild=0;
t->rchild=0;
}
for（;i<=m;++i）
{
++t;
t->weight=0;
t->parent=0;
t->lchild=0;
t->rchild=0;
}
for（i=n+1;i<=m;++i）
{
Select（HT,i-1,&s1,&s2）;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
voidHuffmanCoding（HuffmanTreeHT,HuffmanCode&HC,intn）
{
inti,p,q,start;
char*cd;
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
cd=（char*）malloc（n*sizeof（char））;
cd[n-1]='\0';//编码结束符
for（i=1;i<=n;++i）
{
start=n-1;//编码结束位置
for（p=i,q=HT[i].parent;q!
=0;p=q,q=HT[q].parent）//从叶节点到根节点逆向求编码
{
if（HT[q].lchild==p）
{
start--;
cd[start]='0';//左孩子编码为‘0’
}
else
{
start--;
cd[start]='1';//左孩子编码为‘1’
}
}
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
strcpy（HC[i],&cd[start]）;//将编码从cd复制到HC中
}
free（cd）;
}
voidOutputHuffCode（HuffmanCodeHC,char*ch,float*w,intn）
{
printf（"huffman编À¨¤码?
为a：
êo\n"）;
for（inti=1;i<=n;i++）
{
printf（"%c\t%f\t",ch[i-1],w[i-1]）;
puts（HC[i]）;
}
printf（"\n"）;
}
结果显示：
学习心得：
本次实验，熟悉了课堂上的信源编码的一种，即huffman编码，加深了对知识的理解，通过编程简单实现了编码，但是我的程序存在一些缺陷，即在我的程序中需要手工输入信源符号的概率，我觉得可以输入一串字符串，统计每个字符出现的概率，这样更加方便，另外从HT[1..n]中选出权值最小的两个节点可以通过最小堆来实现，效率更高一些。
附录：
文件huffman.h：
#ifndefHUFFMANCODE_H
#defineHUFFMANCODE_H
#include
#include
#include
typedefstruct
{
floatweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
typedefchar**HuffmanCode;
voidSelect（HuffmanTree&HT,intn,int*s1,int*s2）
{
inti;
floatp,q;
p=q=1.0;
for（i=1;i<=n;i++）
{
if（HT[i].parent==0&&（HT[i].weightif（p{
q=HT[i].weight;
*s2=i;
}
else
{
p=HT[i].weight;
*s1=i;
}
}
if（*s2<*s1）{
i=*s1;
*s1=*s2;
*s2=i;
}
}
voidCreateHuffmanTree（HuffmanTree&HT,float*w,intn）
{
inti,m;
ints1,s2;
HuffmanTreet;
if（n<=1）
return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
for（t=HT,i=1;i<=n;++i,++w）
{
++t;
t->weight=*w;
t->parent=0;
t->lchild=0;
t->rchild=0;
}
for（;i<=m;++i）
{
++t;
t->weight=0;
t->parent=0;
t->lchild=0;
t->rchild=0;
}
for（i=n+1;i<=m;++i）
{
Select（HT,i-1,&s1,&s2）;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
}
voidHuffmanCoding（HuffmanTreeHT,HuffmanCode&HC,intn）
{
inti,p,q,start;
char*cd;
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
cd=（char*）malloc（n*sizeof（char））;
cd[n-1]='\0';
for（i=1;i<=n;++i）
{
start=n-1;
for（p=i,q=HT[i].parent;q!
=0;p=q,q=HT[q].parent）;
{
if（HT[q].lchild==p）
{
start--;
cd[start]='0';}
else
{
start--;
cd[start]='1';
}
}
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
strcpy（HC[i],&cd[start]）;
}
free（cd）;
}
voidOutputHuffCode（HuffmanCodeHC,char*ch,float*w,intn）
{
printf（"huffman编À¨¤码?
为a：
êo\n"）;
for（inti=1;i<=n;i++）
{
printf（"%c\t%f\t",ch[i-1],w[i-1]）;
puts（HC[i]）;
}
printf（"\n"）;
}
#endif
main函数：
int_tmain（intargc,_TCHAR*argv[]）
{
HuffmanTreeHT;
HuffmanCodeHC;
intn,i;
floatsum=0;
char*ch;
float*w;
cout<<"请?
输º?
入¨?
字Á?
符¤?
个?
数ºy：
êo";
cin>>n;
w=（float*）malloc（n*sizeof（float））;
ch=（char*）malloc（n*sizeof（char））;
cout<<"请?
输º?
入¨?
字Á?
符¤?
和¨ª每?
个?
字Á?
符¤?
发¤¡é生¦¨²的Ì?
概?
率¨º：
êo"<for（i=0;i{
cin>>ch[i]>>w[i];
sum+=w[i];
cout<<"剩º¡ê余®¨¤概?
率¨º为a"<<1.0-sum<<"!
"<}
for（i=0;i{
CreateHuffmanTree（HT,w,n）;
}
HuffmanCoding（HT,HC,n）;
OutputHuffCode（HC,ch,w,n）;
free（w）;
free（ch）;
return0;
}
实验2CRC校验码编码实验
本实验中，是对（7,4）循环码的编码。
实验原理：
CRC校验的基本思想是利用线性编码理论，在发送端根据要传送的k位二进制码序列，以一定的规则产生一个校验用的监督码（CRC码）r位，并附在信息后边，构成一个新的二进制码序列数共（k+r）位，最后发送出去。
在接收端，则根据信息码和CRC码之间所遵循的规则进行检验，以确定传送中是否出错。
数据结构：
定义生成多项式为g（x）=x^3+x^2+1,因此采用数组inta[4]={1,1,0,1}来表示该多项式。
主要函数：
voidcode（inta1[],intb1[]）
{
intc[7];
inti,j;
for（i=0;i<7;i++）//把所有的信息位左移三位
{
if（i<4）
c[i]=b1[i];
else
c[i]=0;
}
for（i=0;i<4;i++）
{
for（j=0;j<4;j++）
{
c[i+j]=c[i+j]^a1[j];
}
}
for（i=0;i<7;i++）
{
if（i<4）
c[i]=b1[i];
cout<}
}
实验结果：
实习体会
通过这个实验，我熟悉了按位计算CRC码，但是我的算法不具有普遍性和通用性，针对是特点情况，另外我在网上还看到了其他几种方式来计算CRC码，如按字节计算CRC码，按半字节计算CRC码，但是按字节计算CRC码需要很大的空间，按位计算CRC码需要较长的时间，而按半字节计算CRC码就均衡了上面的两种方式。
代码附录：
#include
usingnamespacestd;
voidcode（inta1[],intb1[]）
{
intc[7];
inti,j;
for（i=0;i<7;i++）//把所有的信息位左移三位
{
if（i<4）
c[i]=b1[i];
else
c[i]=0;
}
for（i=0;i<4;i++）
{
for（j=0;j<4;j++）
{
c[i+j]=c[i+j]^a1[j];
}
}
for（i=0;i<7;i++）
{
if（i<4）
c[i]=b1[i];
cout<}
}
int_tmain（intargc,_TCHAR*argv[]）
{
inta[4]={1,1,0,1};
intb[4];
cout<<"本程序是实现（7,4）循-环码?
，生成多项式为个g（x）=x^3+x^2+1！
"<cout<<"请输入4位的信息位?
：
";
for（inti=0;i<4;i++）
cin>>b[i];
cout<<"7位编码为：
";
code（a,b）;
cout<return0;
}
升级会员 