5/3小波提升結(jié)構(gòu)的深度流水線優(yōu)化

摘 要:為了滿足基于小波變換的高速信號實時處理的需求，在FPGA上實現(xiàn)更高速的5/3小波變換。采用靜態(tài)時序分析的方法分析了當前5/3小波變換結(jié)構(gòu)中影響速度的主要因素，并采用深度流水線技術(shù)切斷原結(jié)構(gòu)中存在的較長組合邏輯路徑，從而提高了最高工作頻率。使設(shè)計中僅增加少量寄存器開銷便可獲得原結(jié)構(gòu)250%的速度，最高可實現(xiàn)每秒300M樣本的數(shù)據(jù)吞吐量，可用于設(shè)計基于小波變換和FPGA的高速信號處理系統(tǒng)。

關(guān)鍵詞:5/3小波; 提升結(jié)構(gòu); 靜態(tài)時序分析; 流水線技術(shù); 現(xiàn)場可編程門陣列

中圖分類號:TP391141文獻標志碼:A

文章編號:1001-3695(2010)03-0975-02

doi:10.3969/j.issn.10013695.2010.03.045

Deeppipeline optimization for lifting architecture of 5/3 DWT

XU Yong1， 2， XU Zhi-yong1， ZHANG Qi-heng1

(1.Institute of Optics Electronics， Chinese Academy of Sciences， Chengdu 610209， China; 2.Graduate School， Chinese Academy of Sciences， Beijing 100039， China)

Abstract:To realize higher speed 5/3 discrete wavelet transform (DWT) for the demands of realtime high speed signals processing based on DWT. This paper studied speed limit factors in current 5/3 DWT architecture by using static timing analysis， then redesigned the current architecture with pipeline technique to break through the overlong strict path. Experiment results indicate that at the price of increasing a few cost of registers， proposed 5/3 DWT architecture’s maximum frequencies are speed up to 250% of original architecture， and can achieve a maximum speed of 300 MSPS(million samples per second). This architecture can be used in high performance waveletbased signal processing applications on FPGA.

Key words:5/3 DWT; lifting architecture; static timing analysis; pipeline technique; FPGA



小波變換是現(xiàn)代數(shù)字信號處理的一個重要分析工具。它具有獨特的時頻分析特性，在獲得各尺度的頻率信息的同時仍能保留空間的位置信息，因此被廣泛應(yīng)用于信號檢測分析、去噪、融合、壓縮等應(yīng)用。目前，小波變換的主要實現(xiàn)方法是基于提升結(jié)構(gòu)[1]實現(xiàn)小波變換，相比于基于濾波器的Mallat實現(xiàn)算法而言，用提升結(jié)構(gòu)實現(xiàn)小波變換的計算量減少了一半，并具有原位計算、節(jié)約存儲空間的特點。在硬件實現(xiàn)方面，Tan等人[2]于2001年提出的內(nèi)嵌擴展(embedded extension)提升算法很好地解決了信號邊界擴展的問題，其后多位研究者相繼提出了多種基于該算法的硬件實現(xiàn)的提升結(jié)構(gòu)設(shè)計[3~5]，這些基于FPGA或VLSI實現(xiàn)的小波變換能達到較高的速度。然而隨著信號采樣分辨率和采樣速度的提高，實際工程中仍需要具有更高變換速度的小波變換結(jié)構(gòu)。在相同的硬件并行度下，提高計算結(jié)構(gòu)的處理能力只有通過提高其工作頻率實現(xiàn)。為此，本文通過對當前基于FPGA實現(xiàn)的5/3小波提升結(jié)構(gòu)進行靜態(tài)時序分析，找出其中影響速度的關(guān)鍵因素，并采用流水線設(shè)計的方法對其進行改進，充分切斷了原結(jié)構(gòu)中存在的多條過長關(guān)鍵路徑，減小了寄存器到寄存器的路徑延時，提高了小波變換的工作頻率。試驗結(jié)果表明，在FPGA中采用本文設(shè)計的基于流水線優(yōu)化的提升結(jié)構(gòu)實現(xiàn)小波變換，僅增加七組寄存器的開銷，便可以獲得現(xiàn)有結(jié)構(gòu)250%的小波變換速度，可以滿足工程應(yīng)用中實時實現(xiàn)基于小波的高速信號處理的需求。

1 小波變換及提升結(jié)構(gòu)

以Daubechies等人研究提出的多相位矩陣因子分解定理為基礎(chǔ)，Swedens[1]在1996年提出了小波提升算法，提升算法與傳統(tǒng)的Mallat實現(xiàn)算法相比，運算量減少了一半，能夠?qū)崿F(xiàn)小波變換的原位計算。采用該結(jié)構(gòu)實現(xiàn)小波變換，可以很容易地進行邊界擴展[2]，而且比較適于基于FPGA的實現(xiàn)。通過提升結(jié)構(gòu)實現(xiàn)小波變換的通用結(jié)構(gòu)[6]如圖1所示。該結(jié)構(gòu)由若干預(yù)測和更新操作串聯(lián)組成，適于通過FPGA或VLSI等硬件來實現(xiàn)高速的小波變換。

5/3小波是一種雙正交小波變換，可以實現(xiàn)整數(shù)到整數(shù)的變換及逆變換，它具有良好的能量聚集效應(yīng)、時—頻分析特性及可逆性，因此5/3小波變換常常被用于信號的時頻分析及無損壓縮應(yīng)用。實現(xiàn)5/3小波變換時，僅需一次預(yù)測及更新過程，其預(yù)測和更新公式如式(1)(2)[3]所示。其中:xextent為原始信號x(n)的邊界擴展信號，一般采用邊界對稱擴展模式;算符*」表示對*取下整數(shù)。

y(2n+1)=xextent(2n+1)-[xextent(2n)+xextent(2n+2)]/2」(1)

y(2n)=xextent(2n)+[y(2n-1)+y(2n+1)+2]/4」(2)

為了實現(xiàn)快速的5/3小波變換以滿足工程中的實時小波變換需求，在內(nèi)嵌擴展提升算法[2]的基礎(chǔ)上，當前研究提出了基于FPGA實現(xiàn)的5/3小波變換結(jié)構(gòu)[3](圖2)。

該結(jié)構(gòu)具有設(shè)計簡潔、易于實現(xiàn)和占用資源較少的特點?；赬ilinx公司的Spartan3(-4)器件實現(xiàn)時可達到47.5 M的數(shù)據(jù)吞吐率，可以滿足大部分應(yīng)用的速度要求。然而，隨著信號采樣速率和信號處理速度要求的提高，該結(jié)構(gòu)就無法滿足更高速信號的處理要求。例如，對于高速高分辨率圖像，如果需要實時實現(xiàn)基于小波的去噪或壓縮時，就需要更高速的小波變換結(jié)構(gòu)來支持。

為此，本文研究了如何提高目前小波變換結(jié)構(gòu)的速度以滿足某高速高分辨率圖像壓縮課題中對高速小波變換的需求。本文以下部分采用靜態(tài)時序分析方法討論了當前小波變換結(jié)構(gòu)中的速度制約因素，并針對性地采用流水線技術(shù)對當前結(jié)構(gòu)進行優(yōu)化。實驗表明，經(jīng)流水線優(yōu)化過的提升結(jié)構(gòu)達到了更高的工作頻率，可以滿足工程中為實現(xiàn)高速信號處理而提出的高速小波變換的要求。

2 利用流水線技術(shù)優(yōu)化小波提升結(jié)構(gòu)

在一個遵循同步設(shè)計準則的時序電路系統(tǒng)中，系統(tǒng)的穩(wěn)定最高工作頻率fmax取決于其關(guān)鍵路徑的延時。時序電路中關(guān)鍵路徑指的是一個設(shè)計中任意兩個寄存器間邏輯延時和走線延時總和的最大值。如圖3所示，寄存器R1到R2之間通過一個組合邏輯電路(CL)，為了使R2在時鐘上升沿到來時寄存到正確數(shù)據(jù)，那么該電路的最高穩(wěn)定工作頻率對應(yīng)的時鐘周期Tmin必須大于該段路徑延時，表述如式(3)，且最高工作頻率fmax為Tmin的倒數(shù)，如式(4)所示。

Tmin≥(Tcko_1+TCL+Tnet+Tsetup_2-Tclk_skew)(3)

fmax=1Tmin(4)

其中:式(3)中Tcko_1為寄存器R1的時鐘到輸出延時;TCL為組合邏輯延時;Tnet為線延時;Tsetup_2為R2的數(shù)據(jù)建立時間;Tclk_skew為時鐘扭曲，指兩個寄存器的觸發(fā)時鐘上升沿相差時間。也就是說，在一個包含若干寄存器到寄存器路徑的時序電路中，擁有最長路徑延時的路徑就稱為關(guān)鍵路徑，電路的最小時鐘周期必須大于關(guān)鍵路徑的延時。這是因為在t0時刻，clk_1的上升沿到來后，R1的輸出在Tcko_1后穩(wěn)定，經(jīng)過TCL+Tnet后到達R2的輸入端，再經(jīng)過Tsetup_2后建立，必須在這之后R2的上升沿才能到來，才能使得數(shù)據(jù)正確，因此要提高系統(tǒng)工作頻率必須減小其中關(guān)鍵路徑的延時。

采用靜態(tài)時序分析方法對圖2中的傳統(tǒng)5/3提升小波實現(xiàn)結(jié)構(gòu)進行分析，可以分析出其中存在一條較長的關(guān)鍵路徑。在圖2中，以source為起點，沿著虛線所標記路徑經(jīng)過四個加法器、兩個移位除法器、兩個選通器才到達終點destination。正是由于這條路徑中組合邏輯的邏輯深度過長，導(dǎo)致圖2中的提升結(jié)構(gòu)難以達到很高的工作頻率。為此，本文依據(jù)流水線設(shè)計中切分前向割集的原則[7]，按圖2中所示的三條點畫線將原結(jié)構(gòu)切分為幾個前向割集，并在與分割線相交的線路上加入寄存器，得到如圖4所示的基于流水線設(shè)計的小波提升結(jié)構(gòu)。另外，為了保證電路正確工作，需要按照控制信號與數(shù)據(jù)信號延時對齊的原則調(diào)整控制信號的延時。

圖2中，前向割集劃分線(點畫線)和電路中數(shù)據(jù)通路的交點共10個，因此如果加入三級流水線，需要插入10個寄存器組，但在采用邏輯復(fù)用等手段精簡電路后，僅需要在邏輯路徑中插入圖4中陰影標記的七組寄存器。對圖4中優(yōu)化過的結(jié)構(gòu)進行靜態(tài)時序分析可以看出，原結(jié)構(gòu)中的幾條較長組合邏輯路徑已經(jīng)被充分切斷，此時最長的路徑上僅有一個加法器和一個選通器。由于組合邏輯深度的變淺，減小了組合電路的邏輯延時及布線延時。那么，式(3)中的關(guān)鍵路徑延時也減小。因此，理論上來說，使用流水線技術(shù)優(yōu)化后結(jié)構(gòu)的最高工作頻率fmax就應(yīng)該得到大幅提升，在基于FPGA實現(xiàn)的實驗及具體工程應(yīng)用中，這點得到了很好的驗證。

3 實現(xiàn)結(jié)果

為了測試在工程實現(xiàn)時本文設(shè)計的經(jīng)流水線優(yōu)化過的小波變換結(jié)構(gòu)可以得到多大程度的速度提升，實驗在Xilinx公司的ISE8.2開發(fā)環(huán)境下采用VHDL語言描述了全流水線設(shè)計的5/3小波提升結(jié)構(gòu)(圖4)和原提升結(jié)構(gòu)(圖2)。該結(jié)構(gòu)采用模塊化設(shè)計，便于層次化設(shè)計。它可以用于實現(xiàn)不同長度數(shù)據(jù)的5/3小波變換。其模塊接口如圖5所示。輸入包括:data_length指明了輸入數(shù)據(jù)長度，data_in為輸入數(shù)據(jù)，reset信號。輸出包括:L_out，H_out為低頻高頻分量輸出，out_valid標志輸出有效。圖6為該結(jié)構(gòu)對一組長度為16的數(shù)據(jù)變換得到的數(shù)據(jù)，證明了該結(jié)構(gòu)的功能正確;另外也可以從波形圖看出，由于加入了三級流水線，輸入數(shù)據(jù)到輸出的流水時延(pipelinelatency)為九個時鐘。

表1中列出了優(yōu)化后的全流水線結(jié)構(gòu)和原結(jié)構(gòu)在各種器件上綜合得到的最高工作頻率。對于各類器件，流水線結(jié)構(gòu)速度為原結(jié)構(gòu)的2.5倍左右。在數(shù)據(jù)長度較大的應(yīng)用中，可以忽略流水線時延(latency)的影響(每組數(shù)據(jù)九個時鐘)，那么在Spartan3(-4)的FPGA上就能實現(xiàn)每秒126 M的數(shù)據(jù)吞吐量，而采用Virtex5(-3)的FPGA上可實現(xiàn)高達每秒300 MB的數(shù)據(jù)吞吐量。表2列出了本文優(yōu)化后結(jié)構(gòu)和原結(jié)構(gòu)硬件資源消耗的對比，可以看出，在速度提高為原來2.5倍的情況下，硬件資源開銷僅增加了50%。

4 結(jié)束語

為滿足基于小波的高速信號實時處理的要求，基于FPGA實現(xiàn)更高速的5/3小波變換，需設(shè)計一種能工作在更高頻率的高速小波變換結(jié)構(gòu)。本文利用靜態(tài)時序分析的方法分析了現(xiàn)有小波變換結(jié)構(gòu)[3]設(shè)計中制約速度的關(guān)鍵因素，針對性地采用流水線設(shè)計的方法對原結(jié)構(gòu)進行改進優(yōu)化，以提高5/3提升小波結(jié)構(gòu)的工作頻率。實驗采用VHDL語言實現(xiàn)了流水線設(shè)計的5/3小波變換結(jié)構(gòu)和原設(shè)計中的變換結(jié)構(gòu)。結(jié)果表明，優(yōu)化后的流水線結(jié)構(gòu)在Xilinx公司的幾種常用FPGA器件上得到的最高綜合頻率均達到原結(jié)構(gòu)的250%，能夠在FPGA上實行更高速的變換結(jié)構(gòu)，更好地滿足高速信號處理需求。

參考文獻:

[1]

SWEDENS W. The lifting scheme: a new philosophy in biorthogonal wavelet constructions[C]// Proc of SPIE. San Diego: SPIE， 1995: 68-79.

[2]TAN K C B，ARSLAN Low power embedded extension algorithmfor liftingbased discrete wavelet transform in JPEG 2000[J]. Electronics  Letters ，2001， 37(25):1328-1330.

[3]黃思齊，楊魯平，劉橋. 一種適合JPEG 2000 的5/ 3 離散小波變換硬件系統(tǒng)結(jié)構(gòu)[C]// 2004 年中國自動化學會，中國儀器儀表學會會議論文集.2004.

[4]黃思齊，楊魯平，劉橋. JPEG 2000的5/ 3離散小波變換FPGA硬件實現(xiàn)[J]. 貴州大學學報， 2004，21(4): 403-406.

[5]熊承義，田金文，柳健，等. 有效的JPEG 2000小波變換VLSI結(jié)構(gòu)設(shè)計[J]. 計算機工程與應(yīng)用，2004，40(22):14-15，66.

[6]孫延奎. 小波分析及其應(yīng)用[M]. 北京:機械工業(yè)出版社， 2005.

[7]CILETTI M D. Verilog HDL高級數(shù)字設(shè)計[M]. 北京:電子工業(yè)出版社， 2005.