信息论霍夫曼、香农-费诺编码

1、信息论霍夫曼、香农-费诺编码信息论第二次作业数据压缩算法的实现班别： 1307011 班学号：名：黄丹丹一、实验目的：- 费诺编码和霍夫通过该实验，利用香农编码 曼编码实现图像数据压缩。二、实验原理：1、香农 - 费诺编码首先 , 将信源符号 以概率递减 的次序排 列进来，将排列好的信源符号划分为两大组， 使第组的 概率和近于 相同, 并各赋 于一个二 元码符号” 0”和” 1”. 然后，将每一大组的 信源符号再分成两组，使同一组的两个小组 的概率和近于相同，并又分别赋予一个二元 码符号。依次下去，直至每一个小组只剩下 一个信源符号为止。这样，信源符号所对应 的码符号

2、序列则为编得的码字。译码原理， 按照编码的二叉树从树根开始，按译码序列 进行逐个的向其叶子结点走，直到找到相应 的信源符号为止。之后再把指示标记回调到 树根，按照同样的方式进行下一序列的译码 到序列结束。如果整个译码序列能够完整的 译出则返回成功，否则则返回译码失败。2、霍夫曼编码 霍夫曼编码属于码词长度可变的编码 类，是霍夫曼在 1952 年提出的一种编码方法， 即从下到上的编码方法。同其他码词长度可 变的编码一样，可区别的不同码词的生成是 基于不同符号出现的不同概率。生成霍夫曼 编码算法基于一种称为“编码树” （ coding tree ）的技术。算法步骤如下： （ 1）初始化，根据符号概

3、率的大小按由大到 小顺序对符号进行排序。（ 2 ）把概率最小的两个符号组成一个新符号 （节点），即新符号的概率等 于这两个符号概率之和。（ 3）重复第 2 步，直到形成一个符号为止 （树），其概率最后等于 1 。（ 4）从编码树的根开始回溯到原始的符号， 并将每一下分枝赋值为 1，上 分枝赋值为 0。三、实验环境matlab7.1四、实验内容1、对于给定的信源的概率分布，用香农- 费诺编码实现图像压缩2、对于给定的信源的概率分布，用霍夫曼编 码实现图像压缩五、实验过程1. 香农 -费诺编码编码 1function c=shannon(p)%p=0.2 0.15 0.15 0.1 0.1 0.1

4、 0.1 0.1%shannon(p)p,index=sort(p)p=fliplr(p) n=length(p)pa=0for i=2:npa(i)= pa(i-1)+p(i-1) end k=ceil(-log2(p) c=cell(1,n) for i=1:nci= ” tmp=pa(i) for j=1:k(i) tmp=tmp*2 if tmp>=1 tmp=tmp-1 ci(j)='1'elseci(j) = '0'endendendc = fliplr(c)c(index)=c编码 2clc;clear;A=0.4,0.3,0.1,0.09,

5、0.07,0.04;A=fliplr(sort(A);% 降序排列 m,n=size(A);for i=1:nB(i,1)=A(i);% 生成 B的第 1 列 end%生成 B第 2 列的元素a=sum(B(:,1)/2;for k=1:n-1 ifabs(sum(B(1:k,1)-a)<=abs(sum(B(1:k+1,1)-a)break;endendfor i=1:n%生成 B第 2 列的元素if i<=k B(i,2)=0; elseB(i,2)=1; end end %生成第一次编码的结果END=B(:,2)'END=sym(END);%生成第 3 列及以后几列的

6、各元素 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;endendend if y=1 q=q+1;endif 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' elsea=sum(B(p:q-1,1)/2;for

7、k=p:q-2ifabs(sum(B(p:k,1)-a)<=abs(sum(B(p:k+1, 1)-a);break;endendfor i=p:q-1if i<=kB(i,j)=0;END(i)=char(END(i),'0'elseB(i,j)=1;END(i)=char(END(i),'1'endendend endp=q;endC=B(:,j);D=find(C=-1);e,f=size(D);if e=nj=0;elsej=j+1;endendBAENDfor i=1:nu,v=size(char(END(i);L(i)=v;endavlen=sum(L.*A)2. 霍夫曼编码 function c=huffman(p) n=size(p,2)if n=1c=cell(1,1)c1=''returnendp1,i1=min(p)index=(1:i1-1),(i1+1:n) p=p(index)n=n-1p2,i2=min(p)index2=(1:i2-1),(i2+1:n) p=p(index2);i2=index(i2) index