李　榮

(安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455000)

?

基于MATLAB的Huffman編碼實驗教學平臺設計

李榮

(安陽師范學院 數(shù)學與統(tǒng)計學院，河南 安陽 455000)

[摘要]針對Huffman編碼實驗教學中的有關(guān)計算問題，本文利用MATLAB 的圖形用戶界面，設計開發(fā)了一個簡單實用的實驗教學平臺。該平臺實現(xiàn)了理論和實驗相結(jié)合，為Huffman編碼的實驗教學提供了一個有效的工具。

[關(guān)鍵詞]Huffman編碼；變長碼；MATLAB應用；圖形用戶界面；仿真實驗教學

0引言

Huffman編碼是變長碼(Variable-Length Coding，VLC)中的一種無損壓縮方法[1-2]。它主要依據(jù)字符出現(xiàn)的概率來給不同的信號分配碼字，對出現(xiàn)概率高的信號分配短碼字，出現(xiàn)概率低的信號分配長碼字。在有效譯碼的前提下，若信源具有相同的概率分布，Huffman編碼的平均碼字長度比其他任何一種有效編碼方法都短[3]。它具有編碼速度快，實現(xiàn)方式靈活，可有效消除編碼冗余等多種優(yōu)點。因此，Huffman編碼在壓縮文本和程序文件中得到了廣泛應用。

MATLAB 是由美國的MathWorks公司在1984 年首次發(fā)布的一種數(shù)學軟件, 它可以實現(xiàn)大型矩陣運算、繪制函數(shù)圖像、創(chuàng)建用戶界面、連接其他編程語言的程序等多種功能[4-5]，并且應用領域廣泛，主要有信號處理與通訊、信號檢測、圖像處理、金融建模設計與分析等[6-7]。同時，MATLAB的語言簡單, 允許用戶以數(shù)學形式的語言編寫程序, 操作和指令簡單,解算問題要比用C，F(xiàn)ORTRAN等語言完成相同的事情簡捷得多。因此, MATLAB不僅可以作為理論教學的示范性工具, 更適合作為仿真實驗教學的主要工具。

在Huffman編碼的教學過程中，經(jīng)常面臨問題理論性太強，概念過于抽象，數(shù)學推導繁冗，致使學生理解起來非常困難，利用MATLAB 中GUI 圖形用戶界面相關(guān)知識設計Huffman編碼的實驗圖形界面，只需簡單操作文本輸入框和按鈕，就可直觀便捷地解決這些問題，有助于教學質(zhì)量的提高。

1Huffman編碼實驗原理

1.1　Huffman編碼的一般步驟

(1) 將信源消息符號按其出現(xiàn)的概率大小依次排列為

P1≥P2≥……≥Pn

(2) 取兩個概率最小的字母分別配以0和1兩個碼元，并將這兩個概率相加作為一個新字母的概率，與未分配的二進符號的字母重新排隊。

(3) 對重排后的兩個概率最小符號重復步驟(2)的過程。

(4) 不斷繼續(xù)上述過程，直到最后兩個符號配以0和1為止。

(5) 從最后一級開始，向前返回得到各個信源符號所對應的碼元序列，即相應的碼字。

1.2　Huffman編碼的優(yōu)缺點

Huffman編碼是用概率匹配方法進行信源編碼，它的優(yōu)點有：

(1) Huffman碼的編碼方法保證了概率大的符號對應于短碼，概率小的符號對應于長碼，充分利用了短碼；

(2) 縮減信源的最后二個碼字總是最后一位不同，從而保證了Huffman碼是即時碼。

(3) Huffman碼是無損編碼，相對于定長碼具有較高的編碼效率。

Huffman碼在實際中已經(jīng)廣泛應用，但它仍存在一些缺點。

(1)對于過短的文件進行編碼時，編碼效果不佳，并且當合并的符號數(shù)增加時，存儲哈夫曼樹的信息將要占用大量的存儲空間；

(2)對較大的文件進行編碼時，會出現(xiàn)頻繁的磁盤讀寫訪問，對設備的要求更加復雜，并且降低了數(shù)據(jù)編碼的速度。

2基于MATLAB 的Huffman編碼實驗系統(tǒng)GUI 操作界面

Graphical User Interface(以下稱GUI)，是圖形用戶界面的意思。隨著計算機技術(shù)的飛速發(fā)展，人與計算機的通信方式也發(fā)生了質(zhì)的飛躍，從原來的命令行通訊方式(例如很早的DOS系統(tǒng))發(fā)展到了GUI下的人機交互模式。同很多高級編程語言一樣，MATLAB也具有GUI開發(fā)環(huán)境。下面我們就利用它來設計實現(xiàn)離散信源的Huffman編碼的實驗系統(tǒng)操作界面。

首先，在離散信源的Huffman編碼GUI實驗界面中，我們將信源符號的個數(shù)N 和信源符號的概率分布p 作為輸入，并且在設計界面中添加兩個文本框控件( Edit Text) ，作為N 和p 的輸入框；然后，設置一個按鈕控件( Radio Buttons) ，作為編碼方法的響應鍵，得出計算結(jié)果；最后，按照實驗要求將Huffman編碼的編碼效率、平均碼長和碼字作為輸出顯示出來，界面如圖1所示。

3Huffman編碼應用實例

設有離散無記憶信源的概率分布如下

[X，P]=

在界面中N的位置鍵入6，P處鍵入[0.32,0.22,0.04,0.08,0.16,0.18]，點擊計算結(jié)果按鈕，從圖2中可以看到，每個信源符號所對應的碼字分別為11，01，00，101，1001，1000，平均碼長為2.4碼元/符號，編碼效率為98.01%，相較于其他最佳碼而言，Huffman碼具有較高的編碼效率。

4小結(jié)

本文設計了用于Huffman編碼的軟件實驗教學平臺, 此平臺僅需簡單的輸入操作，就可以得到信源的編碼效率、平均碼長和碼字。作者已將該平臺投入到實際教學過程中，實踐證明，該平臺操作簡單，運行結(jié)果直觀。在實驗過程中, 學生既可以修改相關(guān)參數(shù)來比較實驗結(jié)果, 有能力的同學還可以通過修改源程序?qū)崿F(xiàn)與之相關(guān)的Shannon編碼和Fano編碼的教學平臺設計，增強了學生的動手能力，提高了學生的學習興趣，為課程的教學帶來了可喜的成效。

[參考文獻]

[1]章毓晉.圖像工程(上冊)：圖像分析和處理[M].北京：清華大學出版社，2002.

[2]徐飛，施曉紅.Matlab應用圖像處理[M].西安：西安電子科技大學出版社，2003.

[3]嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)：C 語言版[M]. 北京：清華大學出版社，1997.

[4]陳杰.Matlab寶典[M].北京：電子工業(yè)出版社，2008.

[5]張威.Matlab基礎與編程入門第2版[M].西安：西安電子科技，2008.

[6]陳天華.數(shù)字圖像處理[M].北京：清華大學出版社，2007.

[7]高成.Matlab圖像處理與應用[M].北京：國防工業(yè)出版社，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