信息论与编码实验报告.docx
《信息论与编码实验报告.docx》由会员分享，可在线阅读，更多相关《信息论与编码实验报告.docx（15页珍藏版）》请在冰点文库上搜索。
信息论与编码实验报告
信息论与编码
实验报告
学院：
计算机与通信工程学院
班级：
计1201
学号：
41255020
姓名：
周文文
2014年12月30日
实验一：
唯一可译码判别准则
一、实验目的
（1）进一步熟悉唯一可译码判决准则；
（2）掌握C语言字符串处理程序的设计和调试技术
二、实验内容
（1）已知：
信源符号个数q、码字集合C。
（2）输入：
任意的一个码。
码字个数和每个具体的码字在运行时从键盘输入。
（3）输出：
判决（是唯一可译码/不是唯一可译码）。
三、实验原理
（1）首先判断其是否是非奇异码。
若是奇异码，则一定不是唯一可译码。
（2）考察C中所有的码字，若Wi是Wj的前缀，则将对应的后缀作一个尾随后缀码放入集合F0中。
（3）考察C和Fi中的所有码字，若Fi中的码字Wi是C中的码字Wj的前缀或者C中的码字Wi是Fi中的码字Wj的前缀，则将相应的后缀放在Fi+1中。
（4）若F1,F2,…的并集F中出现了C中的元素，则判别该码不是唯一可译码，否则该码是唯一可译码。
四、实验环境
机电楼301机房，VC++
五、实验文件存档名
Shiyan1
六、实验结果及分析
（1）源代码：
#include
#include
chara[100][100];
charb[100][100];
intN;
intnum=0;
intonly;
voidmain（）//主函数
{
voidfunc（chara[],chard[]）;
inti,j;
charx='Y';
while（x=='Y'||x=='y'）//可循环的输入
{
printf（"请输入码字个数:
"）;
scanf（"%d",&N）;
only=0;
printf（"请输入码字:
\n"）;
for（i=0;i{
scanf（"%s",&a[i]）;
}
for（i=0;ifor（j=i+1;j{
if（strcmp（a[i],a[j]）==0）
{
only=1;break;
}
}
if（only==1）
{
printf（"这不是唯一可译码。
\n"）;
}
else//唯一可译码的判别准则
{
for（i=0;i{
for（j=i+1;j{
func（a[i],a[j]）;
}
}
for（i=0;;i++）
{
ints=0;
for（j=0;j{
if（i==num）
{
s=1;break;
}
elsefunc（b[i],a[j]）;
}
if（s==1）break;
}
for（i=0;i{
for（j=0;j{
if（strcmp（b[i],a[j]）==0）
{
only=1;
break;
}
}
}
if（only==1）
{
printf（"不是唯一可译码\n"）;
}
else
printf（"是唯一可译码\n"）;
}
printf（"继续?
（Y/N）:
"）;
scanf（"%s",&x）;
}
}
voidfunc（chara[],chard[]）//构建F集合
{inti,j,k;
for（i=0;;i++）
{
if（a[i]=='\0'&&d[i]=='\0'）
break;
if（a[i]=='\0'）
{
for（j=i;d[j]!
='\0';j++）
b[num][j-i]=d[j];
b[num][j-i]='\0';
for（k=0;k{
if（strcmp（b[num],b[k]）==0）
{num--;break;}
}
num++;
break;
}
if（d[i]=='\0'）
{
for（j=i;a[j]!
='\0';j++）
b[num][j-i]=a[j];
b[num][j-i]='\0';
for（k=0;k{
if（strcmp（b[num],b[k]）==0）
{
num--;break;
}
}
num++;
break;
}
if（a[i]!
=d[i]）
break;
}
}
（2）实验结果截图：
依次测试的是：
110100
1011010
0100011110001
（3）结果分析：
如：
对于C={110100}
首先判断C是非奇异码，然后利用唯一可译码的判别方法，F1={000}，F2=Φ，所以该码是唯一可译码。
对于C={1011010}
首先判断C是非奇异码，然后利用唯一可译码的判别方法，F1={010}，F2={0}，F3={1}，此时F3中出现了C中的码字，所以该码不是唯一可译码。
实验二：
Huffman编码
一、实验目的
（1）进一步熟悉Huffman编码过程；
（2）掌握C语言递归程序的设计和调试技术。
二、实验内容
（1）输入：
信源符号个数r、信源的概率分布P；
（2）输出：
每个信源符号对应的Huffman编码的码字。
三、实验原理
（1）将r个信源符号按概率大小递减排列p（s1）≥p（s2）≥…≥p（sr）;
（2）用“0,1”码符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含q-1个符号的新信源，称为缩减信源S1；
（3）把缩减信源S1的符号仍按概率大小递减的次序排列，再将其最后两个概率最校的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了q-2个信源符号的S2；
（4）依次继续下去，直到信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二院码符号“0”和“1”表示；
（5）然后从最后一级缩减信源开始，进行回溯，就得到了各信源符号所对应的码符号序列，即相应的码字。
四、实验环境
VC++
五、实验文件存档名
Shiyan2
六、实验结果及分析
（1）源代码：
#include
#include
#include
#include
#include
#defineMAXSIZE50
//定义huffnode及huffcode，分别用来存储节点信息及各节点编码
typedefstruct//霍夫曼树节点的定义
{
intweight;//权值
intparent;
intleft;
intright;
intflag;
}huffnode;
typedefstruct
{
charcode[MAXSIZE];
intstart;
}huffcode;
huffnodehtree[2*MAXSIZE];
huffcodehcode[MAXSIZE];
//寻找权值最小的节点
intselect（inti）
{
intk=1000;
intj,q;
for（j=0;j<=i;j++）{
if（htree[j].weight{
k=htree[j].weight;
q=j;
}
}
htree[q].flag=1;
returnq;
}
//创建哈夫曼树
voidcreat_hufftree（intn）
{
inti,l,r;
for（i=0;i<2*n-1;i++）
htree[i].parent=htree[i].left=htree[i].right=htree[i].flag=-1;
for（i=n;i<2*n-1;i++）
{
l=select（i-1）;
r=select（i-1）;
htree[l].parent=i;
htree[r].parent=i;
htree[i].weight=htree[l].weight+htree[r].weight;
htree[i].left=l;
htree[i].right=1;
}
}
//为各节点进行哈夫曼编码
voidcreat_huffcode（intn）
{
inti,f,c;
huffcoded;
for（i=0;i{
d.start=n+1;
c=i;
f=htree[i].parent;
while（f!
=-1）
{
if（htree[f].left==c）
d.code[--d.start]='0';
else
d.code[--d.start]='1';
c=f;
f=htree[f].parent;
}
hcode[i]=d;
}
}
//输出节点编码
voiddisplay_huffcode（intn）
{
inti,k;
for（i=0;i{
printf（"概率为%.2f的信源符号对应的哈夫曼编码是:
",htree[i].weight*0.01）;
for（k=hcode[i].start;k<=n;k++）
{
printf（"%c",hcode[i].code[k]）;
}
printf（"\n"）;
}
}
//主函数
voidmain（）
{
intn;
inti,s=0;
charch='Y';
while（ch=='Y'||ch=='y'）//设置可循环的输入
{
printf（"请输入所给的信源符号个数:
"）;
scanf（"%d",&n）;
printf（"请输入每个信源符号发生的概率为百分之多少:
"）;
for（i=0;i{
scanf（"%d",&htree[i].weight）;
s=s+htree[i].weight;
}
if（s==100）
{creat_hufftree（n）;
creat_huffcode（n）;
display_huffcode（n）;
s=0;
}
if（s!
=100）
{printf（"您所输入的概率错误"）;
s=0;}
printf（"继续?
（Y/N）:
"）;
scanf（"%s/n",&ch）;
}
}
（2）实验结果截图：
依次测试的是：
0.1,0.1,0.2,0.2,0.4
0.2，0.2,0.2,0.4
0.1,0.1,0.1，0.1,0.6
0.3,0.3，0.3
0.3，0.3,0.3,0.3
（3）实验结果分析
如:
若每个信源符号发生的概率为：
0.1,0.1,0.2,0.2,0.4
由此构造的霍夫曼树：
0.4
1
0.110.61
0.20
0.10
1.0
0.21
0.40
0.20
所以，概率为0.1的信源符号对应的霍夫曼编码为100
概率为0.1的信源符号对应的霍夫曼编码为101
概率为0.2的信源符号对应的霍夫曼编码为00
概率为0.2的信源符号对应的霍夫曼编码为01
概率为0.4的信源符号对应的霍夫曼编码为11
升级会员 