数字信号处理时间抽取FFT

1、数字信号处理(Digital Signal Processing) 离散傅里叶变换快速算法(FFT)问题的提出解决问题的思路与方法 基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用 实序列的DFT计算，IDFT的快速计算方法时间抽取FFT问题的提出4点序列2，3，3，2 DFT的计算复杂度复数加法N(N-1)复数乘法N 2如何提高DFT的运算效率?时间抽取FFT解决问题的思路1. 将长序列DFT分解为短序列的DFT2. 利用旋转因子 的周期性、对称性、可约性。时间抽取FFT旋转因子 的性质(1) 周期性(以N为周期)(2) 对称性(3) 可约性时间抽取FFT解决问题的方法 将时

2、域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。 基2时间抽取(Decimation in time)FFT算法 基2频率抽取(Decimation in frequency)FFT算法时间抽取FFT基2时间抽取FFT算法基2时间抽取FFT算法推导基2时间抽取FFT算法流图基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律时间抽取FFT基2时间抽取FFT算法推导时间抽取FFT基2时间抽取FFT算法推导因此有:由于X1m 和X2m隐含有周期性，可得时间抽取FFT基2时间抽取FFT算法流图N=2xk=x0, x1时间抽取FFT4点基2时间抽取F

3、FT算法流图x0 x2x1x3X10X11X20X212点DFT2点DFT-1-1-1-1X 0X 1X 2X 3时间抽取FFT4点基2时间抽取FFT算法流图时间抽取FFT8点基2时间抽取FFT算法流图4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-1时间抽取FFT4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7-1-1-1-18点基2时间抽取FFT算法流图时间抽取FFT第一级第

4、二级第三级8点基2时间抽取FFT算法流图时间抽取FFTFFT算法流图旋转因子 规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级的蝶形系数为 ，蝶形节点的距离为N /2。时间抽取FFT8点基2时间抽取FFT算法流图第一级第二级第三级时间抽取FFT算法的计算复杂度复乘次数复乘次数NN 2时间抽取FFT原位运算x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列存储单元第一级输出第二级输入第二级输出第三级输入X10X11X20X21X30X31X40X41A

5、(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X50X51X52X53X60X61X62X63A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X 0X 1X 2X 3X 4X 5X 6X 7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三级输出时间抽取FFT倒序k0k1k2xk2 k1k0 x000 x100 x0100101112 xkk0 xk2 k101x110 x001x101x011x11101010101时间抽取FFT倒序的实现变址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元x000 x001 x010

6、 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然顺序输入倒序变址xk2k1k0存储单元数据不对换存储单元数据对换时间抽取FFT例：已知xk=1,2,3,4，利用基2FFT算法流图计算13244 6-2-2 -j10-2-2+2j-2-2jDFTxk=10, -2+2j,-2,-2-2j04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1时间抽取FFT补零,插零序列的DFTx1k=1,2,3,4x2k=1,2,3,4,0,0,0,0 x3k=1,0,2,0,3,0,4,0DFTx1k=10, -2+2j, -2, -2-2jDFTx2k=10, -0.4142-7.2426j, -2+2j, 2.4142-1.2426j, -