基于MATLAB的Huffman編碼實(shí)驗(yàn)教學(xué)平臺(tái)設(shè)計(jì)

李　榮

(安陽(yáng)師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 安陽(yáng) 455000)

?

基于MATLAB的Huffman編碼實(shí)驗(yàn)教學(xué)平臺(tái)設(shè)計(jì)

李榮

(安陽(yáng)師范學(xué)院 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，河南 安陽(yáng) 455000)

[摘要]針對(duì)Huffman編碼實(shí)驗(yàn)教學(xué)中的有關(guān)計(jì)算問(wèn)題，本文利用MATLAB 的圖形用戶(hù)界面，設(shè)計(jì)開(kāi)發(fā)了一個(gè)簡(jiǎn)單實(shí)用的實(shí)驗(yàn)教學(xué)平臺(tái)。該平臺(tái)實(shí)現(xiàn)了理論和實(shí)驗(yàn)相結(jié)合，為Huffman編碼的實(shí)驗(yàn)教學(xué)提供了一個(gè)有效的工具。

[關(guān)鍵詞]Huffman編碼；變長(zhǎng)碼；MATLAB應(yīng)用；圖形用戶(hù)界面；仿真實(shí)驗(yàn)教學(xué)

0引言

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

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

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

1Huffman編碼實(shí)驗(yàn)原理

1.1　Huffman編碼的一般步驟

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

P1≥P2≥……≥Pn

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

(3) 對(duì)重排后的兩個(gè)概率最小符號(hào)重復(fù)步驟(2)的過(guò)程。

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

(5) 從最后一級(jí)開(kāi)始，向前返回得到各個(gè)信源符號(hào)所對(duì)應(yīng)的碼元序列，即相應(yīng)的碼字。

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

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

(1) Huffman碼的編碼方法保證了概率大的符號(hào)對(duì)應(yīng)于短碼，概率小的符號(hào)對(duì)應(yīng)于長(zhǎng)碼，充分利用了短碼；

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

(3) Huffman碼是無(wú)損編碼，相對(duì)于定長(zhǎng)碼具有較高的編碼效率。

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

(1)對(duì)于過(guò)短的文件進(jìn)行編碼時(shí)，編碼效果不佳，并且當(dāng)合并的符號(hào)數(shù)增加時(shí)，存儲(chǔ)哈夫曼樹(shù)的信息將要占用大量的存儲(chǔ)空間；

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

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

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

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

3Huffman編碼應(yīng)用實(shí)例

設(shè)有離散無(wú)記憶信源的概率分布如下

[X，P]=

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

4小結(jié)

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

[參考文獻(xiàn)]

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

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

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

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

[5]張威.Matlab基礎(chǔ)與編程入門(mén)第2版[M].西安：西安電子科技，2008.

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

[7]高成.Matlab圖像處理與應(yīng)用[M].北京：國(guó)防工業(yè)出版社，2007.

[責(zé)任編輯：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

[中圖分類(lèi)號(hào)]O236

[文獻(xiàn)標(biāo)識(shí)碼]A

[文章編號(hào)]1671-5330(2015)02-0044-03

[作者簡(jiǎn)介]李榮(1985-)，女，主要從事辛算法及混沌研究。

[收稿日期]2015-01-20