高速無損壓縮的FPGA實現方法研究

尹維漢，孟令軍，龔 敬，嚴 帥

(中北大學電子測試技術國家重點實驗室儀器科學與動態測試教育部重點實驗室，太原 山西 030051)

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

1 高速無損壓縮方法的過程描述

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

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

1.1 壓縮過程描述

壓縮過程步驟:

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

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

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

4)(1)將數據緩存區中n個字符所組成字符串{C0 C1 C2…C(n－1)}、{C0 C1 C2…C(n－2)}…{C0 C1}同時與字典DICT(n－1)、DICT(n－2)…DICT1中已經存儲的字符串進行比較即查字典。

①如果在字典DICT(n－1)中查找到對應的字符串，則將該字符串對應的匹配地址(索引號)DICT_MATCHAED_ADDR(n－1)輸出到壓縮數據流中。數據緩存區清空，i=0，執行步驟2)。

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

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

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

②如果在字典 DICT(j－1)…DICT(j－ m)(m=1，2，3，…，j－1)中沒有查找到對應的字符串，而在字典DICT(j－m－1)中查找到字符串，則將該字符串對應的匹配地址DICT_MATCHAED_ADDR(j－m－1)輸出到編碼數據流中。同時將字符串{C0…C(j－m)}寫入到字典DICT(j－m)的寫入地址DICT_ADDR(j－m)處，字典DICT(jm)寫入地址DICT_ADDR(j－m)加1。數據緩存區中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，執行步驟4)中(2);如果 j=1，將字符C0對應于DICT0的匹配地址輸出到編碼數據流中，壓縮結束。

1.2 解壓縮過程描述

解壓縮過程步驟:

1)字典初始化。

2)從編碼數據中讀取一個編碼值到OLD_CODE。

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

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

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

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

將字符串{OLDC0…OLDC(i－1)}和字符C0或字符串{C0…C(j)}中第1個字符 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個字符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對應的字符串為{OLDC0…OLDC(i－1)OLDC0}。

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

1.3 壓縮及解壓縮實例

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

解壓縮過程中使用的分級字典體系與壓縮時完全相同。表3給出了解壓縮的實現過程，字典重構如表2所示。

2 硬件實現的體系結構

采用上文所描述的算法，筆者設計了基于FPGA的高速無損壓縮系統，原理如圖1所示。

表1 壓縮過程描述

表2 分級字典體系結構

表3 解壓縮過程描述

圖1 硬件系統原理框圖

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

圖2為作者在FPGA上設計的高速無損壓縮系統在測試時獲取的一張SignalTap波形圖，其中clk為系統時鐘輸入管腳，reset為系統復位輸入管腳，wrreq，wrclk，data[7..0]分別為數據流輸入請求信號、輸入數據同步時鐘、輸入數據流管腳，dataend為壓縮結束信號輸入管腳;wrfull為 FiFo 滿信號輸出管腳，encodedata[0..9]，codeclk分別為編碼數據流輸出、編碼數據流同步時鐘管腳。

圖2 SignalTap波形圖(截圖)

對系統的實際測試表明，當系統時鐘為50 MHz時，壓縮速度可達8 bit× 8=246.15 Mbit/s，平均壓縮比約為55%。

3 結語

本文首先闡明了硬件實現基于LZW算法的高速無損壓縮基本原理，分別對壓縮過程與解壓縮過程進行了詳細描述，并給出了壓縮與解壓縮實例。根據這些基本原理在FPGA上設計了高速無損壓縮系統并進行了實際測試。測試結果表明，系統壓縮速度快，壓縮比高，達到了預期設計目標。

利用該高速無損壓縮FPGA實現方法所設計的無損壓縮系統，可極大地提高數據壓縮速度，減少數據的存儲空間。同時，在數據傳輸領域，該系統能夠將高速信號轉換為緩變信號進行傳輸，從而降低通信的信道占用費用，提高數據傳輸的可靠性。

[1]李錦明，張文棟，毛海央，等.實時無損數據壓縮算法硬件實現的研究[J].哈爾濱工業大學學報，2006，38(2):315－317.

[2]王偉，劉文怡，秦麗，等.遙測數據實時壓縮技術的設計與實現[J].儀器儀表學報，2006，27(6):2467－2469.

[3]王文延，趙中華，朱磊.一種JPEG無損壓縮專利算法的改進與實現[J].電視技術，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配置數據無損壓縮算法[J].計算機研究與發展，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]應駿，李莉.MPEG－4解碼的并行處理優化[J].電視技術，2007，31(8):29－31.