北京交通大学：《数字信号处理》课程教学课件（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

时间抽取与频率抽取之间的对称wo0X[m]X,[m]基2时间抽取FFT频域合成0WrmX,[m]-1X[m+N / 2]wo1基2频率抽取FFT0x,[k]x[k]1时域分解Wk10[x[k]x[k + N /2]N

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 时域分解 基2时间抽取FFT 频域合成 0 1 2 [ ] 0 1 1 [ ] [ ] 0 1 1 [ / 2] N k N x k W x k x k W x k N = − +                     

时间抽取与频率抽取之间的对称0X[m]1wX,[m]1001WM0j00X,[m]X[m+N /4]1-j-1基4时间抽取FFTWe0-100X,[m]X[m+2N/4]1-11频域合成00W3":1i-10X,[m]X[m+3N /4]-j1wo0001.[x,[K]]11x[k]基4频率抽取FFTW01-1x[k]00-jjx[k + N / 4]时域分解W01-11x,[k]00-1x[k +2N / 4]Wak0010[x[k]J-1-ix[k + 3N / 4]基r时间抽取FFT算法中频域合成的系数矩阵与基r频率抽取FFT算法中时域分解的系数矩阵相同，）旋转因子矩阵的形式相同

时间抽取与频率抽取之间的对称 基4频率抽取FFT 时域分解 基4时间抽取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 − − + = − − + − − +                                           基r时间抽取FFT算法中频域合成的系数矩阵与基r频率抽取FFT 算法中时域分解的系数矩阵相同，旋转因子矩阵的形式相同

时间抽取与频率抽取之间的对称oXmXi[m]o基2时间抽取FFT频域合成WmX2[m]0oX[m+N/2]wyx[k]o-0 xi[K]基2频率抽取FFT时域分解Wk-0x2[k]x[k+N/2]o-基r时间抽取FFT算法中频域合成的系数矩阵与基r频率抽取FFT算法中时域分解的系数矩阵相同，旋转因子矩阵的形式相同

0 WN k WN 1 1 1 −1 x[k] x[k+N/2] x1[k] x2[k] 0 WN m WN 1 1 1 −1 X1[m] X2[m] X[m] X[m+N/2] 时间抽取与频率抽取之间的对称 基2频率抽取FFT 时域分解 基2时间抽取FFT 频域合成 基r时间抽取FFT算法中频域合成的系数矩阵与基r频率抽取FFT 算法中时域分解的系数矩阵相同，旋转因子矩阵的形式相同

FFT算法中的对称性谢谢本课程所引用的一些素材为主讲老师多年的教学积累，来源于多种媒体及同事和同行的交流，难以一一注明出处，特此说明并表示感谢！

谢 谢 本课程所引用的一些素材为主讲老师多年的教学积累，来源 于多种媒体及同事和同行的交流，难以一一注明出处，特此说明 并表示感谢！ FFT算法中的对称性