信息论实验报告实验人：邓放学号：20123022572014年11月21日一、实验目的1、掌握哈夫曼编码算法的基本原理；要求对图片进行哈夫曼编码。
2、掌握算术编码算法的基本原理；要求对图片进行算术编码。
3、掌握LZ算法的基本原理；要求对图片进行LZ编码。
二、实验原理1、哈夫曼编码l）将信号源的符号按照出现概率递减的顺序排列。
（注意，一定要递减）2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现的概率。
3）重复进行步骤1和2直到概率相加的结果等于1为止。
4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。
5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。
下面我举个简单例子:一串信号源S＝{s1,s2,s3,s4,s5}对应概率为p＝{40，30，15，10，5}，（百分率）按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！最后概率最大的编码为0，最小的编码为1。
如图所示：所以，编码结果为s1=1s2=00s3=010s4=0110s5=0111霍夫曼编码具有如下特点：1)编出来的码都是异字头码，保证了码的唯一可译性。
2)由于编码长度可变。
因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
3)编码长度不统一，硬件实现有难度。
4)对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
5)由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。
2、算术编码根据信源可能发现的不同符号序列的概率，把[0，1]区间划分为互不重叠的子区间，子区间的宽度恰好是各符号序列的概率。
这样信源发出的不同符号序列将与各子区间一一对应，因此每个子区间内的任意一个实数都可以用来表示对应的符号序列，这个数就是该符号序列所对应的码字。
显然，一串符号序列发生的概率越大，对应的子区间就越宽，要表达它所用的比特数就减少，因而相应的码字就越短。
3、LZ 编码设信源符号集A={a1，a2，…，aK}共K 个符号，设输入信源符号序列为u =(u1，u2，…，uL)编码是将此序列分成不同的段。
分段的规范为：尽可能取最少个相连的信源符号，并保证各段都不相同。
开始时，先取一个符号作为第一段，然后继续分段。
若出现与前面相同的符号时，就再取紧跟后面的一个符号一起组成一个段，使之与前面的段不同。
这些分段构成字典。
当字典达到一定大小后，再分段时就应查看有否与字典中的短语相同，若有重复就添加符号，以便与字典中短语不同，直至信源序列结束。
编码的码字由段号加一个符号组成。
设u 构成的字典中的短语共有M （u ）个。
若编码为二元码，段号所需码长n=「log M （u ）「（注：代表上取整符号），每个符号需要的码长为log [M （u)]。
单符号的码字段号为0，非单字符的码字段号为除最后一个符号外字典中相同短语的段号。
例如，设U={a1，a2，a3，a4}，信源序列为a1，a3，a2，a3，a2，a4，a3，a2，a1，a4，a3，a2，a1，共13位，字典如表所示：rr P S p S P a S P )()(),(+=⎥⎥⎤⎢⎢⎡=)(1log S p L三、实验结果1.哈夫曼2.算术编码Gui界面3.Lz编码四．代码哈夫曼：clcclearclose all;%定义HufData/Len为全局变量的结构体global HufData;global Lendisp('计算机正在准备输出哈夫曼编码结果,请耐心等待……'); %原始码字的灰度I_rgb=imread('3.jpg');a=rgb2gray(I_rgb);%图像的灰度统计GrayStatistics=imhist(a);GrayStatistics=GrayStatistics';GrayRatioo=GrayStatistics/sum(GrayStatistics); GrayRatioNO=find(GrayRatioo~=0);Len=length(GrayRatioNO);%初始化灰度集，防止系统随即赋予其垃圾值GrayRatio=ones(1,Len);for i=1:LenGrayRatio(i)=GrayRatioo(i);endGrayRatio=abs(sort(-GrayRatio));%将图像灰度概率赋予结构体for i=1:LenHufData(i).value=GrayRatio(i);end%哈夫曼编码/霍夫曼编码HuffmanCode(Len);%输出码字zippedHuffman=1;for i=1:LentmpData=HufData(i).code;str='';for j=1:length(tmpData)str=strcat(str,num2str(tmpData(j)));zippedHuffman=zippedHuffman+1;enddisp(strcat(str))endi;%计算计算机一共输出多少个霍夫曼编码zippedHuffman;%计算在删去0灰度级压缩之前的原始图像字节容量unzipped_delete=i*8;%计算压缩比率ratio_delete=zippedHuffman\unzipped_delete;ad=num2str(ratio_delete*100);str2=strcat(ad,'%');disp(strcat('哈夫曼编码压缩比率','=',str2))算术A=imread('t01db9375674cc395c6.jpg');for k=1:length(A)if(A(k)==0)A(k)=1;elseif(A(k)==255)A(k)=254;endend[M,N]=size(A);temp=zeros(1,256);for m=1:M;for n=1:N;if A(m,n)==0;i=1;elsei=A(m,n);endtemp(i)=temp(i)+1;endendtemp=temp/(M*N);p=temp;[i,j,v]=find(p);pp=[j'v'];h=[];h=j';w=[];w=v';P=1;for k=1:length(A)P=(w(find((h<(A(k)+1))&(h>(A(k)-1)))))*P;endL=ceil(log2(1/P));g=[];g(1)=w(find((h<(A(1)+1))&(h>(A(1)-1))));ppp=[];ppp(1)=g(1);for k=2:length(A)g(k)=g(k-1)+g(k-1)*ppp(k-1);ppp(k)=ppp(k-1)*w(find((h<(A(k)+1))&(h>(A(k)-1))));t=g(k);endtLinnum=t;N=L-1;%输入为非整数的情况nint=floor(innum);%整数部分nf=innum-nint;%小数部分res_nint=dec2bin(nint);res_nint=double(res_nint)-48;count=0;tempnum=nf;record=zeros(1,N);while(N)count=count+1;%长度小于Nif(count>N)N=0;%return;endtempnum=tempnum*2;%小数转换为二进制,乘2取整if tempnum>1record(count)=1;tempnum=tempnum-1;elseif(tempnum==1)record(count)=1;N=0;%stop loopelserecord(count)=0;endendres_nf=record;numint=res_nint;numf=res_nf;num=[numint,numf]%ss=dec2bin(t*2^7)%ss=[ss(1:L)];%Lzunction LZmain()%LZ encode main functionclc;%open the source file to get the contentfid=fopen('1.jpeg','r');seq=fread(fid);fclose(fid);seq=reshape(seq,1,length(seq));if~isempty(seq)%call the Entropy function to calculate the source entropy[entropy]=Entropy(seq);%call the LZcode function to encode the symbol[dictionary codelength]=LZcode(seq);%calculate the efficiency,and display the entropy,average length %as well as efficiencyavglength=((codelength*length(dictionary))/length(seq));%efficiency=(length(seq)/(codelength*length(dictionary)));disp(strcat('Entropy=',num2str(entropy)));disp(strcat('Code length=',num2str(codelength)));disp(strcat('Average length=',num2str(avglength)));%disp(strcat('Efficiency=',num2str(efficiency)));display('Dictionary content:Look dictionary.m.');fiddic=fopen('dictionary.m','w');fprintf(fiddic,'The content of the dictionary is:\n');for i=1:length(dictionary)dic=fwrite(fiddic,[''''dictionary(i).sym''':'dictionary(i).code setstr(10)]);endfclose(fiddic);%encode the source file,and write the enseq into the file--encode.txtdisplay('Encoded Sequence:Look encode.txt.');enseq=LZencode(dictionary);fiden=fopen('encode.txt','w');en=fwrite(fiden,enseq);fclose(fiden);%decode the encode file,and write the deseq into the file--decode.txtdisplay('Decoded Sequence:Look decode.txt.');deseq=LZdecode(dictionary);fidde=fopen('decode.txt','w');de=fwrite(fidde,deseq);fclose(fiden);elsedisplay('Empty Sequence....');endend。