[發明專利]一種基于FPGA的優化FFT算法和裝置

有效

• 申請號: 201910609346.4
• 申請日: 2019-07-08
• 公開（公告）號: CN110347968B
• 公開（公告）日: 2023-06-13
• 發明（設計）人: 王海濱;王楊圣;張辰予;孫洪文;羅成名;張杰;陳正鳴
• 申請（專利權）人: 河海大學常州校區
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 張倩倩

本發明公開一種基于FPGA的優化FFT算法和裝置，涉及集成電路數字信號處理技術領域。方法包括：響應于外部輸入有待分析數據，存儲相應數據；按照預設的讀取規則讀取已存儲的待分析數據；對待分析數據進行預處理；基于預處理后的待分析數據以及預設的旋轉因子進行基2?FFT的前兩級蝶形計算；基于基2?FFT的前兩級蝶形計算結果進行基2?FFT前兩級之后的其它級蝶形計算，計算結果即為所述優化FFT算法的計算結果。本發明利用蝶形運算的前兩級旋轉因子取值有限的特性，通過預設旋轉因子對傳統的基2?FFT算法進行簡化，從而實現可由輸入序列快速得到前兩級蝶形運算的結果，且本發明能夠適用于任何2supgt;N/supgt;（N≥2）點FFT運算，實現算法的有效加速。

技術領域

本發明涉及集成電路數字信號處理技術領域，特別是一種基于FPGA的優化FFT算法和?裝置。

背景技術

為了更好的對信號進行分析，工程師們常常會使用傅里葉變換將復雜無序的信號分解為?一定頻率的正弦信號和余弦信號的疊加，然后從已知的正弦信號和余弦信號的特性出發，分?析出原來信號的某些特性。由于直接進行離散傅里葉變換(DFT)的計算復雜度太高，所以?通常會選擇使用計算復雜度較低的快速傅里葉變換(FFT)。

傳統的快速傅里葉變換(Fast?Fourier?Transformation，簡稱FFT)相對DFT算法在很大程?度上優化了信號處理時的計算復雜度，但仍存在以下問題：傳統的基2-FFT算法由多級蝶形?運算構成，而每完成一次蝶形運算都需要進行1次復數乘法和2次復數加法，這對于資源有?限的FPGA來說無疑會浪費巨大的資源；傳統的基2-FFT算法在信號采樣點數較多時，其蝶?形運算的級數也會增加較多。

在宇宙空間中存在著許多高能粒子，這些高能粒子的打擊極容易使航天器中FPGA的功?能發生錯誤。在該輻射環境中，為了降低高能粒子對電路的影響，需要盡可能的對FFT電路?在面積和速度方面進行優化。而傳統的基2-FFT算法電路倘若被高能粒子擊中，中間電路的?故障極有可能被傳播到輸出上。

發明內容

本發明的目的是，提供一種基于FPGA的優化FFT算法和裝置，可對傳統基2-FFT算法?進行加速、降低資源消耗并提高可靠性。

本發明采取的技術方案為：一種基于FPGA的優化FFT算法，包括：

響應于外部輸入有待分析數據，存儲相應數據；

按照預設的讀取規則讀取已存儲的待分析數據；

對待分析數據進行預處理；

基于預處理后的待分析數據以及預設的旋轉因子進行基2-FFT的前兩級蝶形計算；

基于基2-FFT的前兩級蝶形計算結果進行基2-FFT前兩級之后的其它級蝶形計算，計算?結果即為所述優化FFT算法的計算結果。

本發明利用蝶形運算的前兩級旋轉因子取值有限的特性，通過預設旋轉因子對傳統的基?2-FFT算法進行簡化，從而實現可由輸入序列快速得到前兩級蝶形運算的結果，且本發明能?夠適用于任何2^N(N≥2)點FFT運算，實現算法的有效加速，進而可降低高能粒子對FFT?電路的影響。

優選的，響應于外部輸入有待分析數據，將外部輸入的待分析數據的實部和虛部分別存?儲。可存儲至數據ROM。

優選的，所述預設的讀取規則為：響應于外部讀取啟動信號，利用時鐘計數器在每個時?鐘周期的上升沿讀取一個已存儲的待分析數據，直至取出全部已存儲的待分析數據，時鐘計?數器停止計數。

優選的，所述對待分析數據進行預處理包括：將待分析數據轉化為16bit二進制補碼數據?并保存為COE文件。