正交变换及其快速算法3.1 快速傅里叶变换 (FFT)FFT算法分类：1) 按时间抽取 (DIT)2) 按频率抽取 (DIF)快速傅里叶变换 (FFT)Date 13.1.1 按时间抽取 (DIT)的 FFT按时间抽取 (DIT)的 FFTDate 2这样，一个 N点的 DFT被分解成两个 N/2点的 DFTDate 3Date 4总结： FFT算法的两个特点1) 原位运算即每一级运算的结果仍然存储在原来的存储器中2) 变址输入倒序，输出顺序，存在 “码位倒置 ”Date 53.1.2 按频率抽取 (DIF)的 FFT按频率抽取 (DIF)的 FFTDate 6Date 73.1.3 IFFT的运算方法算法一： FFT流图中所有系数变符号，再除以常数 N,然后输入输出位置对换，即为 IFFT算法二：改变蝶形公式时间抽取的 FFT频率抽取的 IFFT频率抽取的 FFT时间抽取的 IFFTIFFT的运算方法Date 83.1.4 混合基 FFT算法定义：当 N是一个复合数 ,即可把 N分解成一些因子的乘积则可以用 FFT的一般算法混合基 FFT算法Date 9Date 10
