盧小杰，葉明全，黃道斌

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

?

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

盧小杰，葉明全，黃道斌

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

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

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

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

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

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

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

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

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

圖2　某條織物紋板圖

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

圖3紋板圖和紋板矩陣

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

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

(1)

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

Fn=(n-1)F/N

(2)

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

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

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

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

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

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

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

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

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

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

(1) 初始化根結(jié)點(diǎn)、空葉子結(jié)點(diǎn)；

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

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

(4) 輸出空葉子結(jié)點(diǎn)編碼，將該字符作為當(dāng)前空葉子結(jié)點(diǎn)的右孩子，新空編號(hào)為當(dāng)前空葉子結(jié)點(diǎn)編號(hào)減1，葉子結(jié)點(diǎn)作為當(dāng)前空葉子結(jié)點(diǎn)的左孩子，編號(hào)為當(dāng)前空葉子結(jié)點(diǎn)編號(hào)減2，且左右孩子的權(quán)重均為零。

(5) 判斷當(dāng)前結(jié)點(diǎn)是否為根結(jié)點(diǎn)。如果是進(jìn)入步驟(6)，反之進(jìn)入步驟(7)。

(6) 把當(dāng)前根結(jié)點(diǎn)到該字符結(jié)點(diǎn)路徑上所有結(jié)點(diǎn)的重量加1，重復(fù)(2)到(5)。

(7) 將當(dāng)前結(jié)點(diǎn)與權(quán)重相同、序號(hào)最大的結(jié)點(diǎn)(該結(jié)點(diǎn)不為當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn))進(jìn)行交換(不交換序號(hào))，并使序號(hào)最大結(jié)點(diǎn)的父結(jié)點(diǎn)成為新的當(dāng)前結(jié)點(diǎn)，重復(fù)步驟(5)。

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

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

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

(1) 初始化根結(jié)點(diǎn)、空葉子結(jié)點(diǎn)；

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

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

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

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

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

3.1堆排序的設(shè)計(jì)

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

本文使用極小堆的方式排序，極小堆是一種每個(gè)結(jié)點(diǎn)都小于其葉子結(jié)點(diǎn)的完全二叉樹， 算法如下

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

3.2減小誤碼率的設(shè)計(jì)

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

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

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

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

圖4　CRC算法流程圖

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

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

3.3處理無效位的設(shè)計(jì)

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

DATA_TAB

DB00000000b,10000000b,11000000b

DB11100000b,11110000b,11111000b

DB11111100b,11111110b,11111111b

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

4實(shí)驗(yàn)結(jié)果

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

實(shí)驗(yàn)中選用壓縮率作為壓縮效果的標(biāo)準(zhǔn)。壓縮率為壓縮后的數(shù)據(jù)大小與原數(shù)據(jù)大小的比值，在信息論中作為衡量壓縮效果的一個(gè)重要指標(biāo)，一般認(rèn)為壓縮率越小越好，大于1的則稱為負(fù)壓縮。實(shí)驗(yàn)結(jié)果如表1所示。

表1　實(shí)驗(yàn)結(jié)果對(duì)比

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

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

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

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

5結(jié)束語

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

參考文獻(xiàn):

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

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

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

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

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

[6] 李焱, 張?jiān)迫? 異構(gòu)平臺(tái)上性能自適應(yīng)FFT框架[J]. 計(jì)算機(jī)研究與發(fā)展, 2014, 51(3): 637-649.

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

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

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

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

[11] 寧平.FPGA上實(shí)現(xiàn)CRC16糾錯(cuò)編碼并行計(jì)算的探討[J]. 計(jì)算機(jī)工程與科學(xué), 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

基金項(xiàng)目：安徽省高校省級(jí)自然科學(xué)研究重點(diǎn)項(xiàng)目 (KJ2014A266)。

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

中圖分類號(hào)：TP399

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

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

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