[發明專利]一種快速傅里葉變化的基2-4-8混合基蝶算器及其應用

有效

• 申請號: 201410834299.0
• 申請日: 2014-12-29
• 公開（公告）號: CN104657334B
• 公開（公告）日: 2018-12-28
• 發明（設計）人: 李麗;韓峰;于東;徐斌;潘紅兵;沙金;何書專;于宗光
• 申請（專利權）人: 南京大學
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 南京匯盛專利商標事務所(普通合伙) 32238
• 代理人: 陳揚

本發明涉及一種快速傅里葉變化的基2?4?8混合基蝶算器，包括基2單元、基4單元以及基8單元，所述基8單元包括主要由第一復數加法器、實數運算單元連接組成的前置運算單元與基4單元，所述前置運算單元通過第一寄存器與所述基4單元連接，所述基8單元、基4單元以及基2單元并接形成流水線架構。益效果為：相對于完整的基8蝶形運算器資源開銷小使用更加靈活，同時有良好的并行性來滿足高吞吐率系統的需求；基2?4?8混合基的結構使蝶算器可以像基2算法一樣可以支持2的整數次冪點的序列長度。

技術領域

本發明涉及一種應用在數字信號處理中的快速傅里葉變換數字集成電路設計，尤其是一種快速傅里葉變化的基2-4-8混合基蝶算器。

背景技術

1965年Cooley和Tukey提出快速傅里葉變換算法，利用旋轉因子的周期性和對稱性，把長序列的DFT分解成更小點數的DFT從而減少乘法次數提高計算效率。此算法一經問世就得到極大關注，并迅速發展出現了很多相關的算法。1968年Bergland對FFT的基2，基4算法進行了改進推導出了基8、基16算法。FFT算法被廣泛運用于雷達系統、圖像處理、通信系統、航天航空等領域，隨著對系統性能指標要求的提升、傳統的基2算法已不能滿足雷達、通信和電子對抗等高速處理系統的計算要求，采用高基數算法成為提高FFT處理速度的主要途徑之一。

目前，公知的快速傅立葉變換模塊多采用蝶形運算器完成運算。但是蝶形運算器的大小，蝶算器采用的算法都會對FFT模塊的性能產生影響。蝶算器越大，快速傅立葉變換運算并行度越大，FFT模塊的性能越高，同時開銷也越大，即數字電路設計所消耗的邏輯資源多、芯片面積大。蝶形運算器可以采用不同的2的整數次冪作為基，如基2、基4以及基8等算法。對于基2算法實現最為直接可以支持2的整數次冪點長度序列的FFT運算。基2算法雖然簡單且易于實現，但是在源數據序列較長的大點數FFT運算時所需要的運算級數也最多，如2的n次冪點長度的序列需要進行n級運算才能完成快速傅里葉變換。基4、基8等高基的算法可以有效減少長序列的運算技術從而提高性能，但是高基數的算法也存在一定的局限：第一，高基數算法的蝶算器設計相對復雜，如一個完整基8蝶形運算器比基2蝶算器的資源開銷大4倍以上，同時對訪存的帶寬的需求是基2蝶形運算器的4倍；第二，高基的蝶算器不能像基2算法一樣支持的2整數次冪的序列長度，而是所選用高基算法的基數的整數次冪。例如，基8算法支持的序列長度應為8的整數次冪點。當需要運算的長度越大時，高基數的FFT算法帶來的性能提升也越明顯。

發明內容

本發明目的在于克服以上現有技術之不足，提供一種對于大數據量、大點數的數據處理有很好的性能提升的快速傅里葉變化的基2-4-8混合基蝶算器，具體有以下技術方案實現：

所述快速傅里葉變化的基2-4-8混合基蝶算器，包括基2單元、基4單元以及基8單元，所述基8單元包括主要由第一復數加法器、實數運算單元連接組成的前置運算單元與基4單元，所述前置運算單元通過第一寄存器與所述基4單元連接，所述基8單元、基4單元以及基2單元并接形成流水線架構。

所述快速傅里葉變化的基2-4-8混合基蝶算器的進一步設計在于，所述基8單元的前置運算單元還包括第二寄存器，所述實數運算單元的輸入端連接復數加法器的輸出端，輸出端連接所述第一寄存器，所述第一復數加法器通過所述第二寄存器與第一寄存器連接，所述實數運算單元由兩條運算支路并接組成，每條運算支路由一個實數加法器與一個實數乘法器串接組成。

所述快速傅里葉變化的基2-4-8混合基蝶算器的進一步設計在于，所述基2單元為一個復數加法器。

所述快速傅里葉變化的基2-4-8混合基蝶算器的進一步設計在于，所述基4單元包括第一復數加法單元、第二復數加法單元以及流水線寄存器，所述每個復數加法單元由兩個復數加法器并接組成，第一復數加法單元通過所述流水線寄存器與第二復數加法單元連接。