信息论大作业new

1、信息论大作业电子工程学院班号1. Huffman编码1 Huffman 编码原理：将信源符号按概率从大到小的顺序排列，令p(x1) p(x2) p(xn)给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n2)个符号的缩减信源S2。重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编

2、码路径向前返回，就得到各信源符号所对应的码字。 2. 霍夫曼编码优缺点：1) 编出来的码都是异字头码，保证了码的唯一可译性。2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。3) 编码长度不统一，硬件实现有难度。4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100的编码效率；若信号源符号的概率相等，则编码效率最低。5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。3.编码流程： 读入一幅图像的灰度值;1. 将矩阵的不同数统计在数组c的第一列中;2. 将相同的数占站整个

3、数组总数的比例统计在数组p中;3. 找到最小的概率,相加直到等于1,把最小概率的序号存在tree第一列中,次小放在第二列,和放在p像素比例之后;4. C数组第一维表示值,第二维表示代码数值大小,第三维表示代码的位数；5. 把概率小的值为1标识，概率大的值为0标识；6. 计算信源的熵 ；7. 计算平均码长 ；8. 计算编码效率'；9. 计算冗余度。源程序：p=input('请输入数据:'); n=length(p);for i=1:n if p(i)<0 fprintf('n 提示：概率值不能小于0!n'); p=input('请重新输入数据

4、:'); endend if abs(sum(p)>1 fprintf('n 哈弗曼码中概率总和不能大于1!n'); p=input('请重新输入数据:'); endq=p;a=zeros(n-1,n); %生成一个n-1 行n 列的数组 for i=1:n-1 q,l=sort(q); a(i,:)=l(1:n-i+1),zeros(1,i-1); q=q(1)+q(2),q(3:n),1; end for i=1:n-1 c(i,1:n*n)=blanks(n*n); endc(n-1,n)='0' c(n-1,2*n)=

5、9;1' for i=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(find(a(n-i+1,:)=1)-(n-2):n*(find(a(n-i+1,:)=1) ;c(n-i,n)='0' ; c(n-i,n+1:2*n-1)=c(n-i,1:n-1) ;c(n-i,2*n)='1' ; for j=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(a(n-i+1,:)=j+1)-1)+1:n*find(a(n-i+1,:)=j+1);endend %完成huffman 码字的分配for i=1:nh

6、(i,1:n)=c(1,n*(find(a(1,:)=i)-1)+1:find(a(1,:)=i)*n); ll(i)=length(find(abs(h(i,:)=32); %计算每一个huffman 编码的长度endl=sum(p.*ll); %计算平均码长fprintf('n Huffman编码结果为:n'); hfprintf('n 编码的平均码长为:n'); lhh=sum(p.*(-log2(p); %计算信源熵fprintf('n 信源熵为:n'); hhfprintf('n 编码效率为:n'); t=hh/l %计

7、算编码效率运行结果为：请输入数据:0.1,0.1,0.1,0.2,0.1,0.1,0.2,0.1 Huffman编码结果为:h = 1100 1101 010 111 011 000 10 001 编码的平均码长为:l = 3 信源熵为:hh = 2.9219 编码效率为:t =0.97402.fano编码：Fano码:费诺编码属于概率匹配编码，但它不是最佳的编码方法。不过有时也可以得到紧致码的性能。信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于

8、相同,并又分别赋予一个二元码符号.依次下去,直至每一个小组只剩下一个信源符号为止.这样,信源符号所对应的码符号序列则为编得的码字。费诺码编码的一般步骤如下：（1）将信源消息符号按其出现的概率大小依次排列排列：。（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并且对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并且对各组赋予一个二进制符号“0”和“1”。以上两部分在程序中。（4）如此重复，直到每个组只剩下一个信源符号为止。在程序中本部分采用递归思想。信源符号所对应的码字即为费诺编码。费诺编码特点费诺编码，

9、它编码后的费诺码要比香农码的平均码长小，消息传输速率达，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。源程序：A=input('input the A:');A=fliplr(sort(A);%降序排列m,n=size(A);for i=1:n encoding(i,1)=A(i);%生成B的第1列end%生成B第2列的元素a=sum(encoding(:,1)/2;for k=1:n-1 if abs(sum(encoding(1:k,1)-a)<=abs(sum(encoding(1:k+1,1)-a) break; endendfor i=1:n%生成B第2

10、列的元素 if i<=k encoding(i,2)=0; else encoding(i,2)=1; endend%生成第一次编码的结果CODE=encoding(:,2)'CODE=sym(CODE);%生成第3列及以后几列的各元素j=3;while (j=0) p=1; while(p<=n) x=encoding(p,j-1); for q=p:n if x=-1 break; else if encoding(q,j-1)=x y=1; continue; else y=0; break; end end end if y=1 q=q+1; end if q=p|

11、q-p=1 encoding(p,j)=-1; else if q-p=2 encoding(p,j)=0; CODE(p)=char(CODE(p),'0' encoding(q-1,j)=1; CODE(q-1)=char(CODE(q-1),'1' else a=sum(encoding(p:q-1,1)/2; for k=p:q-2 if abs(sum(encoding(p:k,1)-a)<=abs(sum(encoding(p:k+1,1)-a); break; end end for i=p:q-1 if i<=k encoding(i

12、,j)=0; CODE(i)=char(CODE(i),'0' else encoding(i,j)=1; CODE(i)=char(CODE(i),'1' end end end end p=q; end C=encoding(:,j); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendencodingACODEfor i=1:n u,v=size(char(CODE(i); L(i)=v;endavlen=sum(L.*A)运行结果：input the A:0.3,0.1,0.2,0.3,0.1encoding = 0.3000 0 0 -1.0000 -1.0000 0.3000 0 1.0000 -1.0000 -1.0000 0.2000 1.0000 0 -1.0000 -1.0000 0.1000 1.0000 1.0000 0 -1.0000 0.1000 1.0000 1.0000 1.0000 -1.0000A = 0.3000 0.3000 0.2000 0.1000 0.