盧小杰，葉明全，黃道斌

(皖南醫(yī)學院 計算機教研室， 安徽 蕪湖 241000)

?

基于織物信息的動態(tài)Huffman壓縮算法優(yōu)化

盧小杰，葉明全，黃道斌

(皖南醫(yī)學院 計算機教研室， 安徽 蕪湖 241000)

摘要：針對嵌入式系統(tǒng)內(nèi)存不足的特點，為了使上下位機更有效地進行數(shù)據(jù)傳輸，對動態(tài)Huffman壓縮算法進行優(yōu)化，使用堆排序的方法來構造Huffman樹，緩解了嵌入式系統(tǒng)的內(nèi)存壓力；在數(shù)據(jù)傳輸過程中增加CRC校驗位，以此來提高數(shù)據(jù)傳輸精度，并在解壓中處理了無效位。同時對嵌入式織造系統(tǒng)中的織物信息數(shù)據(jù)進行頻譜分析。實驗結果表明，優(yōu)化的Huffman壓縮算法能夠獲得更好的壓縮效果，并且壓縮率與數(shù)據(jù)的頻率相關。

關鍵詞：嵌入式技術；FFT；數(shù)據(jù)壓縮； Huffman壓縮算法； CRC校驗位

DOI：10.13757/j.cnki.cn34-1150/n.2016.02.012

隨著現(xiàn)代紡織業(yè)的發(fā)展，嵌入式技術(Embedded Technology)和物聯(lián)網(wǎng)(Internet of Things，IOT)技術被應用在紡織機械控制系統(tǒng)中，稱為嵌入式織造系統(tǒng)，一般由上下位機構成，上位機為PC機或其他嵌入式主控系統(tǒng)，下位機為51單片機系統(tǒng)或者其他精簡的單片機系統(tǒng)。如圖1所示。

圖1　織造系統(tǒng)示意圖

在實際工業(yè)生產(chǎn)中，把織物信息數(shù)據(jù)由上位機的主控系統(tǒng)傳輸至下位機中，由下位機控制紡織機械。為了保障數(shù)據(jù)在工業(yè)級應用中有較好的實時性和較低的誤碼率，本文研究針對織物信息數(shù)據(jù)的壓縮算法。任何一種數(shù)據(jù)形態(tài)都有一定的冗余度，有效地減少冗余度可以大大提高數(shù)據(jù)的傳輸速度、節(jié)省數(shù)據(jù)存儲空間、減少內(nèi)存消耗、降低硬件成本。因此，研究針對嵌入式織造系統(tǒng)中織物信息數(shù)據(jù)的壓縮算法具有很高的應用價值。在上位機中壓縮后的數(shù)據(jù)傳輸至下位機，在下位機有限的內(nèi)存空間和較低的運算速度下有效地解壓出來[1]。目前應用于嵌入式系統(tǒng)的壓縮算法很多，如RLE壓縮算法[2]、Huffman壓縮算法、LZSS壓縮算法[3-4]和LZW壓縮算法[5]等，這些壓縮算法各有其特點和適用領域。本文在此基礎上選取Huffman壓縮算法，對其進行改進，使之能夠對織物數(shù)據(jù)有較好的壓縮效果。

1織物信息數(shù)據(jù)

織物信息數(shù)據(jù)中比較重要的一項為紋板數(shù)據(jù)，即用來控制織物的紋板花紋的數(shù)據(jù)。紋板數(shù)據(jù)包含穿綜信息和組織信息，如圖2。沖孔為1，不沖孔為0，形成二進制數(shù)據(jù)流，如圖3。

圖2　某條織物紋板圖

0001001001001000é?êêêêêù?úúúúú

圖3紋板圖和紋板矩陣

由圖3可知，紋板數(shù)據(jù)可以看作二進制流的數(shù)據(jù)文件?？椢镄畔?shù)據(jù)從統(tǒng)計學上說是一種隨機的二維矩陣，對此二維系數(shù)矩陣進行頻譜分析，在頻域空間上進行傅里葉(FFT)變換。

N點序列x(n)的離散傅里葉變換(DFT)和離散傅里葉逆變換(IDFT)的復數(shù)表示形式為[6]

(1)

FFT是DFT在工程應用中的快速傅里葉變換，基于2-DFT的蝶形運算，如經(jīng)過8點蝶形運算的DFT化為FFT。假設采樣頻率為F，采樣點數(shù)為N，某點n頻率為

Fn=(n-1)F/N

(2)

在Matlab中二維系數(shù)矩陣為A(∶)，經(jīng)過函數(shù)fftshift(fft(A(∶)))變換后得到相應的織物信息頻譜?？椢镄畔?shù)據(jù)的頻譜與后面研究的Huffman壓縮算法得到的壓縮率相關。

2動態(tài)Huffman壓縮算法

在嵌入式織造系統(tǒng)中常常要求有較高的實時性，使用動態(tài)的Huffman壓縮可以一邊壓縮一邊解壓，字符的編碼長度是與壓縮和解壓一個字符的時間成正比，可以實時進行。

2.1動態(tài)Huffman壓縮過程

動態(tài)Huffman壓縮算法主要是針對靜態(tài)Huffman壓縮算法存在的不足而提出來的。靜態(tài)Huffman壓縮算法具有以下缺陷[7]：

(1)要對文件掃描兩遍，先遍歷所有字符，在數(shù)據(jù)傳輸過程中很難預知所有字符概率，現(xiàn)實應用中可行性差；

(2)先建立Huffman編碼表，浪費了額外的空間來維護和傳輸編碼表；

(3)靜態(tài)Huffman壓縮算法在實際應用中壓縮效率比較低，且將Huffman樹的信息隨著壓縮數(shù)據(jù)傳輸，不利于較短數(shù)據(jù)的壓縮。

動態(tài)Huffman壓縮算法無需預知字符概率，核心是邊讀取數(shù)據(jù)邊修改Huffman樹，壓縮和解壓縮都由空Huffman樹開始，第i+1個字符的編碼是根據(jù)第i個字符的Huffman樹來進行的，不停地改變樹的結構，不需要為解壓而保存樹的有關信息。

動態(tài)Huffman壓縮算法步驟如下[8]

(1) 初始化根結點、空葉子結點；

(2) 讀入第1個字符，作為根結點的右孩子，其重量為1，空葉子結點作為根結點的左孩子，其重量為0。

(3) 讀入字符，如果是文件結尾則結束，反之判斷該字符是否出現(xiàn)在編碼樹中，如果不是進入步驟(4)，反之輸出字符編碼，以該字符結點作為當前結點。

(4) 輸出空葉子結點編碼，將該字符作為當前空葉子結點的右孩子，新空編號為當前空葉子結點編號減1，葉子結點作為當前空葉子結點的左孩子，編號為當前空葉子結點編號減2，且左右孩子的權重均為零。

(5) 判斷當前結點是否為根結點。如果是進入步驟(6)，反之進入步驟(7)。

(6) 把當前根結點到該字符結點路徑上所有結點的重量加1，重復(2)到(5)。

(7) 將當前結點與權重相同、序號最大的結點(該結點不為當前結點的父結點)進行交換(不交換序號)，并使序號最大結點的父結點成為新的當前結點，重復步驟(5)。

2.2動態(tài)Huffman解壓過程

解壓是壓縮的逆過程?？紤]下位機有限的內(nèi)存空間，如果Huffman樹以字節(jié)為單位，由于紋板數(shù)據(jù)每位的概率是隨機的，因此最大需要建立256個葉子結點的Huffman樹，而動態(tài)Huffman樹是根據(jù)輸入字節(jié)的頻度動態(tài)調(diào)整Huffman樹的，在上位機壓縮后無需傳輸編碼樹，下位機也可以解壓出來。另外在下位機中解壓出來的數(shù)據(jù)可以轉存出去，有效緩解了下位機的存儲壓力。

動態(tài)Huffman解壓算法步驟如下[9]

(1) 初始化根結點、空葉子結點；

(2) 讀入第1個字符，作為根結點的右孩子，其編碼為1，空葉子結點作為根結點的左孩子，其編碼為0。

(3) 若不是文件結尾，從壓縮文件中讀入1位二進制數(shù)，若是0，則沿左孩子搜索；若是1，則沿右孩子搜索。

(4) 判斷是否是葉子結點，如果是重復步驟(3)，反之判斷是否是空葉子結點；如果是將該葉子結點代表的字符取出存盤，反之，從壓縮文件讀入1個字符存盤。

(5) 修正Huffman樹，直至文件解壓結束。

3動態(tài)Huffman壓縮算法優(yōu)化

3.1堆排序的設計

Huffman樹構造過程常使用鏈表方式選擇排序，這種方法效率低、速度慢，本文使用堆排序，堆排序可以減小對內(nèi)存的讀取、提高系統(tǒng)的響應速度[10]，這有利于嵌入式系統(tǒng)實時控制紡織機械。

本文使用極小堆的方式排序，極小堆是一種每個結點都小于其葉子結點的完全二叉樹， 算法如下

void HuffHeapSort(DataType R[],int n){

int i;

for i=n/2 to 0

HeapAdjust(R,i,n);//調(diào)整堆算法

for i=n to 0

R[0]=R[1]; R[1]=R[i]; R[i]=R[0];//R[i]交換堆底元素

HeapAdjust(R,1,i-1);

}

堆排序比較次數(shù)和移動次數(shù)較小，對于無規(guī)則且數(shù)據(jù)流0、1交替較密集的紋板數(shù)據(jù)來說可以有效減少內(nèi)存讀取次數(shù)，緩解內(nèi)存壓力。另外堆排序的算法時間復雜度是O(nlog2n)，一般選擇排序的時間復雜度為O(knlog2n)，最壞的時間復雜度為O(n2)，所以堆排序要優(yōu)于選擇排序算法。

3.2減小誤碼率的設計

嵌入式織造系統(tǒng)對織物信息數(shù)據(jù)的傳輸精度要求高，在工業(yè)級應用中采用RS485和RS232的數(shù)據(jù)傳輸方式，保障了短距離物聯(lián)網(wǎng)空間中數(shù)據(jù)的精度，要求數(shù)據(jù)傳輸過程有較高的抗噪能力，保障數(shù)據(jù)有足夠高的正確率。

本文使用以下兩種方法減少誤碼率：

(1)在數(shù)據(jù)字符串尾部加上CRC(CyclicRedundancyCheck)校驗位[11]，CRC校驗是循環(huán)冗余校驗，相對于奇偶校驗、和校驗等其他校驗方式具有很好的糾錯能力，這種數(shù)據(jù)傳輸錯誤檢查方法經(jīng)常被用在較易受工業(yè)干擾的嵌入式控制系統(tǒng)通信上。

在上位機到下位機傳輸數(shù)據(jù)的過程中，二進制數(shù)據(jù)流易造成“0”“1”互換差錯，在嵌入式系統(tǒng)中實現(xiàn)CRC校驗方式要求算法簡單、易于實現(xiàn)。在經(jīng)過Huffman壓縮后的數(shù)據(jù)流后加上CRC校驗位，其算法流程如圖4所示。

圖4　CRC算法流程圖

經(jīng)過試驗表明，CRC循環(huán)冗余校驗會稍微增加一定的冗余度，但是能夠很好地進行差錯控制，使得數(shù)據(jù)糾錯率達97%以上。所以在嵌入式通信領域是被應用最廣泛的一種糾錯方式。

(2)如果出現(xiàn)傳輸錯誤，采用重新發(fā)送的方式解決錯誤。這是由于Huffman編碼壓縮是可變長度的編碼壓縮方式，無法從壓縮文件中恢復查找內(nèi)容，織造系統(tǒng)數(shù)據(jù)傳輸單元又是實時自動傳輸?shù)?，因此須重新發(fā)送數(shù)據(jù)。

3.3處理無效位的設計

數(shù)據(jù)被壓縮以后以數(shù)據(jù)流的形式傳輸?shù)较挛粰C，以bit位為基本單元，8bit為一個字節(jié)，以字節(jié)為單位解壓，如果以最高位開始，壓縮碼不是從字節(jié)的最高位開始，需要一定的數(shù)據(jù)結構來處理無效的位，其數(shù)據(jù)結構如下所示：

DATA_TAB

DB00000000b,10000000b,11000000b

DB11100000b,11110000b,11111000b

DB11111100b,11111110b,11111111b

Huffman每個字符與以上相應的數(shù)據(jù)進行“與”運算，用來處理無效的位。

4實驗結果

選用M058LBN型號的單片機作為下位機、PC機作為上位機進行實驗。M058LBN單片機屬于Cortex-M0系列單片機，此系列單片機因價格低廉、高性能的CPU及較高的性價比被廣泛應用在嵌入式控制系統(tǒng)中。M058LBN單片機具有4kBRAM，其空間大小完全滿足算法的需要。

實驗中選用壓縮率作為壓縮效果的標準。壓縮率為壓縮后的數(shù)據(jù)大小與原數(shù)據(jù)大小的比值，在信息論中作為衡量壓縮效果的一個重要指標，一般認為壓縮率越小越好，大于1的則稱為負壓縮。實驗結果如表1所示。

表1　實驗結果對比

由實驗結果可以看出，經(jīng)過優(yōu)化的動態(tài)Huffman壓縮算法能夠降低壓縮率，提高了壓縮效果，節(jié)省了傳輸時間；另外使用堆排序構建Huffman樹也一定程度上緩解了內(nèi)存壓力，降低了算法的時間復雜度；在算法實現(xiàn)的過程中，在數(shù)據(jù)傳輸過程中增加CRC校驗位和使用一定的數(shù)據(jù)結構處理無效的數(shù)據(jù)位，有效提高了數(shù)據(jù)傳輸精度，減小了誤碼現(xiàn)象?？傊?，經(jīng)過優(yōu)化的Huffman壓縮算法在嵌入式織造系統(tǒng)中有很高的實際應用價值。

選用.jc5格式的紋板數(shù)據(jù)，這種紋板數(shù)據(jù)在江浙一帶的織造業(yè)中比較常見。對上述4組數(shù)據(jù)進行頻譜分析，頻譜圖如圖5所示。

圖5紋板數(shù)據(jù)采樣頻譜圖

Huffman壓縮算法對于不同紋板數(shù)據(jù)的壓縮效果也會出現(xiàn)差別。由紋板數(shù)據(jù)的頻譜圖可以看出，聚集在0點頻率周圍的頻譜壓縮率低，壓縮效果相對較好，相對數(shù)據(jù)壓縮效果越好；而頻率點分散的壓縮效果比較差，如數(shù)據(jù)4.jc5。這是因為Huffman壓縮算法是基于統(tǒng)計模型的壓縮算法，數(shù)據(jù)概論統(tǒng)計的權值比較均衡的壓縮率高，壓縮效果差，反之壓縮率低。

5結束語

本文介紹了動態(tài)Huffman壓縮算法在嵌入式織造系統(tǒng)中的應用，說明了Huffman算法存在的不足，改進后的Huffman壓縮算法節(jié)省了數(shù)據(jù)傳輸時間，這對實時性要求較高的織造控制系統(tǒng)是非常有效的。 同時，經(jīng)過對織物信息數(shù)據(jù)頻譜的分析，結合嵌入式系統(tǒng)的特點，簡單易行的Huffman壓縮算法也得到了很好的應用，經(jīng)過改進后的算法可以保障解壓的順利進行，在工業(yè)級上的抗噪性能設置也具有很好的實用價值，另外經(jīng)過頻譜分析可以看出織物信息數(shù)據(jù)頻譜與壓縮率有很大的關聯(lián)性。此研究方法同樣可以運用到其他嵌入式系統(tǒng)的數(shù)據(jù)壓縮中去，具有非常高的實用價值。

參考文獻:

[1] 王海威, 倪宏, 朱明, 等. 一種嵌入式系統(tǒng)多媒體文件快速傳輸協(xié)議[J]. 小型微型計算機系統(tǒng), 2011, 2(2): 208-213.

[2]SahnounK,BenabadjiN.AhybridDPCM-DCTandRLEcodingforsatelliteimagecompression[J].IJCSITCE,2014,1(1):1-6.

[3] 王馳, 王健, 楊萌, 等. 一種新型的FPGA配置位流壓縮算法[J]. 復旦學報(自然科學版), 2014, 53(3): 365-370.

[4] 馬慶, 呂玉琴.SIP信令壓縮動態(tài)字典方案[J]. 計算機工程, 2009, 35(24):72-74.

[5]LiShujun,LiChengqing,KuoJ.OnthesecurityofasecureLempel-Ziv-Welch(LZW)algorithm[C].IEEEInternationalConferenceonMultimediaandExpo,Piscataway:IEEE, 2011:1- 5.

[6] 李焱, 張云泉. 異構平臺上性能自適應FFT框架[J]. 計算機研究與發(fā)展, 2014, 51(3): 637-649.

[7] 薩洛蒙. 數(shù)據(jù)壓縮原理與應用[M]. 2版. 吳樂南, 譯. 北京: 電子工業(yè)出版社, 2003.

[8] 張銀鈴, 武彤, 鄧少勛. 基于快速排序和Huffman樹的物化視圖增量保持算法[J]. 計算機科學, 2014, 41(6A): 451-454.

[9]LinYinkai,HuangShuchien.AfastalgorithmforHuffmandecodingbasedonarecursionHuffmantree[J].TheJournalofSystems&Software, 2012,85 (4):974-980.

[10] 趙學鋒, 楊海斌, 張貴倉. 基于堆的最小連通支配集高效近似算法[J]. 計算機工程, 2011, 37(2):54-56.

[11] 寧平.FPGA上實現(xiàn)CRC16糾錯編碼并行計算的探討[J]. 計算機工程與科學, 2014, 36 (6):1023-1027.

Dynamic Huffman Compression Algorithm Optimization Based on Fabric Information

LU Xiao-jie, YE Ming-quan, HUANG Dao-bin

(School of Computer teaching, Wannan Medical College, Wuhu, Anhui 241000, China)

Abstract:According to the insufficient memory, in order to make the host-computer and lower system more efficient data transmission, the paper improves the dynamic Huffman compression algorithm, uses the heap sort of method to construct the Huffman tree, alleviates the pressure memory of the embedded system. In order to improve the precision of data transmission, the CRC check bits is increased and invalid bits in the decompression are eliminated. Meanwhile, the frequency spectrum of fabric information data spectrum in embedded weaving system is analyzed. The experimental results show that the optimization of Huffman compression algorithm can obtain better compression effect, and the compression ratio is associated with the data frequency.

Key words:Embedded technology; FFT; data compression; Huffman compression algorithm; CRC check Bits

* 收稿日期：2015-09-24

基金項目：安徽省高校省級自然科學研究重點項目 (KJ2014A266)。

作者簡介：盧小杰，女，安徽阜陽人，碩士，皖南醫(yī)學院教師，研究方向為數(shù)據(jù)處理、嵌入式技術。E-mail:luxiaojie06@163.com

中圖分類號：TP399

文獻標識碼：A

文章編號：1007-4260(2016)02-0043-05

網(wǎng)絡出版時間：2016-06-08 12:57網(wǎng)絡出版地址：http://www.cnki.net/kcms/detail/34.1150.N.20160608.1257.012.html