APP下载

基于MATLAB的Huffman编码实验教学平台设计

2015-02-20

安阳师范学院学报 2015年2期

李 荣

(安阳师范学院 数学与统计学院,河南 安阳 455000)



基于MATLAB的Huffman编码实验教学平台设计

李荣

(安阳师范学院 数学与统计学院,河南 安阳 455000)

[摘要]针对Huffman编码实验教学中的有关计算问题,本文利用MATLAB 的图形用户界面,设计开发了一个简单实用的实验教学平台。该平台实现了理论和实验相结合,为Huffman编码的实验教学提供了一个有效的工具。

[关键词]Huffman编码;变长码;MATLAB应用;图形用户界面;仿真实验教学

0引言

Huffman编码是变长码(Variable-Length Coding,VLC)中的一种无损压缩方法[1-2]。它主要依据字符出现的概率来给不同的信号分配码字,对出现概率高的信号分配短码字,出现概率低的信号分配长码字。在有效译码的前提下,若信源具有相同的概率分布,Huffman编码的平均码字长度比其他任何一种有效编码方法都短[3]。它具有编码速度快,实现方式灵活,可有效消除编码冗余等多种优点。因此,Huffman编码在压缩文本和程序文件中得到了广泛应用。

MATLAB 是由美国的MathWorks公司在1984 年首次发布的一种数学软件, 它可以实现大型矩阵运算、绘制函数图像、创建用户界面、连接其他编程语言的程序等多种功能[4-5],并且应用领域广泛,主要有信号处理与通讯、信号检测、图像处理、金融建模设计与分析等[6-7]。同时,MATLAB的语言简单, 允许用户以数学形式的语言编写程序, 操作和指令简单,解算问题要比用C,FORTRAN等语言完成相同的事情简捷得多。因此, MATLAB不仅可以作为理论教学的示范性工具, 更适合作为仿真实验教学的主要工具。

在Huffman编码的教学过程中,经常面临问题理论性太强,概念过于抽象,数学推导繁冗,致使学生理解起来非常困难,利用MATLAB 中GUI 图形用户界面相关知识设计Huffman编码的实验图形界面,只需简单操作文本输入框和按钮,就可直观便捷地解决这些问题,有助于教学质量的提高。

1Huffman编码实验原理

1.1 Huffman编码的一般步骤

(1) 将信源消息符号按其出现的概率大小依次排列为

P1≥P2≥……≥Pn

(2) 取两个概率最小的字母分别配以0和1两个码元,并将这两个概率相加作为一个新字母的概率,与未分配的二进符号的字母重新排队。

(3) 对重排后的两个概率最小符号重复步骤(2)的过程。

(4) 不断继续上述过程,直到最后两个符号配以0和1为止。

(5) 从最后一级开始,向前返回得到各个信源符号所对应的码元序列,即相应的码字。

1.2 Huffman编码的优缺点

Huffman编码是用概率匹配方法进行信源编码,它的优点有:

(1) Huffman码的编码方法保证了概率大的符号对应于短码,概率小的符号对应于长码,充分利用了短码;

(2) 缩减信源的最后二个码字总是最后一位不同,从而保证了Huffman码是即时码。

(3) Huffman码是无损编码,相对于定长码具有较高的编码效率。

Huffman码在实际中已经广泛应用,但它仍存在一些缺点。

(1)对于过短的文件进行编码时,编码效果不佳,并且当合并的符号数增加时,存储哈夫曼树的信息将要占用大量的存储空间;

(2)对较大的文件进行编码时,会出现频繁的磁盘读写访问,对设备的要求更加复杂,并且降低了数据编码的速度。

2基于MATLAB 的Huffman编码实验系统GUI 操作界面

Graphical User Interface(以下称GUI),是图形用户界面的意思。随着计算机技术的飞速发展,人与计算机的通信方式也发生了质的飞跃,从原来的命令行通讯方式(例如很早的DOS系统)发展到了GUI下的人机交互模式。同很多高级编程语言一样,MATLAB也具有GUI开发环境。下面我们就利用它来设计实现离散信源的Huffman编码的实验系统操作界面。

首先,在离散信源的Huffman编码GUI实验界面中,我们将信源符号的个数N 和信源符号的概率分布p 作为输入,并且在设计界面中添加两个文本框控件( Edit Text) ,作为N 和p 的输入框;然后,设置一个按钮控件( Radio Buttons) ,作为编码方法的响应键,得出计算结果;最后,按照实验要求将Huffman编码的编码效率、平均码长和码字作为输出显示出来,界面如图1所示。

3Huffman编码应用实例

设有离散无记忆信源的概率分布如下

[X,P]=

在界面中N的位置键入6,P处键入[0.32,0.22,0.04,0.08,0.16,0.18],点击计算结果按钮,从图2中可以看到,每个信源符号所对应的码字分别为11,01,00,101,1001,1000,平均码长为2.4码元/符号,编码效率为98.01%,相较于其他最佳码而言,Huffman码具有较高的编码效率。

4小结

本文设计了用于Huffman编码的软件实验教学平台, 此平台仅需简单的输入操作,就可以得到信源的编码效率、平均码长和码字。作者已将该平台投入到实际教学过程中,实践证明,该平台操作简单,运行结果直观。在实验过程中, 学生既可以修改相关参数来比较实验结果, 有能力的同学还可以通过修改源程序实现与之相关的Shannon编码和Fano编码的教学平台设计,增强了学生的动手能力,提高了学生的学习兴趣,为课程的教学带来了可喜的成效。

[参考文献]

[1]章毓晋.图像工程(上册):图像分析和处理[M].北京:清华大学出版社,2002.

[2]徐飞,施晓红.Matlab应用图像处理[M].西安:西安电子科技大学出版社,2003.

[3]严蔚敏,吴伟民. 数据结构:C 语言版[M]. 北京:清华大学出版社,1997.

[4]陈杰.Matlab宝典[M].北京:电子工业出版社,2008.

[5]张威.Matlab基础与编程入门第2版[M].西安:西安电子科技,2008.

[6]陈天华.数字图像处理[M].北京:清华大学出版社,2007.

[7]高成.Matlab图像处理与应用[M].北京:国防工业出版社,2007.

[责任编辑:D]

Design of Experiment Teaching Platform for Huffman coding Based on MATLAB

LI Rong

(School of Mathematics and Statistics, Anyang Normal University, Anyang 455000,China)

Abstract:This paper exploits a simple practical experiment teaching platform based on the Graphical User Interface programming method of Matlab in order to solve the computing issues of Huffman algorithm. This platform can realize the combination of theories and experiment, and offer an effective tool for the experimental teaching.

Key words:Huffman algorithm; Variable-Length Coding; Matlab application; Graphical User Interface ; simulation experimental teaching

[中图分类号]O236

[文献标识码]A

[文章编号]1671-5330(2015)02-0044-03

[作者简介]李荣(1985-),女,主要从事辛算法及混沌研究。

[收稿日期]2015-01-20