3.3 一维快速傅里叶变换 一、基本思想 其中Wux为变换矩阵元素； 由变换矩阵元素可见，利用矩阵元素的周期性与对称性之后，变换矩阵中许多元素相同。换言之，变换矩阵与输入信号相乘过程中存在着不必要的重复计算。 改进DFT的关键： 利用变换矩阵元素的周期性与对称性，合理安排（即避免）重复出现的相乘运算，就能显著减少计算工作量。 二、一维FFT FFT重要环节 重新安排计算次序 矩阵分解 1、重新安排计算次序 设N=2n，经过n步计算后，其结果为fn(k)= F(l)其中k 的二进制表示为 2、矩阵分解 当N=2n，将变换矩阵分解成n个矩阵，使每个矩阵中每一行仅含有两个非零元素。有两种分解方法： 一种是按时间分解 一种是按频率分解 下面仅介绍按时间分解的FFT算法 u和x的二进制表示为：