离散傅里叶变换快速算法（FFT）问题的提出解决问题的思路与方法基2时间抽取FFT算法基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律基2频率抽取FFT算法FFT算法的实际应用7/2/2025崔丽珍信息工程学院
7/2/2025 信息工程学院 崔丽珍 离散傅里叶变换快速算法(FFT) ◼ 问题的提出 ◼ 解决问题的思路与方法 ◼ 基2时间抽取FFT算法 ◼ 基2时间抽取FFT算法的计算复杂度 ◼ 基2时间抽取FFT算法流图规律 ◼ 基2频率抽取FFT算法 ◼ FFT算法的实际应用
问题的提出4点序列2，3，3，2DFT的计算复杂度如何提高DFT的运算效率？N-1x[kjWk"，m= 0,],...N-1X[m] =k=0X[0] = 2W + 3W +3W + 2W = 10X[1]= 2W +3W +3W2 +2W = -1- jX[2] = 2W + 3W + 3W4 + 2W = 0X[3] = 2W +3W +3W + 2W= -1+ j复数乘法 N2复数加法N(N-1)7/2/2025崔丽珍信息工程学院
7/2/2025 信息工程学院 崔丽珍 问题的提出 4点序列{2，3，3，2} DFT的计算复杂度 [ ] [ ] , 0,1, 1 1 0 = = − − = X m x k W m N k m N N k [0] 2 3 3 2 10 0 0 0 0 X = WN + WN + WN + WN = X W W W W j [1] = 2 N + 3 N + 3 N + 2 N = −1− 0 1 2 3 [2] 2 3 3 2 0 0 2 4 6 X = WN + WN + WN + WN = X W W W W j [3] = 2 N + 3 N + 3 N + 2 N = −1+ 0 3 6 9 复数加法 N(N-1) 复数乘法 N 2 如 何 提 高DFT 的 运 算 效 率 ?
解决问题的思路1.将长序列DFT分解为短序列的DFTWk的周期性、对称性、可约性。2.利用旋转因子7/2/2025崔丽珍信息工程学院
7/2/2025 信息工程学院 崔丽珍 解决问题的思路 1. 将长序列DFT分解为短序列的DFT 2. 利用旋转因子 WN km 的周期性、对称性、可约性
Whn旋转因子的性质1)周期性W(k+N)m= Wk(m+N)= WkmtNN2)对称性Nmk+(wk")"=Wmk= -Wmk2WNN3)可约性=WnmkWmknNWmk=WnW"， N /n为整数7/2/2025崔丽珍信息工程学院
7/2/2025 信息工程学院 崔丽珍 旋转因子 的性质 km WN km N k m N N k N m WN =W =W ( + ) ( + ) 1)周期性 2) 对称性 ( ) mk N km WN W − = 3)可约性 mk N N mk WN = −W + 2 nmk nN mk WN =W WN m k =WN m k / n / n , N / n为整数
解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimation in time)FFT算法[x[2r]Nr=0,1-1x[k]→2x[2r +1]基2频率抽取(Decimation infrequency)FFT算法X[2m]X[m] -→X[2m + 1]7/2/2025信息工程学院崔丽珍
7/2/2025 信息工程学院 崔丽珍 解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子 的特性，由子序列的DFT来实现整个序列的DFT。 基2时间抽取(Decimation in time)FFT算法 1 2 0,1, [2 1] [2 ] [ ] = − + → N r x r x r x k 基2频率抽取(Decimation in frequency)FFT算法 + → [2 1] [2 ] [ ] X m X m X m
基2时间抽取FFT算法流图N=2x[k]=(x[0], x[1]]X[0] = x[0] + W2 x[1]X[1] = x[0] + W2 x[1] = x[0] - W2 x[1]x[0] X[o]Wx[1]:.X[1]17/2/2025崔丽珍信息工程学院
7/2/2025 信息工程学院 崔丽珍 基2时间抽取FFT算法流图 N=2 x[k]={x[0], x[1]} [0] [0] [1] 0 2 X = x +W x [1] [0] [1] 1 2 X = x +W x x[0] x[1] X[0] -1 0 W2 X[1] [0] [1] 0 2 = x −W x
m=0,1X[m] = Xi[m]+W4" X2[m],X[m+2] = Xi[m] - Wm X2[m],2 m=0,14点基2时间抽取FFT算法流图Xi[0]x[0] X[0]2点DFTW?Xi[1]x[2] X[1]-1WaX2[0]x[1]X[2]2点DFTW4W2X[1]x[3]X[3]-1崔丽珍7/2/2025信息工程学院
7/2/2025 信息工程学院 崔丽珍 4点基 2时间抽取FFT算法流图 x[0] x[2] x[1] x[3] X1 [0] X1 [1] X2 [0] X2 [1] 2 点DFT 2 点DFT − 1 − 1 − 1 − 1 0 W41 W4 0 W20 W2 X [0] X [1] X [2] X [3] X[m] = X 1[m] + W4 X 2[m], m = 0,1 m X[m + 2] = X1[m] − W4 X 2[m], m = 0,1 m
4点基2时间抽取FFT算法流图X,[0]x[0] X[0]福w!X[1]x[2]+ X[1]-1WX,[0]X[2]x[1] :W!WX,[1]x[3] X[3]-1-1信息工程学院崔丽珍7/2/2025
7/2/2025 信息工程学院 崔丽珍 4点基2时间抽取FFT算法流图 x[0] x[2] x[1] x[3] −1 −1 −1 −1 X[0] X[2] X[1] X[3] X1[0] X2[0] X1[1] X2[1] 0 W4 1 W4 0 W4 0 W4
X[m] = X,[m] + Wm X2[m],m = 0,1,2,38点基X[m+ 4] = Xi[m] - W" X2[m],m = 0,1,2,3X [0]x[0] :X[0]X,[1]X[1]x[2] ·4点DFTX;[2]X[2]x[4] :X;[3]X[3]x[6] :X2[0] W?X[4]x[1] :X[1] W]X[5]x[3] ·4点DFTX[2] W2x[5] :X[6]X2[3] W?X[7]x[7] :+崔丽珍7/2/2025信息工程学院
7/2/2025 信息工程学院 崔丽珍 8点基 2时间抽取FFT算法流图 4点DFT 4点DFT x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] X1 [0] X1 [1] X1 [2] X1 [3] X2 [0] X2 [1] X2 [2] X2 [3] X [0] X [1] X [2] X [3] X [4] X [5] X [6] X [7] − 1 − 1 − 1 − 1 0 W8 1 W82 W83 W8 X[m + 4] = X1[m]− W8 X2[m], m = 0,1,2,3 m X[m] = X1[m]+ W8 X2[m], m = 0,1,2,3 m
8点基2时间抽取FFT算法流图X [0]XXiax[0]X[0]2点DFTweX,[1]XXLI)x[4] X[1]XEOpwX,[2]x[2] X[2]w2点DFTALUWe!X,[3]LUx[6] X[3]-1X2[0] WL00x[1] X[4]w2点DFTX2[1] Wg]x[5] X[5]WboWoX2[2] W?X[6]x[3] W.ou!2点DFTX2[3]W38X[7]x[7] -1佳丽珍11212025信总工程字院
7/2/2025 信息工程学院 崔丽珍 4点DFT 4点DFT x[0] x[2] x[4] x[6] x[1] x[3] x[5] x[7] X1 [0] X1 [1] X1 [2] X1 [3] X2 [0] X2 [1] X2 [2] X2 [3] X [0] X [1] X [2] X [3] X [4] X [5] X [6] X [7] −1 −1 −1 −1 0 W8 1 W8 2 W8 3 W8 2点DFT 2点DFT x[0] x[4] x[2] x[6] −1 1 W4 X11[0] X11[1] X12[0] X12[1] 0 W4 2点DFT 2点DFT −1 −1 X21[0] X21[1] X22[0] X22[1] x[1] x[5] x[3] x[7] 1 W4 0 W4 −1 −1 −1 −1 x[0] x[4] x[2] x[6] 2 W8 0 W8 0 W8 0 W8 X11[0] X11[1] X12[0] X12[1] −1 −1 −1 −1 x[1] x[5] x[3] x[7] 2 W8 0 W8 0 W8 0 W8 X21[0] X21[1] X22[0] X22[1] 8点基2时间抽取FFT算法流图