离散傅里叶变换快速算法（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