中南大学信息论与编码编码部分实验报告.docx

1、中南大学信息论与编码编码部分实验报告 信息论与编码编码部分实验报告 课程名称：信息论与编码 实验名称：关于香农码费诺码Huffman码的实验学院：信息科学与工程学院班级：电子信息工程1201姓名： viga 学号：指导老师：张祖平日期：2014年1月3日 实验目的及要求 1.1 实验目的4 1.2 开发工具及环境4 1.3 需求分析与功能说明4 实验设计过程 2.1 用matlab实现香农码、费诺码和Huffman编码 2.1.1 说明6 2.1.2 源代码7 2.1.3 运行结果（截图）19 2.2 用CC+ 实现香农码 2.2.1 说明22 2.2.2 源代码23 2.2.3 运行结果（截

2、图）26 2.3 用CC+ 实现Huffman码 2.3.1 说明26 2.3.2 源代码29 2.3.3 运行结果（截图）36 2.4 用CC+ 实现费诺码 2.4.1 说明37 2.4.2 源代码37 2.4.3运行结果结果（截图）40课程设计总结42 参考资料 4.1 课程设计指导书43 实验目的及要求1.1 实验目的1.掌握香农码、费诺码和Huffman编码原理和过程。2.熟悉matlab软件的基本操作，练习使用matlab实现香农码、费诺码和Huffman编码。3.熟悉C/C+语言，练习使用C/C+实现香农码、费诺码和Huffman编码。4.应用Huffman编码实现文件的压缩和解压

3、缩。1.2 开发工具及环境MATLAB 7.0、wps文字、红精灵抓图精灵2010Windows7 系统环境1.3 需求分析与功能说明1、使用matlab实现香农码、费诺码和Huffman编码，并自己设计测试案例。2、使用CC+实现香农码、费诺码和Huffman编码，并自己设计测试案例。3、可以用任何开发工具和开发语言，尝试实现Huffman编码应用在数据文件的压缩和解压缩中，并自己设计测试案例。具体要求：读入有关信源的文本文件（测试用例，里面为每个符号的概率，概率数值用,隔开），然后分别用matlab实现香农码、费诺码和Huffman编码，并计算各个码的平均码长，编码效率，并用matlab图

4、示出来（可以是曲线图或直方图），再尝试对同样的信源用CC+实现香农码、费诺码和Huffman编码。文本文件例如infosource.txt。文件里面的内容为 0.4，0.2，0.1，0.1，0.15，0.05（，可能是全角或半角）。 实验设计过程2.1 用matlab实现香农码、费诺码和Huffman编码2.1.1 说明（1）使用matlab实现香农码、费诺码和Huffman编码，并自己设计测试案例。具体要求：读入有关信源的文本文件（测试用例，里面为每个符号的概率，概率数值用,隔开），然后分别用matlab实现香农码、费诺码和Huffman编码，并计算各个码的平均码长，编码效率，并用matla

5、b图示出来（直方图）文本文件例如gailv.txt我测试的案例为0.4 0.2 0.1 0.1 0.15 0.05，存在gailv.txt这个文本文档中。用“load gailv.txt”语句读入文本文档中的概率分布。（2）编码部分设计：香农编码：1、将概率序列按降序排序，为方便，还是记作p，在编程时调整一下就行。2、算累加概率 B(i)=p(i-1)+B(i-1); , i= 0.i-1，视B(0) = 03、算码长C=-log2(p); N=ceil(C); ceil函数为取不小于自变量的最小整数的函数4、将pa(i)换成二进制表示，取小数前k(i)位为c(i)费诺编码：1、将概率序列排序

6、，为方便，还是记作p，在编程时调整一下就行。2、按编码进制数将概率分组，尽量使每组的概率和接近。3、给每组分配一位码元（0，1，。）4、对每一组按同样地方法划分，直到每个符号有唯一码字。哈夫曼编码：可以用哈夫曼树的观点来看。1、选取概率最小的两个节点a，b2、将他们合并为c加入原概率序列3、从c指向a的边标为0，向b的边标为14、重复到仅有一棵树为止。5、每个符号的码字就是从根走到该符号的所有边上的码元连接起来。2.1.2 源代码1、程序总程序（源文件见zong.m，文本文档见gailv.txt）% load mydata A; %A是原始概率load gailv.txt;A=gailv;m,

7、n=size(A); %m为A的行数 n为A的列数%香农码 for i=1:n if(A(i)0.0001) error(信源概率之和必须为1); EndA=sort(A,2,descend); %完成对A的降序排列for i=1:n if i=1 B(i)=0; else B(i)=A(i-1)+B(i-1); %B是累加后概率 endendC=-log2(A); %C是对A求log2N=ceil(C); %N是每一个码的长度m=max(max(N);INT=ones(n,m);for i=1:n for j=1:N(i) B(i)=2*B(i); if B(i)1 INT(i,j)=0;

8、else INT(i,j)=1; end B(i)=rem(B(i),1); endend %求二进制并进行编码string=码字;ST=cell(1,n);for i=1:n for j=1:N(i) a=num2str(INT(i,j); ST(i)=strcat(ST(1,i),a); endendfprintf(n 信源概率为：n);disp(A);fprintf(n 香农码为：n);disp(ST);fprintf(n 香农平均码长为：n);n_1=sum(N.*A);disp(n_1);fprintf(n 香农编码效率为:n);ha=sum(A.*(-log2(A);t1=ha/n

9、_1; disp(t1);%费诺码 for i=1:n B(i,1)=A(i); %生成B的第1列enda=sum(B(:,1)/2;for k=1:n-1 if abs(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; else B(i,2)=1; endend%生成第一次编码的结果FN=B(:,2);FN=sym(FN);%生成第3列及以后几列的各元素j=3;while (j=0) p=1; while(p=n) x=B(p,j-1); for q=p:n if

10、x=-1 break; else if B(q,j-1)=x y=1; continue; else y=0; break; end end end if y=1 q=q+1; end if q=p|q-p=1 B(p,j)=-1; else if q-p=2 B(p,j)=0; FN(p)=char(FN(p),0; B(q-1,j)=1; FN(q-1)=char(FN(q-1),1; else a=sum(B(p:q-1,1)/2; for k=p:q-2 if abs(sum(B(p:k,1)-a)=abs(sum(B(p:k+1,1)-a); break; end end for i

11、=p:q-1 if i=k B(i,j)=0; FN(i)=char(FN(i),0; else B(i,j)=1; FN(i)=char(FN(i),1; end end end end p=q;end C=B(:,j); D=find(C=-1); e,f=size(D); if e=n j=0; else j=j+1; endendfor i=1:n u,v=size(char(FN(i); lon(i)=v;endlonl=sum(A.*lon);fprintf(n 信源概率为：n);disp(A);fprintf(n 费诺码为：n);disp(FN);fprintf(n 费诺编码效率

12、为:n);ha=sum(A.*(-log2(A);t2=ha/l; disp(t2);fprintf(n 费诺码平均码长为：n);n_2=sum(lon)/n;disp(n_2);%HuffmanQ=A; %建立索引矩阵IndexIndex=zeros(n-1,n); %初始化Index for i=1:n-1 Q,L=sort(Q); Index(i,:)=L(1:n-i+1),zeros(1,i-1); G(i,:)=Q; Q=Q(1)+Q(2),Q(3:n),1; %将概率最小的两个元素相加end for i=1:n-1 %进行回溯 Char(i,:)=blanks(n*n);end%从

13、码树的树根向树叶回溯，即从G矩阵的最后一行按与Index中的索引位置的对应关系向其第一行进行编码Char(n-1,n)=0;%G中的N-1行即最后一行第一个元素赋为0，存到Char中N-1行的N列位置Char(n-1,2*n)=1;%G中的N-1行即最后一行第二个元素赋为1，存到Char中N-1行的2*N列位置%以下从G的倒数第二行开始向前编码for i=2:n-1 Char(n-i,1:n-1)=Char(n-i+1,n*(find(Index(n-i+1,:)=1) -(n-2):n*(find(Index(n-i+1,:)=1); %将Index后一行中索引为1的编码码字填入到当前行的第

14、一个编码位置 Char(n-i,n)=0; %然后在当前行的第一个编码位置末尾填入0 Char(n-i,n+1:2*n-1)=Char(n-i,1:n-1); %将G后一行中索引为1的编码码字填入到当前行的第二个编码位置 Char(n-i,2*n)=1; %然后在当前行的第二个编码位置末尾填入1 for j=1:i-1 %内循环作用：将Index后一行中索引不为1处的编码按照左右顺序填入当前行的第3个位置开始的地方,最后计算到Index的首行为止 Char(n-i,(j+1)*n+1:(j+2)*n)=Char(n-i+1,n*(find(Index(n-i+1,:)=j+1)-1)+1:n*

15、find(Index(n-i+1,:)=j+1); end end %Char中第一行的编码结果就是所需的Huffman 编码输出，通过Index中第一行索引将编码对应到相应概率的信源符号上。 for i=1:n result(i,1:n)=Char(1,n*(find(Index(1,:)=i)-1)+1:find(Index(1,:)=i)*n); lon(i)=length(find(abs(result(i,:)=32); %求每个码的长度 end l=sum(A.*lon);fprintf(n 信源概率为：n);disp(A);fprintf(n 哈夫曼码为:n); disp(res

16、ult);fprintf(n 哈夫曼平均码长为：n);n_3=sum(lon.*A);disp(n_3);fprintf(n 哈夫曼编码效率为:n);t3=ha/n_3;disp(t3);x=1,2,3;y=t1,t2,t3;z=n_1,n_2,n_3;figure(1);subplot(1,2,1);bar(x,y,m);xlabel(香农码 费诺码 哈夫曼码);title(编码效率);hold off;gridsubplot(1,2,2);bar(x,z,b);xlabel(香农码 费诺码 哈夫曼码);title(平均码长);hold off;grid;2.1.3 运行结果（截图）首先将概

17、率数据存入gailv.txt这一文本文档中，再通过load gailv.txt这一语句将概率分布读入。从文本文档gailv.txt中读入概率分布进行香农码的运算：再进行费诺码的编码：最后进行Huffman编码：就得到了接下来的图形：（分别将香农码费诺码Huffman编码的概率效率与平均码长用柱状图表示出来）2.2 用CC+ 实现香农码2.2.1 说明（1）将信源发出的N个消息符号按其概率的递减次序排列（2）按下式计算第个消息的二进制代码组的码长,并取整 （3）计算第个消息的累加概率(为小数)（4）将累加概率变换成二进制数（5）去掉小数点,并根据取小数点后的前几位为对应的代码组。2.2.2 源代

18、码#include#include#include#includeclass Tpublic: T() T(); void Create(); void Coutpxj(); void Coutk(); void Coutz(); void Print();protected: int n; double *p; double *pxj; int *k; double *mz;void T:Create() coutn; p=new doublen; cout请分别输入这n个概率:n; for(int i=0;ipi; pxj=new doublen; k=new intn; mz=new d

19、oublen; double sum=0.0; for(i=0;in;i+) sum+=pi; if(sum!=1.0) throw 1; else for(i=0;in;i+) int k=i; for(int j=i+1;jn;j+) if(pkpj) k=j; double m=pi; pi=pk; pk=m; T:T() delete p; delete pxj; delete k; delete mz;void T:Coutpxj() pxj0=0; for(int i=1;in;i+) pxji=0; for(int j=0;ji;j+) pxji+=pj; void T:Cout

20、k() for(int i=0;i0) ki=(int)d+1; else ki=(int)d; void T:Print() coutXisetw(8)P(xi) setw(8)Pa(xj) setw(8)Ki setw(8)码字 endl; for(int i=0;in;i+) coutXi+1 setw(8)setprecision(2)pi setw(8)setprecision(2)pxji setw(8)ki ; mzi=pxji; for(int j=0;j=0) cout1; mzi=2*mzi-1; else cout0; mzi=2*mzi; coutendl; doubl

21、e K=0.0,H=0.0,Y; for(i=0;in;i+) K+=(double)pi*ki; H+=(-1)*pi*(log10(pi)/log10(2.0); Y=H/K; cout平均码长:Kendl; cout信源熵:Hendl; cout编码效率:Yendl;void main() T t;int e; try t.Create(); t.Coutpxj(); t.Coutk(); t.Print(); catch(int e) if(e=1) cout输入错误，请重新运行;2.2.3 运行结果（截图）2.3 用CC+ 实现Huffman码2.3.1 说明1）编码原理霍夫曼码由霍

22、夫曼树构造，平均码长是霍夫曼树的带权路径长度，由于霍夫曼树是权最小的树，故其压缩效果最好。霍夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的。 霍夫曼码是用概率匹配方法进行信源编码。有两个明显特点：一是保证了概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。

23、 霍夫曼变长码的效率很高，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也易实现，但要注意，更高效率的编码仍须按长序列来计算，这样才能使平均码字降低。2）霍夫曼编码的步骤（l）将信号源的符号按照出现概率递减的顺序排列。（2）将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。（3）重复进行步骤1和2直到概率相加的结果等于1为止。（4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。（5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。例如：设信号源为 ss1, s2, s3, s4, s5,s6对应的概率为p0.4，0

24、.2，0.1, 0.1，0.15，0.05。根据字符出现的概率来构造平均长度最短的异字头码字。霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。3)编码的特点（1）哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，因此，编出的码是即时码。（2）哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。（3）每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字并不惟一。优点：(1)有效的信源编码可取得较好

25、的冗余压缩效果。(2)有效的信源编码可使输出码元概率均匀化。在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。缺点：（1）由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。（2）编码长度不统一，硬件实现有难度。（3） 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100的编码效率；若信号源符号的概率相等，则编码效率最低。（4） 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩

26、性能。2.3.2 源代码#include #include #include #include #include #define HuffmanTree HF#define HuffmanCode HMCtypedef structunsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HF;typedef char *HMC;typedef struct unsigned int s1;unsigned int s2; MinCode; void Error(char *message);HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n);MinCode Select(HF HT,unsigned int n); void Error(char *message) fprintf(stderr,Error:%sn,message);exit(1);HMC HuffmanCoding(HF HT,HMC HC,