北京交通大学：《数字信号处理》课程教学课件（PPT讲稿）第3章 快速傅里叶算法FFT 3.6 FFT算法对称性分析

FFT算法中的对称性时间抽取FFT算法中的对称频率抽取FFT算法中的对称时间抽取与频率抽取之间的对称

FFT算法中的对称性 ◆ 时间抽取FFT算法中的对称 ◆ 频率抽取FFT算法中的对称 ◆ 时间抽取与频率抽取之间的对称

时间抽取FFT算法中的对称基2时间抽取FFTX[0]x[0]时域到频域X[1]x[1] X[m]0W.X,[m]A频域合成X[m + N / 2]0Wm[X,[m]

时间抽取FFT算法中的对称 [0] 1 1 [0] [1] 1 1 [1] X x X x       =             − 0 1 2 [ ] 1 1 0 [ ] [ / 2] 1 1 0 [ ] N m N X m W X m X m N W X m = + −                   频域合成 时域到频域 基2时间抽取FFT

时间抽取FFT算法中的对称基4时间抽取FFT11X[0]11x[0]]1x[1]X[1]-j-1j时域到频域X[2]-11x[2]1-1x[3]X[3]1j-1-jw0X[m]111010X,[m]1100-10-jW"X,[m]X[m+ N / 4]频域合成W?"101-1-100X[m+2N /4]X,[m]11-1000W"-jX[m+3N/4]X,[m]时域到频域变换的系数矩阵与频域合成的系数矩阵相同

时间抽取FFT算法中的对称 频域合成 时域到频域 时域到频域变换的系数矩阵与频域合成的系数矩阵相同 基4时间抽取FFT

频率抽取FFT算法中的对称基2频率抽取FFTWox,[k]x[k]N时域分解x[k]0Wx[k + N / 2]N[X[0]x[0]时域到频域X[1] x[1]

频率抽取FFT算法中的对称 [0] 1 1 [0] [1] 1 1 [1] X x X x       =             − 0 1 2 [ ] 0 1 1 [ ] [ ] 0 1 1 [ / 2] N k N x k W x k x k W x k N = − +                      时域分解 时域到频域 基2频率抽取FFT

频率抽取FFT算法中的对称基4频率抽取FFTwo[x,[k]00011x[k]WK0时域分解x[k]001-1-jix[k + N / 4]Wi0100-1x[k]1-1x[k +2N / 4]Wk000L1-1x[k]ix[k +3N /4]11[X[0]11x[0]]X[1]-1x[1]-jj时域到频域1X[2]-1-1x[2]11X[3]-1x[3]-i时域分解的系数矩阵与时域到频域变换的系数矩阵相同

频率抽取FFT算法中的对称 0 2 3 1 2 3 4 [ ] 0 0 0 1 1 1 1 [ ] [ ] 0 0 0 1 j 1 j [ / 4] [ ] 0 0 0 1 1 1 1 [ 2 / 4] [ ] 0 0 0 1 j 1 j [ 3 / 4] N k N k N k N x k W x k x k W x k N x k W x k N x k W x k N − − + = − − + − − +                                           时域分解 时域到频域 时域分解的系数矩阵与时域到频域变换的系数矩阵相同 基4频率抽取FFT