[發(fā)明專利]一種高效離散傅里葉變換方法

在審

• 申請?zhí)枺?/td>: 201510726103.0
• 申請日: 2015-10-30
• 公開（公告）號: CN105302774A
• 公開（公告）日: 2016-02-03
• 發(fā)明（設計）人: 劉憲軍;陳俊霖;向川云;彭艷
• 申請（專利權(quán)）人: 中國電子科技集團公司第二十九研究所
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 成都九鼎天元知識產(chǎn)權(quán)代理有限公司 51214
• 代理人: 錢成岑

技術(shù)領(lǐng)域

本發(fā)明涉及一種高效離散傅里葉變換方法，特別是涉及一種適用于一種高效離散傅里葉變換方法。

背景技術(shù)

離散傅立葉變換(DFT)是數(shù)字信號處理領(lǐng)域中遇到的最常用，功能最強大的處理方法之一，是數(shù)字信號處理的核心。利用DFT變換，可以實現(xiàn)信號與系統(tǒng)的分析與綜合。同時，許多算法，如相關(guān)、濾波、譜估計等也可以轉(zhuǎn)化為DFT來實現(xiàn)，因此DFT在許多工程領(lǐng)域都已獲得了許多應用。

離散傅立葉變換的目的是把信號由時域變換到頻域，從而可以在頻域分析處理信息。同時得到的結(jié)果也可以再由離散傅立葉逆變換到時域。雖然離散傅立葉變換有著明確的物理意義，是確定時域序列的頻率成分的最直接的數(shù)學過程，也便于計算機進行處理，但它的運算效率非常低，對實時問題處理意義不大，因此長期以來并沒有得到真正廣泛的應用。

發(fā)明內(nèi)容

本發(fā)明要解決的技術(shù)問題是提供一種資源利用率低，運算效率低，計算更高效的離散傅里葉變換方法。

本發(fā)明采用的技術(shù)方案如下：一種高效離散傅里葉變換方法，具體方法為：

一、確定要完成的N點向量X＝[x₁x₂x₃…x_N-1x_N]的DFT運算的N分解需要經(jīng)過的迭代次數(shù)k(k＝1,2,3,4…)；所述N為奇數(shù)，N＝3,5,7…；

二、構(gòu)造旋轉(zhuǎn)因子指數(shù)矩陣S：矩陣中各元素定義為S(a，b)＝(a*b)modN，其中a＝1,2,3…N-1；b＝1,2,3…N-1；

三、搜索原根m：找出一個原根m，使得當g＝1,2,3…N-2時，m^gmodN≠1；當g＝N-1時，m^gmodN＝1；

四、構(gòu)造P向量：利用步驟三搜索到的原根m，P向量的各個元素為P(i)＝m^i-1modN，其中i＝1,2,3…N-1；

五、按照P向量的元素順序，將自然向量[123…N-1]通過元素互換的方式重新排列，得出互換位置關(guān)系，根據(jù)該互換位置關(guān)系，將旋轉(zhuǎn)因子指數(shù)矩陣S的行的對應位置關(guān)系進行行列互換，并且，將旋轉(zhuǎn)因子指數(shù)矩陣S的列的對應位置關(guān)系進行互換，得到新的旋轉(zhuǎn)因子指數(shù)矩陣S'；

六、構(gòu)造對角線元素相同的矩陣R：將矩陣S'的各列，按照兩兩配對的原則進行互換，互換后的矩陣為對角線元素相同的矩陣R；

七、DFT降階運算：將步驟六得到的對角線元素相同的矩陣R的第1行向量[r₁r₂r₃…r_N-1]取出，分別進行向量及旋轉(zhuǎn)因子ω^k構(gòu)成的的進行N-1點的DFT變換運算；其中，ω^k＝e^-j2pk/N，k＝1,2,3…N-1；降階運算后，向量X的DFT運算所含元素個數(shù)由奇數(shù)個變?yōu)榕紨?shù)個；

八、判斷是否需要蝶形化簡，是則進入下一步，否則進入步驟十；如果降階后元素個數(shù)為2，則不再需要蝶形化簡，如果降階后的偶數(shù)個元素大于2，如4、6或8，則需要對降級后的DFT運算向量進行蝶形化簡；