信息论大作业
电子工程学院
班 号
1.Huffman编码
1． Huffman 编码原理：
①将信源符号按概率从大到小的顺序排列，令p(x1)≥ p(x2)≥?≥ p(xn) ②给两个概率最小的信源符号p(xn-1)和p(xn)各分配一个码位“0”和“1”，将这两个信源符号合并成一个新符号，并用这两个最小的概率之和作为新符号的概率，结果得到一个只包含(n－1)个信源符号的新信源。称为信源的第一次缩减信源，用S1表示。
③将缩减信源S1的符号仍按概率从大到小顺序排列，重复步骤2，得到只含(n－2)个符号的缩减信源S2。 ④重复上述步骤，直至缩减信源只剩两个符号为止，此时所剩两个符号的概率之和必为1。然后从最后一级缩减信源开始，依编码路径向前返回，就得到各信源符号所对应的码字。
2. 霍夫曼编码优缺点：
1) 编出来的码都是异字头码，保证了码的唯一可译性。
2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
3) 编码长度不统一，硬件实现有难度。
4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。 3.编码流程：
读入一幅图像的灰度值;
1. 将矩阵的不同数统计在数组c的第一列中;
2. 将相同的数占站整个数组总数的比例统计在数组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('请重新输入数据:'); end end
if abs(sum(p))>1
fprintf('\\n 哈弗曼码中概率总和不能大于1!\\n'); p=input('请重新输入数据:'); end q=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); end
c(n-1,n)='0'; c(n-1,2*n)='1'; for i=2:n-1
c(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-1 c(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)); end
end %完成huffman 码字的分配 for i=1:n
h(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 编码的长度 end
l=sum(p.*ll); %计算平均码长 fprintf('\\n Huffman编码结果为:\\n'); h fprintf('\\n 编码的平均码长为:\\n'); l hh=sum(p.*(-log2(p))); %计算信源熵 fprintf('\\n 信源熵为:\\n'); hh
fprintf('\\n 编码效率为:\\n'); t=hh/l %计算编码效率
运行结果为：
请输入数据:[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.9740
2.fano编码：
Fano码:
费诺编码属于概率匹配编码，但它不是最佳的编码方法。不过有时也可以得到紧致码的性能。信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号.依次下去,直至每一个小组只剩下一个信源符号为止.这样,信源符号所对应的码符号序列则为编得的码字。 费诺码编码的一般步骤如下：
（1）将信源消息符号按其出现的概率大小依次排列排列：
p1?p2???pn。
（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并且对各组赋予一个二进制码元“0”和“1”。
（3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并且对各组赋予一个二进制符号“0”和“1”。以上两部分在程序中。
（4）如此重复，直到每个组只剩下一个信源符号为止。在程序中本部分采用递归思想。
信源符号所对应的码字即为费诺编码。
费诺编码特点
费诺编码，它编码后的费诺码要比香农码的平均码长小，消息传输速率达，编码效率高，但它属于概率匹配编码它不是最佳的编码方法。
源程序：
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)