一維離散小波變換VLSI結構分析設計

摘 要:提升算法的推出使得離散小波變換硬件的快速實現成為可能。翻轉結構在提升架構的基礎上進一步提高運算速度。在此，對翻轉結構的舍入誤差進行了分析，在翻轉結構的基礎上，對提升步驟進行了合并，提出一種有效的DWT硬件實現方案。實驗結果表明，通過采用流水線模式提出的這種硬件結構，在關鍵路徑約束的條件下，可以充分利用硬件資源。關鍵詞:離散小波變換; 提升算法; 翻轉結構; 舍入誤差

中圖分類號:TN919-34; TP274 文獻標識碼:A

文章編號:1004-373X(2010)18-0124-03

Analysis and VLSI Architecture for 1-D Discrete Wavelet Transform

XIN Qin， ZHONG Yan-hua， LIU Chun-feng， PAN Li-ming

(School of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073， China)

Abstract: The introduction of lifting scheme makes the fast hardware implementation of DWT come true. The flipping structure speeds up further the computation for lifting-based architecture. The roundoff error of the flipping structure is analyzed. Based on the flipping structure， the lifting step is modified and an efficient hardware structure for DWT derived from flipping structure is proposed. Experimental results show that the proposed structure， which adopts the pipeline design， could effectively make full use of the arithmetic resources under the condition of the tight critical path.Keywords: discrete wavelet transform; lifting scheme; flipping structure; roundoff error

收稿日期:2010-05-21

0 引 言

離散小波變換(discrete wavelet transform，DWT) 良好的時頻域局部化分析性能，使其在信號分析、圖像壓縮、視頻壓縮等領域成為一個應用廣泛的DSP工具[1]。隨著DWT研究與應用的日益普及，其硬件實現的需求日益迫切。Sweldens在Mallat算法基礎上提出提升算法(lifting scheme)[2]，為小波變換提供了一種快速實現方法，并且已經被應用于JPEG2000標準中。基于提升算法的DWT，可以有效地減少乘加法的運算量，比較適合VLSI(very large scale integration)[3-4]架構實現。最近有人提出了1種翻轉結構(flipping structure)[5-7]，它對提升結構的系數進行了巧妙的翻轉和合并，使乘法和加法的運算量進一步降低。

本文在翻轉結構的基礎上，將兩級“預測”步驟和“更新”步驟合并成一個單獨的提升步驟，并引入2選1的多路選擇器到縮放步驟中，有效調整了原始數據的路徑，節省了硬件乘法器的資源，更利于硬件實施。同時還對翻轉結構中乘法器引入的舍入誤差進行了分析。

1 小波提升算法

任何完全重構的DWT濾波器組都可以分解成一系列有限長度的提升步驟。目標小波濾波器的多相矩陣(polyphase matrix)[8]可以分解成式(1)中lifting的實現方式，如:

P(z)=he(z)ge(z)

ho(z)go(z)=∏mi=11si(z)

01#8226;

10

ti(z)1K0

01K(1)

式中:si(z)和ti(z)為羅朗多項式;si(z)是推舉因子;ti(z)是對偶推舉因子;k是1個非零常數，是歸一化因子。

采用提升算法，(9，7)小波的多相位矩陣分解式為:

P(z)=1α(1+z-1)

0110

β(1+z)1#8226;

1γ(1+z-1)

0110

δ(1+z)1ζ0

01ζ(2)

式中:α=-1.586 134 342;β=-0.052 980 118;γ=0.882 911 076;δ=0.443 506 852;ζ=1.149 604 398。若不包括ζ和1/ζ的乘法，計算一級變換需要4次乘法，8次加法，考慮用流水線結構，則每個流水線的最小周期是1次乘法，2次加法。

基于翻轉結構的離散小波變換仍是基于提升的結構，只是改變了系數的位置。對P(z)進行變形，提取每個主提升和對偶提升過程的系數，實施矩陣的初等變換，翻轉提升結構的系數，P(z)可以分解為如下形式:

P(z)=11+z-1

0ab01+z1#8226;

11+z-1

0cd01+z1k10

0k2(3)

式中:a=1/α;b=1/αβ;c=1/βγ;d=1/γδ;k1，k2是新生成的(9，7)小波變換翻轉結構的系數，k1=αβγδζ;k2=αβγ/ζ。

由于翻轉之后，將導致乘法溢出，運算使級聯誤差會隨級聯而增大;所需數據寬度也將隨級聯增加。為了解決上述問題，對系數進行移位。變形結果為:

P(z)=11+z-1

0a′b′0

(1+z)/161#8226;

1(1+z-1)/2

0c′d′0

(1+z)/21k1′0

0k2′(4)

式中:a′=1/α;b′=1/16αβ;c′=1/32βγ;d′=1/4γδ;k1′=64αβγδζ;k2′=αβγ/ζ。翻轉結構示意圖如圖1所示。

圖1 (9，7)小波翻轉結構

(9，7)小波提升的具體實現步驟如式(5)~式(12)所示，{xi|i∈Z}表示原始的輸入數據序列，用s0i和d0i分別表示輸入的奇數分量和偶數分量，用sni和dni(n=1，2)表示提升分解得到的中間值，用si和di分別表示信號的低頻分量和高頻分量輸出。

(1) 分裂步驟(splitting step)

s0i=x2i(5)

d0i=x2i+1(6)

(2) 提升步驟(lifting step)

第一級提升步驟:

d1i=a′×d0i+s0i+s0i+1(7)

s1i=b′×s0i+(d1i+d1i-1)4(8)

第二級提升步驟:

d2i=c′×d1i+(s1i+s1i+1)1(9)

s2i=d′×s1i+(d2i+d2i-1)1(10)

(3) 縮放步驟(scaling step)

si=k1′×s2i(11)

di=k2′×d2i(12)

2 DWT的舍入誤差分析

在實現DWT的硬件過程中，當算法采用定點表示時，引入的舍入誤差將嚴重影響整個算法的運算精度，因此，對其進行精度分析是非常重要的。翻轉結構的舍入誤差主要由乘法器引起，圖1結構圖對應的舍入噪聲模型如圖2所示。

圖2 舍入誤差模型

圖中:E2(n)表示第一級 “預測”步驟的舍入誤差;yH(n)表示高頻輸出的舍入誤差。其中，e1(n)，e2(n)，e3(n)和e4(n)是噪聲信號。噪聲信號e(n)可假定為獨立同分布的白噪聲，方差為σ2e;yH，lifting(n)是基于標準提升算法結構的高頻舍入噪聲;yH，flipping(n)是翻轉結構的高頻舍入噪聲。現將二者進行比較:

yH，lifting(n)=e3(n)+0.882 91[e2(n)+e2(n-1)]-

0.046 78[e1(n)+e1(n-2)]+

0.906 44e1(n-1)

yH，flipping(n)=e3(n)+0.5[e2(n)+e2(n-1)]+

0.031 25[e1(n)+e1(n-2)]-

0.605 57e1(n-1)

因為均值都等于零，所以方差:

σ2q=E(X2)-E2(X)=E(X2)

E[y2H，lifting(n)]=3.385 07σ2e

E[y2H，flippting(n)]=1.868 67σ2e

由此可見，由于翻轉結構使用了移位及乘法系數，翻轉變小，其舍入誤差比標準提升算法得到大大改善。

3 DWT的硬件實現

翻轉結構是非常適合用于硬件流水線來實現DWT的。本節采用合并提升步驟的方法，先把每級“預測”步驟和“更新”步驟便合并成一個新的提升步驟，然后再把兩級新得到的提升步驟合并成一個單獨的提升步驟。

將式(7)代入式(8)中，從而第一級“預測”步驟和“更新”步驟合并成一個新的表達式，如式(13)所示;然后將式(9)代入式(10)中，同理可得到式(14)，最后合并兩級新得到的提升步驟，即將式(13)代入式(14)中，得到式(15)。

第一級提升步驟:

s1i=b′×s0i+d1i+d1i-1=b′×s0i+a′×d0i+s0i+s0i+1+a′×d0i-1+s0i-1+s0i(13)

第二級提升步驟:

s2i=d′×s1i+d2i+d2i-1=d′×s1i+c′×d1i+s1i+s1i+1+c′×d1i-1+s1i-1+s1i(14)

合并兩級提升步驟成一個新的表達式:

s2i=d′×(b′×s0i+a′×d0i+s0i+s0i+1 +a′×d0i-1+s0i-1+s0i)+c′×(a′×d0i+s0i+s0i+1+a′×d0i-1+s0i-1+s0i)

+b′×s0i+1+a′×d0i+1+s0i+1+s0i+2+b′×s0i+a′×d0i+s0i+s0i+1+a′×d0i+s0i+s0i+1+a′×d0i-1+s0i-1+s0i +

a′×d0i-1+s0i-1+s0i+a′×d0i-2+s0i-2+s0i-1+b′×s0i+a′×d0i+s0i+s0i+1 +b′×s0i-1+a′×d0i-1+s0i-1+s0i(15)

利用式(15)，每4個時鐘周期完成1次(9，7)離散小波變換的提升步驟。每4個時鐘周期的第一個時鐘周期完成一次濾波器常系數a′的乘法，同時完成2次加法操作。其中，新產生的中間結果存入Delay_reg1，同時從Delay_reg1讀取中間結果，以供計算使用，最后利用Pipeline寄存器實現流水線處理，然后依次完成其他3個時鐘周期的濾波器常系數乘法操作和加法操作。可見，(9，7)小波提升步驟具有4路相同的原始數據的運算路徑，這樣可以用幾個4選1的多路選擇器來控制原始數據運算路徑。針對本文每個時鐘周期輸入1/2數據的特點，對縮放步驟引入2個二選一的多路選擇器，節省了一個硬件乘法器。據此，可設計一個(9，7)小波提升步驟的流水線結構，如圖3所示。

圖3 (9，7)小波提升步驟的流水線結構

從結構中可以看到，在關鍵路徑為Tm的約束條件下(Tm和Ta分別代表乘法器和加法器的計算延時)，完成一次(9，7)小波的提升步驟，需要1個乘法器、2個加法器和8個內部寄存器。這樣可以有效地調整原始數據的運算路徑，更好地發揮算術運算資源的作用，節省硬件乘法器、硬件加法器和內部寄存器的資源。

綜上可得，隨著數據的連續輸入，該硬件結構連續處理數據，這樣可以充分利用硬件資源，利用率幾乎可達到100%，而且控制非常簡單，只是利用幾個Pipeline寄存器即可實現濾波的流水線處理

。

表 1 1-D DWT性能比較

結構乘法器加法器寄存器關鍵路徑

Direct[9]4864Tm +8Ta

Direct +fully pipeline[9] 4832Tm 

Flipping+ no pipeline[10]484Tm +5Ta

Flipping+5 pipeline [10]4811Tm

本文算法228Tm

表1中文獻[9]是直接基于卷積Direct結構，采用pipeline之后，關鍵路徑降低，但需要消耗大量的硬件資源;文獻[10]采用的是翻轉架構，寄存器的數量比Direct結構進一步減少，關鍵路徑也比較理想;通過比較，在關鍵路徑的約束條件下，顯然采用本算法的硬件結構，寄存器、內部存儲器和硬件乘法器數量上會進一步的減少。

4 結 語

本文提出了一種有效的基于翻轉結構DWT硬件實現架構。采用合并提升步驟和流水線設計的方法，并引入多路選擇器到縮放步驟中，節約了硬件資源，降低了功耗。此外，本文還對比研究了標準提升算法和翻轉結構中乘法器的舍入誤差，并與其進行了比較。按本文思想，目前正在進行二維多級小波變換的設計。

參考文獻

[1]LAI Yeong-Kang， CHEN Lien-Fei， SHIH Yui-Chih. A high-performance and memory-efficient VLSI architecture with parallel scanning method for 2-D lifting-based discrete wavelet transform[J]. IEEE Transaction on Consumer Electronics， 2009，55(2): 206-211.

[2]LIAN C J， CHEN K F， CHEN H H， et al. Lifting based discrete wavelet transform architecture for JPEG2000[J]. IEEE Int.Symp. Circuits Syst.， 2001，2: 445-450.

[3]WANG Chao， WU Zhi-lin， CAO Peng， et al. An efficient VLSI architecture for lifting-based discrete wavelet transform[C]//ICME.[S.l.]: ICME， 2007: 1575-1578.

[4]SHIAU Y H， JOU J M， LIU C C. Efficient VLSI architectures for the biorthogonal wavelet transform by filter bank and lifting scheme[J]. IEEE Transactions， 2004，e87(7): 1867-1877.

[5]歐龍，張啟衡，楊洪，等.基于FPGA的二維提升小波變換IP核設計[J].微計算機信息 2009，25(2):74-76.

[6]董文輝，劉明業.JPEG2000小波提升算法的硬件設計[J].電子學報，2003，31(11):1674-1677.

[7]郝燕玲，劉營，仲訓昱.一種有效的基于翻轉結構的DWT硬件結構[J].四川大學學報:工程科學版，2009(4):43-45.

[8]成禮智，王洪霞，羅永.小波的理論與應用[M].北京:科學出版社，2004.

[9]HUANG Chao-Tsung， TSENG Po-Chih，CHEN Liang-gee. Analysis and VLSI architectures for 1-D and 2-D discrete wavelet transform[J]. IEEE Transactions on signal processing， 2005，53(4): 1575-1586.

[10]HUANG Chao-Tsung， TSENG Po-Chih， CHEN Liang-Gee. Flipping structure:an efficient VLSI architecture for lifting-based discrete wavelet transform[J]. IEEE Tran-saction on signal processing， 2004， 52(4): 1080-1089.