[發明專利]一種快速傅里葉變換代碼的生成方法及裝置

有效

• 申請號: 201810823431.6
• 申請日: 2018-07-24
• 公開（公告）號: CN110750249B
• 公開（公告）日: 2021-08-20
• 發明（設計）人: 李志豪;齊霽;張邵敏;景玉超;賈海鵬
• 申請（專利權）人: 華為技術有限公司
• 主分類號: G06F8/30
• 分類號: G06F8/30;G06F17/14
• 代理公司: 深圳市深佳知識產權代理事務所(普通合伙) 44285
• 代理人: 王仲凱

1.一種快速傅里葉變換代碼的生成方法，其特征在于，包括：

獲取需要進行快速傅里葉變換FFT的數據序列以及所述數據序列的長度；

根據所述數據序列的長度確定所述數據序列的FFT分解方式，得到對應所述FFT分解方式的蝶形網絡的一個或多個級，每個級對應一種蝶形的基；

根據每一級對應的蝶形的基確定每一級中需要調用的蝶形代碼以及每一級中的所述蝶形代碼被調用的調用次數，其中，所述蝶形代碼包括一種或多種原子模板，每種原子模板的個數為一個或多個，所述原子模板是預定義對所述數據序列進行蝶形運算所需的基本的代碼；

根據每一級中的所述蝶形代碼以及每一級中的所述蝶形代碼被調用的調用次數逐級生成各個級的代碼，以得到對所述數據序列進行快速傅里葉變換的FFT代碼。

2.根據權利要求1所述的生成方法，其特征在于，

所述蝶形網絡的級數為1，相應地，所述根據每一級中的所述蝶形代碼以及所述每一級中的蝶形代碼被調用的次數逐級生成各個級的代碼包括：生成第一級的代碼，其中，所述第一級的代碼包括多次調用所述第一級的蝶形代碼的代碼，其中，調用的次數為第一級中的調用次數；

或者，所述蝶形網絡的級數為大于1的整數，相應地，所述根據每一級中的所述蝶形代碼以及所述每一級中的蝶形代碼被調用的次數逐級生成各個級的代碼包括：生成第一級的代碼，其中，所述第一級的代碼包括多次調用所述第一級的蝶形代碼的代碼，其中，調用的次數為第一級中的調用次數；后續依次針對每個級，生成當前級的代碼，其中，所述當前級的代碼包括多次調用所述當前級的蝶形代碼的代碼，調用的次數為所述當前級中的調用次數，所述當前級的蝶形代碼的輸入為前一級的輸出，所述當前級為當前需要生成代碼的級。

3.根據權利要求1或2所述的方法，其特征在于，每一級對應的蝶形的基為2，或者4，或者為不等于2的質數。

4.根據權利要求3所述的生成方法，其特征在于，一個或多個原子模板包括以下6種原子模板中的任意一個或者任意多個的組合，其中，各個原子模板涉及的各個輸入輸出都只在各個原子模板內適用，而不適用于其他原子模板：

第一原子模板：用于對原始輸入復數ORI以及累加復數SUM進行運算，輸出的結果跟通過如下方式輸出的結果相同：

對所述累加復數SUM乘以2得到新的累加復數；

對所述新的累加復數減去所述輸入復數ORI，得到輸出復數OUT；

其中，所述新的累加復數以及所述輸出復數OUT作為運算后的輸出；

第二原子模板：用于對復數IN1和復數IN2進行運算，輸出的結果跟通過如下方式輸出的結果相同：

對所述復數IN1和所述復數IN2的實部、虛部分別進行加運算，得到輸出復數OUT1；

對所述復數IN1和所述復數IN2的實部、虛部分別進行減運算，得到輸出復數OUT2；

其中，所述OUT1以及所述OUT2作為運算后的輸出；

第三原子模板：用于對復數A，復數B以及實數S進行運算，輸出的結果跟通過如下方式輸出的結果相同：

將所述復數B乘以所述實數S，得到新的復數B’；

將所述A的實部加上所述B’的虛部以得到復數Z1的實部；

將所述A的虛部減去所述B’的實部以得到所述Z1的虛部；

將所述A的實部減法所述B’的虛部以得到復數Z2的實部；

將所述A的虛部加上所述B’的實部以得到復數Z2的虛部；

其中，所述Z1以及所述Z2作為運算后的輸出；

第四原子模板：用于對復數IN1、復數IN2、旋轉因子TW的實部TWR、旋轉因子TW的虛部TWI、中間值TMP以及累加復數F進行運算，輸出的結果跟通過如下方式輸出的結果相同：

將所述IN1的實部乘以所述TW的實部并加上所述F的實部得到所述SUM的實部；

將所述IN1的虛部乘以所述TW的實部加上所述F的虛部得到所述SUM的虛部；

將所述IN2的虛部乘以所述TW的虛部得到所述TMP的實部；

將所述IN2的實部乘以所述TW的虛部得到所述TMP的虛部；

將所述SUM的實部減去所述TMP的實部得到所述OUT的實部；

將所述SUM的虛部加上所述TMP的虛部得到所述OUT的虛部；

其中，所述SUM以及所述OUT作為運算后的輸出；

第五原子模板：用于對復數IN1、復數IN2、旋轉因子TW的實部TWR、旋轉因子TW的虛部TWI、第一中間值TMP1、第二中間值TMP2、累加復數SUM以及輸出數據OUT進行運算，輸出的結果跟通過如下方式輸出的結果相同：

將復數IN1的實部乘以所述TWR得到所述TMP1的實部；

將復數IN1的虛部乘以所述TWR得到所述TMP1的虛部；

將復數IN2的虛部乘以所述TWI得到所述TMP2的實部；

將復數IN2的實部乘以所述TWI得到所述TMP2的虛部；

將所述OUT的實部加上所述TMP1的實部再減去所述TMP2的實部得到更新后的輸出復數OUT的實部；

將所述OUT的虛部加上所述TMP1的虛部再加上所述TMP2的虛部得到所述更新后的輸出復數OUT的虛部；

將所述SUM的實部加上所述TMP1的實部得到更新后的累加復數SUM的實部；

將所述SUM的虛部加上所述TMP1的虛部得到所述更新后的累加復數SUM的虛部；

其中，所述更新后的輸出復數OUT以及所述更新后的累加復數SUM為作為運算后的輸出；

第六原子模板：用于對復數A和復數B的實部、虛部進行運算，輸出的結果跟通過如下方式輸出的結果相同：

將復數A的實部加上復數B的實部得到復數C的實部；

將復數A的虛部加上復數B的虛部得到復數C的虛部；

得到輸出復數C；

其中，所述復數C作為運算后的輸出。