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

有效

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

1.一種實現優化FFT計算的FPGA，其特征是，包括：

待分析數據接收模塊，用于響應于外部輸入有待分析的數據，存儲相應數據；

待分析數據讀取模塊，用于按照預設的讀取規則讀取已存儲的待分析數據；

預處理模塊，用于對待分析數據進行預處理；

簡化計算模塊，用于基于預處理后的待分析數據以及預設的旋轉因子進行基2-FFT的前兩級蝶形計算，其中，所述預設的旋轉因子中，第一級蝶形運算的旋轉因子為1，第二級蝶形運算的旋轉因子為1或-j，-j為實部是0，虛部是-1的復數；

以及結果計算模塊，用于基于基2-FFT的前兩級蝶形計算結果進行基2-FFT前兩級之后的其它級蝶形計算，計算結果即為優化FFT算法的計算結果；

其中，待分析數據接收模塊響應于外部輸入有待分析數據，將外部輸入的待分析數據的實部和虛部分別存儲；

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

所述預處理模塊對待分析數據進行預處理包括：將待分析數據轉化為16bit二進制補碼數據并保存為COE文件；以及，基于讀出的待分析數據進行無故障注入條件下的FFT計算，得到參考輸出結果數據，并將參考輸出數據轉化為16bit二進制補碼數據，保存為COE文件；且兩類需要保存的COE文件分別存儲于不同數據ROM中，用于在有故障注入影響下的算法結果驗證；

所述簡化計算模塊基于預處理后的待分析數據以及預設的旋轉因子進行基2-FFT的前兩級蝶形計算包括：

以預處理后的待分析數據作為輸入數據序列，對輸入數據序列進行二進制數倒序排列；

定義N為大于等于2的正整數，對于任意n＝2^N點的FFT運算，將倒序排列后的輸入數據序列x(0)～x(n)分為n/4組；

基于每個分組的輸入數據序列分別進行4點FFT運算的前兩級蝶形計算：

利用基2-FFT算法獲得輸出數據與輸入序列之間的關系數據，所述關系數據包括第一級旋轉因子和第二級旋轉因子；

利用預設的旋轉因子取值替換關系數據中的兩級旋轉因子，得到輸出數據與輸入序列之間的簡化關系數據，進而得到第二級蝶形運算的輸出數據，即為基2-FFT算法前兩級蝶形運算的計算結果；

其中，定義分組后的4點FFT輸入數據序列為x(0)～x(3)，定義x(0)+x(2)＝A，x(1)+x(3)＝B，x(0)-x(2)＝C，x(3)-x(1)＝D，x(1)-x(3)＝E，預設的第一級旋轉因子為第二級旋轉因子則該4點FFT運算的輸出序列，即相應輸入數據序列組對應的基2-FFT前兩級蝶形運算結果為：

2.根據權利要求1所述的實現優化FFT計算的FPGA，其特征是，基2-FFT算法前兩級蝶形運算的旋轉因子根據以下公式計算得到：

式中，為N點FFT運算中第m+1級的旋轉因子，

對于一個4點FFT的前兩級基2-FFT蝶形運算，分解為兩個2點DFT后，

m＝0對應的第一級蝶形運算的旋轉因子m＝1對應的第二級蝶形運算的旋轉因子和分別為1和-j。