一維離散小波變換VLSI結(jié)構(gòu)分析設(shè)計(jì)

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

中圖分類號(hào):TN919-34; TP274 文獻(xiàn)標(biāo)識(shí)碼:A

文章編號(hào):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) 良好的時(shí)頻域局部化分析性能，使其在信號(hào)分析、圖像壓縮、視頻壓縮等領(lǐng)域成為一個(gè)應(yīng)用廣泛的DSP工具[1]。隨著DWT研究與應(yīng)用的日益普及，其硬件實(shí)現(xiàn)的需求日益迫切。Sweldens在Mallat算法基礎(chǔ)上提出提升算法(lifting scheme)[2]，為小波變換提供了一種快速實(shí)現(xiàn)方法，并且已經(jīng)被應(yīng)用于JPEG2000標(biāo)準(zhǔn)中。基于提升算法的DWT，可以有效地減少乘加法的運(yùn)算量，比較適合VLSI(very large scale integration)[3-4]架構(gòu)實(shí)現(xiàn)。最近有人提出了1種翻轉(zhuǎn)結(jié)構(gòu)(flipping structure)[5-7]，它對(duì)提升結(jié)構(gòu)的系數(shù)進(jìn)行了巧妙的翻轉(zhuǎn)和合并，使乘法和加法的運(yùn)算量進(jìn)一步降低。

本文在翻轉(zhuǎn)結(jié)構(gòu)的基礎(chǔ)上，將兩級(jí)“預(yù)測(cè)”步驟和“更新”步驟合并成一個(gè)單獨(dú)的提升步驟，并引入2選1的多路選擇器到縮放步驟中，有效調(diào)整了原始數(shù)據(jù)的路徑，節(jié)省了硬件乘法器的資源，更利于硬件實(shí)施。同時(shí)還對(duì)翻轉(zhuǎn)結(jié)構(gòu)中乘法器引入的舍入誤差進(jìn)行了分析。

1 小波提升算法

任何完全重構(gòu)的DWT濾波器組都可以分解成一系列有限長(zhǎng)度的提升步驟。目標(biāo)小波濾波器的多相矩陣(polyphase matrix)[8]可以分解成式(1)中l(wèi)ifting的實(shí)現(xiàn)方式，如:

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)為羅朗多項(xiàng)式;si(z)是推舉因子;ti(z)是對(duì)偶推舉因子;k是1個(gè)非零常數(shù)，是歸一化因子。

采用提升算法，(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/ζ的乘法，計(jì)算一級(jí)變換需要4次乘法，8次加法，考慮用流水線結(jié)構(gòu)，則每個(gè)流水線的最小周期是1次乘法，2次加法。

基于翻轉(zhuǎn)結(jié)構(gòu)的離散小波變換仍是基于提升的結(jié)構(gòu)，只是改變了系數(shù)的位置。對(duì)P(z)進(jìn)行變形，提取每個(gè)主提升和對(duì)偶提升過(guò)程的系數(shù)，實(shí)施矩陣的初等變換，翻轉(zhuǎn)提升結(jié)構(gòu)的系數(shù)，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)小波變換翻轉(zhuǎn)結(jié)構(gòu)的系數(shù)，k1=αβγδζ;k2=αβγ/ζ。

由于翻轉(zhuǎn)之后，將導(dǎo)致乘法溢出，運(yùn)算使級(jí)聯(lián)誤差會(huì)隨級(jí)聯(lián)而增大;所需數(shù)據(jù)寬度也將隨級(jí)聯(lián)增加。為了解決上述問(wèn)題，對(duì)系數(shù)進(jìn)行移位。變形結(jié)果為:

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′=αβγ/ζ。翻轉(zhuǎn)結(jié)構(gòu)示意圖如圖1所示。

圖1 (9，7)小波翻轉(zhuǎn)結(jié)構(gòu)

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

(1) 分裂步驟(splitting step)

s0i=x2i(5)

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

(2) 提升步驟(lifting step)

第一級(jí)提升步驟:

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

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

第二級(jí)提升步驟:

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的舍入誤差分析

在實(shí)現(xiàn)DWT的硬件過(guò)程中，當(dāng)算法采用定點(diǎn)表示時(shí)，引入的舍入誤差將嚴(yán)重影響整個(gè)算法的運(yùn)算精度，因此，對(duì)其進(jìn)行精度分析是非常重要的。翻轉(zhuǎn)結(jié)構(gòu)的舍入誤差主要由乘法器引起，圖1結(jié)構(gòu)圖對(duì)應(yīng)的舍入噪聲模型如圖2所示。

圖2 舍入誤差模型

圖中:E2(n)表示第一級(jí) “預(yù)測(cè)”步驟的舍入誤差;yH(n)表示高頻輸出的舍入誤差。其中，e1(n)，e2(n)，e3(n)和e4(n)是噪聲信號(hào)。噪聲信號(hào)e(n)可假定為獨(dú)立同分布的白噪聲，方差為σ2e;yH，lifting(n)是基于標(biāo)準(zhǔn)提升算法結(jié)構(gòu)的高頻舍入噪聲;yH，flipping(n)是翻轉(zhuǎn)結(jié)構(gòu)的高頻舍入噪聲。現(xiàn)將二者進(jì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)

因?yàn)榫刀嫉扔诹悖苑讲?

σ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

由此可見(jiàn)，由于翻轉(zhuǎn)結(jié)構(gòu)使用了移位及乘法系數(shù)，翻轉(zhuǎn)變小，其舍入誤差比標(biāo)準(zhǔn)提升算法得到大大改善。

3 DWT的硬件實(shí)現(xiàn)

翻轉(zhuǎn)結(jié)構(gòu)是非常適合用于硬件流水線來(lái)實(shí)現(xiàn)DWT的。本節(jié)采用合并提升步驟的方法，先把每級(jí)“預(yù)測(cè)”步驟和“更新”步驟便合并成一個(gè)新的提升步驟，然后再把兩級(jí)新得到的提升步驟合并成一個(gè)單獨(dú)的提升步驟。

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

第一級(jí)提升步驟:

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

第二級(jí)提升步驟:

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

合并兩級(jí)提升步驟成一個(gè)新的表達(dá)式:

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

圖3 (9，7)小波提升步驟的流水線結(jié)構(gòu)

從結(jié)構(gòu)中可以看到，在關(guān)鍵路徑為T(mén)m的約束條件下(Tm和Ta分別代表乘法器和加法器的計(jì)算延時(shí))，完成一次(9，7)小波的提升步驟，需要1個(gè)乘法器、2個(gè)加法器和8個(gè)內(nèi)部寄存器。這樣可以有效地調(diào)整原始數(shù)據(jù)的運(yùn)算路徑，更好地發(fā)揮算術(shù)運(yùn)算資源的作用，節(jié)省硬件乘法器、硬件加法器和內(nèi)部寄存器的資源。

綜上可得，隨著數(shù)據(jù)的連續(xù)輸入，該硬件結(jié)構(gòu)連續(xù)處理數(shù)據(jù)，這樣可以充分利用硬件資源，利用率幾乎可達(dá)到100%，而且控制非常簡(jiǎn)單，只是利用幾個(gè)Pipeline寄存器即可實(shí)現(xiàn)濾波的流水線處理

。

表 1 1-D DWT性能比較

結(jié)構(gòu)乘法器加法器寄存器關(guān)鍵路徑

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中文獻(xiàn)[9]是直接基于卷積Direct結(jié)構(gòu)，采用pipeline之后，關(guān)鍵路徑降低，但需要消耗大量的硬件資源;文獻(xiàn)[10]采用的是翻轉(zhuǎn)架構(gòu)，寄存器的數(shù)量比Direct結(jié)構(gòu)進(jìn)一步減少，關(guān)鍵路徑也比較理想;通過(guò)比較，在關(guān)鍵路徑的約束條件下，顯然采用本算法的硬件結(jié)構(gòu)，寄存器、內(nèi)部存儲(chǔ)器和硬件乘法器數(shù)量上會(huì)進(jìn)一步的減少。

4 結(jié) 語(yǔ)

本文提出了一種有效的基于翻轉(zhuǎn)結(jié)構(gòu)DWT硬件實(shí)現(xiàn)架構(gòu)。采用合并提升步驟和流水線設(shè)計(jì)的方法，并引入多路選擇器到縮放步驟中，節(jié)約了硬件資源，降低了功耗。此外，本文還對(duì)比研究了標(biāo)準(zhǔn)提升算法和翻轉(zhuǎn)結(jié)構(gòu)中乘法器的舍入誤差，并與其進(jìn)行了比較。按本文思想，目前正在進(jìn)行二維多級(jí)小波變換的設(shè)計(jì)。

參考文獻(xiàn)

[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核設(shè)計(jì)[J].微計(jì)算機(jī)信息 2009，25(2):74-76.

[6]董文輝，劉明業(yè).JPEG2000小波提升算法的硬件設(shè)計(jì)[J].電子學(xué)報(bào)，2003，31(11):1674-1677.

[7]郝燕玲，劉營(yíng)，仲訓(xùn)昱.一種有效的基于翻轉(zhuǎn)結(jié)構(gòu)的DWT硬件結(jié)構(gòu)[J].四川大學(xué)學(xué)報(bào):工程科學(xué)版，2009(4):43-45.

[8]成禮智，王洪霞，羅永.小波的理論與應(yīng)用[M].北京:科學(xué)出版社，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.