DOT快速算法及其通用架構設計

黃 海，劉紅雨，邢 琳，那 寧，李春寶

(1.哈爾濱理工大學 軟件與微電子學院，哈爾濱 150080；2.哈爾濱理工大學 計算機科學與技術學院，哈爾濱 150080)

0 引 言

DOT主要分為兩大類，即離散非正弦類正交變換和離散正弦類正交變換。其中正弦類一直是數字信號處理領域的研究熱點，主要包括離散 Hartley 變換(DHT)、離散傅里葉變換(DFT)、離散余弦變換(DCT)、和離散正弦變換(DST)等[1]。

為了滿足圖像和視頻領域的要求，許多正交變換快速算法被提出。最早出現的快速算法大多是通過計算FFT間接得到其他正交變換[2-3]，由于FFT算法本身存在許多的復數乘法，因此這種方法總有一定的局限性。隨后，許多利用矩陣分解來計算正交變換的方法相繼被提出[4-5]，雖然很大程度上降低了計算復雜度，但是難于擴展到大點數DOT，并未得到廣泛使用。為了實現算法的可擴展性，許多針對序列長度N=2n和N≠2n的DOT快速算法相繼被提出[6-7]。如基-r的DOT快速算法、基于混合基DOT快速算法，以上計算序列長度N≠2n的DOT快速算法不具有通用性且算法計算復雜度較高。相比之下，對于序列長度為N=2n的DOT快速算法多是采用分治策略[8]，通過奇偶分解法將長序列分解成兩個大小相等的短序列，之后再利用變換核函數自有的特點，進而降低了計算復雜度。但多數都是基于乘法器的，不易于VLSI的實現，所以也并未得到廣泛應用。在此基礎上，文[9]提出一種通過向量編碼來計算DOT的快速算法,文[10]一種基于分裂基的DOT快速算法。歸納以上DOT快速算法，都存在以下問題：許多算法都是針對具體點數的DOT，沒有考慮到可擴展性；過于追求降低算法復雜度，而忽略了算法的VLSI實現的。

現如今，人們對圖像、視頻的處理速度以及質量要求越來越高，一種正交變換編碼已經不能滿足需求[11-12]。將多種正交變換相互結合，充分發揮各自的優點，已經勢在必行。上述方法的實施關鍵是正交變換通用架構的設計。目前也存在許多的通用架構，Chiper 等提出基于存儲器的DCT-DST通用架構[13]；Wu 等提出一種低運算復雜度、低硬件復雜度的DCT-IDCT的通用架構[14]；劉媛媛等提出一種立體類蝶形運算的DCT-IDCT通用架構[15]；Wang等通過數學公式重構了FFT和DCT的公式，并設計了FFT-IFFT-DCT-IDCT通用架構[16]；Singh等提出了一種基于圖像壓縮的DCT-IDCT通用架構[17]；Feng等提出一種基于自適用編碼CORDIC的低功耗、高PSNR的DCT-IDCT通用[18]架構。以上通用架構雖然可以實現多種正交變換，但存在以下缺點：硬件復用率比較低，控制電路比較復雜，不同的正交變換的變換核函數不同。

本文通過奇偶分解法，提出了一種可實現任意2的冪次點數的基于CORDIC的基-2DOT快速換算法，其變換核函數是旋轉角度為等差序列的CORDIC單元。該算法利用變換核函數固有的特性降低了計算復雜度，具有易于VLSI硬件實現、硬件復雜度低、可擴展性強、易于流水線設計、易于模塊化設計等優點。在該算法的基礎上，設計了一種DOT通用架構，該架構可以同時實現DHT、DFT、DCT、IDCT、DST、IDST六種正交變換，且具有硬件復用率高、不同類型的DOT變換核函數相同、可擴展性強等優點。

1 基于CORDIC的DOT快速算法研究

1.1 基于CORDIC的基-2DHT快速算法研究

1.1.1 基-2DHT快速算法推導

DHT的計算見式(1)。

(1)

先按照n的奇偶把信號分成以下兩組，

(2)

則DHT的計算公式可以重新寫成：

(3)

其中，k=0,…,N-1。

(4)

其中YH(k)，ZH(k)分別表示N/2點DHT，且周期為N/2。

由于，

(5)

將式(3)重新寫為：

(6)

即，N點DHT被分解成N/2點DHT。

由式(6)可得式(7)。

(7)

即,

(8)

其中，

(9)

可以看出，N點DHT最終可以分解為2點DHT。因此將該算法定義為基于CORDIC的基-2 DHT快速算法，該算法可以擴展到任意N=2n點DHT。此外，從式(9)可以看出N點DHT的變換核為：旋轉角度為等差序列的CORDIC運算單元。對于VLSI硬件實現而言，由于該算法中只有加減法和CORDIC運算單元，而CORDIC運算單元VLSI實現只需要移位和加法，因此非常易于VLSI實現。

1.1.2 基-2DHT快速算法的信號流圖

根據上述算法，可以得到N點DHT快速算法流程圖，如圖1所示。

圖1 N點DHT快速算法流程圖Fig.1 Signal flow of the N-point DHT

1.1.3 基-2DHT快速算法性能分析

本文提出的基于CORDIC的DHT快速算法，是將高階DHT分解為低階DHT，從而簡化算法，有效降低算法的復雜度。計算N點DHT可以通過兩個N/2點DHT，N/4-1個CORDIC運算單元以及N次加法來實現。因此計算N點DHT需要的CORDIC運算單元數及加法如式(10)所示：

(10)

為了對本文提出的算法進行評估，將本文的算法與現有的算法[2,4,6]在算法復雜度，是否易于流水線設計，可擴展性進行了比較。比較結果如表1所示。

表1 本文算法與現有的DHT快速算法比較結果Tab.1 Comparisons among the proposed algorithm and the existed DHT fast algorithms

1.2 基于CORDIC的基-2DFT快速算法研究

1.2.1 基-2DFT快速算法推導

(11)

1.2.2 基-2DFT快速算法的信號流圖

根據上述算法，可以得到N點DFT快速算法流程圖，如圖2所示。

圖2 N點DFT快速算法流程圖Fig.2 Signal flow of the N-point DFT

1.2.3 基-2DFT快速算法的信號流圖

本文提出的基于CORDIC的DFT快速算法,在現有的FFT算法基礎上，將復數乘法轉化成CORDIC運算單元，有效降低算法的復雜度且易于VLSI實現。為了對本文提出的算法進行評估，將本文的算法與現有的算法[9-10]在算法復雜度，是否易于流水線設計，可擴展性進行了比較。比較結果如表2所示。

表2 本文算法與現有的DFT快速算法比較結果Tab.2 Comparisons among the proposed algorithm and the existed DFT fast algorithms

此外，作者在文[19]中已經推導出基于CORDIC的基-2 DCT-Ⅱ、基-2 DST-Ⅱ、基-2 DST-Ⅲ/DST-Ⅲ的快速算法并實現。

2 基于CORDIC的正交變換通用架構設計

2.1 CORDIC設計

由于CORDIC算法只有加減和移位操作，因此非常易于硬件實現。且具有VLSI實現的規則化、模塊化等要求；具有規則的數據流，易于流水線實現等優勢。目前，CORDIC的實現方式主要有重疊結構和非重疊結構兩種。重疊結構節省硬件資源、面積以及功耗比較低，但是難于流水線設計、運算速度較慢、吞吐率低。而非重疊結構，解決了迭代結構的弊端，但是存在精度和迭代的次數相互矛盾問題。本文采用第二種結構，并基于此進行完善與改進，改善其存在的問題。

對于CORDIC算法，為了將一個向量(x,y)旋轉角度θ，θ分解為一系列可通過移位操作來實現的角度的加權和，其計算公式

(12)

則向量旋轉可通過以下迭代方式實現。

xi+1=xi-σi·yi·2-i

yi+1=yi+σi·xi·2-i

(13)

在此基礎上還需要將所得結果乘以比例因子，如式(14)所示：

xi+1=xi(1+γi·Fi)

yi+1=yi(1+γi·Fi)

(14)

其中：γi=(0,1,-1),Fi=2-i。

由此可知CORDIC的計算只需要移位和加法操作。由于DOT計算過程中使用的CORDIC是固定旋轉角度且是等差序列，在實現過程中有一些角度是可以忽略的。將所需旋轉的固定角度進行角度編碼，用最小的旋轉次數得到最佳的旋轉結果，這也是與傳統COEDIC的最大區別。表3給出了3種旋轉角度的角度編碼，包括迭代的次數和取值。

表3 3種旋轉角度的角度編碼[17]Tab.3 Angle coding for three rotation angles[17]

2.2 CORDIC模塊化及復用設計

本文提出的算法是以旋轉角度為等差序列的CORDIC為變換核函數，根據這一特點，采用三角函數，可以對不同旋轉角度的CORDIC進行模塊化設計，可以大幅度減少CORDIC運算單元的數量。

以16點DOT為例，按照本章提出的算法，共有24種不同類型的CORDIC運算單元，如表4所示。按照文[19]中公式(3-7),可以將CORDIC較少為14種，除了-π/32…-7π/32以外還有-π/8…-7π/8，利用文[19]中公式(3-10)旋轉-3π/32可通過旋轉-π/16和-π/32得到、旋轉-5π/32可通過旋轉-π/8和-π/32得到，如式(15)所示；利用文[19]中公式(3-8)旋轉-3π/16可通過旋轉-π/16之后再進行一次蝶形運算得到、旋轉-7π/32可通過旋轉-π/32之后再進行一次蝶形運算得到，如式(16)所示；其中旋轉角度為-π/4、-π/2、-3π/4的CORDIC值均為常數，利用文[19]中公式(3-10)可以間接計算-3π/8、-5π/8、-7π/8，如式(17)所示。從式(15)、式(16)和式(17)可以看出，采用三種CORDIC即旋轉角度分別為-π/8、-π/16、-π/32就可以實現16點DOT的計算。

對于16點DOT，計算旋轉角度為-3π/32、-5π/32、-3π/16、-7π/32、-3π/8、-5π/8和-7π/8的CORDIC流程圖如圖3所示。可以看出，對于16點DOT只需要三種類型的CORDIC(-π/8)、CORDIC(-π/16)和CORDIC(-π/32)。通過復用設計思想，可以進一步降低了硬件復雜度[20]。

(15)

(16)

(17)

表4 N點DOT用到的旋轉角度Tab.4 Rotation angles for 16-point DOT

圖3 旋轉角度為-3π/32、-5π/32、-3π/16、-7π/32、 -3π/8、-5π/8和-7π/8 CORDIC 流程圖Fig.3 Signal flow of the CORDIC with -3π/32、 -5π/32、-3π/16、-7π/32、-3π/8、-5π/8 and -7π/8 angle rotation

2.3 16點DOT通用架構設計

本節以16點DOT為例介紹其通用架構設計。通過上述分析可知，對于16點DOT可以通過三種類型的CORDIC實現，不同的正交變化可以選擇不同的CORDIC及相應的互連網絡，16點DOT通用架構如圖4所示。通用架構包括蝶形運算陣列、CORDIC陣列(含互連網絡)、多路選擇器陣列和控制器。

圖4 16點DOT通用架構Fig.4 Unified architecture of the 16-point DOT

3 功能仿真與實驗結果分析

3.1 DOT通用架構的功能仿真

為了驗證DOT通用架構的功能是否正確，對設計的架構進行進行Verilog HDL建模，以DHT算法為例，利用Modelsim對DHT算法進行功能仿真，仿真結果如圖5所示，圖中clk為整個程序的時鐘控制信號，信號open為整個程序的開始信號，open為1時整個程序開始運行，信號reset為復位信號，reset為0時進行復位，o0～o15為輸出信號。通用架構可以通過控制信號sel來控制不同DOT算法的切換。當控制信號為1時，DOT通用架構執行DHT算法。與此同時，將測試文件產生的隨機數輸入到Matlab，并得到正確結果如圖6所示。將Modelsim的仿真結果和Matlab產生的結果相比較，從仿真結果可以看出，本文提出的快速算法在誤差允許的范圍內，與正確結果基本保持一致。

圖5 DOT通用架構的DHT算法仿真結果Fig.5 Accuracy of the 16-point DHT and DFT

圖6 DHT的Matlab計算結果Fig.6 Matlab calculation results of DHT

3.2 DOT通用架構性能分析

本節對所設計的通用架構與現有的通用架構[14-17]在變換的種類、運算單元、控制復雜度、模塊化及流水線實現等方面進行了比較。表5給出了比較結果。

1)變換種類：本文提出的架構可同時實現DHT、DFT、DCT、IDCT、DST、IDST六種正6種DOT的變換，而文[14]～[17]可實現的變換種類都少于本文提出的架構。

2)控制復雜度：本文提出的架構采用多路選擇器即可實現不同正交變換間的切換。與文[14]需要較復雜的存儲單元、文[15]需要特定的處理單元、文[16]需要地址發生器相比，其控制復雜度較低。

表5 與現有通用架構的性能比較Tab.5 Comparison with existing architectures

3)模塊化：本文提出的通用架構采用的CORDIC，其旋轉角度為等差序列，可以利用三角函數大幅度降低CORDIC的類型，有效的降低了硬件復雜度，使設計高度模塊化，同時非常適合VLSI的流水線設計。

此外，本文提出的架構在預處理、流水線實現等方面由于其他架構。

4 結 論

針對傳統正交變換，本文提出一種新型的基于CORDIC的DOT快速算法，該算法采用分治策略以及變換核固有的特性，大幅度降低了算法的復雜度，在算法復雜度、可擴展性等性能指標明顯優于現有算法。再此基礎上，設計出一種DOT的通用架構。該架構可以實現多種正交變換，具有高度的可擴展性、模塊化、規律性，并且能夠實現高效流水線技術。