中南大学信息论与编码编码部分实验报告.docx
《中南大学信息论与编码编码部分实验报告.docx》由会员分享，可在线阅读，更多相关《中南大学信息论与编码编码部分实验报告.docx（34页珍藏版）》请在冰点文库上搜索。
中南大学信息论与编码编码部分实验报告
信息论与编码编码部分实验报告
课程名称：
信息论与编码
实验名称：
关于香农码费诺码Huffman码的实验
学院：
信息科学与工程学院
班级：
电子信息工程1201
姓名：
viga
学号：
指导老师：
张祖平
日期：
2014年1月3日
⊙实验目的及要求
1.1实验目的………………………………………………4
1.2开发工具及环境………………………………………4
1.3需求分析与功能说明…………………………………4
⊙实验设计过程
2.1用matlab实现香农码、费诺码和Huffman编码
2.1.1说明………………………………………………6
2.1.2源代码……………………………………………7
2.1.3运行结果（截图）………………………………19
2.2用C\C++实现香农码
2.2.1说明………………………………………………22
2.2.2源代码……………………………………………23
2.2.3运行结果（截图）………………………………26
2.3用C\C++实现Huffman码
2.3.1说明………………………………………………26
2.3.2源代码……………………………………………29
2.3.3运行结果（截图）………………………………36
2.4用C\C++实现费诺码
2.4.1说明………………………………………………37
2.4.2源代码……………………………………………37
2.4.3运行结果结果（截图）…………………………40
⊙课程设计总结……………………………………………42
⊙参考资料
4.1课程设计指导书……………………………………43
实验目的及要求
1.1实验目的
1.掌握香农码、费诺码和Huffman编码原理和过程。
2.熟悉matlab软件的基本操作，练习使用matlab实现香农码、费诺码和Huffman编码。
3.熟悉C/C++语言，练习使用C/C++实现香农码、费诺码和Huffman编码。
4.应用Huffman编码实现文件的压缩和解压缩。
1.2开发工具及环境
MATLAB7.0、wps文字、红精灵抓图精灵2010
Windows7系统环境
1.3需求分析与功能说明
1、使用matlab实现香农码、费诺码和Huffman编码，并自己设计测试案例。
2、使用C\C++实现香农码、费诺码和Huffman编码，并自己设计测试案例。
3、可以用任何开发工具和开发语言，尝试实现Huffman编码应用在数据文件的压缩和解压缩中，并自己设计测试案例。
具体要求：
读入有关信源的文本文件（测试用例，里面为每个符号的概率，概率数值用,隔开），然后分别用matlab实现香农码、费诺码和Huffman编码，并计算各个码的平均码长，编码效率，并用matlab图示出来（可以是曲线图或直方图），再尝试对同样的信源用C\C++实现香农码、费诺码和Huffman编码。
文本文件例如infosource.txt。
文件里面的内容为0.4，0.2，0.1，0.1，0.15，0.05（，可能是全角或半角）。
实验设计过程
2.1用matlab实现香农码、费诺码和Huffman编码
2.1.1说明
（1）使用matlab实现香农码、费诺码和Huffman编码，并自己设计测试案例。
具体要求：
读入有关信源的文本文件（测试用例，里面为每个符号的概率，概率数值用,隔开），然后分别用matlab实现香农码、费诺码和Huffman编码，并计算各个码的平均码长，编码效率，并用matlab图示出来（直方图）文本文件例如gailv.txt
我测试的案例为0.40.20.10.10.150.05，存在gailv.txt这个文本文档中。
用“loadgailv.txt”语句读入文本文档中的概率分布。
（2）编码部分设计：
香农编码：
1、将概率序列按降序排序，为方便，还是记作p，在编程时调整一下就行。
2、算累加概率B（i）=p（i-1）+B（i-1）;,i=0..i-1，视B（0）=0
3、算码长C=-log2（p）;N=ceil（C）;[ceil函数为取不小于自变量的最小整数的函数]
4、将pa（i）换成二进制表示，取小数前k（i）位为c（i）
费诺编码：
1、将概率序列排序，为方便，还是记作p，在编程时调整一下就行。
2、按编码进制数将概率分组，尽量使每组的概率和接近。
3、给每组分配一位码元（0，1，。
。
。
）
4、对每一组按同样地方法划分，直到每个符号有唯一码字。
哈夫曼编码：
可以用哈夫曼树的观点来看。
1、选取概率最小的两个节点a，b
2、将他们合并为c加入原概率序列
3、从c指向a的边标为0，向b的边标为1
4、重复到仅有一棵树为止。
5、每个符号的码字就是从根走到该符号的所有边上的码元连接起来。
2.1.2源代码
1、程序总程序（源文件见zong.m，文本文档见gailv.txt）
%loadmydataA;%A是原始概率
loadgailv.txt;
A=gailv;
[m,n]=size（A）;%m为A的行数n为A的列数
%香农码
fori=1:
n
if（A（i）<0）
error（'信源概率不能小于0'）;
End
End
if（（sum（A）-1）>0.0001）
error（'信源概率之和必须为1'）;
End
A=sort（A,2,'descend'）;%完成对A的降序排列
fori=1:
n
ifi==1
B（i）=0;
else
B（i）=A（i-1）+B（i-1）;%B是累加后概率
end
end
C=-log2（A）;%C是对A求log2
N=ceil（C）;%N是每一个码的长度
m=max（max（N））;
INT=ones（n,m）;
fori=1:
n
forj=1:
N（i）
B（i）=2*B（i）;
ifB（i）<1
INT（i,j）=0;
else
INT（i,j）=1;
end
B（i）=rem（B（i）,1）;
end
end%求二进制并进行编码
string='码字';
ST=cell（1,n）;
fori=1:
n
forj=1:
N（i）
a=num2str（INT（i,j））;
ST（i）=strcat（ST（1,i）,a）;
end
end
fprintf（'\n信源概率为：
\n'）;
disp（A）;
fprintf（'\n香农码为：
\n'）;
disp（ST）;
fprintf（'\n香农平均码长为：
\n'）;
n_1=sum（N.*A）;
disp（n_1）;
fprintf（'\n香农编码效率为:
\n'）;
ha=sum（A.*（-log2（A）））;
t1=ha/n_1;
disp（t1）;
%费诺码
fori=1:
n
B（i,1）=A（i）;%生成B的第1列
end
a=sum（B（:
1））/2;
fork=1:
n-1
ifabs（sum（B（1:
k,1））-a）<=abs（sum（B（1:
k+1,1））-a）
break;
end
end
fori=1:
n%生成B第2列的元素
ifi<=k
B（i,2）=0;
else
B（i,2）=1;
end
end
%生成第一次编码的结果
FN=B（:
2）;
FN=sym（FN）;
%生成第3列及以后几列的各元素
j=3;
while（j~=0）
p=1;
while（p<=n）
x=B（p,j-1）;
forq=p:
n
ifx==-1
break;
elseifB（q,j-1）==x
y=1;
continue;
else
y=0;
break;
end
end
end
ify==1
q=q+1;
end
ifq==p|q-p==1
B（p,j）=-1;
elseifq-p==2
B（p,j）=0;
FN（p）=[char（FN（p））,'0'];
B（q-1,j）=1;
FN（q-1）=[char（FN（q-1））,'1'];
else
a=sum（B（p:
q-1,1））/2;
fork=p:
q-2
ifabs（sum（B（p:
k,1））-a）<=abs（sum（B（p:
k+1,1））-a）;
break;
end
end
fori=p:
q-1
ifi<=k
B（i,j）=0;
FN（i）=[char（FN（i））,'0'];
else
B（i,j）=1;
FN（i）=[char（FN（i））,'1'];
end
end
end
end
p=q;
end
C=B（:
j）;
D=find（C==-1）;
[e,f]=size（D）;
ife==n
j=0;
else
j=j+1;
end
end
fori=1:
n
[u,v]=size（char（FN（i）））;
lon（i）=v;
end
lon
l=sum（A.*lon）;
fprintf（'\n信源概率为：
\n'）;
disp（A）;
fprintf（'\n费诺码为：
\n'）;
disp（FN）;
fprintf（'\n费诺编码效率为:
\n'）;
ha=sum（A.*（-log2（A）））;
t2=ha/l;
disp（t2）;
fprintf（'\n费诺码平均码长为：
\n'）;
n_2=sum（lon）/n;
disp（n_2）;
%Huffman
Q=A;%建立索引矩阵Index
Index=zeros（n-1,n）;%初始化Index
fori=1:
n-1
[Q,L]=sort（Q）;
Index（i,:
）=[L（1:
n-i+1）,zeros（1,i-1）];
G（i,:
）=Q;
Q=[Q
（1）+Q
（2）,Q（3:
n）,1];%将概率最小的两个元素相加
end
fori=1:
n-1%进行回溯
Char（i,:
）=blanks（n*n）;
end
%从码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码
Char（n-1,n）='0';%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置
Char（n-1,2*n）='1';%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置
%以下从G的倒数第二行开始向前编码
fori=2:
n-1
Char（n-i,1:
n-1）=Char（n-i+1,n*（find（Index（n-i+1,:
）==1））-（n-2）:
n*（find（Index（n-i+1,:
）==1）））;%将Index后一行中索引为1的编码码字填入到当前行的第一个编码位置
Char（n-i,n）='0';%然后在当前行的第一个编码位置末尾填入'0'
Char（n-i,n+1:
2*n-1）=Char（n-i,1:
n-1）;%将G后一行中索引为1的编码码字填入到当前行的第二个编码位置
Char（n-i,2*n）='1';%然后在当前行的第二个编码位置末尾填入'1'
forj=1:
i-1
%内循环作用：
将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止
Char（n-i,（j+1）*n+1:
（j+2）*n）=Char（n-i+1,n*（find（Index（n-i+1,:
）==j+1）-1）+1:
n*find（Index（n-i+1,:
）==j+1））;
end
end
%Char中第一行的编码结果就是所需的Huffman编码输出，通过Index中第一行索引将编码对应到相应概率的信源符号上。
fori=1:
n
result（i,1:
n）=Char（1,n*（find（Index（1,:
）==i）-1）+1:
find（Index（1,:
）==i）*n）;
lon（i）=length（find（abs（result（i,:
））~=32））;%求每个码的长度
end
l=sum（A.*lon）;
fprintf（'\n信源概率为：
\n'）;
disp（A）;
fprintf（'\n哈夫曼码为:
\n'）;
disp（result）;
fprintf（'\n哈夫曼平均码长为：
\n'）;
n_3=sum（lon.*A）;
disp（n_3）;
fprintf（'\n哈夫曼编码效率为:
\n'）;
t3=ha/n_3;
disp（t3）;
x=[1,2,3];
y=[t1,t2,t3];
z=[n_1,n_2,n_3];
figure
（1）;
subplot（1,2,1）;
bar（x,y,'m'）;
xlabel（'香农码费诺码哈夫曼码'）;
title（'编码效率'）;
holdoff;
grid
subplot（1,2,2）;
bar（x,z,'b'）;
xlabel（'香农码费诺码哈夫曼码'）;
title（'平均码长'）;
holdoff;
grid;
2.1.3运行结果（截图）
首先将概率数据存入gailv.txt这一文本文档中，再通过loadgailv.txt这一语句将概率分布读入。
从文本文档gailv.txt中读入概率分布进行香农码的运算：
再进行费诺码的编码：
最后进行Huffman编码：
就得到了接下来的图形：
（分别将香农码费诺码Huffman编码的概率效率与平均码长用柱状图表示出来）
2.2用C\C++实现香农码
2.2.1说明
（1）将信源发出的N个消息符号按其概率的递减次序排列
（2）按下式计算第
个消息的二进制代码组的码长
并取整
（3）计算第
个消息的累加概率
（为小数）
（4）将累加概率
变换成二进制数
（5）去掉小数点,并根据
取小数点后的前几位为对应的代码组。
2.2.2源代码
#include
#include
#include
#include
classT
{
public:
T（）{}
~T（）;
voidCreate（）;
voidCoutpxj（）;
voidCoutk（）;
voidCoutz（）;
voidPrint（）;
protected:
intn;
double*p;
double*pxj;
int*k;
double*mz;
};
voidT:
:
Create（）
{
cout<<"请输入信源符号个数:
";
cin>>n;
p=newdouble[n];
cout<<"请分别输入这"<\n";
for（inti=0;icin>>p[i];
pxj=newdouble[n];
k=newint[n];
mz=newdouble[n];
doublesum=0.0;
for（i=0;isum+=p[i];
if（sum!
=1.0）
throw1;
else
{
for（i=0;i{
intk=i;
for（intj=i+1;jif（p[k]doublem=p[i];
p[i]=p[k];
p[k]=m;
}
}
}
T:
:
~T（）
{
deletep;
deletepxj;
deletek;
deletemz;
}
voidT:
:
Coutpxj（）
{
pxj[0]=0;
for（inti=1;i{
pxj[i]=0;
for（intj=0;jpxj[i]+=p[j];
}
}
voidT:
:
Coutk（）
{
for（inti=0;i{
doubled=（-1）*（log（p[i]）/log
（2））;
if（d-（int）d>0）k[i]=（int）d+1;
elsek[i]=（int）d;
}
}
voidT:
:
Print（）
{
cout<<"Xi"<<<<<for（inti=0;i{cout<<"X"<<（2）<<（2）<<mz[i]=pxj[i];
for（intj=0;j{
if（2*mz[i]-1>=0）
{
cout<<1;
mz[i]=2*mz[i]-1;
}
else
{
cout<<0;
mz[i]=2*mz[i];
}
}
cout<}
doubleK=0.0,H=0.0,Y;
for（i=0;i{
K+=（double）p[i]*k[i];
H+=（-1）*p[i]*（log10（p[i]）/log10（2.0））;
}
Y=H/K;
cout<<"平均码长:
"<cout<<"信源熵:
"<cout<<"编码效率:
"<}
voidmain（）
{
Tt;inte;
try
{
t.Create（）;
t.Coutpxj（）;
t.Coutk（）;
t.Print（）;
}
catch（inte）
{if（e==1）cout<<"输入错误，请重新运行";}
}
2.2.3运行结果（截图）
2.3用C\C++实现Huffman码
2.3.1说明
1）编码原理
霍夫曼码由霍夫曼树构造，平均码长是霍夫曼树的带权路径长度，由于霍夫曼树是权最小的树，故其压缩效果最好。
霍夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。
在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。
这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。
这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的。
霍夫曼码是用概率匹配方法进行信源编码。
有两个明显特点：
一是保证了概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。
霍夫曼变长码的效率很高，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也易实现，但要注意，更高效率的编码仍须按长序列来计算，这样才能使平均码字降低。
2）霍夫曼编码的步骤
（l）将信号源的符号按照出现概率递减的顺序排列。
（2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。
（3）重复进行步骤1和2直到概率相加的结果等于1为止。
（4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。
（5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。
例如：
设信号源为s＝｛s1,s2,s3,s4,s5,s6｝
对应的概率为p＝｛0.4，0.2，0.1,0.1，0.15，0.05｝。
根据字符出现的概率来构造平均长度最短的异字头码字。
霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。
3）编码的特点
（1）哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，因此，编出的码是即时码。
（2）哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。
（3）每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字并不惟一。
优点：
（1）有效的信源编码可取得较好的冗余压缩效果。
（2）有效的信源编码可使输出码元概率均匀化。
在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。
缺点：
（1）由于编码长度可变。
因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
（2）编码长度不统一，硬件实现有难度。
（3）对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
（4）由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
2.3.2源代码
#include
#include
#include
#include
#include
#defineHuffmanTreeHF
#defineHuffmanCodeHMC
typedefstruct
{unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HF;
typedefchar**HMC;
typedefstruct{
unsignedints1;
unsignedints2;
}MinCode;
voidError（char*message）;
HMCHuffmanCoding（HFHT,HMCHC,unsignedint*w,unsignedintn）;
MinCodeSelect（HFHT,unsignedintn）;
voidError（char*message）
{
fprintf（stderr,"Error:
%s\n",message）;
exit
（1）;
}
HMCHuffmanCoding（HFHT,HMCHC,
升级会员 