信息论与编码技术实验报告

   实 验 题 目        香浓编码                           

   学生专业班级      信息与计算科学 1001             

   学生姓名（学号）  

   指 导 教 师                            

   完 成 时 间      20##年5月18日                 

                             20##  年   5    月   18    日

   实验一　香农编码的实验报告

一、实验目的

1. 了解香农编码的基本原理及其特点；

2. 熟悉掌握香农编码的方法和步骤；

3. 掌握C语言或者Matlab编写香农编码的程序。

二、实验要求

对于给定的信源的概率分布,按照香农编码的方法进行计算机实现.

三、实验原理

给定某个信源符号的概率分布，通过以下的步骤进行香农编码

1．信源符号按概率从大到小排列

2. 对信源符号求累加概率，表达式： Gi=Gi-1+p(xi)

3. 求自信息量，确定码字长度。自信息量I(xi)=-log(p(xi));码字长度取大于等于自信息量的最小整数。

4. 将累加概率用二进制表示，并取小数点后码字的长度的码 。

四、实验内容

离散无记忆信源符号S的概率分布：

对离散无记忆信源分布S进行香农编码

1.画出程序设计的流程图，

2.写出程序代码，

N=input('N=');    %输入信源符号的个数

s=0;

l=0;

H=0;

for i=1:N

    p(i)=input('p=');    %输入信源符号概率分布矢量,p(i)＜1

    s=s+p(i)

H=H+(-p(i)*log2(p(i)));

I(i)=-log2(p(i));    %计算信源信息熵

end

if abs(s-1)＞0,

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

end 

for i=1:N-1

    for j=i+1:N

        if p(i)

            m=p(j);

            p(j)=p(i);

            p(i)=m;

        end

    end

end                  %按概率分布大小对信源排序

for i=1:N

    a=-log2(p(i));

    if mod(a,1)==0

       w=a;

       else

          w=fix(a+1);

    end     %计算各信源符号的码长

     l=l+p(i)*w;       %计算平均码长

end

l=l;

n=H/l;                 %计算编码效率

P(1)=0

for i=2:N

    P(i)=0;

    for j=1:i-1

        P(i)=P(i)+p(j);

    end

end                   %计算累加概率

for i=1:N

    for j=1:w

        W(i,j)=fix(P(i)*2);

        P(i)=P(i)*2-fix(P(i)*2);

    end

end                     %将累加概率转化为L(i)位二进制码字

disp(W)                    %显示码字

disp(l)                   %显示平均码长

disp(n)                %显示编码效率

disp(I)               %显示自信息量

3.写出在调试过程中出现的问题 ，

问题1：自信量程序不会编写

问题2：累加概率时注意P(1)=0

问题3：程序运行时要依次输入各个符号概率

4.对实验的结果进行分析

由程序运行结果，得

2.34   2.41   2.48    2.56  2.74    3.34    6.66

所以我们得到每个信源符号的自信息量为

I(s1)=2.34   I(s2)=2.41   I(s3)=2.48   I(s4)=2.56  I(s5)=2.74  I(s6)=3.34   I(s7)=6.66

根据公式,我们得到每个信源符号的码长为

l1=3  l2=3  l3=3  l4=3  l5=3  l6=4   l7=7

由程序运行结果，

     0     0     0     0     0     0     0

0     0     1     1     0     0     0

     0     1     1     0     0     0     0

     1     0     0     1     0     0     0

     1     0     1     1     0     0     0

     1     1     1     0     0     0     0

     1     1     1     1     1     1     0

我们得到每个信源符号的为对应的二进制数为：

G1=0.0000000  G2=0.0011000  G3=0.0110000  G4=0.1001000  G5=0.1011000  G6=0.1110000     G7=0.1111110

所以我们得到每个信源符号的码字为：

S1=000  s2=001  s3=011  s4=100  s5=101  s6=1110   s7=1111110

平均码长为：3.14

编码效率为：0.831

五、实验结论与心得

此次实验让我认识和熟悉了及步骤，对MATLAB软件也有更加深刻的掌握，会用它求某个符号信源的香农编码程序算法，对我的实验能力有所提高。

Huffman编码软件实现实验报告

一、实验目的

1. 进一步熟悉Huffman编码过程；

2. 掌握Matlab程序的设计和调试技术。

二、实验要求

1. 输入：信源符号个数r、信源的概率分布P；

2. 输出：每个信源符号对应的Huffman编码的码字，编码效率。

三、实验原理：

1．二进制Huffman编码的基本原理

设信源s={}其中对应的概率分布为P()={}则其编码步骤如下：

(1) 将q个信源符号按概率递减的方式排列。

(2) 用0、1码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而的得到的只含q-1个符号的新信源，称为信源的缩减信源

(3) 将缩减信源中的符号仍按概率大小以递减次序排列，重复步骤（2）

(4) 重复（1）(2)(3)三步骤，直至缩减信源只剩下两个符号为止，将这最后两个符号分别用0、1码字表示。

(5)从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。

 2．二进制Huffman编码程序设计的原理（编码步骤）

  (1)程序的输入：

以一维数组的形式输入要进行Huffman编码的信源符号的概率，在运行该程序前，显示文字提示信息，提示所要输入的概率矢量；然后对输入的概率矢量进行合法性判断，原则为：如果概率矢量中存在小于0的项，则输入不合法，提示重新输入；如果概率矢量的求和大于1，则输入也不合法，提示重新输入。

（2）Huffman编码具体实现原理：

   ＜1＞在输入的概率矩阵p正确的前提条件下,对p进行排序，并用矩阵L记录p排序之前各元素的顺序，然后将排序后的概率数组p的前两项，即概率最小的两个数加和，得到新的一组概率序列，重复以上过程，最后得到一个记录概率加和过程的矩阵p以及每次排序之前概率顺序的矩阵a。

＜2＞新生成一个n-1行n列，并且每个元素含有n个字符的空白矩阵，然后进行Huffman编码：将c矩阵的第n-1行的第一和第二个元素分别令为0和1（表示在编码时，根节点之下的概率较小的元素后补0，概率较大的元素后补1，后面的编码都遵守这个原则）然后对n-i-1的第一、二个元素进行编码，首先在矩阵a中第n-i行找到值为1所在的位置，然后在c矩阵中第n-i行中找到对应位置的编码（该编码即为第n-i-1行第一、二个元素的根节点），则矩阵c的第n-i行的第一、二个元素的n-1的字符为以上求得的编码值，根据之前的规则，第一个元素最后补0，第二个元素最后补1，则完成该行的第一二个元素的编码，最后将该行的其他元素按照“矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值”的原则进行赋值，重复以上过程即可完成Huffman编码。

＜3＞计算信源熵和平均码长，其比值即为编码密码效率。

3.部分伪代码：

（1）节点信息结构体

struct HuffNode

{

   int weight;//信源符号的概率

    int parent;

       int lchild;

       int rchild;

};

（2）算法

void Huffman(int weight[], int n, HuffNode hn[], HuffCode hc[])

{

   

    for(i = 0; i != 2*n - 1; ++i) //create Huffman Node,step 1

       {}

       for(i = 0; i != n-1; ++i) //create Huffman Node, step 2

       {

              for(j = 0; j != n+i; j++)

        { if(hn[j].weight ＜ min1 && hn[j].parent == 0)

{}

else if(hn[j].weight ＜ min2 && hn[j].parent == 0)

              {}else ;

        }}

在此逆序存储Huffman编码

    int temp[maxlen];

       for(i = 0; i != n; ++i)

       {

              int parent = hn[i].parent;

              while(hn[child].parent != 0)

4. Huffman编码方法的特征

  （1） 它是一种分组码，各个信源符号都被映射成一组固定次序的马符号。

（2） 它是一种唯一可解的码，任何符号序列只能以一种方式译码。

（3）它是一种即时码：由于代表信源符号的节点都是终端节点，因此其编码不可能是其他终端节点对应的编码的前缀，即Huffman编码所得的码字为即时码。

（4） Huffman码的译码：对接受到的哈弗曼码序列可通过从左到右检查各个符号进行译码。

（5） 哈夫曼编码过程中，当缩减信源的概率分布重新排列时，应使合并得到的概率和尽量处于高的位置，这样可使合并的元素重复编码次数减少，

四、实验内容

对离散无记忆信源 进行Huffman编码。

1. 画出Huffman编码的程序流程图（如下）

2. 写出Huffman编码的源程序

p=input('please input a number:') 

n=length(p);

for i=1:n

  if  p(i)＜0

fprintf('\n The probabilities in huffman can not less than 0!\n'); 

 p=input('please input a number:')  %若输入的概率数组中有小于0的值，则重新输入概率数组

      end

end

if  abs(sum(p)-1)＞0

     fprintf('\n The sum of the probabilities in huffman can more than 1!\n');

      p=input('please input a number:')  

end

q=p;

a=zeros(n-1,n);                       %生成一个n-1行n列的数组

for i=1:n-1 

   [q,l]=sort(q)             

   a(i,:)=[l(1:n-i+1),zeros(1,i-1)]     

   q=[q(1)+q(2),q(3:n),1];          

end 

for i=1:n-1 

   c(i,1:n*n)=blanks(n*n);   

end 

c(n-1,n)='0';          

c(n-1,2*n)='1';         

for i=2:n-1 

c(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)='0'           

   c(n-i,n+1:2*n-1)=c(n-i,1:n-1) 

   c(n-i,2*n)='1'        

   for j=1:i-1 

  c(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))

                                                                                                                                   

     end 

 end                      

for i=1:n 

  h(i,1:n)=c(1,n*(find(a(1,:)==i)-1)+1:find(a(1,:)==i)*n) 

    ll(i)=length(find(abs(h(i,:))~=32))     

end 

l=sum(p.*ll);                           

 fprintf('\n huffman code:\n');

h

hh=sum(p.*(-log2(p)));                    

 fprintf('\n the huffman effciency:\n');

 t=hh/l

3. 运行源程序后，实验过程中的测试结果

p =   0.32    0.22    0.18    0.16    0.08   0.04

q =   0.04    0.08    0.16    0.18    0.22   0.32

q =   0.12    0.16    0.18    0.22    0.32   1.00

q =   0.18    0.22    0.28    0.32    1.00   1.00

q =   0.28    0.32    0.40    1.00    1.00   1.00

q=    0.40    0.60    1.00    1.00    1.00   1.00

ll =  2     4     2     2     3    4

huffman code:

h =

    00

  1001

    01

    11

   101

  1000

the huffman effciency:

t =    0.9801

实验结果分析

信源 的码字长度分别为 2  4  2  2  3  4 ；

所对应的码字为 11  0110  10  00  010  0111 ；

编码效率为 0.9801。

5、总结实验过程遇到的问题及解决方法

  1. 在实验过程中，遇到以下几个问题：

①   信源缩减不知怎么表示；

②   不知如何运用矩阵存储对应概率所对应的位置；

③  起初忘记对输入的各个概率以及概率之和进行判断，导致的程序的不合理性与不可行性。

2. 解决方法：

通过查找资料和相关书籍，学习类似的哈夫曼编码的程序的编写，使得问题得到解决

六、实验心得

通过此次试验，使得我对Huffman编码的编写原理、基本步骤有了更加深刻的理解，此外，我还学到了有关MATLAB知识的运用，比如：一些特殊语句的应用、矩阵存储知识的应用等等。总之，我认为此次实验还是比较成功的。