信息论霍夫曼、香农-费诺编码
更新时间:2024-02-02 23:33:01 阅读量: 教育文库 文档下载
- 信息论与编码费诺编码推荐度:
- 相关推荐
信息论第二次作业
——数据压缩算法的实现
班别:1307011班
学号:13070110009
姓名:黄丹丹
一、实验目的:
通过该实验,利用香农编码-费诺编码和霍夫曼编码实现图像数据压缩。
二、实验原理:
1、香农-费诺编码
首先,将信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号。依次下去,直至每一个小组只剩下一个信源符号为止。这样,信源符号所对应的码符号序列则为编得的码字。译码原理,按照编码的二叉树从树根开始,按译码序列进行逐个的向其叶子结点走,直到找到相应的信源符号为止。之后再把指示标记回调到树根,按照同样的方式进行下一序列的译码到序列结束。如果整个译码序列能够完整的译出则返回成功,否则则返回译码失败。
2、霍夫曼编码
霍夫曼编码属于码词长度可变的编码类,是霍夫曼在1952年提出的一种编码方法,即从下到上的编码方法。同其他码词长度可变的编码一样,可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”(coding tree)的技术。算法步骤如下:
(1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序。
(2)把概率最小的两个符号组成一个新符号(节点),即新符号的概率等 于这两个符号概率之和。
(3)重复第2步,直到形成一个符号为止(树),其概率最后等于1。 (4)从编码树的根开始回溯到原始的符号,并将每一下分枝赋值为1,上 分枝赋值为0。
三、实验环境
matlab7.1
四、实验内容
1、对于给定的信源的概率分布,用香农-费诺编码实现图像压缩 2、对于给定的信源的概率分布,用霍夫曼编码实现图像压缩
五、实验过程
1.香农-费诺编码 编码1
function c=shannon(p)
%p=[0.2 0.15 0.15 0.1 0.1 0.1 0.1 0.1] %shannon(p)
[p,index]=sort(p) p=fliplr(p) n=length(p) pa=0
for i=2:n
pa(i)= pa(i-1)+p(i-1) end
k=ceil(-log2(p)) c=cell(1,n) for i=1:n c{i}=”
tmp=pa(i)
for j=1:k(i) tmp=tmp*2
if tmp>=1 tmp=tmp-1 c{i(j)='1' else
c{i}(j) = '0' end end end
c = fliplr(c) c(index)=c
编码2 clc; clear;
A=[0.4,0.3,0.1,0.09,0.07,0.04]; A=fliplr(sort(A));%降序排列 [m,n]=size(A); for i=1:n
B(i,1)=A(i);%生成B的第1列 end
%生成B第2列的元素 a=sum(B(:,1))/2; for k=1:n-1
if abs(sum(B(1:k,1))-a)<=abs(sum(B(1:k+1,1))-a) break;
end end
for i=1:n%生成B第2列的元素 if i<=k B(i,2)=0; else
B(i,2)=1; end end
%生成第一次编码的结果 END=B(:,2)'; END=sym(END);
%生成第3列及以后几列的各元素 j=3;
while (j~=0) p=1;
while(p<=n) x=B(p,j-1); for q=p:n if x==-1 break; else
if B(q,j-1)==x y=1;
continue; else y=0; break; end end end
if y==1 q=q+1; end
if q==p|q-p==1 B(p,j)=-1; else
if q-p==2 B(p,j)=0;
END(p)=[char(END(p)),'0']; B(q-1,j)=1;
END(q-1)=[char(END(q-1)),'1']; else
a=sum(B(p:q-1,1))/2;
for k=p:q-2
if abs(sum(B(p:k,1))-a)<=abs(sum(B(p:k+1,1))-a); break; end end
for i=p:q-1 if i<=k B(i,j)=0;
END(i)=[char(END(i)),'0']; else
B(i,j)=1;
END(i)=[char(END(i)),'1']; end end end end p=q; end
C=B(:,j);
D=find(C==-1); [e,f]=size(D); if e==n j=0; else j=j+1; end end B A END
for i=1:n
[u,v]=size(char(END(i))); L(i)=v; end
avlen=sum(L.*A)
2. 霍夫曼编码
function c=huffman(p) n=size(p,2) if n==1
c=cell(1,1) c{1}='' return
end
[p1,i1]=min(p)
index=[(1:i1-1),(i1+1:n)] p=p(index) n=n-1
[p2,i2]=min(p)
index2=[(1:i2-1),(i2+1:n)] p=p(index2);
i2=index(i2)
index=index(index2) p(n)=p1+p2 c=huffman(p)
c{n+1}=strcat(c{n},'1') c{n}=strcat(c{n},'0') index=[index,i1,i2] c(index)=c
end
[p1,i1]=min(p)
index=[(1:i1-1),(i1+1:n)] p=p(index) n=n-1
[p2,i2]=min(p)
index2=[(1:i2-1),(i2+1:n)] p=p(index2);
i2=index(i2)
index=index(index2) p(n)=p1+p2 c=huffman(p)
c{n+1}=strcat(c{n},'1') c{n}=strcat(c{n},'0') index=[index,i1,i2] c(index)=c
正在阅读:
信息论霍夫曼、香农-费诺编码02-02
古生物学 复习资料10-26
变压器的概述 - 图文03-06
四年级上册日积月累03-10
网络安全技术与实践第二版课后答案03-16
中国古代文论--中国古代文学批评史习题集(有答案哦)05-03
2015监理工程师考试用书下载地址05-24
社区商业定位、规划08-24
特色办学三年规划02-20
高层消防车道规范06-02
- exercise2
- 铅锌矿详查地质设计 - 图文
- 厨余垃圾、餐厨垃圾堆肥系统设计方案
- 陈明珠开题报告
- 化工原理精选例题
- 政府形象宣传册营销案例
- 小学一至三年级语文阅读专项练习题
- 2014.民诉 期末考试 复习题
- 巅峰智业 - 做好顶层设计对建设城市的重要意义
- (三起)冀教版三年级英语上册Unit4 Lesson24练习题及答案
- 2017年实心轮胎现状及发展趋势分析(目录)
- 基于GIS的农用地定级技术研究定稿
- 2017-2022年中国医疗保健市场调查与市场前景预测报告(目录) - 图文
- 作业
- OFDM技术仿真(MATLAB代码) - 图文
- Android工程师笔试题及答案
- 生命密码联合密码
- 空间地上权若干法律问题探究
- 江苏学业水平测试《机械基础》模拟试题
- 选课走班实施方案
- 霍夫曼
- 香农
- 信息论
- 编码
- 费诺
- 土力学及地基基础模拟考试试题及答案
- ICHGCP(E6)R2--1
- 朝阳之旅:高僧明道清风岭,壮士热血中国地 - 图文
- 柔性掩护支架采煤工作面工程质量管理办法
- 五项管理(行动日志样本)
- 把课堂教学交给学生
- 韩都衣舍案例分析
- 公文写作中的词汇短语成语排比句集锦
- “励志成才看世界”之西安行系列活动策划方案 - 图文
- 初级电工教材 - 图文
- 基于单片机的多点温度检测系统的设计 外文翻译
- 五年级品德与社会下册教案(河北人民出版社)
- 通信原理实验报告3
- XX优秀物业管理住宅小区汇报材料 - 图文
- 组合化学
- 层次分析法步骤解析—根法、和法、幂法
- 大气总量减排电子台账规范
- 丽水市生态环境功能区规划 - 图文
- 赣州市房地产开发商名录2018版1103家 - 图文
- 体育专业体操技巧论文 - 图文