高家明， 梁　煜， 張　為， 劉艷艷

(1. 天津大學(xué) 微電子學(xué)院，天津 300072;2. 南開(kāi)大學(xué) 電子信息與光學(xué)工程學(xué)院，天津 300071)

二維離散小波變換(Discrete Wavelet Transform， DWT)是一種被廣泛應(yīng)用于數(shù)字信號(hào)處理、圖像分析、圖像壓縮等領(lǐng)域的信號(hào)濾波處理方法，其作用是將信號(hào)的主要信息與細(xì)節(jié)信息分離．對(duì)于用硬件實(shí)現(xiàn)二維離散小波變換結(jié)構(gòu)，為了低功耗、高效處理信號(hào)如數(shù)字圖像，在提高系統(tǒng)性能的同時(shí)降低硬件資源使用已逐漸成為二維離散小波變換結(jié)構(gòu)優(yōu)化的主要研究方向．

近年來(lái)，大量關(guān)于二維離散小波變換的超大規(guī)模集成電路(Very Large Scale Integration， VLSI)結(jié)構(gòu)的研究成果被發(fā)表．文獻(xiàn)[1]在已有提升算法的基礎(chǔ)上對(duì)公式進(jìn)行優(yōu)化，提出了新型雙輸入/雙輸出結(jié)構(gòu)，并采用pipeline結(jié)構(gòu)，降低關(guān)鍵路徑延時(shí)(Critical Path Delay， CPD)為一個(gè)乘法器延時(shí)(Tm)，內(nèi)部數(shù)據(jù)存儲(chǔ)減少為4N(N為輸入圖像長(zhǎng)度)．文獻(xiàn)[2]提出了一種橫向Z形掃描的雙輸入/雙輸出結(jié)構(gòu)，關(guān)鍵路徑為一個(gè)乘法器延時(shí)．文獻(xiàn)[3]通過(guò)對(duì)不同掃描方式的對(duì)比，采用圖像分塊掃描的方式降低了資源存儲(chǔ)面積．文獻(xiàn)[4]引入了重復(fù)掃描的方法，通過(guò)重復(fù)掃描1行像素的方法減小了模塊的內(nèi)存儲(chǔ)面積．重復(fù)掃描的方法在文獻(xiàn)[5-9]中也被采用，通過(guò)重復(fù)掃描1行、3行、5行和7行數(shù)據(jù)，可在模塊內(nèi)部分別節(jié)省N、2N、3N和4N的數(shù)據(jù)存儲(chǔ)空間．文獻(xiàn)[9-10]通過(guò)提高并行度的方式來(lái)增加系統(tǒng)的吞吐率，極大地減小了整體運(yùn)算時(shí)間，但是提高并行度的方法在減少運(yùn)算時(shí)間的同時(shí)，會(huì)增加輸入數(shù)據(jù)的寄存空間和運(yùn)算資源消耗．

通過(guò)對(duì)已有結(jié)構(gòu)的分析發(fā)現(xiàn)，圖像數(shù)據(jù)大多在片外隨機(jī)存取存儲(chǔ)器(Random Access Memory，RAM)進(jìn)行整體存儲(chǔ)．然而片外隨機(jī)存取存儲(chǔ)器的存在既會(huì)增加板級(jí)系統(tǒng)設(shè)計(jì)的復(fù)雜度，也會(huì)對(duì)數(shù)據(jù)接口位寬提出更高的要求．尤其對(duì)于實(shí)時(shí)圖像采集壓縮系統(tǒng)而言，原始數(shù)據(jù)通常會(huì)逐行逐點(diǎn)依次到達(dá)，此時(shí)若片外緩存數(shù)據(jù)過(guò)多，則不僅面積偏大而且整體延時(shí)較長(zhǎng)，不利于整體實(shí)現(xiàn)效果．采用片內(nèi)隨機(jī)存取存儲(chǔ)器存儲(chǔ)，同時(shí)對(duì)輸入數(shù)據(jù)掃描順序進(jìn)行調(diào)整，可以有效地緩解這一問(wèn)題，有利于提高實(shí)時(shí)圖像處理性能．同時(shí)，已有結(jié)構(gòu)的運(yùn)算單元也存在延時(shí)高與資源消耗大的缺陷，可結(jié)合二維離散小波變換提升算法對(duì)運(yùn)算結(jié)構(gòu)進(jìn)行改進(jìn)來(lái)實(shí)現(xiàn)優(yōu)化．

筆者將基于二維離散小波變換提升算法改進(jìn)圖像掃描方式，優(yōu)化輸入圖像存儲(chǔ)需求和模塊內(nèi)數(shù)據(jù)存儲(chǔ)需求，提升硬件效率與系統(tǒng)性能．

1　提升算法

二維離散小波變換提升算法最早由Daubechies 和Sweldens所提出，之后文獻(xiàn)[11]對(duì)提升算法進(jìn)行改進(jìn)．改進(jìn)算法如下所示．

首次預(yù)測(cè)與更新:

二次預(yù)測(cè)與更新:

兩步縮放:

上式中，x表示原始輸入數(shù)據(jù)，y表示變換中間值，H0表示最終變換得到的高頻小波系數(shù)，L0表示最終變換得到的低頻小波系數(shù)．α，β，γ，δ，K為常數(shù)定值，取值如下[12]:

α=-1.586 134 342，β=-0.052 980 118，γ=0.882 911 075，δ=0.443 506 852，K=1.230 174 105．

2　數(shù)據(jù)掃描

通過(guò)對(duì)式(1)～(4)分析可以發(fā)現(xiàn)，每一個(gè)公式中都包含一個(gè)乘法運(yùn)算和兩個(gè)加法運(yùn)算．且對(duì)于式(2)～(4)而言，在流水線結(jié)構(gòu)下每一次加法運(yùn)算中的待乘加數(shù)至少比非待乘加數(shù)提前一個(gè)周期到達(dá)．如式(2)中的待乘加數(shù)x2n在第1周期已經(jīng)到達(dá)，而y2n+1與y2n-1至少要在第2周期得到．又因?yàn)?6位加法器與乘法器的典型延時(shí)分別為 3.01 ns 和 6.79 ns[13]，因此基本運(yùn)算中的乘法運(yùn)算與加法運(yùn)算是可以同時(shí)進(jìn)行且不會(huì)對(duì)關(guān)鍵路徑產(chǎn)生影響．

因此，本設(shè)計(jì)對(duì)數(shù)據(jù)輸入順序進(jìn)行了調(diào)整，使得包括式(1)在內(nèi)的每一級(jí)基本運(yùn)算均能滿(mǎn)足乘法與加法并行執(zhí)行的要求．橫向并行三輸入 (2+1，其中一行為重復(fù)掃描)掃描為綜合存儲(chǔ)隨機(jī)存取存儲(chǔ)器最小的掃描方式，通過(guò)調(diào)整寫(xiě)入讀出的時(shí)鐘比為2∶1即可完成并行三輸入掃描[14]．在此基礎(chǔ)上，采取數(shù)據(jù)時(shí)鐘錯(cuò)位的方法，將像素x2n+1點(diǎn)提前于x2n，與x2n+2一個(gè)周期進(jìn)入二維離散小波變換處理模塊，這樣使得每一級(jí)的基本運(yùn)算均可以并行執(zhí)行．掃描方式如圖1所示，其中CLKN代表當(dāng)前行的第N個(gè)周期，灰色像素點(diǎn)為重復(fù)掃描像素點(diǎn)．

圖1　橫向三輸入掃描

3　架構(gòu)設(shè)計(jì)

3.1　模塊設(shè)計(jì)

根據(jù)式(1)～(4)及掃描方式，對(duì)列變換模塊設(shè)計(jì)如下．設(shè)計(jì)采用四級(jí)流水線結(jié)構(gòu)，即每一基本運(yùn)算均在一級(jí)流水線中完成．由于x2n+1先于x2n與x2n+2一個(gè)周期輸入，因此當(dāng)x2n與x2n+2進(jìn)入系統(tǒng)時(shí)，x2n+1的乘法操作已于上一周期完成，故而可直接進(jìn)行連續(xù)加法操作，式(1)基本運(yùn)算的并行處理得以解決．

在式(1)的基本運(yùn)算通過(guò)錯(cuò)位輸入的方式完成后可以發(fā)現(xiàn)，對(duì)于式(2)而言，x2n先于y2n+1一個(gè)周期到達(dá)，因此其乘法運(yùn)算可提前一周期完成，之后與下一周期到達(dá)的y2n+1和由隨機(jī)存取存儲(chǔ)器1輸入的y2n-1進(jìn)行連續(xù)加法來(lái)實(shí)現(xiàn)式(2)的運(yùn)算．式(3)和式(4)的運(yùn)算過(guò)程與式(2)的完全一致．由于數(shù)據(jù)錯(cuò)位輸入后式(1)～(4)的基本運(yùn)算除了乘法系數(shù)外，處理方式完全相同，因此設(shè)計(jì)乘法路徑與加法路徑相分離的基本運(yùn)算單元，如圖2中虛線框所示，并通過(guò)對(duì)基本運(yùn)算模塊的調(diào)用和乘法系數(shù)的多路選擇完成一維變換架構(gòu)的搭建．這樣優(yōu)化后的運(yùn)算結(jié)構(gòu)使得每一級(jí)基本運(yùn)算都得以并行處理，在四級(jí)流水線結(jié)構(gòu)內(nèi)完成了一維離散小波變換處理，節(jié)省了寄存器數(shù)量和運(yùn)算時(shí)間，簡(jiǎn)化了控制邏輯．

圖2　列變換模塊

列變換模塊結(jié)構(gòu)設(shè)計(jì)如圖2所示，圖中帶*項(xiàng)代表下一列的x2n+1值，灰色寄存器為輸出的小波系數(shù)．列變換對(duì)中間值y2n+1、y2n和H2n+1進(jìn)行緩存，共需要3N的數(shù)據(jù)緩存空間．

由列變換模塊輸出的L與H碼流需要經(jīng)過(guò)轉(zhuǎn)置后進(jìn)入行變換模塊處理．由于本結(jié)構(gòu)基于行并行掃描方式，因此轉(zhuǎn)置模塊只需要5個(gè)寄存器即可滿(mǎn)足行變換模塊數(shù)據(jù)錯(cuò)位的三輸入要求．轉(zhuǎn)置模塊的架構(gòu)如圖3所示．

圖3　轉(zhuǎn)置模塊

如圖4所示，基于錯(cuò)位三輸入的行變換模塊結(jié)構(gòu)與列變換模塊結(jié)構(gòu)整體相近．不過(guò)，由于數(shù)據(jù)流是連續(xù)的，因此不需要隨機(jī)存取存儲(chǔ)器進(jìn)行大量的數(shù)據(jù)存儲(chǔ)，只需要在每一級(jí)使用兩個(gè)深度的寄存器(圖中以buffer表示)進(jìn)行兩周期的數(shù)據(jù)緩存即可．

圖4　行變換模塊

對(duì)于縮放模塊，采用了一次縮放方案，即在行變換與列變換的二維處理結(jié)束后對(duì)于輸出數(shù)據(jù)進(jìn)行單次縮放．由式(1)～(4)可知，經(jīng)二維變換后待縮放的數(shù)據(jù)分別為L(zhǎng)L/ (αβγδ)2、LH/ ((αβγ)2δ)、HL/ ((αβγ)2δ) 和HH/ (αβγ)2，縮放模塊如圖5所示．

3.2　整體結(jié)構(gòu)

筆者所設(shè)計(jì)的二維離散小波變換整體結(jié)構(gòu)如圖6所示，輸入像素點(diǎn)逐行依次進(jìn)入

輸入隨機(jī)存取存儲(chǔ)器，之后以并行三輸入方式進(jìn)入行變換模塊進(jìn)行二維離散小波變換，最終數(shù)據(jù)由縮放模塊并行輸出．

圖5　縮放模塊

圖6　離散小波變換整體結(jié)構(gòu)

4　硬件開(kāi)銷(xiāo)對(duì)比

表1中將本結(jié)構(gòu)與其他現(xiàn)有架構(gòu)進(jìn)行了對(duì)比．由于高并行度架構(gòu)需要巨大的輸入隨機(jī)存取存儲(chǔ)器，使得對(duì)比意義不大，因此所列舉架構(gòu)均取并行度S=1 的二維離散小波變換硬件結(jié)構(gòu)．通常原始像素?cái)?shù)據(jù)為 8 bit，進(jìn)入系統(tǒng)前需要拓展為 16 bit，因此表中輸入隨機(jī)存取存儲(chǔ)器為 8 bit，暫存隨機(jī)存取存儲(chǔ)器為 16 bit，乘法器(mul)、加法器(add)與寄存器(reg)均為 16 bit．Tm表示一個(gè)乘法器延時(shí)，Ta表示一個(gè)加法器延時(shí)，N為圖像每行像素個(gè)數(shù)，輸入數(shù)據(jù) (2+1) 表示一行為重復(fù)掃描．

表1　整體硬件開(kāi)銷(xiāo)對(duì)比

通過(guò)整體硬件開(kāi)銷(xiāo)對(duì)比可以發(fā)現(xiàn)，本結(jié)構(gòu)的運(yùn)算資源消耗少于絕大部分文獻(xiàn)中的列舉結(jié)構(gòu)．文獻(xiàn)[4]雖然寄存器數(shù)量少于本結(jié)構(gòu)，但是其關(guān)鍵路徑延時(shí)約為本結(jié)構(gòu)的1.5倍，綜合考慮硬件效率仍略低于本結(jié)構(gòu)的．為了更加直觀地對(duì)各硬件架構(gòu)的硬件效率進(jìn)行對(duì)比，文獻(xiàn)[15]提出了對(duì)晶體管數(shù)量-延時(shí)-吞吐量(Transistor count Delay Product， TDP)進(jìn)行綜合對(duì)比．TDP值為晶體管總數(shù)(Transistor Count， TC)、關(guān)鍵路徑延時(shí)(CPD)以及活動(dòng)周期數(shù)(Active Cycle Time， ACT)三者的乘積．其中，一個(gè)乘法器的延時(shí)Tm= 6.79 ns，一個(gè)加法器的延時(shí)Ta= 3.01 ns，TACT=N2/T(T為吞吐量)．因此可以認(rèn)為，TDP評(píng)價(jià)方式考慮了數(shù)據(jù)吞吐量、架構(gòu)對(duì)于時(shí)間和硬件開(kāi)銷(xiāo)的綜合需求．TDP值越小，代表架構(gòu)的硬件效率越高．

對(duì)于器件中的晶體管數(shù)量，文獻(xiàn)[15-16]中提供了一種基于陣列加法器和陣列乘法器的晶體管數(shù)量計(jì)算方法．其中，8 bit 的乘法器、加法器、寄存器和隨機(jī)存取存儲(chǔ)器的晶體管數(shù)量分別為 1 085、248、128和48，16 bit 的加法器、寄存器和隨機(jī)存取存儲(chǔ)器的晶體管數(shù)量分別是504、256和96，16 bit 乘法器的晶體管數(shù)量為 5 084．綜合考慮以上因素后，表2對(duì)已有結(jié)構(gòu)硬件效率進(jìn)行了綜合對(duì)比，測(cè)試圖像大小為 512× 512，表中mul、add、reg和隨機(jī)存取存儲(chǔ)器代表乘法器、加法器、寄存器和隨機(jī)存取存儲(chǔ)器的晶體管數(shù)量．

表2　硬件效率對(duì)比

通過(guò)對(duì)比結(jié)果可以發(fā)現(xiàn)，同已有最優(yōu)架構(gòu)相比，本結(jié)構(gòu)硬件效率優(yōu)化達(dá)到8.4%; 與文獻(xiàn)[4]中同為三輸入的結(jié)構(gòu)相比，本結(jié)構(gòu)硬件效率優(yōu)化達(dá)到30%以上．因此可以得出結(jié)論，筆者設(shè)計(jì)的架構(gòu)在硬件效率(TDP)上均優(yōu)于現(xiàn)有架構(gòu)．

5　總　　結(jié)

筆者設(shè)計(jì)了一種高性能的二維離散小波變換架構(gòu)，采用了并行三輸入數(shù)據(jù)錯(cuò)位的掃描方式，優(yōu)化了變換模塊內(nèi)部運(yùn)算結(jié)構(gòu)，減少了硬件開(kāi)銷(xiāo)，硬件效率提高8%以上．

參考文獻(xiàn)：

[1] ZHANG W, JIANG Z, GAO Z, et al. An Efficient VLSI Architecture for LIfting-based Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2012, 59(3): 158-162.

[2]DARJI A, AGRAWAL S, OZA A, et al. Dual-scan Parallel Flipping Architecture for a Lifting-based 2-D Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2014, 61(6): 433-437.

[3]YE L N, HOU Z. Memory Efficient Multilevel Discrete Wavelet Transform Schemes for JPEG2000[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2015, 25(11): 1773-1785.

[4]HU Y S, JONG C C. A Memory-efficient Scalable Architecture for Lifting-based Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2013, 60(8): 502-506.

[5]MOHANTY B K, MEHER P K. Area-delay-power-efficient Architecture for Folded Two-dimensional Discrete Wavelet Transform by Multiple Lifting Computation[J]. IET Image Processing, 2014, 8(6): 345-353.

[6]MOHANTY B K, MEHER P K, SRIKANTHAN T. Critical-path Optimization for Efficient Hardware Realization of Lifting and Flipping DWTs[C]//Proceedings of the 2015 IEEE International Symposium on Circuits and Systems. Piscataway: IEEE, 2015: 1186-1189.

[7]TODKAR S, SHASTRY P V S. Flipping Based High Performance Pipelined VLSI Architecture for 2-D Discrete Wavelet Transform[C]//Proceedings of the 2015 International Conference on Applied and Theoretical Computing and Communication Technology. Piscataway: IEEE, 2015: 832-836.

[8]DARJI A D, LIMAYE A. Memory Efficient VLSI Architecture for Lifting-based DWT[C]//Proceedings of the 2014 Midwest Symposium on Circuits and Systems. Piscataway: IEEE, 2014: 189-192.

[9]HU Y, JONG C C. A Memory-efficient High-throughput Architecture for Lifting-based Multi-Level 2-D DWT[J]. IEEE Transactions on Signal Processing, 2013, 61(20): 4975-4987.

[10]MOHANTY B K, MAHAJAN A, MEHER P K. Area- and Power-efficient Architecture for High-throughput Implementation of Lifting 2-D DWT[J]. IEEE Transactions on Circuits and Systems Ⅱ: Express Briefs, 2012, 59(7): 434-438.

[11]HUANG C T, TSENG P C, CHEN L G. Flipping Structure: an Efficient VLSI Architecture for Lifting-based Discrete Wavelet Transform[J]. IEEE Transactions on Signal Processing, 2004, 52(4): 1080-1089.

[12]董明巖, 雷杰, 王柯儼, 等. 高效低存儲(chǔ)DWT的VLSI結(jié)構(gòu)設(shè)計(jì)[J]. 西安電子科技大學(xué)學(xué)報(bào), 2016, 43(2): 35-40.

DONG Mingyan, LEI Jie, WANG Keyan, et al. Highly Efficient VLSI Architecture for DWT with Low-storage Implementation[J]. Journal of Xidian University, 2016, 43(2): 35-40.

[13]HSIA C H, CHIANG J S, GUO J M. Memory-efficient Hardware Architecture of 2-D Dual-mode Lifting-based Discrete Wavelet Transform[J]. IEEE Transactions on Circuits and Systems for Video Technology, 2013, 23(4): 671-683.

[14]WU C K, ZHANG W, JIA Q, et al. Hardware Efficient Multiplier-less Multi-level 2D DWT Architecture without off-chip RAM[J]. IET Image Processing, 2017, 11(6): 362-369.

[15]賈琦, 梁煜, 張為. 一種無(wú)片外存儲(chǔ)的高性能二維DWT架構(gòu)[J]. 西安電子科技大學(xué)學(xué)報(bào), 2017, 44(4): 150-155.

JIA Qi, LIANG Yu, ZHANG Wei. Hardware Efficient 2-D DWT Architecture without off-chip RAM[J]. Journal of Xidian University, 2017, 44(4): 150-155.

[16]MOHANTY B K, MEHER P K. Memory Efficient Modular VLSI Architecture for Highthroughput and Low-latency Implementation of Multilevel Lifting 2-D DWT[J]. IEEE Transactions on Signal Processing, 2011, 59(5): 2072-2084.