中南大学信息论与编码编码部分实验报告.docx
- 文档编号:7511254
- 上传时间:2023-05-11
- 格式:DOCX
- 页数:34
- 大小:463.44KB
中南大学信息论与编码编码部分实验报告.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;i cin>>p[i]; pxj=newdouble[n]; k=newint[n]; mz=newdouble[n]; doublesum=0.0; for(i=0;i sum+=p[i]; if(sum! =1.0) throw1; else { for(i=0;i { intk=i; for(intj=i+1;j if(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;j pxj[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,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中南 大学 信息论 编码 部分 实验 报告