http://blog.163.com/yangxiaoquan20080808@126/blog/static/856940402011055567463/

香 农 编 码

 问题背景：

   1949年香农在《有噪声时的通信》一文中提出了信道容量的概念和信道编码定理，为信道编码奠定了理论基础。无噪信道编码定理（又称香农第一定理）指出，码字的平均长度只能大于或等于信源的熵。有噪信道编码定理（又称香农第二定理）则是编码存在定理。它指出只要信息传输速率小于信道容量，就存在一类编码，使信息传输的错误概率可以任意小。随着计算技术和数字通信的发展，纠错编码和密码学得到迅速的发展。 

课题分析：

   运用matlab编写程序求解任给信源符号概率的香农编码。给定一组信源符号概率，通过所编写的程序对信源符号概率编码，求出此信源符号概率对应的香农编码。

编程方法：

据课本上的介绍编码香农码的方法。

首先，给定信源符号概率，要先判断信源符号概率是否满足概率分布，即各概率之和是否为1，如果不为1就没有继续进行编码的必要，虽然任可以正常编码，但编码失去了意义。

其次，对信源符号概率进行从小到大的排序，以便进行下一步。从第一步就知道信源符号的个数n，于是构造一个nx4的零矩阵D，以便储存接下来运算的结果。把排好序的信源符号概率以列的形式赋给D的第一列。

再次，做编码的第二步，求信源符号概率的累加概率（方法见程序），用来编写码字。

接着求各信源符号概率对应的自信息量，用于求解码长k。

然后，我们对刚求的自信息量对无穷方向取最小正整数，得到的最小正整数就是该信源符号所对应编码的码长k，有了码长，接下来就可以求解码字。

最后，对所求到的累加概率求其二进制，取其小数点后的数，所取位数由该信源符号对应的码长决定，所用的步骤结束，依次得到各信源符号的香农编码。

程序展现：

%求解给定信源符号概率的香农编码

n=input('输入信源符号个数n=')

p=zeros(1,n);

for i=1:n

p(1,i)=input('输入信源符号概率:');

end

if sum(p)<1||sum(p)>1

error('输入概率不符合概率分布')

end

y=fliplr(sort(p));%从大到小的排序

D=zeros(n,4);%生成7*4的零矩阵

 D(:,1)=y';%把y赋给零矩阵的第一列

 for i=2:n

    D(1,2)=0;%令第一行第二列的元素为0

    D(i,2)=D(i-1,1)+D(i-1,2);%第二列其余的元素用此式求得,即为累加概率

 end

   for i=1:n

    D(i,3)=-log2(D(i,1));%求第三列的元素

    D(i,4)=ceil(D(i,3));%求第四列的元素，对D(i,3)向无穷方向取最小正整数

   end

D

A=D(:,2)';%取出D中第二列元素

B=D(:,4)';%取出D中第四列元素

for j=1:n

C=deczbin(A(j),B(j))%生成码字

end

function [C]=deczbin(A,B)%对累加概率求二进制的函数

C=zeros(1,B);%生成零矩阵用于存储生成的二进制数，对二进制的每一位进行操作

temp=A;%temp赋初值

 for i=1:B%累加概率转化为二进制，循环求二进制的每一位，A控制生成二进制的位数

  temp=temp*2;

  if temp>1

  temp=temp-1;

 C(1,i)=1;

  else

 C(1,i)=0;

  end

 end

实验过程及结果分析：

   此程序是据课本香农编码叙述编写，编写过程简洁，能够看到每个过程的结果，经过多次循环和函数调用直接求解码字。在运行开始先确定要求解的信源符号个数，输入概率时循环控制输入的次数，接下来判断概率是否符合要求。

    香农编码是码符号概率大的用短码表示，概率小的是用长码表示，程序中对概率排序，最后求得的码字就依次与排序后的符号概率对应。此程序缺点是，第一个码字都是以0开始，因为对累加概率求二进制后，小数点后的数都是0，取几位由码长确定，而香农编码是不唯一的，如果手动编码就不存在这样的问题。后面求得的编码没有下标就需要注意是与上面排序后的信源符号对应。