尹維漢，孟令軍，龔 敬，嚴(yán) 帥

(中北大學(xué)電子測(cè)試技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室儀器科學(xué)與動(dòng)態(tài)測(cè)試教育部重點(diǎn)實(shí)驗(yàn)室，太原 山西 030051)

當(dāng)今社會(huì)，信息技術(shù)發(fā)展飛快，快速、高效的存儲(chǔ)與傳輸信息變得尤為重要，從而使得數(shù)據(jù)壓縮技術(shù)在工程上具有了很大的需求背景。數(shù)據(jù)壓縮分為無(wú)損壓縮和有損壓縮，無(wú)損壓縮指的是壓縮還原后的數(shù)據(jù)與壓縮前的數(shù)據(jù)完全相同，而有損壓縮壓縮還原后的數(shù)據(jù)與壓縮前的數(shù)據(jù)相比存在一定的偏差。無(wú)損壓縮主要應(yīng)用于對(duì)數(shù)據(jù)要求很高，不允許數(shù)據(jù)失真的場(chǎng)合，如文本數(shù)據(jù)、程序和特殊應(yīng)用場(chǎng)合的圖像數(shù)據(jù)(指紋圖像、醫(yī)學(xué)圖像等)的壓縮。有損壓縮廣泛應(yīng)用于語(yǔ)音、圖像和視頻數(shù)據(jù)的壓縮[1－3]。本文主要研究了一種基于LZW算法的無(wú)損壓縮FPGA實(shí)現(xiàn)方法[4－5]，利用該方法設(shè)計(jì)的數(shù)據(jù)壓縮系統(tǒng)壓縮速度高達(dá)66.67 ～246.15 Mbit/s。

1 高速無(wú)損壓縮方法的過程描述

LZW無(wú)損壓縮算法的實(shí)現(xiàn)通常采用計(jì)算機(jī)軟件的方法[6]，而軟件方法一般存在著壓縮速度慢、占用資源多等缺點(diǎn)，而采用硬件實(shí)現(xiàn)的LZW無(wú)損壓縮可以很好地克服這些缺點(diǎn)，并能夠?qū)崿F(xiàn)對(duì)數(shù)據(jù)流的實(shí)時(shí)、高效及自適應(yīng)壓縮。本文主要研究了一種無(wú)損壓縮的FPGA實(shí)現(xiàn)方法，該方法基于LZW算法的改進(jìn)算法。改進(jìn)后的LZW算法使用分級(jí)字典體系[7]，以充分利用FPGA的并行處理[8]能力來(lái)實(shí)現(xiàn)高速無(wú)損壓縮。這種分級(jí)字典體系由字寬度不同的多個(gè)并行字典組成，不同字典間的字寬度連續(xù)遞增，每個(gè)字典的地址空間為分級(jí)字典體系地址空間中的一段。修改后的算法實(shí)現(xiàn)過程描述如下:

假設(shè)分級(jí)字典體系中字典個(gè)數(shù)為n，字典DICT0字寬度為1個(gè)字符，字典DICT(n－1)字寬度為n個(gè)字符，其中n=2，3，…;數(shù)據(jù)緩存區(qū)長(zhǎng)度為n個(gè)字符;字典DICT0的地址空間為0 ～ADDR0，ADDR0=256;字典DICT1的地址空間為ADDR0～ADDR1;字典DICT(n－1)的地址空間為ADDR(n－2)～ADDR(n－1);則分級(jí)字典體系的地址空間為0～ADDR(n－1)。

1.1 壓縮過程描述

壓縮過程步驟:

1)字典(字符串表)初始化，i=0。

2)如果有數(shù)據(jù)流輸入，從輸入數(shù)據(jù)流中讀取1個(gè)字符填寫到數(shù)據(jù)緩存區(qū)C(i)中，i加1;如已沒有數(shù)據(jù)流輸入，緩存區(qū)中字符數(shù)為j(j＜n)，執(zhí)行步驟4)中的(2)。

3)如果緩存區(qū)中字符數(shù)為n，執(zhí)行步驟4)中的(1);如果緩存區(qū)中字符數(shù)小于n，執(zhí)行步驟2)。

4)(1)將數(shù)據(jù)緩存區(qū)中n個(gè)字符所組成字符串{C0 C1 C2…C(n－1)}、{C0 C1 C2…C(n－2)}…{C0 C1}同時(shí)與字典DICT(n－1)、DICT(n－2)…DICT1中已經(jīng)存儲(chǔ)的字符串進(jìn)行比較即查字典。

①如果在字典DICT(n－1)中查找到對(duì)應(yīng)的字符串，則將該字符串對(duì)應(yīng)的匹配地址(索引號(hào))DICT_MATCHAED_ADDR(n－1)輸出到壓縮數(shù)據(jù)流中。數(shù)據(jù)緩存區(qū)清空，i=0，執(zhí)行步驟2)。

②如果在字典DICT(n－1)…DICT(n－m)(m=1，2，3，…，n－1)中沒有查找到對(duì)應(yīng)的字符串，而在字典DICT(n－m－1)中查找到對(duì)應(yīng)的字符串，則將該字符串對(duì)應(yīng)的匹配地址DICT_MATCHAED_ADDR(n－m－1)輸出到編碼數(shù)據(jù)流中。同時(shí)將字符串{C0…C(n－m)}寫入到字典DICT(n－m)的寫入地址DICT_ADDR(n－m)處，字典DICT(n－m)寫入地址DICT_ADDR(n－m)加1。數(shù)據(jù)緩存區(qū)中C0=C(n－m)、C1=C(n－m+1)…C(m －2)=C(n－2)、C(m －1)=C(n－1)，i=m，執(zhí)行步驟2)。

(2)如果j=0，壓縮結(jié)束;如果j≠0(j＜n)，將數(shù)據(jù)緩存區(qū)中j個(gè)字符所組成字符串{C0 C1 C2…C(j－1)}、{C0 C1 C2…C(j－2)}…{C0 C1}同時(shí)與字典 DICT(j－1)、DICT(j－2)…DICT1中已經(jīng)存儲(chǔ)的字符串進(jìn)行比較即查字典。

①如果在字典DICT(j－1)中查找到對(duì)應(yīng)的字符串，則將該字符串對(duì)應(yīng)的匹配地址DICT_MATCHAED_ADDR(n－1)輸出到編碼數(shù)據(jù)流中，j=0，壓縮結(jié)束。

②如果在字典 DICT(j－1)…DICT(j－ m)(m=1，2，3，…，j－1)中沒有查找到對(duì)應(yīng)的字符串，而在字典DICT(j－m－1)中查找到字符串，則將該字符串對(duì)應(yīng)的匹配地址DICT_MATCHAED_ADDR(j－m－1)輸出到編碼數(shù)據(jù)流中。同時(shí)將字符串{C0…C(j－m)}寫入到字典DICT(j－m)的寫入地址DICT_ADDR(j－m)處，字典DICT(jm)寫入地址DICT_ADDR(j－m)加1。數(shù)據(jù)緩存區(qū)中C0=C(j－m)、C1=C(j－m+1)…C(m －2)=C(j－2)、C(m －1)=C(j－1)，j=m。

③如果j＞1，執(zhí)行步驟4)中(2);如果 j=1，將字符C0對(duì)應(yīng)于DICT0的匹配地址輸出到編碼數(shù)據(jù)流中，壓縮結(jié)束。

1.2 解壓縮過程描述

解壓縮過程步驟:

1)字典初始化。

2)從編碼數(shù)據(jù)中讀取一個(gè)編碼值到OLD_CODE。

3)將字典DICT(n－1)或字典DICT(n－2)…DICT0中對(duì)應(yīng)于地址OLD_CODE處所存儲(chǔ)的字符或者字符串{OLDC0…OLDC(i－1)}(i=1，2，3，…，n)輸出。

4)如果還有編碼數(shù)據(jù)輸入，讀入一編碼值到NEW_CODE;如果已沒有編碼數(shù)據(jù)輸入，解壓結(jié)束。

5)(1)如果NEW_CODE的值小于字典寫入地址DICT_ADDR0的值，得DICT0中對(duì)應(yīng)于字典地址NEW_CODE的字符C0。

如果NEW_CODE的值大于字典地址ADDR(j－1)的值，且小于字典寫入地址DICT_ADDR(j)的值，其中0＜j＜n，得DICT(j)中對(duì)應(yīng)于字典地址NEW_CODE的字符串{C0…C(j)}。

將字符串{OLDC0…OLDC(i－1)}和字符C0或字符串{C0…C(j)}中第1個(gè)字符 C 0組成新字符串{OLDC0…OLDC(i－1)C0}。如果 i＜ n，將字符串{OLDC0…OLDC(i－1)C0}添加到字典DICT(i)寫入地址DICT_ADDR(i)處，字典 DICT(i)寫入地址DICT_ADDR(i)加1;如果i=n，不處理。

(2)如果NEW_CODE不滿足步驟5)(1)中的條件，將字符或字符串{OLDC0…OLDC(i－1)}加上該字符串中第1個(gè)字符OLDC0組成新字符串{OLDC0…OLDC(i－1)OLDC0}(i＜n)，將字符串{OLDC0…OLDC(i－1)OLDC0}添加到字典DICT(i)寫入地址DICT_ADDR(i)處，字典DICT(i)寫入地址DICT_ADDR(i)加1，這樣字典地址NEW_CODE對(duì)應(yīng)的字符串為{OLDC0…OLDC(i－1)OLDC0}。

6)將NEW_CODE的值賦給OLD_CODE，執(zhí)行步驟3)。

1.3 壓縮及解壓縮實(shí)例

以上對(duì)算法進(jìn)行了詳細(xì)描述，為了更好地表達(dá)算法的實(shí)現(xiàn)過程，以下給出了一個(gè)壓縮及解壓縮實(shí)例。在該實(shí)例中，輸入為字符數(shù)據(jù)流“/WED/WE/WEE/WEB/WE”，分級(jí)字典體系中字典個(gè)數(shù)為4，字典 DICT0，DICT1，DICT2，DICT3 的字寬度分別為1，2，3，4 個(gè)字符，字典地址分別為0～255，256～511，512～767，768～1023。表1給出了壓縮實(shí)現(xiàn)的過程，表2給出了壓縮過程中所使用的分級(jí)字典體系結(jié)構(gòu)。

解壓縮過程中使用的分級(jí)字典體系與壓縮時(shí)完全相同。表3給出了解壓縮的實(shí)現(xiàn)過程，字典重構(gòu)如表2所示。

2 硬件實(shí)現(xiàn)的體系結(jié)構(gòu)

采用上文所描述的算法，筆者設(shè)計(jì)了基于FPGA的高速無(wú)損壓縮系統(tǒng)，原理如圖1所示。

表1 壓縮過程描述

表2 分級(jí)字典體系結(jié)構(gòu)

表3 解壓縮過程描述

圖1 硬件系統(tǒng)原理框圖

該系統(tǒng)主要由算法控制模塊、分級(jí)字典、數(shù)據(jù)輸入FiFo及數(shù)據(jù)緩存區(qū)等組成，系統(tǒng)時(shí)鐘為50 MHz。其中算法控制器為整個(gè)系統(tǒng)的核心部分，協(xié)調(diào)控制系統(tǒng)其余各個(gè)模塊共同完成算法的計(jì)算流程。分級(jí)字典是系統(tǒng)的關(guān)鍵組成部分，用于存儲(chǔ)無(wú)損壓縮過程中產(chǎn)生的中間數(shù)據(jù)。數(shù)據(jù)緩存區(qū)完成對(duì)輸入字符數(shù)據(jù)流8字符緩存，從而實(shí)現(xiàn)并行查找字典的功能。FiFo模塊用于協(xié)調(diào)輸入數(shù)據(jù)流與無(wú)損壓縮之間的速度差。系統(tǒng)中字典更新采用先進(jìn)先出策略，即一個(gè)字典填寫滿后將從該字典低地址處開始覆蓋寫人，而不清除字典高地址處已寫入內(nèi)容;分級(jí)字典由8個(gè)字典組成，其中字典0字寬為1個(gè)字符，由256個(gè)字符組成，占用地址空間為0～256，不需要在硬件中實(shí)際構(gòu)建，其余7 個(gè)字典字寬分別為2，3，4，5，6，7，8 個(gè)字符，占用的地址空間長(zhǎng)度分別為 256，128，128，64，64，64，64，在硬件系統(tǒng)中需要實(shí)際構(gòu)建。

圖2為作者在FPGA上設(shè)計(jì)的高速無(wú)損壓縮系統(tǒng)在測(cè)試時(shí)獲取的一張SignalTap波形圖，其中clk為系統(tǒng)時(shí)鐘輸入管腳，reset為系統(tǒng)復(fù)位輸入管腳，wrreq，wrclk，data[7..0]分別為數(shù)據(jù)流輸入請(qǐng)求信號(hào)、輸入數(shù)據(jù)同步時(shí)鐘、輸入數(shù)據(jù)流管腳，dataend為壓縮結(jié)束信號(hào)輸入管腳;wrfull為 FiFo 滿信號(hào)輸出管腳，encodedata[0..9]，codeclk分別為編碼數(shù)據(jù)流輸出、編碼數(shù)據(jù)流同步時(shí)鐘管腳。

圖2 SignalTap波形圖(截圖)

對(duì)系統(tǒng)的實(shí)際測(cè)試表明，當(dāng)系統(tǒng)時(shí)鐘為50 MHz時(shí)，壓縮速度可達(dá)8 bit× 8=246.15 Mbit/s，平均壓縮比約為55%。

3 結(jié)語(yǔ)

本文首先闡明了硬件實(shí)現(xiàn)基于LZW算法的高速無(wú)損壓縮基本原理，分別對(duì)壓縮過程與解壓縮過程進(jìn)行了詳細(xì)描述，并給出了壓縮與解壓縮實(shí)例。根據(jù)這些基本原理在FPGA上設(shè)計(jì)了高速無(wú)損壓縮系統(tǒng)并進(jìn)行了實(shí)際測(cè)試。測(cè)試結(jié)果表明，系統(tǒng)壓縮速度快，壓縮比高，達(dá)到了預(yù)期設(shè)計(jì)目標(biāo)。

利用該高速無(wú)損壓縮FPGA實(shí)現(xiàn)方法所設(shè)計(jì)的無(wú)損壓縮系統(tǒng)，可極大地提高數(shù)據(jù)壓縮速度，減少數(shù)據(jù)的存儲(chǔ)空間。同時(shí)，在數(shù)據(jù)傳輸領(lǐng)域，該系統(tǒng)能夠?qū)⒏咚傩盘?hào)轉(zhuǎn)換為緩變信號(hào)進(jìn)行傳輸，從而降低通信的信道占用費(fèi)用，提高數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

[1]李錦明，張文棟，毛海央，等.實(shí)時(shí)無(wú)損數(shù)據(jù)壓縮算法硬件實(shí)現(xiàn)的研究[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2006，38(2):315－317.

[2]王偉，劉文怡，秦麗，等.遙測(cè)數(shù)據(jù)實(shí)時(shí)壓縮技術(shù)的設(shè)計(jì)與實(shí)現(xiàn)[J].儀器儀表學(xué)報(bào)，2006，27(6):2467－2469.

[3]王文延，趙中華，朱磊.一種JPEG無(wú)損壓縮專利算法的改進(jìn)與實(shí)現(xiàn)[J].電視技術(shù)，2010，34(5):26－29.

[4]AKIL M，PERROTON L，GRANDPIERRE T.FPGA－based architecture for hardware compression/decompression of wide format images[J].Journal of Real－Time Image Processing，2006，1(2):163－170.

[5]古海云，李麗，許居衍，等.一種Virtex系列FPGA配置數(shù)據(jù)無(wú)損壓縮算法[J].計(jì)算機(jī)研究與發(fā)展，2006，43(5):940－945.

[6]AGNEW G B，SIVANANDAN A.A fast method for determining the origins of documents based on LZW compression[J].International Journal on Digital Libraries，2000，3(4):297－301.

[7]LIN M B.A hardware architecture for the lzw compression and decompression algorithms based on parallel dictionaries[J].The Journal of VLSI Signal Processing，2000，26(3):369－381.

[8]應(yīng)駿，李莉.MPEG－4解碼的并行處理優(yōu)化[J].電視技術(shù)，2007，31(8):29－31.