高速無損壓縮的FPGA實現(xiàn)方法研究

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

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

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

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

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

假設分級字典體系中字典個數(shù)為n，字典DICT0字寬度為1個字符，字典DICT(n－1)字寬度為n個字符，其中n=2，3，…;數(shù)據(jù)緩存區(qū)長度為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)如果有數(shù)據(jù)流輸入，從輸入數(shù)據(jù)流中讀取1個字符填寫到數(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個字符所組成字符串{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)輸出到壓縮數(shù)據(jù)流中。數(shù)據(jù)緩存區(qū)清空，i=0，執(zhí)行步驟2)。

②如果在字典DICT(n－1)…DICT(n－m)(m=1，2，3，…，n－1)中沒有查找到對應的字符串，而在字典DICT(n－m－1)中查找到對應的字符串，則將該字符串對應的匹配地址DICT_MATCHAED_ADDR(n－m－1)輸出到編碼數(shù)據(jù)流中。同時將字符串{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，壓縮結束;如果j≠0(j＜n)，將數(shù)據(jù)緩存區(qū)中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)輸出到編碼數(shù)據(jù)流中，j=0，壓縮結束。

②如果在字典 DICT(j－1)…DICT(j－ m)(m=1，2，3，…，j－1)中沒有查找到對應的字符串，而在字典DICT(j－m－1)中查找到字符串，則將該字符串對應的匹配地址DICT_MATCHAED_ADDR(j－m－1)輸出到編碼數(shù)據(jù)流中。同時將字符串{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對應于DICT0的匹配地址輸出到編碼數(shù)據(jù)流中，壓縮結束。

1.2 解壓縮過程描述

解壓縮過程步驟:

1)字典初始化。

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

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

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

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，執(zhí)行步驟3)。

1.3 壓縮及解壓縮實例

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

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

2 硬件實現(xiàn)的體系結構

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

表1 壓縮過程描述

表2 分級字典體系結構

表3 解壓縮過程描述

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

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

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

圖2 SignalTap波形圖(截圖)

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

3 結語

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

利用該高速無損壓縮FPGA實現(xiàn)方法所設計的無損壓縮系統(tǒng)，可極大地提高數(shù)據(jù)壓縮速度，減少數(shù)據(jù)的存儲空間。同時，在數(shù)據(jù)傳輸領域，該系統(tǒng)能夠將高速信號轉換為緩變信號進行傳輸，從而降低通信的信道占用費用，提高數(shù)據(jù)傳輸?shù)目煽啃浴?/p>

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

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

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