信息论大作业.pdf
信息论大作业信息论大作业姓名：姓名：学号：学号：学院：学院：专业：专业：75751.fano1.fano 编码编码FanoFano 码：码：费诺编码属于概率匹配编码，但它不是最佳的编码方法。不过有时也可以得到紧致码的性能。信源符号以概率递减的次序排列进来,将排列好的信源符号划分为两大组,使第组的概率和近于相同,并各赋于一个二元码符号”0”和”1”.然后,将每一大组的信源符号再分成两组,使同一组的两个小组的概率和近于相同,并又分别赋予一个二元码符号.依次下去,直至每一个小组只剩下一个信源符号为止.这样,信源符号所对应的码符号序列则为编得的码字。费诺码编码的一般步骤如下：（1）将信源消息符号按其出现的概率大小依次排列排列：p1 p2 pn。（2）将依次排列的信源符号按概率值分为两大组，使两个组的概率之和近似相同，并且对各组赋予一个二进制码元“0”和“1”。（3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和近似相同，并且对各组赋予一个二进制符号“0”和“1”。以上两部分在程序中。（4）如此重复，直到每个组只剩下一个信源符号为止。在程序中本部分采用递归思想。信源符号所对应的码字即为费诺编码。源程序如下：源程序如下：clearclcA=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-1if abs(sum(encoding(1:k,1)-a)=abs(sum(encoding(1:k+1,1)-a)break;endendfor i=1:n%生成B第2列的元素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:nif x=-1break;elseif encoding(q,j-1)=x y=1;continue;else y=0;break;endendendif y=1 q=q+1;endif q=p|q-p=1 encoding(p,j)=-1;elseif 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-2ifabs(sum(encoding(p:k,1)-a)=abs(sum(encoding(p:k+1,1)-a);break;endendfor i=p:q-1if i=k encoding(i,j)=0;CODE(i)=char(CODE(i),0;else encoding(i,j)=1;CODE(i)=char(CODE(i),1;endendendend 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.1,0.2,0.3,0.4,0.1,0.6encoding=0.600000-1.0000-1.0000-1.00000.400001.0000-1.0000-1.0000-1.00000.30001.00000-1.0000-1.0000-1.00000.20001.00001.00000-1.0000-1.00000.10001.00001.00001.00000-1.00000.10001.00001.00001.00001.0000-1.0000A=0.60000.40000.30000.20000.10000.1000CODE=0,1,10,110,1110,1111avlen=32.Huffman2.Huffman 编码编码HuffmanHuffman 码：码：霍夫曼（Huffman）编码是 1952 年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。Huffman 编码的一般步骤如下：l）将信号源的符号按照出现概率递减的顺序排列。（注意，一定要递减）2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。3）重复进行步骤 1 和 2 直到概率相加的结果等于 1 为止。4）在合并运算时，概率大的符号用编码 0 表示，概率小的符号用编码 1 表示。5）记录下概率为 1 处到当前信号源符号之间的 0，l 序列，从而得到每个符号的编码。源程序如下：源程序如下：clearclcp=input(请输入数据:);n=length(p);for i=1:nif p(i)1 fprintf(哈弗曼码中概率总和不能大于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;endfor i=1:n-1 c(i,1:n*n)=blanks(n*n);endc(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-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: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编码的长度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%计算编码效率运行结果如下：运行结果如下：请输入数据:-0.1,-0.3,0.1,-0.2提示：概率值不能小于0!请重新输入数据:0.5,0.2,0.3,0.1,0.2哈弗曼码中概率总和不能大于1!请重新输入数据:0.1,0.1,0.2,0.1Huffman编码结果为:h=110111010编码的平均码长为:l=1信源熵为:hh=1.4610编码效率为:t=1.4610运行结果分析：运行结果分析：完成编写设计后，在MATLAB 中运行并验证结果，首先输入概率向量：p=0.30,0.20,0.18,0.10,0.08,0.07,0.04,0.03;再调用编写的Huffman函数：HuffmanTree,HuffmanCode,SumCode,Entropy=Huffman(p)回车即可得到执行的结果，编码长度为 L=2.7100，H(X)=2.6606，结 果 如 上 图 所 得 的 结 果 与 实 际 预 测 的 理 论 结 果L=2.71,H(X)=2.66 在误差允许范围内一致。
