3.3 一维快速傅里叶变换 一、基本思想 其中Wux为变换矩阵元素； 由变换矩阵元素可见，利用矩阵元素的周期性与对称性之后，变换矩阵中许多元素相同。换言之，变换矩阵与输入信号相乘过程中存在着不必要的重复计算。 改进DFT的关键： 利用变换矩阵元素的周期性与对称性，合理安排（即避免）重复出现的相乘运算，就能显著减少计算工作量。 二、一维FFT FFT重要环节 重新安排计算次序 矩阵分解 1、重新安排计算次序 设N=2n，经过n步计算后，其结果为fn(k)= F(l)其中k 的二进制表示为 2、矩阵分解 当N=2n，将变换矩阵分解成n个矩阵，使每个矩阵中每一行仅含有两个非零元素。有两种分解方法： 一种是按时间分解 一种是按频率分解 下面仅介绍按时间分解的FFT算法 u和x的二进制表示为： 矩阵表示 3、FFT流程图 N=8时FFT流程图 (1) 整个流程需要的计算步数为n=log2N (N=2n)； (2) 在第r步计算中，要乘的因子为 (3) 第r步计算中有2r-1个组，每组有（N/2r-1）个元素，每组的W因子各不相同，且每组只有一种类型的W因子，此因子在组中上一半为正，下一半为负。 (4) 对比DFT与IDFT的定义式，只要将上述FFT算法中W因子用其共轭代替，并将最后结果乘以1/N，就是计算IDFT即离散傅里叶反变换的快速算法。 (5) 在每步计算中，需要的乘法次数N/2，加法次数为N，因此FFT的总计算量为： 乘法次数为 加法次数为 而直接计算DFT的计算量为：乘法次数为N2，加法次数为N(N-1)。当N=2048时，DFT需要4194304次乘法运算，而FFT只需要11264次乘法运算，二者之比为