信息论实验信源的二元Huffman编码

wilyes11收集博客(与学习无关)：信源的二元Huffman编码一.实验目的任选C语言，C++，或MATLAB等一种方法编写程序，对离散信源进行二元Huffman编码，计算平均码长及编码效率，并通过1~2个运行的结果，验证程序的正确性。通过实验，掌握r元Huffman编码的方法，学会平均码长与编码效率等常见计算。二.实验内容编写程序实现：输入：信源X的分布12,,,mppp，11miip；输出：二元变长码12{,,,}mCccc，平均码长n，编码效率。三.实验方案或步骤（程序设计说明）(1)把信源符号ix(i=1,2,…,m)出现的概率ip按由大到小的顺序排列；(2)对两个概率最小的符号分别标“0”和“1”，然后把这两个概率相加作为一个新的辅助符号的概率；(3)将这个新的辅助符号与其他符号一起重新按概率大小顺序排列；(4)跳到第2步，直到出现概率相加为1为止；(5)用线将符号连接起来，得到一个码树，树的m个端点对应m个信源符号；(6)从最后一个概率为1的节点开始，沿着码树分别到达每个信源符号，将一路遇到的“0”和“1”顺序排列起来，就是对应端点的信源符号的码字。wilyes11收集博客(与学习无关)：四.实验程序（经调试后正确的源程序）p=input('\n输入信源X的分布,格式[p1p2…pm]：\n');if(length(find(p0))~=0)error('数组中概率有负的');%p概率为负拒绝编码endif(abs(sum(p)-1)10e-10)error('概率之和不为1');%概率之和与1差的绝对值大于10的负10次方endn=length(p);%数组中元素的个数，循环操作用q=p;%信源的概率赋给q，以便后面排序、合并用m=zeros(n-1,n);%定义m为零数组，记录排列顺序（小概率求和后再重新排列，这就存在排序的问题）fori=1:n-1[q,k]=sort(q);%k是排列后的顺序，sort(q)是对q进行升序m(i,:)=[k(1:n-i+1),zeros(1,i-1)];%概率小的相加之后重新排序，排列顺序记录在m矩阵中q=[q(1)+q(2),q(3:n),1];%最后两个概率小的合并成一个endfori=1:n-1c(i,:)=blanks(n*n);%blanks(n*n)是一个1行n*n列的数组，里面是空的endc(n-1,n)='0';%把c这个空数组的(n-1,n)这个位置赋值0c(n-1,2*n)='1';%把c这个空数组的(n-1,2*n)这个位置赋值1fori=2:n-1c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))-(n-2):n*(find(m(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';forj=1:i-1c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,n*(find(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1));endendfori=1:nh(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n);%h是Huffman编码ll(i)=length(find(abs(h(i,:))~=32));%ll为各码的码长endla=sum(p.*ll);%la是平均码长H=sum(-p.*log2(p));%H是信息熵RW=H/la;%RW是编码效率fori=1:n%显示概率及Huffman编码fprintf('概率：%g编码：%s\n',p(i),h(i,:))endfprintf('平均码长为：%g\n',la)%显示平均码长fprintf('编码效率为：%g\n',RW)%显示编码效率%例1：p=[0.2,0.3,0.4,0.06,0.04];%例2：p=[0.18,0.17,0.01,0.15,0.2,0.19,0.1];wilyes11收集博客(与学习无关)：五．程序运行结果（列举2-3个）输入信源X的分布,格式[p1p2…pm]：[0.2,0.3,0.4,0.06,0.04]概率：0.2编码：111概率：0.3编码：10概率：0.4编码：0概率：0.06编码：1101概率：0.04编码：1100平均码长为：2编码效率为：0.971767输入信源X的分布,格式[p1p2…pm]：[0.18,0.17,0.01,0.15,0.2,0.19,0.1]概率：0.18编码：111概率：0.17编码：110概率：0.01编码：1000概率：0.15编码：101概率：0.2编码：01概率：0.19编码：00概率：0.1编码：1001平均码长为：2.72编码效率为：0.959075六．实验总结及心得体会Huffman编码方法是《数据结构》课程中的一个重要内容，当时是用二叉树来实现的。在《信息论与编码》中，Huffman树的概念虽然提的很少，但整体思想仍然是相同的，因此编程过程还比较顺利。实验中涉及到大量向量、排序、比较运算，让我体验到了采用MATLAB处理这一类编程问题的方便性。七．教师评语教师签名：年月日