[發明專利]一種基于FPGA的基2-2快速傅里葉變換硬件設計方法

有效

• 申請號: 201910978042.5
• 申請日: 2019-10-15
• 公開（公告）號: CN110765709B
• 公開（公告）日: 2023-08-29
• 發明（設計）人: 張為;駱陽
• 申請（專利權）人: 天津大學
• 主分類號: G06F30/32
• 分類號: G06F30/32;G06F17/14
• 代理公司: 天津市北洋有限責任專利代理事務所 12201
• 代理人: 程毓英

本發明涉及一種基于FPGA的基2?2快速傅里葉變換硬件設計方法，由四級相似的蝶形單元、旋轉因子乘法器模塊、正序輸出模塊和控制模塊組成：每級蝶形單元電路結構和工作方式均相似，只是其中的移位寄存器深度按等比數列方式依次遞減；蝶型單元，其作用是對輸入數據的實部和虛部進行加減運算，運算結果進入后面的旋轉因子乘法器單元，實現數據與旋轉因子相乘的功能，其中奇數級進入簡單旋轉因子乘法器單元，而偶數級進入通用旋轉因子乘法器單元，其中第四級運算之后的旋轉因子都為1；正序輸出模塊通過比特反位的方式將最終數據結果重新排序，使其按照正確的順序輸出。

技術領域

本發明屬于超大規模集成電路(Very?Large?Scale?Integration，簡稱VLSI)設計范疇，設計出一種基于現代FPGA技術特點的基2²算法結構的快速傅里葉變換的硬件實現結構。

背景技術

快速傅里葉變換(Fast?Fourier?Transform，FFT)由離散傅里葉變換(DiscreteFourier?Transformation,DFT)發展而來，已經成為信號處理中最重要的算法之一，在通信、濾波以及數字頻譜分析等領域都有著廣泛應用。為滿足數字信號處理的實時性需求，人們已經提出許多算法和硬件結構，來提高處理速度以及減少硬件資源的使用情況。

目前主要有Good-Thomas算法、Winograd算法、CORDIC算法以及Cooley-Tukey算法四種形式。其中Cooley-Tukey算法應用最多，該算法于1965年被J.W.Cooley和J.W.Tukey提出，它利用旋轉因子的特性，將一維長序列的DFT轉換為容易計算的二維或多維DFT，從而減少運算量。分解的基數越高，運算量越少，但蝶形結構越復雜而不易實現。緊接著G.Sande和J.W.Tukey又提出了快速頻域抽取(Decimation?In?Frequency,DIF)基2算法，使得FFT得到了迅速的發展，其應用成為可能，開啟了數字信號處理的新紀元。1996年瑞典隆德大學的Prof.He在論文《ANew?Approach?to?Pipeline?FFT?Processor》^[1]中綜合了高基數算法硬件消耗少和基2算法易于實現的優點提出了基2²-FFT算法，其以運算量小、蝶形運算簡單等優勢，一經提出便得到了迅速發展，此算法的提出是FFT硬件架構設計的里程碑。

目前FFT處理器的典型處理方式主要有順序處理，流水線處理，并行處理和陣列處理四種，這幾種處理方式的硬件消耗依次增加，運算速度也依次提升，綜合折中考慮這兩個因素，流水線處理方式有較大優勢。它是把一個重復的過程分解為幾個獨立并行的子過程，每一級都使用一個獨立的蝶形運算單元和存儲單元，用它們來完成這一級所有數據的計算和保存工作，各蝶形運算單元之間按照順序工作。上世紀70年代開始至今，流水線型FFT架構發展出兩種常用結構：一種是串行流水線結構，這種結構每個時鐘周期處理1個采樣點數據，主要有單路延遲反饋結構(Single-path?Delay?Feedback,SDF)和單路延遲交叉結構(Single-path?Delay?Commutator,SDC)；另一種是并行流水線結構，這種結構每個時鐘周期處理多個采樣點數據，主要有多路徑延遲反饋結構(Multi-path?Delay?Feedback,MDF)和多路延遲交叉結構(Multi-path?Delay?Commutator,MDC)。