信息论与编码课程设计.doc
《信息论与编码课程设计.doc》由会员分享,可在线阅读,更多相关《信息论与编码课程设计.doc(16页珍藏版)》请在冰点文库上搜索。
河南理工大学课程设计报告书
信息论与编码课程设计报告
设计题目:
统计信源熵、香农编码与费诺编码
专业班级:
XXXXXXXXXXXX
姓名:
XXXXXXXXXXXX
学号:
XXXXXXXXXXXX
指导老师:
XXXXXXXXXXXX
成绩:
时间:
2015年3月31日
目录
一、设计任务与要求..............................2
二、设计思路....................................2
三、设计流程图..................................5
四、程序及结果..................................7
五、心得体会....................................11
六、参考文献...................................12
附录...........................................13
一、设计任务与要求
1. 统计信源熵
要求:
统计任意文本文件中各字符(不区分大小写)数量,计算字符概率,并计算信源熵。
2. 香农编码
要求:
任意输入消息概率,利用香农编码方法进行编码,并计算信源熵和编码效率。
3. 费诺编码
要求:
任意输入消息概率,利用费诺编码方法进行编码,并计算信源熵和编码效率。
二、设计思路
1、统计信源熵:
统计信源熵就是对一篇英文文章中的种字符(包括标点符号及空格,英文字母不区分大小写)统计其出现的次数,然后计算其出现的概率,最后由信源熵计算公式:
算出信源熵。
所以整体步骤就是先统计出文章中总的字符数,然后统计每种字符的数目,直到算出所有种类的字符的个数,进而算出每种字符的概率,再由信源熵计算公式计算出信源熵。
在这里我选择用Matlab来计算信源熵,因为Matlab中系统自带了许多文件操作和字符串操作函数,其计算功能强大,所以计算信源熵很是简单。
2、香农编码
信源编码模型:
信源编码就是从信源符号到码符号的一种映射,它把信源输出的符号变换成码元序列。
信源编码器
信源码元
码符号
次扩展信源无失真编码器
凡是能载荷一定的信息量,且码字的平均长度最短,可分离的变长码的码字集合都可以称为最佳码。
为此必须将概率大的信息符号编以短的码字,概率小的符号编以长的码字,使得平均码字长度最短。
能获得最佳码的编码方法主要有:
香农(Shannon)、费诺(Fano)、哈夫曼(Huffman)编码等。
香农第一定理:
离散无记忆信源为
熵,其次扩展为
熵为,码符号集为。
先对信源进行编码,总可以找到一种编码方法,构成唯一可译码,使中每个信源符号所需的平均码长满足
且当时有,是平均码长,是对应的码字长度。
香农编码方法:
(1)将信源消息符号按其出现的概率大小依次排列:
(2)确定满足下列不等式整数码长为
(3)为了编成唯一可译码,计算第个消息的累加概率为
(4)将累加概率变成二进制数。
(5)取二进制数小数点后位即为该消息符号的二进制码字。
3、费诺编码方法
(1)将信源消息符号按其出现的概率大小依次排列:
(2)将依次排列的信源符号按概率值分为两大组,使两个组的概率之和近似相同,并对各组赋予一个二进制码元“0”和“1”。
(3)将每一大组的信源符号再分为两组,使划分后的两个组的概率之和近似相同,并对各组赋予一个二进制符号“0”和“1”。
(4)如此重复,直至每个组只剩下一个信源符号为止。
(5)信源符号所对应的码字即为费诺码。
三、设计流程图
1、统计信源熵
用Matlab读入一段英文计算这段文字的字符总数unm
①②
统计每种字符的个数n(i)算出每种字符的概率p(i)
③④
由信源熵计算公式计算出信源熵
⑤
2、香农编码
开始
输入概率矩阵
将概率由大到小排列
计算累加概率和概率的个数
根据公式调用函数计算码长
用循环程序编码并调整输出格式
计算信源熵和编码效率
输出信源熵、编码效率和码字
结束
3、费诺编码
开始
输入概率矩阵
将概率由大到小排列
计算累加概率和概率的个数
在两组概率之和近似相等的条件下将
概率分为两组,各赋予0,1两个码元
将每一大组的的概率重复上一步操作,直到每组只剩一个概率
用循环程序编码并调整输出格式
计算信源熵和编码效率
输出信源熵、编码效率和码字
结束
四、程序及结果
1、统计信源熵的Matlab程序
functionh=entropy(p)
clc
fid=fopen('shuju.txt','r');%打开txt文件
[ex,num]=fscanf(fid,'%c',inf)%读取二进制文件的数据,并将数据存入矩阵
str1=lower(ex)%将字符串中的大写字母转换成小写字母
sort_str1=sort(str1);%按照字符的ASCII值对字符串排序
j=1;
fori=1:
length(sort_str1)-1%计算出字符串的种类
ifstrcmp(sort_str1(i),sort_str1(i+1))~=1%比较两个字符串是否完全相等,相等是1,否则0
j=j+1;
str2(j)=sort_str1(i);
end
str2(j+1)=sort_str1(i+1);
end
fori=1:
length(str2)%length函数获取字符串长度
str_num=strfind(sort_str1,str2(i));%strfind(S1,S2):
寻找S2是否匹配S1,并返回S2的位置
count1(i)=length(str_num);
end
str2
count=count1(3:
end)
p=count./sum(count)
sum(-p.*log2(p))%计算信源熵
待读取的英文:
ThePressureofGraduateStudents
NowIamapostgraduatestudent,Iwillgraduatenextyear,soIstarttofindjobsrecently,Ifeelsomuchpressure,thoughIhavegoodeducation,Istillgetrejectionfromthecompanies.Thepressureofgraduatestudentsaresoheavy,thecompetitionissofiercethatmanystudentscan’tgettheidealjobs.Theyshouldadjusttheirstrategies.
Thepressureofgraduatestudentsissoheavy.Ontheonehand,theydon’thaveexperience,sotheydon’tknowhowtogetthejobinterviewandmissmanychances.Ontheotherhand,therearemoreandmorestudentshavehigheducation,somehavereceivedhighereducation,somehavestudiesabroadwhichmaketheirresumesstandout.Thoseaveragestudentsdon’thaveadvantagesovertheabovementionedones.
Averagestudentsneedtomaketheirresumesspecially,sotheycanhavethechance.Theycandescribetheircharacteristictofitthejob,theemployerswillseethisandgiveyouthechance.Studentscanalsomaketheirinternshipexperiencestandout,becausetheemployerspayspecialattentiontoit.
Thejobpressureisheavyforeverygraduatestudent,ifthestudentstakethewisestrategy,theycanhavemorechancestogetthejob.
程序运行结果:
总共出现的字符种类:
.abcdefghijklmnoprstuvwxy’
每种字符对应出现的次数:
[206161178103342161102065538516215864165580113362083204]
每种字符出现的概率:
[0.16720.01300.00890.06330.00810.02680.03410.13070.00810.01620.05280.04300.00650.00410.01300.01700.04710.05190.01300.04460.06490.09170.02920.01620.00650.00240.01620.0032]
信源熵:
4.1250
2、香农编码程序
functionc=shannon(p)
%p=[0.250.250.200.150.100.05];
%shannon(p);
[p,index]=sort(p);
p=fliplr(p);%从大到小
n=length(p);
pa=0;%累加概率
fori=2:
n
pa(i)=pa(i-1)+p(i-1);
end
k=ceil(-log2(p));%码长计算
c=cell(1,n);%生成元胞数组,存码字,是cell,跟上一行不一样
fori=1:
n
c{i}='';
tmp=pa(i);
forj=1:
k(i)
tmp=tmp*2;
iftmp>=1
tmp=tmp-1;
c{i}(j)='1';
else
c{i}(j)='0';
end
end
end
%p
%pa
%交换回原来的顺序
c=fliplr(c);
c(index)=c;
fprintf('信源信息熵:
\n');
H=sum(-p.*log2(p))%计算信源熵
fprintf('平均码长:
\n');
K=sum(p.*k)%计算平均码长
fprintf('编码效率:
\n');
w=H./K%计算编码效率
fprintf('码字:
\n');
c
程序运行结果:
p=[0.250.250.200.150.100.05];
shannon(p);
信源信息熵:
H=2.4232
平均码长:
K=2.7000
编码效率:
w=0.8975
码字:
c='01''00''100''101''1101''11110'
3、费诺编码程序
主程序
functionc=fano1(p)
%p=[0.250.250.200.150.100.05]
%c=fano1(p)
n=size(p,2);
ifn==1
c=cell(1,1);
c{1}='';
return
end
[p,index]=sort(p);%按概率排序
p=fliplr(p);
total=sum(p);%总概率
acc=0;%累积概率
flag=0;%是否到达尾部的标志
fori=1:
n-1
newacc=acc+p(i);
ifabs(total-2*newacc)>=abs(total-2*acc)
flag=1;
break;
end
acc=newacc;
end
if~flag
i=n;
end
split=i;%从分界点对两边的码递归做fano
c1=fano1(p(1:
split-1));
c2=fano1(p(split:
n));
c=cell(1,n);
%添加前缀0,1
fori=1:
split-1
c{i}=strcat('0',c1{i});
end
fori=split:
n
c{i}=strcat('1',c2{i-split+1});
end
%将顺序调整回去
c=fliplr(c);
c(index)=c;
子程序
function[]=fano2(c,p)
fori=1:
length(c)%求平均码长
count(i)=length(cell2mat(c(i)));
end
fprintf('信源信息熵:
\n');
H=sum(-p.*log2(p))%计算信源熵
fprintf('平均码长:
\n')
K=sum(count.*p)%计算平均码长
fprintf('编码效率:
\n')
w=H./K%计算编码效率
fprintf('码字:
\n')
c
程序运行结果:
p=[0.250.250.200.150.100.05]
c=fano1(p)
fano2(c,p)
p=0.25000.25000.20000.15000.10000.0500
c='00''01''10''110''1110''1111'
信源信息熵:
H=2.4232
平均码长:
K=2.4500
编码效率:
w=0.9891
码字:
c='00''01''10''110''1110''1111'
五、心得体会
做这次课程设计前前后后花了三天时间,之前并没有用心想,只是看了看网上的资料,看人家都是用什么方法解决的。
我看的有用C(包括C++和C#)语言的,有用Matlab的,还有用别的什么软件的。
由于我对Matlab编程还比较熟悉一点,最后我还是选择用Matlab来做。
一开始编程,我甚至连一些常用的Matlab函数都忘了,没什么想法后我在网上看了一些人用Matlab编的程序,拿来仔细研究后也慢慢着编出了自己的程序。
在编程过程中,遇到了各种问题问题,有时由于一个小问题不通,我要反复琢磨半天,最后发现是在一个小地方上出错了,真是备受煎熬,但这也是编程的乐趣所在,在这个过程中自己也学到了许多编程知识和技巧。
在编程过程中,我体会到了Matlab功能的强大,我需要好好学习一下,这对我以后在信号处理与仿真计算上有很大帮助。
通过这次课程设计,我对信息论与编码技术中的一些基础知识,如信源熵、通信系统模型、信道与信源编码等知识又重新学习了一下,感觉虽是学过的知识,但隔一段时间不看合上书自己竟然什么也想不起来。
学过的知识,觉得自己早就已经理解了的,在实际用来解决问题时又是无从下手,需多看人家的例子,在此基础上才能用来解决自己的问题。
我之所以自己一组,是想真学到点东西,这过程中很累人,但这是因为自己当初没有提早准备,还有就是自己知识也学的不扎实造成的,于是感悟到做什么事情都要有计划地提早准备,不然会坐失良机,最后只能悔不当初。
六、参考文献
[1]曹雪虹,张宗橙.信息论与编码(第二版).北京:
清华大学出版社,2009.2
[2]王薇,姚鑫锋.从零开始学MATLAB .北京:
电子工业出版社,2012.9
附录
1、统计信源熵的Matlab程序
functionh=entropy(p)
clc
fid=fopen('shuju.txt','r');%打开txt文件
[ex,num]=fscanf(fid,'%c',inf)%读取二进制文件的数据,并将数据存入矩阵
str1=lower(ex)%将字符串中的大写字母转换成小写字母
sort_str1=sort(str1);%按照字符的ASCII值对字符串排序
j=1;
fori=1:
length(sort_str1)-1%计算出字符串的种类
ifstrcmp(sort_str1(i),sort_str1(i+1))~=1%比较两个字符串是否完全相等,相等是1,否则0
j=j+1;
str2(j)=sort_str1(i);
end
str2(j+1)=sort_str1(i+1);
end
fori=1:
length(str2)%length函数获取字符串长度
str_num=strfind(sort_str1,str2(i));%strfind(S1,S2):
寻找S2是否匹配S1,并返回S2的位置
count1(i)=length(str_num);
end
str2
count=count1(3:
end)
p=count./sum(count)
sum(-p.*log2(p))%计算信源熵
2、香农编码程序
functionc=shannon(p)
%p=[0.250.250.200.150.100.05];
%shannon(p);
[p,index]=sort(p);
p=fliplr(p);%从大到小
n=length(p);
pa=0;%累加概率
fori=2:
n
pa(i)=pa(i-1)+p(i-1);
end
k=ceil(-log2(p));%码长计算
c=cell(1,n);%生成元胞数组,存码字,是cell,跟上一行不一样
fori=1:
n
c{i}='';
tmp=pa(i);
forj=1:
k(i)
tmp=tmp*2;
iftmp>=1
tmp=tmp-1;
c{i}(j)='1';
else
c{i}(j)='0';
end
end
end
%p
%pa
%交换回原来的顺序
c=fliplr(c);
c(index)=c;
fprintf('信源信息熵:
\n');
H=sum(-p.*log2(p))%计算信源熵
fprintf('平均码长:
\n');
K=sum(p.*k)%计算平均码长
fprintf('编码效率:
\n');
w=H./K%计算编码效率
fprintf('码字:
\n');
shannon(p);
信源信息熵:
H=2.4232
4、费诺编码程序
主程序
functionc=fano1(p)
%p=[0.250.250.200.150.100.05]
%c=fano1(p)
n=size(p,2);
ifn==1
c=cell(1,1);
c{1}='';
return
end
[p,index]=sort(p);%按概率排序
p=fliplr(p);
total=sum(p);%总概率
acc=0;%累积概率
flag=0;%是否到达尾部的标志
fori=1:
n-1
newacc=acc+p(i);
ifabs(total-2*newacc)>=abs(total-2*acc)
flag=1;
break;
end
acc=newacc;
end
if~flag
i=n;
end
split=i;%从分界点对两边的码递归做fano
c1=fano1(p(1:
split-1));
c2=fano1(p(split:
n));
c=cell(1,n);
%添加前缀0,1
fori=1:
split-1
c{i}=strcat('0',c1{i});
end
fori=split:
n
c{i}=strcat('1',c2{i-split+1});
end
%将顺序调整回去
c=fliplr(c);
c(index)=c;
子程序
function[]=fano2(c,p)
fori=1:
length(c)%求平均码长
count(i)=length(cell2mat(c(i)));
end
fprintf('信源信息熵:
\n');
H=sum(-p.*log2(p))%计算信源熵
fprintf('平均码长:
\n')
K=sum(count.*p)%计算平均码长
fprintf('编码效率:
\n')
w=H./K%计算编码效率
fprintf('码字:
\n')
c
15