[發明專利]一種并行快速傅立葉變換處理方法

有效

• 申請號: 201610052233.5
• 申請日: 2016-01-26
• 公開（公告）號: CN105718424B
• 公開（公告）日: 2018-11-02
• 發明（設計）人: 禹霽陽;汪路元;李欣;徐軻;郭麗明;馮國平;徐勇;李珂
• 申請（專利權）人: 北京空間飛行器總體設計部
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 中國航天科技專利中心 11009
• 代理人: 范曉毅

本發明提供了一種并行快速傅立葉變換處理方法，該方法將點數為N＝r^S的數據序列x(n)劃分為vr個二級數據塊，然后采用基r?FFT計算得到每個二級數據塊中的個數據的FFT結果，其中：v＝r^Z，r和S為任意整數，Z＝0、1、…或S?2，因此本發明的數據點數N具有更多的取值，可以在這些取值中選擇補零最少的方案，從而減少對存儲空間和計算時間的占用；而且本發明采用多蝶形并行計算，且并行蝶形計算單元的個數v＝r^Z，因此本發明可以根據硬件資源的配置來選擇并行度，具有較大的靈活性。

技術領域

本發明涉及FFT處理器設計技術領域，特別涉及一種并行快速傅立葉變換處理方法。

背景技術

快速傅立葉變換是通信、雷達系統中數字信號處理過程的關鍵組成，用來實現數字信號在時域和頻域之間的變換。它在實際應用中能夠實現諸如頻譜分析、數字濾波、相關處理等功能。

當前，多蝶形并行計算快速傅立葉變換基本采用原位存儲下的基2、基4結構實現，主要包括存儲器訪問地址生成、無沖突數據交換、蝶形計算等步驟。無沖突數據交換過程中，如果采用加入額外緩存的方法，會使得緩存的占用量隨著點數的增加而增加，同時大量緩存的讀寫操作會增加整個計算的時間。目前多蝶形并行計算快速傅立葉變換中，多采用存儲器無沖突訪問地址生成模塊，由此抵消掉蝶形計算前數據訪問過程中產生的沖突，在無沖突訪問存儲器的條件下進行多蝶形并行計算。

北京理工大學CN101504638號專利公開了一種可變點數流水線FFT處理器，該發明是一種可變點數流水線FFT處理器，包括第一1024點可變FFT處理模塊、旋轉因子處理模塊、第二1024點可變FFT處理模塊、選擇與控制模塊。上述四個模塊與處理器外部的中間數據存儲模塊共同完成大點數FFT的二維處理。中興通訊股份有限公司CN101847986A號專利公開了一種實現FFT/IFFT變換的電路及方法，方法為：確定迭代次數、第一和第二RAM的深度、ROM存儲器的深度；將待變換的輸入數據的前和后半部分分別存入第二和第一RAM；進行迭代蝶形運算：第首次迭代中，讀取第一和第二RAM時采用倒位序讀取，偶數次蝶形運算結果寫入第一RAM，奇數次蝶形運算結果寫入第二RAM；在其他迭代中，采用正常位序讀取第一和第二RAM，寫回RAM的方式與第一次相同；最后一次迭代采用正常順序來訪問存儲器。

上述方法主要存在以下問題：

(1)基數的單一性影響了實際應用中傅里葉變換點數的選擇

現有技術中的快速傅里葉變換在基2、基4相對應的點數選擇時，最多需要補足一倍的零以此來達到長度為2的冪次方的條件。這就使得在計算過程中增加一倍的存儲空間和一倍以上的計算時間。

(2)基數的單一性影響了實際應用中蝶形計算單元并行度的選擇

現有技術中，由于基數是2的冪次方，蝶形計算單元的并行度也要是2的冪次方才能達到計算效率最高。而在實際應用中硬件資源可能達不到這樣的要求，這種情況下采用降低并行度滿足設計要求則會顯著降低系統計算的性能。

發明內容

本發明的目的在于克服現有技術的不足，提供一種并行快速傅立葉變換處理器及處理方法，可以實現。

本發明的上述目的通過以下方案實現：

一種并行快速傅立葉變換處理方法，包括如下步驟：

(1)、對接收到的數據序列x(n)進行第一級數據分組，即將N個數據劃分為v個一級數據塊，每個所述一級數據塊包括個數據；其中，第n₂個一級數據塊中第n₁個數據為x′(n₁,n₂)＝x(n₁v+n₂)，n2＝0、1、…、v-1；N＝r^S，v＝r^Z，Z＝0、1、…或S-2，S和r為整數；