高速、可配置的一維離散小波變換vlsi結構的製作方法

2023-06-17 14:55:06

專利名稱：高速、可配置的一維離散小波變換vlsi結構的製作方法
技術領域：
本發明主要是關於一種高速、可配置的一維5/3和9/7小波變換的VLSI實現結構。
小波變換的VLSI實現研究一直是近些年來國際上的研究的熱點。G.Knowles等人的論文——「VLSI Architecture for the Discrete Wavelet Transform，」Electronic letters，vol.26，no.15，1990，pp.2091-2110，提出了第一個關於離散小波變換的VLSI結構。該結構中離散小波變換作為一個低通濾波器和一個高通濾波器進行實現，中間計算是通過大量的乘加運算來實現的，因此從經濟成本角度來看，該結構不適合用於ASIC的實現。其後，A.S.Lewis等人在提出了一種無乘法操作兩維離散小波變換的VLSI結構(A.S.Lewis and G.Knowles，「VLSI Architecture for 2-D Daubechies Wavelet Transform Without Multipliers，」Electronicletters，vol.27，no.2，1991，pp.171-173)。但是這個結構主要適用於Daubechies的四階小波濾波器，對於其它形式的小波濾波器並不是十分理想。後來，Aware公司提出了一種摺疊方式小波變換結構，其結構將所有各級的小波變換的計算採用一組低通和高通小波濾波起來實現，這樣的結構各級間具有較低處理延時，但是增加了硬體面積，同時需要複雜的互連方式(Aware Inc.，Cambridge，Aware Wavelet Transform Processor(WTP)Preliminary，1991)。儘管由Parhi和Nishitani提出的串行處理的小波變換VLSI結構，克服了上述的摺疊結構的缺點，但是增加了系統延時(K.K.Parhi and T.Nishitani，「VLSI Architecture for DiscreteWavelet Transform，」IEEE Transactions on Very Large Scale Integration(VLSI)System，vol.1，no.2，1993，pp.191-202)。後來，Firdman，Owens，Chakrabarti，Denk等人在他們的論文中提出多種改進結構，但是所有的這些結構都是基於傳統的卷積方式實現的小波變換，因此，這些結構計算單元和邏輯控制都十分複雜。於是，一種改進的基於提升(lifting)結構的小波變換算法被提出來，並且迅速得到廣泛應用。
基於提升(lifting)結構的小波變換算法是由美國著名數學家Wim Sweldens於上世紀90年代中期提出的。它的原理是將低通和高通濾波處理分解成為一系列上三角和下三角矩陣的乘積。如此的結構具有明顯的優點，例如，可以實現原位計算，即計算的結果可以存入相應原數據存儲單元，這樣節省了計算過程的中間數據緩存。它可以實現整數處理，這對於無損情況下的編碼處理十分有效；另外，它的正向變換和逆向變換具有相似的對稱結構。由於基於提升(lifting)結構的小波變換算法的諸多優點，它已經成為國際最新影像壓縮標準——JEPG2000核心編碼算法(標準號15444-1)的推薦小波變換算法。標準中推薦了兩個小波濾波器——基於整數的5/3濾波器(5階低通濾波器和3階高通濾波器組成的濾波器組)；基於實數的9/7濾波器(9階低通濾波器和7階高通濾波器組成的濾波器組)。
於是，基於提升(lifting)結構的小波變換算法的VLSI結構研究也就成為了目前的研究熱點。這裡已經有幾種相應的VLSI結構推出，其中最為有代表性的是由臺灣大學Chung-Jr Lian等人提出的直接硬體映射結構(C.J.Lian，K.F.Chen，H.H.Chen，and L.G.Chen，「Lifting Based Discrete Wavelet Transformation Architecture for JPEG2000，」CAS2001.pp.II445-II448)和美國亞利桑那州立大學Kishore Andra等人提出的聯合方式的小波變換結構(K.Andra，C.Chakrabarti，and T.Acharya，「A VLSI architecture for lifting-basedforward and inverse wavelet transform，」IEEE Transactions on Signal processing，Vol.50，No.4，pp.966-977，April.2002)。前者的結構是根據提升(lifting)結構的小波變換算法的特點，將其直接映射相應硬體運算單元，其結構簡單易於形成流水處理。可是結構在數據延拓，以及正向變換和逆向變換的資源共享方面還有一定的缺點。後者的結構是一種摺疊的處理方式，這種結構具有較高的硬體利用效率。但是，當進行9/7小波變換時，需要將第一次計算結果反饋回輸入端，這樣增加控制的複雜度和造成數據通路流水處理間斷。
本發明提出的一維離散小波變換VLSI結構，其數據通路是基於流水線操作方式，結構包括基於流水線的多級提升(lifting)處理單元，嵌入式數據延拓控制單元，輸入/輸出控制單元。
本發明中的一維小波變換結構是對一維數據進行處理。待處理的一維數據按照奇/偶索引分別送入本發明提出的結構中，經過多級的提升(lifting)運算處理(5/3小波為2級提升操作；9/7小波為4級提升操作)，這裡每一級提升(lifting)運算對應著一個乘加單元(MAC)；經過提升(lifting)運算後分別生成小波變換後的低頻數據和高頻數據。
上述輸入/輸出控制單元，在數據的輸出端根據小波濾波器的不同，選擇相應的數據輸出。當進行5/3小波變換時，數據直接進行輸出，當進行9/7小波變換時，提升(lifting)處理後的數據需要進行重規整化處理，即低頻和高頻數據分別乘上規整化係數，然後輸出處理結果。上面是進行正向小波變換時的數據流程。
當進行逆向小波變換時，輸入數據按照低頻和高頻分為兩組分別送入處理結構中。輸入端首先進行判斷，5/3小波逆向變換時，數據直接送入進行提升(lifting)處理；當9/7小波逆向變換時，數據首先進行逆向的重規整化處理，即輸入的低頻和高頻係數分別乘以逆向的重規整化係數，然後，將逆向重規整化後的係數進行逆向提升(lifting)處理，5/3小波對應著2級逆向提升(lifting)處理，9/7小波對應著4級逆向提升(lifting)處理。每一級逆向提升(lifting)處理對應著一個乘加單元(MAC)，不過這裡的乘加單元(MAC)和正向變換時的乘加單元(MAC)具有不同的係數。提升(lifting)處理後生成原數據的奇偶索引數據。於是，可以看出正向小波變換過程和逆向小波變換過程具有不完全統一的數據通路，但是具有統一的控制邏輯。另外，結構的數據延拓部分採用了本發明中獨有的嵌入式數據延拓方法。
圖2多級提升(lifting)處理的流水線操作。
圖3每一級提升(lifting)處理對應的乘加單元結構示意圖。
圖4傳統的直接數據延拓方式。
圖5改進的嵌入時數據延拓方法。
基於流水線的多級提升(lifting)處理兩種小波變換分別對應著多級的提升(lifting)操作，這樣的多級提升(lifting)處理經過適當的安排和調度構成一個多級流水線(pipelining)處理方式。其中因為9/7小波變換時需要4級提升(lifting)處理，而5/3小波變換時僅需要2級提升(lifting)處理，於是整個處理過程是一個基於四級流水的流水線。每一級處理的數據經過一次緩存後送入下一級流水處理。當進行5/3小波變換時，將經過兩級流水處理後的數據進行結果輸出。圖2中給出了流水線處理示意圖。
流水線的每一級處理過程對應著一個乘加單元(MAC)，每個乘加單元(MAC)具有不同的計算係數。表1給出了5/3小波和9/7小波的各個流水階段對應乘加單元(MAC)的係數。可以看出，5/3小波具有規整的整數係數，因此可以移位操作來實現乘法運算。然而，9/7小波具有浮點型的係數，如果採用浮點型的運算結構，將增加結構的複雜度和設計成本。因此，本結構中採用其定點表示方式。另外，因為進行常係數乘法操作，於是可以採用係數的CSD編碼方式(K.K.Parhi，VLSI Digital Signal Processing SystemsDesignand Implementation，John Wiley Sons，1999)，將常係數的乘法操作轉變為加法操作，這樣減少了設計的複雜度。表2給出了9/7小波的各個係數對應的CSD表示形式。完成的係數的轉換處理後，這裡要介紹一下所採用的乘加單元(MAC)。這裡的乘加單元(MAC)不同於常規意義上的乘加單元。它完成了兩次加法和一次乘法操作，這裡的乘法操作已經轉變為加法處理。圖3是乘加單元(MAC)的示意圖。
在不同的小波(5/3和9/7)、不同的變換方式(正向和逆向)中，每一級提升(lifting)操作對應著不同的乘加單元(MAC)。流水線處理中，每一級輸入端的數據同時輸入到該級的乘加單元進行處理，在輸出端根據預定處理方式選擇相應結果進行輸出。所有這些控制通過8個2選1的數據選擇器來完成的，如

圖1中所示。
嵌入式數據延拓控制單元當進行小波變換時，通常需要對要處理的數據兩端進行延拓處理。圖4給出了傳統的直接數據延拓方式，表3給出了5/3小波和9/7小波的數據延拓規則。直接數據延拓方式是直接將延拓數據增加到待處理一維數據的兩端，這樣得到一個增長了的一維數據，然後再對增長了的一維數據進行小波變換處理。這種延拓方式簡單、直接，但是在硬體實現時，這種方式具有嚴重的缺點。首先，它需要額外存儲單元存儲一維數據兩端增加的延拓數據；另外，進行直接延拓處理還增加了對數據存儲單元的訪問次數；最重要的是在計算過程中增加了對延拓數據的計算，從而增加了整個處理過程的計算量。鑑於直接數據延拓方式的諸多缺點，英國人K.C.B.Tan和T.Arslan在其論文「Low power embedded extensionalgorithm for lifting-based discrete wavelet transform in JPEG2000，」ELECTRONICS LETTERS，Vol.37，No.22，pp.1328-1330，Oct.2001中，提出了基於5/3小波的嵌入式數據延拓的思想。嵌入式數據延拓的主要思想是根據延拓數據關於起始數據和末尾數據的對稱性，通過及時調整小波變換的計算過程來達到等效數據延拓處理，它將數據延拓過程嵌入到正常的小波變換處理中，因此稱為嵌入式數據延拓方式。圖5給出了嵌入式數據延拓的原理示意圖。可以看出，通過調整起始端和結尾端的數據計算過程，就能夠達到數據延拓處理，這種方式只需要增加較少的數據操作控制邏輯，但是可以避免數據延拓所需要的額外存儲單元，額外的存儲單元的訪問，以及計算延拓數據所需要的計算過程。從而，減少了硬體設計的複雜度和成本，降低了設計結構的功率消耗。
K.C.B.Tan等人給出了5/3小波的嵌入式處理方式，但是沒有對9/7小波的嵌入式延拓方式進行論述，並且沒有給出嵌入式數據延拓的VLSI實現結構。本發明中給出了9/7小波的嵌入式數據延拓的實現算法，同時結合本發明的結構特點，提出一種簡單有效的嵌入式數據延拓的VLSI結構。如圖1中的四塊橢圓內的結構。
式(1)(2)給出了K.C.B.Tan等人提出的5/3小波的嵌入式延拓算法。式(3)到式(8)給出了本發明中提出的9/7小波的嵌入式數據延拓算法。
y(2n+1)＝-k×y(2n+1)i0≤2n+1≤il-1 (7)y(2n)＝y(2n)/ki0≤2n≤il-1 (8)
其中，x(n)表示待處理的一維數據，y(n)為小波處理後的輸出結果，w(n)為9/7小波變換過程中的中間計算結果，i0表示待處理一維數據起始索引，il表示待處理一維數據結尾數據後面一個數據的索引，α，β，γ和δ分別為9/7小波變換過程中的各級提升操作中的計算係數，k為重規整化係數。嵌入式數據延拓將原來的數據計算過程分為三個計算過程，即正常數據計算過程，起始端數據延拓過程和結尾端數據延拓過程。每個計算過程對應不同的計算方法。從改進後的算法上可以看出，在嵌入式延拓算法中，延拓的處理是將對兩端延拓數據的操作映射到對中間等效的數據單元的操作來實現的，這在硬體實現結構中可以通過簡單的2選1數據選擇器來實現。圖1給出了各級提升(lifting)處理過程中對應的嵌入式數據延拓操作。通過採用8個2選1數據選擇器來控制數據流的處理過程，從而完成三個計算過程。表4給出了三個過程中，各個數據選擇器的控制情況。控制信號的產生時間是根據要處理的數據長度和進行的處理方式進行控制的。
輸入/輸出端的數據控制單元該部分主要是完成輸入端的處理時序的調整，輸出數據的控制，以及9/7小波變換時的重規整化處理或逆向重規整化處理。
當選擇偶索引延拓時，輸入端的時序需要進行適當的調整以滿足連續流水的小波處理方式，這裡通過對奇索引數據輸入端增加一級數據延遲來實現。在數據的輸出端需要根據選擇的小波濾波器，來控制相應的數據通路的輸出數據，這個控制是通過兩個2選1數據選擇器來實現的。另外，在進行9/7小波變換處理時，還需要增加重規整化處理。當進行正向9/7小波變換時，在處理數據的輸出端增加重規整化處理，即生成的低頻和高頻係數分別乘上重規整化係數；當進行逆向9/7小波變換時，在處理數據的輸入端增加逆向重規整化處理，即輸入的奇偶索引數據分別乘以逆向重規整化係數；由於重規整化係數為常數，這裡採用和提升(lifting)處理中相同的CSD表示方式，把乘法運算轉變為加法運算，減少設計的複雜度。這些操作是通過採用四個2選1的數據選擇器和四個採用加法操作的常係數乘法器來實現的。
本發明結構的性能分析本發明還對提出的結構進行了性能分析，並對處理N×M兩維數據塊時，結構的存儲單元數量，存儲單元的訪問次數，結構的數據處理能力，以及理論的功耗分析等方面和臺灣大學Chung-JrLian等人提出的直接硬體映射結構進行了比較，表5給出了具體的比較結果。其中，L是進行小波變換的級數；fclk為系統的時鐘頻率，函數f為存儲單元的能量消耗與存儲單元尺寸之間的關係函數，它主要是由製造工藝所決定。可以明顯看出，本發明中提出的結構在存儲單元的數量，存儲單元的訪問次數，結構的數據處理能力，以及理論的功耗分析等方面都有十分顯著的改進。
表1各級提升(lifting)處理對應的乘加單元的係數

表2 9/7小波的乘加單元係數的CSD編碼表示

表3 5/3和9/7小波在不同索引情況下的數據延拓情況

表4嵌入式數據延拓過程的控制

表5本發明結構的性能比較

權利要求
1.一種高速、可配置的一維5/3和9/7小波變換的VLSI實現結構。其特徵在於數據通路是基於流水線操作方式，結構包括基於流水線的多級提升處理單元，嵌入式數據延拓控制單元，輸入/輸出控制單元。
2.根據權利要求1所述的VLSI結構，其特徵在於基於流水線的多級提升處理單元中，5/3小波為兩級提升，9/7小波為4級提升，每級提升對應著一個乘加單元，提升處理後分別生成小波變換後的低頻數據和高頻數據。
3.根據權利要求2所述的VLSI結構，其特徵在於上述輸入/輸出控制單元，當進行正向小波變換時，(1)如為5/3小波正向變換，數據直接輸出；(2)如為9/7小波正向變換，低頻數據和高頻數據分別乘以規整化係數，然後再輸出結果。
4.根據權利要求2所述的VLSI結構，其特徵在於上述輸入/輸出控制單元，當進行逆向小波變換時，(1)如為5/3小波逆向變換，數據直接送入進行提升處理；(2)如為9/7小波逆向變換，數據首先進行逆向重規整化處理輸入的低頻和高頻係數分別乘以逆向的重規整化係數，然後將逆向重規整化後的係數進行逆向提升處理；5/3小波對應兩級逆向提升處理，9/7小波對應4級逆向提升處理，每級提升處理對應著一個乘加單元。
5.根據權利要求1所述的VLSI結構，其特徵在於所述的嵌入式數據延拓控制單元中，對於5/3小波數據延拓採用下述算法 對於9/7小波數據延拓採用下述算法 y(2n+1)＝-k×y(2n+1) i0≤2n+1≤il-1 (7)y(2n)＝y(2n)/ki0≤2n≤il-1 (8)
6.根據權利要求5所述的VLSI結構，其特徵在於所述的嵌入式數據延拓操作通過採用8個2選1的數據選擇器來實現。
7.根據權利要求4所述的VLSI結構，其特徵在於對9/7小波變換的重規整化處理操作通過四個2選1的數據選擇器和四個採用加法操作的常係數乘法器來實現。
全文摘要
本發明為一種高速、可配置的一維5/3和9/7小波變換的VLSI實現結構。其數據通路是基於流水線操作方式，它由多級提升(lifting)處理單元，嵌入式數據延拓控制單元，輸入/輸出控制單元組成。嵌入式數據延拓控制單元採用改進的嵌入式數據延拓算法，輸入/輸出控制單元完成了正向/逆向重規整化操作。本發明在存儲單元的數量，存儲單元的訪問次數，結構的數據處理能力，以及理論的功耗分析等方面較現有的技術都有十分顯著的改進。
文檔編號G06F9/38GK1477498SQ03129688
公開日2004年2月25日 申請日期2003年7月3日 優先權日2003年7月3日
發明者朱珂, 華林, 周曉方, 章倩苓, 朱 珂 申請人:復旦大學