信息论与编码综合性实验报告

xxxx学院xxxx学院综合性实验报告专业：xxxx年级/班级：xxxx级xxxx—xxxx学年第一学期课程名称信息论与编码指导教师本组成员学号姓名实验地点实验时间项目名称二元哈夫曼编码实验类型综合性一、实验目的用Matlab语言编程实现霍夫曼（Huffman）编码。二、实验仪器或设备一台计算机。MATLAB软件。三、总体设计将信源消息符号按其出现的概率大小依次排列，p1≥p2≥…≥pq取两个概率最小的字母分别配以0和1两个码元，并将这两个概率相加作为一个新字母的概率，从而得到只包含q-1个符号的新信源S1。对重排后的缩减信源S1重新以递减次序排序，两个概率最小符号重复步骤(2)的过程。不断继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的码字。先生成的编码表0.40.40.40.40.20.20.40.60.20.20.200.10.2000.1222编码表每列为缩减信源概率第一列为输入n个信源概率；第二列为第一次缩减后t=n-1个概率；第（n，2）元素放置合并元素在本列中位置；…如果输入n个概率，则需要缩减n-1次后，剩下t=2两个概率；所以编码表可以定义为n行n-1列。编码表生成后，从最后一列开始编码。首先最后一列两个元素分别编码为0和1；对其中某j列，其前t-2个元素编码为j+1列非合并概率移植过来。（问题,如何知道j=1列中非合并元素的位置？）第t-1元素和第t个元素为j+1列合并概率编码分别加0和加1。（合并概率的位置已经在本列最后一个元素中标出）四、实验步骤%输入一个概率矩阵p，判断其合理性，如果合理则通过函数调用对其进行哈弗曼编码functionhuffman(p)ifsum(p)~=1%判断所输入概率矩阵p的元素的和是否为1display('pleaseinputtherightnumbers!')returnend%如果所输入概率矩阵合理，则进行哈弗曼编码m=size(p,2);%p中元素个数%b=sort(p,'descend');b=fliplr(sort(p));%用于最后的输出fori=1:m-1%对输入概率矩阵p进行编码前的准备，用矩阵a记录哈弗曼编码的过程%p=sort(p,'descend');p=fliplr(sort(p));n=size(p,2);a(:,i)=p';p(n-i)=p(n-i+1)+p(n-i);forj=n-i+1:mp(j)=0;endendn=m;fori=1:m-2%矩阵a从第二列开始，每一列的最后一个元素用于保存前次求和后元素所处位置x=a(n-i+1,i)+a(n-i,i);r=find(a(:,i+1)==x);a(n,i+1)=r(end);enda%输出编码表%---------------------------------------------------------%根据a对所输入概率矩阵p进行哈弗曼编码code1=sym('[01]');%给最后一列的元素编码h=code1;t=3;%控制编码个数，初始为3d=1;forj=n-2:-1:1%从倒数第二列开始依次对各列元素编码fori=1:t-2ifi>1&a(i,j)==a(i-1,j)d=d+1;elsed=1;enda(a(n,j+1),j+1)=-1;%对已经编码的赋值为-1temp=a(:,j+1);x=find(temp==a(i,j));h(i)=code1(x(d));endy=a(n,j+1);h(t-1)=[char(code1(y)),'0'];h(t)=[char(code1(y)),'1'];t=t+1;code1=h;endb%排序后的原概率序列h%编码结果结果：>>p=[0.20.190.180.170.150.10.01];>>huffman(p)a=0.20000.20000.26000.35000.39000.61000.19000.19000.20000.26000.35000.39000.18000.18000.19000.20000.260000.17000.17000.18000.1900000.15000.15000.17000000.10000.110000000.01006.00001.00001.00001.00001.0000b=0.20000.19000.18000.17000.15000.10000.0100h=[10,11,000,001,010,0110,0111]/*以下为任课教师提供%p1=fliplr(sort(p));%将信源从大到小排序%p=sort(p);%从小到大排序%find(A>5)%返回矩阵中大于5的元素所在的位置%排N-1次后结束clear,clc%p=[0.4,0.2,0.2,0.1,0.1];p=[0.1,0.1,0.2,0.2,0.4];q=sort(p);n=length(p);a=zeros(n-1,n);b=zeros(n-1,n);%生成一个n-1行n列的数组fori=1:n-1[q,l]=sort(q);%对概率数组q进行从小至大的排序，并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编号b(i,:)=[q(1:n-i+1),zeros(1,i-1)];a(i,:)=[l(1:n-i+1),zeros(1,i-1)];%由数组l构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码%b(i,:)=[l(1:n-i+1),zeros(1,i-1)];q=[q(1)+q(2),q(3:n),1];%将排序后的概率数组q的前两项，即概率最小的两个数加和，得到新的一组概率序列endb%输出霍夫曼编码表a%输出对应霍夫曼编码表位置矩阵fori=1:n-1c(i,1:n*n)=blanks(n*n);%生成一个n-1行n列，并且每个元素的的长度为n的空白数组，c矩阵用于进行huffman编码，并且在编码中与a矩阵有一定的对应关系endc(n-1,n)='0';%由于a矩阵的第n-1行的前两个元素为进行huffman编码加和运算时所得的最c(n-1,2*n)='1';%后两个概率，因此其值为0或1，在编码时设第n-1行的第一个空白字符为0，第二个空白字符1。fori=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-1的字符赋值为对应于a矩阵中第n-i+1行中值为1的位置在c矩阵中的编值c(n-i,n)='0';%根据之前的规则，在分支的第一个元素最后补0c(n-i,n+1:2*n-1)=c(n-i,1:n-1);%矩阵c的第n-i的第二个元素的n-1的字符与第n-i行的第一个元素的前n-1个符号相同，%因为其根节点相同c(n-i,2*n)='1';%根据之前的规则，在分支的第一个元素最后补1forj=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));%矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值endend%完成huffman码字的分配fori=1:nh(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n);%用h表示最后的huffman编码，矩阵h的第i行的元素对应于矩阵c的第一行的第i个元素ll(i)=length(find(abs(h(i,:))~=32));%计算每一个huffman编码的长度endsort(p)',h%输出编码结果结果b=0.10000.10000.20000.20000.40000.20000.20000.20000.400000.20000.40000.4000000.40000.600000