日志

快速傅里叶变换FFT

已有 1262 次阅读2006-7-9 15:39 |个人分类:硬件|系统分类:嵌入式系统

快速傅里叶变换FFT

(1) FFT不是一种新的变换，而是DFT的快速算法。

(2) 直接DFT计算的复杂度：

计算DFT需要：次复数乘法；次复数加法。

(3) FFT算法推导：

(i) 第L次迭代中对偶结点值的计算公式为：

，是循环控制变量。

(ii) 对偶结点的关系如图2所示：

图2 FFT中对偶结点关系图

(i) 旋转因子：被称为旋转因子，可预先算好并保存。

(ii) 整序：经过r次迭代后，得到结果，实际结果应是，所以流程的最后一步是按下标的正常二进制顺序对结果进行整序。

(4) FFT算法特点：( )

(i) 共需次迭代；

(ii) 第次迭代对偶结点的偶距为，因此一组结点覆盖的序号个数是。

(iii) 第次迭代结点的组数为。

(iv) 可以预先计算好，而且的变化范围是。

(5) FFT算法流程：( )

(i) 初始化：；

(ii) 第次迭代：

(a) 下标控制变量初始化；

(b) “结点对”的个数初始化 ;

(c)

Ø 按对偶结点对的计算公式进行置位运算，得到和的值；

Ø ；；

Ø 跳过已经计算过的结点(即上面所对应的那些结点)：；