无失真变长编码及其MATLAB实现

无失真变长编码及其MATLAB实现我最近阅读了一篇关于无失真变长编码的期刊文献，通过阅读这篇文章我学到了更多关于信源编码的知识以及几种编码方法的MATLAB实现过程。这篇文章主要介绍了无失真变长编码的两种编码方法：Shannon和Huffman编码，以及它们的MATLAB实现方法和分析比较。我们都知道通信的本质就是信息的传输，即信源信息通过信道传给信宿，关键就是要高质量、高速度地传送信息，为了提高信号的传输速率，主要必须解决信号失真和受干扰这两个问题。文章针对无失真这种情况讲述了两种无失真编码的原理，即Shannon编码和Huffman编码，因为这两种编码方法的工作量很大，若采用人工计算就会使工作效率和编码精确度大大降低，因而运用了语言简洁方便的MATLAB编程软件来实现其编码，并举出了两种编码方法的MATLAB实例及对两者进行了比较来说明两者的优缺点。无失真信源编码主要有等长编码和变长编码两种，其中等长编码的效率较低，而变长编码具有很高的效率，往往在码长不大时就可编出效率很高而且无失真的信源码，因此一般广泛采用后者。变长编码中用编码效率来衡量各种编码方法的优劣，编码效率为：IsH)(，其中：)(sH为信息熵，)(log)()(21iqiispspsH，)(isp为信源符号is出现的概率；I为平均码长，iqiiIspI1)(。对同一信源来说，若码的平均码长越短，越接近信息熵得值，则编码效率越接近1，编码方法就越好。下面通过MATLAB实例来比较Shannon编码和Huffman编码。1.Shannon编码方法及MATLAB实现：第一步：将信源发出的N个消息符号按其概率的递减次序依次排列。第二步：计算第i个消息的二进制代码组的码长iI。第三步：计算第I个消息的累加概率，然后将累加概率变换成二进制数。第四步：去除小数点，并根据码长iI，取小数点后iI位数作为第i个消息的代码组。MATLAB实现：clear;N=input('N=');s=0;I=0;H=0;fori=1:NP(i)=input('P=');s=s+P(i);H=H+(-P(i)*log2(P(i)));endifabs(s-1)0error('不符合概率分布');endfori=1:N-1forj=i+1:NifP(i)P(j)m=P(j);P(j)=P(i);P(i)=m;endendendfori=1:NL(i)=fix(-log2(P(i))+1);I=I+P(i)*L(i);endn=H/I;disp(I)disp(n)2.Huffman编码方法及MATLAB实现：第一步：将信源消息按照概率大小顺序排列。第二步：从最小概率的两个消息开始编码，并给与一定编码规则。第三步：将已编码的两个消息对应概率相加，并重新按概率大小排列，重复第二步。第四步：重复第三步，直至合并概率达到1.0。第五步：编码的变长码是按后出现编的方式。MATLAB实现：clear;A=input('pleaseinputstr:');A=fliplr(sort(A));T=A;[m,n]=size(A);B=zeros(n,n-1);fori=1:nB(i,1)=T(i);endr=B(i,1)+B(i-1,1);T(n-1)=r;T(n)=0;T=fliplr(sort(T));t=n-1;forj=2:tfori=1:tB(i,j)=T(i);endK=find(T==r);B(n,j)=K(end);r=(B(t-1,j)+B(t,j));T(t-1)=r;T(t)=0;T=fliplr(sort(T));t=t-1;endB;END1=sym('[0,1]');END=END1;t=3;d=1;forj=n-2:-1:1fori=1:t-2ifi1&B(i,j)==B(i-1,j)d=d+1;elsed=1;endB(B(n,j+1),j+1)=-1;temp=B(:,j+1);x=find(temp==B(i,j));END(i)=END1(x(d));endy=B(n,j+1);END(t-1)=[char(END1(y)),'1'];END(t)=[char(END1(y)),'0'];t=t+1;END1=END;endAENDfori=1:n[a,b]=size(char(END(i)));L(i)=b;endavlen=sum(L.*A)H1=log2(A);H=-A*(H1')P=H/avlen现对同一离散信源分别调用以上两种编码的MATLAB程序，输入信息如下：N=6，p(1)=0.30,p(2)=0.25,p(3)=0.21,p(4)=0.10,p(5)=0.09,p(6)=0.05.则有：1.Shannon编码2.Huffman编码从程序的运行结果可以知道，这两种编码方法的运行时间比人工编码的短了很多，并且Huffman编码的平均码长较小，其编码效率比Shannon编码更高。