第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
基2时间抽取FFT算法流图 N=2 x[]={x[0],x1]} A0]=x[0+W2x X[1=x[0]+W2x[=x101-W x[ll A[0 W
基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
XIm=Film+W4, m=0, Xm+21=X1[m1-W4X2[m],m=0,1 x1[0 [0] RoI W 02点DFT[xL 「21 2 X[1 X2[ W4 x[1 X[2] 2点DFT W x[3 2 X[3]
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 W4 1 W4 0 W2 0 W2 X [0] X [1] X [2] X [3] X[m] = X1 [m] +W4 X2 [m], m = 0,1 m X[m + 2] = X1 [m] −W4 X2 [m], m = 0,1 m
4点基2时间抽取FFT算法流图 x[0 21。W X1[1 1 x2[0 W x12] 04 elr X
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
Xm]=X1[m]+W8X2[ml,m=0,23 Xm+4]=X1ml-W8X2[ml,m=01,2,3 [0」 X10I x[2] X[1 4点DFT 4 X[2] x[6 X[3] X2IOJ W8 x[1 X[4] x[3] XIi 4点DFT [5 x2W32 X[6] X2[3]W3 x[7 X[7
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] XLAP X10I 2点DFT X[1 X[2] W2点DT x6] X[3] XylOn X2O⊥WQ X[4] 2点DFT x[5] XIi x2[21W8 x X[6] W2点BFT x[7] (23 Ws X[7
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 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 W40 W4 −1−1 −1−1 x [ 0 ] x [ 4 ] x [ 2 ] x [ 6 ] 2 W80 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 W80 W8 0 W8 0 W8 X21[0] X21[1] X22[0] X22[1] 8点基 2时间抽取FFT算法流图