[發明專利]一種FFT實現裝置和方法

有效

• 申請號: 201410502055.2
• 申請日: 2014-09-26
• 公開（公告）號: CN104268124B
• 公開（公告）日: 2017-07-07
• 發明（設計）人: 熊春林;王建;王杉;魏急波;陳彬;張康俐
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F17/14
• 分類號: G06F17/14;G06F9/38
• 代理公司: 北京集佳知識產權代理有限公司11227
• 代理人: 王寶筠

技術領域

本發明屬于信號與信息處理技術領域，尤其涉及一種FFT(Fast Fourier Transform，快速傅里葉變換)實現裝置和方法。

背景技術

FFT作為DFT(Discrete Fourier Transform，離散傅里葉變換)的高效計算方法，在數字信號處理領域發揮著重要作用，用于實現OFDM(Orthogonal Frequency Division Multiplexing，正交頻分復用)信號的調制和解調。

目前，FFT的硬件實現主要采用并行流水線結構來滿足實際系統對吞吐量和處理能力的需求。典型的并行流水線結構包括MDC(Multipath Delay Commutator，多路延遲換向)前饋方案和MDF(Multipath Delay Feedback，多路延遲反饋)反饋方案。針對需進行FFT運算的N點序列x，MDC前饋結構和MDF反饋結構均需要采用P個基于流水線結構的計算單元對x的P條并行輸入支路進行支路內FFT并行計算，硬件資源開銷較大。

發明內容

有鑒于此，本發明的目的在于提供一種FFT實現裝置和方法，以克服現有FFT并行流水線結構實現方案的硬件資源開銷較大的問題，進而為高質量的通信服務提供支持。

為此，本發明公開如下技術方案：

一種快速傅里葉變換FFT實現裝置，包括支路內FFT計算模塊、數據旋轉模塊和支路間FFT計算模塊，其中：

所述支路內FFT計算模塊，用于對N點序列x的P條輸入支路并行執行S點FFT變換，以得到Τ_SX，其中，S＝N/P，T_S為S點DFT變換矩陣，X表示S×P維的輸入數據矩陣，所包含的P列與序列x的P條輸入支路一一對應，N≥P且N,P為不小于1的自然數；

其中，所述支路內FFT計算模塊包括個基于流水線結構的計算單元以及P個數據排序單元，所述計算單元與所述數據排序單元之間以一對二的映射關系相連，每個由所述計算單元與相應的兩個數據排序單元組成的模塊結構用于采用以下方式同時處理兩條輸入支路的數據流：

對于正向輸入的數據流，先對其進行S點的按頻率抽取DIF FFT運算，再將運算結果轉換為倒位序形式；對于逆向輸入的數據流，先將其轉換為倒位序形式，再對倒位序形式的數據流進行S點的按時間抽取DIT FFT運算；

所述數據旋轉模塊，用于采用預先設定的N個旋轉因子對所述支路內FFT計算模塊的各輸出數據進行支路間并行的加權操作，實現數據旋轉，以得到其中和分別表示S維和P維的對角矩陣，D為由所述N個旋轉因子構成的S×P維矩陣，表示兩個矩陣的Hadamard積；

所述支路間FFT計算模塊，用于對的各行進行P點FFT變換，以得到通過P條支路并行輸出的序列x的FFT變換結果其中T_P為P點DFT變換矩陣，Y表示S×P維的FFT輸出矩陣，該矩陣的P列與所述的P條輸出支路一一對應。

上述裝置，優選的，所述旋轉因子為e^-j2πuv/N，其中，u∈{0,1,…,P-1}，v∈{0,1,…,S-1}。

上述裝置，優選的，所述基于流水線結構的計算單元包括級依次相連接的計算子單元，計算子單元包括復數加法器、復數乘法器、復移位寄存器組與數據選擇器。

上述裝置，優選的，在每條支路數據流對所述計算子單元中乘法器的利用率高于50％時，所述計算子單元采用TypeⅠ結構對其包括的復數加法器進行復用，所述TypeⅠ結構包括一個Radix-2蝶形運算單元、兩組復移位寄存器以及六個數據選擇器，其中第k(k∈{1,…,log₂(N/P)})級計算子單元所對應的復移位寄存器長度為所述Radix-2蝶形運算單元包括一個復數加法器和一個復數減法器；在TypeⅠ結構內部，每組移位寄存器的輸入端口各與一個數據選擇器相連，用于切換不同的數據流送入移位寄存器進行緩存；兩組移位寄存器的輸出端口以及計算子單元的兩個數據輸入端口各利用一個數據選擇器連接至Radix-2蝶形運算單元，以此實現兩路數據流對蝶形運算單元的復用；蝶形運算單元的一條輸出支路直接反饋回相應的復移位寄存器，另一條輸出支路則通過兩個數據選擇器連接到計算子單元的兩個數據輸出端口上。