huffman编码实验matlab

多媒体通信技术实验

实验题目：Huffman编码

姓名：崔毅坚

学号：2008100894

班级: 通信08-03班

实验报告 Huffman编码算法的实现

一、实验目的

1、学习Matlab软件的使用和编程；

2、进一步深入理解Huffman编码算法的原理；

3、提高独立进行算法编程的能力。

二、实验内容

1、用Matlab实现Huffman编码算法程序；

2、要求程序输出显示所有的码字以及编码效率；

3、设计简单的输入界面（可以是简单的文字提示信息），程序运行时提示用户输入代表信源符号概率的向量；要对用户输入的概率向量进行合法性检查。

三、实验原理

1、二进制Huffman编码的基本原理及算法

(1) 把信源符号集中的所有符号按概率从大到小排队。

(2) 取概率最小的两个符号作为两片叶子合并（缩减）到一个 节点。

(3) 视此节点为新符号，其概率等于被合并（缩减）的两个概率之和，参与概率排队。

(4) 重复(2)(3)两步骤，直至全部符号都被合并（缩减）到根。

(5) 从根出发，对各分枝标记0和1。从根到叶的路径就给出了各个码字的编码和码长。

2、程序设计的原理

(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>计算信源熵和平均码长，其比值即为编码密码效率。

四、Huffman编码的Matlab源程序

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:') %如果输入的概率数组总和大于1，则重新输入概率数组

end

q=p;

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

for i=1:n-1

[q,l]=sort(q) %对概率数组q进行从小至大的排序，并且用l数组返回一个数组，该数组表示概率数组q排序前的顺序编号

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

%由数组l构建一个矩阵，该矩阵表明概率合并时的顺序，用于后面的编码

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

%将排序后的概率数组q的前两项，即概率最小的两个数加和，得到新的一组概率序列

end

for i=1:n-1

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

%生成一个n-1行n列，并且每个元素的的长度为n的空白数组，c矩阵用于进行huffman编码，并且在编码中与a矩阵有一定的对应关系

end

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

%由于a矩阵的第n-1行的前两个元素为进行huffman编码加和运算时所得的最

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

后两个概率，因此其值为0或1，在编码时设第n-1行的第一个空白字符为0，第二个空白字符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-1的字符赋值为对应于a矩阵中第n-i+1行中值为1的位置在c矩阵中的编码值

c(n-i,n)='0'

%根据之前的规则，在分支的第一个元素最后补0

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

%根据之前的规则，在分支的第一个元素最后补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))

%矩阵c中第n-i行第j+1列的值等于对应于a矩阵中第n-i+1行中值为j+1的前面一个元素的位置在c矩阵中的编码值

end

end

%完成huffman码字的分配

for i=1:n

h(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编码的长度

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

%计算编码效率

五、程序运行结果

（1）如果输入正确的概率矢量，结果如下：

please input a number:[0.32 0.18 0.05 0.10 0.15 0.2]

p =

0.3200 0.1800 0.0500 0.1000 0.1500 0.2000

huffman code:

h =

11

00

1010

1011

100

01

the huffman effciency:

t = 0.9774

（2）如果输入不正确的概率矢量，结果如下：

please input a number:[-0.2 0.5 0.3 0.4]

p =

-0.2000 0.5000 0.3000 0.4000

The probabilities in huffman can not less than 0!

please input a number:[0.6 0.1 0.3 0.4]

p =

0.6000 0.1000 0.3000 0.4000

The sum of the probabilities in huffman can more than 1!

please input a number:[0.05 0.09 0.10 0.21 0.25 0.30]

p =

0.0500 0.0900 0.1000 0.2100 0.2500 0.3000

huffman code:

h =

0110

0111

010

00

10

11

the huffman effciency:

t =0.9894

六、实验总结

1、在该实验的过程中，利用一个矩阵记录每次排序前概率的所在位置，是该实验的关键，在编码的过程中利用该矩阵就能比较容易进行huffman编码。

2、通过这个实验，对huffman编码的具体实现原理了解的更加深刻，在实验的过程中也遇到了一些问题，通过查找资料和相关书籍得到了解决，总的来说，在完成该实验的过程中，还是学到了比较多的知识，包括使对一些matlab语句的掌握的更加熟练，完成一个算法必须要有一个整体的把握等等。