第4章快速傅立叶变换 ■问题的提出 ■解决问题的思路与方法 基2时间抽取FFT算法 基2时间抽取FFT算法的计算复杂度 基2时间抽取FFT算法流图规律 基2频率抽取FFT算法 FFT算法的实际应用
第4章 快速傅立叶变换 ▪ 问题的提出 ▪ 解决问题的思路与方法 ▪ 基2时间抽取FFT算法 ▪ 基2时间抽取FFT算法的计算复杂度 ▪ 基2时间抽取FFT算法流图规律 ▪ 基2频率抽取FFT算法 ▪ FFT算法的实际应用
问题的提出 4点序列{2,3,3,2}DFT的计算复杂度 Xm=2对W,m=0LN=1提 k=0 X[O]=2W0+30+3W0+2W0=10 X1=2M+3WM+3W+2WN=-1-j X12-2WN+3WN+3WN+2WN=0 运 算 X[3]=2WN+3W+3W8+2WN=-1+/效 复数加法 复数乘法 率
问题的提出 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分解为短序列的DFT 2.利用旋转因子W的周期性、对称性、可约性
解决问题的思路 1. 将长序列DFT分解为短序列的DFT 2. 利用旋转因子 WN km 的周期性、对称性、可约性
旋转因子Wm的性质 1)周期性 7(k+N)m k(m+N) N N 2)对称性 N mk+ W2=-W mk Wkn )= mk 3)可约性 wmk=wamk Wmk=Wmbn,N/n为整数
旋转因子 WN km 的性质 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[2门] N x[k]→ 0.1. [2r+1 2 基2频率抽取 Decimation in frequency)FFT算法 X[2m] Xm]→ X[2m+1]
解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子 的特性，由子序列的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