[發明專利]信息處理設備、其控制方法、程序及計算機可讀存儲媒體

有效

• 申請號: 200980162964.3
• 申請日: 2009-12-16
• 公開（公告）號: CN102652315A
• 公開（公告）日: 2012-08-29
• 發明（設計）人: 淺中和典
• 申請（專利權）人: 瑞典愛立信有限公司
• 主分類號: G06F17/14
• 分類號: G06F17/14
• 代理公司: 中國專利代理(香港)有限公司 72001
• 代理人: 楊美靈;朱海煜

技術領域

本發明涉及信息處理設備及其控制方法、程序和計算機可讀存儲媒體，并且具體涉及但不限于使用小容量存儲器來提供快速傅立葉變換。

背景技術

快速傅立葉變換(FFT)是計算離散傅立葉變換(DFT)及其逆的有效算法。假設???????????????????????????????????????????????是N個復數。DFT由公式定義，其中，。直接對此定義求值要求O(N²)個運算：有N個輸出X(k)，并且每個輸出要求N項之和。FFT是用O(NlogN)個運算來計算相同結果的任何方法。

（庫利－圖基算法）

庫利－圖基（Cooley-Tukey）算法是最常用的FFT算法。它遞歸地根據大小N₁和N₂的更小DFT來重新表達任意復合大小N=N₁N₂的DFT以便為高復合N（平滑數）將計算時間減少到O(NlogN)。

基2時間抽取(DIT)?FFT是庫利－圖基算法的最簡單和最常用形式。基2?DIT通過每個遞歸級將大小為N的DFT分割成大小為N/2的兩個交織DFT（因此名稱為“基2”）。基2?DIT首先計算偶數索引數和奇數索引數的傅立葉變換，然后組合那兩個結果以產生整個序列的傅立葉變換。

更明確地說，讓我們將偶數索引數x(2m)的DFT標記為X_E(k)，并且將奇數索引數x(2m+1)的DFT標記為X_O(k)，則得出：

其中，。因此，用于原始數據序列x(i)的DFT?X(k)表示為：

。

基2?DIT?DFT通過遞歸地應用上述過程到每個X_E(k)和X_O(k)而得以實現。

圖1示出基2?DIT-FFT的信號流程圖(N=16)。如圖1中所示，DIT-FFT包括比特反轉運算（bit-reverse?operation）和多個蝶式運算（butterfly?operation）。

比特反轉運算是置換輸入數據序列的運算。在置換期間，輸入數據序列被分割成偶數索引數據序列和奇數索引數據序列，并且隨后奇數索引數據序列級聯到偶數索引數據序列。即，在此級聯后，生成級聯的數據序列。接著，為級聯數據序列的第一半和第二半遞歸運行類似的運算。此處所述置換對應于將輸入數據序列重新排序，使得其索引由二進制表示中的表示的數據序列被置換到的位置。為此，此置換稱為“比特反轉”運算。圖2示出比特反轉運算的示例(N=128)。例如，在圖1中，諸如、、等每對輸入數據序列在比特反轉運算中相互置換。

圖3示出基2?DIT?FFT的蝶式運算。在圖3的蝶式運算中，根據以下公式，通過預確定系數W，使用輸入數據A和B計算輸出數據P和Q：

P?=?A?+?WB

Q?=?A?-?WB

其中，W的定義已經在上面描述。如圖1中所示，給定FFT包括多個上述蝶式運算。例如，在圖1中的0級運算中，得出：

，，

，，

，，

，，

，，

，，

，，以及

，。

如本領域技術人員所熟知的一樣，可以用許多其它形式來實現FFT。例如，可通過在頻率中抽取樣本數據序列而不是在時間中抽取它們來實現基2?FFT。圖4示出基2頻率抽取(DIF)?FFT的信號流程圖(N=16)。如圖4中所示，DIF?FFT也包括比特反轉運算和多個蝶式運算，而DIF-FFT的蝶式運算由圖5示出。