第三章离散傅里叶变换快速算法FFT的提出基2时间抽取FFT基2频率抽取FFT任意基时间抽取FFTFFT算法中的对称关系混合基FFTFFT算法应用
第三章 离散傅里叶变换快速算法 ⚫ FFT的提出 ⚫ 基2时间抽取FFT ⚫ 基2频率抽取FFT ⚫ 任意基时间抽取FFT ⚫ FFT算法中的对称关系 ⚫ 混合基FFT ⚫ FFT算法应用
FFT算法思想FFT算法的基本思想：长序列DFT分解为短序列的DFT旋转因子的性质W(k+N)m =Wk(m+N) =Wkm(1）周期性NNmk+N"=Wmk(2)对称性=-Wmk2WNN=Wmk/MWmk=WMmk(3）可约性WmkN/M为整数NNIM"NMN
FFT算法的基本思想：长序列DFT分解为短序列的DFT FFT算法思想 ( ) ( ) k N m k m N km WWW NNN + + (1) 周期性 = = (2) 对称性 ( ) km mk W W N N − = (3) 可约性 2 N mk mk W W N N + = − mk Mmk W W N MN = / / , / mk mk M W W N M N N M = 为整数 旋转因子的性质
基2时间抽取FFT算法基2时间抽取FFT算法的原理、过程、矩阵表示、流图形式原理：在时域按照奇偶拆分的形式将长序列逐渐分解为两组子序列，计算两点序列的DFT将时域转换到频域，由两组短序列的DFT逐次合成长序列的DFT。N-1x[k]=x[2k]N2x[kjwknX[m] = x[k] -k =0,1,2[x2[k]=x[2k+1]k=0N/2-N/2-Zx[2k + 1JW(2k+1)mx[2k]W2km+X[m]= X,[m] +W"X,[m]NNk=0k=0X[m+N /2]=X,[m]-WmX,[m]2N/2-1Zx[2k +1] WN7?x[2k] Wk72"+W"Nm= 0,1Lk=0k=02
基2时间抽取FFT算法的原理、过程、矩阵表示、流图形式 基2时间抽取FFT算法 原理：在时域按照奇偶拆分的形式将长序列逐渐分解为两组子序列，计算两点序 列的DFT将时域转换到频域，由两组短序列的DFT逐次合成长序列的DFT。 /2 1 /2 1 /2 /2 0 0 [ 2 ] [2 1] N N km m km N N N k k x k x k W W W − − = = = + + 1 0 [ ] [ ] − = = N km N k X m x k W /2 1 /2 1 2 (2 1) 0 0 [2 ] [2 1] N N km k m N N k k x k W x k W − − + = = = + + 1 2 [2 [ ] ] 0,1, , 1 [ ] [ ] [ 1 2 ] 2 x k x x k x k N x k k k = → = = + − 1 2 [ ] [ ] [ ] m X m X m W X m N = +1 2 [ / 2] [ ] [ ] m X m N X m W X m + = − N 0,1 1 2 N m = − L
基2时间抽取FFT算法短序列DFT合成长序列DFTX[m]X,[m]x[0X[O]X[m+ N /2]Wm X,[m]x[2]XT11时域到频域X[2]x[1][8] - X[3]x[3]
基2时间抽取FFT算法 0 1 2 [ ] 1 1 0 [ ] [ / 2] 1 1 0 [ ] N m N X m W X m X m N W X m = + − 短序列DFT合成长序列DFT [0] [0] [1] [ 1 1 1 1 1] X x X x = − 时域到频域 −1 −1 −1 −1 −j x[0] x[3] x[2] x[1] X[3] X[2] X[1] X[0]
基2时间抽取FFT算法计算N=16点的DFT，直接计算DFT计算量是多少？如果用基2时间抽取FFT算法，计算量是多少？直接计算DFT：N2=1621og, N =161og, 16= 32基2时间抽取FFT：?
基2时间抽取FFT算法 计算N=16点的DFT，直接计算DFT计算量是多少？ 如果用基2时间抽取FFT算法，计算量是多少？ 直接计算DFT：N2=162 基2时间抽取FFT： 2 log 2 N N 2 16log 16 32 2 = =
基2频率抽取FFT算法基2频率抽取FFT算法的原理、过程、矩阵表示、流图形式原理：在时域逐次将长序列分解为两组子序列，计算两点序列的DFT将时域转换到频域，由短序列的DFT按照奇偶顺序逐次合成长序列的DFT。N/2-2N-1x[kjWmkx[kjWmk2Cx[kjWmkX[m]=MNANk=N/2k=0N/2-N/2-2x[k + N /2]Wm(k+N/2)x[k]WmkW!+NN/2-(x[k]+(-1)"x[k + N /2]) WmkZN/2-1X[2m]= (x[K]+x[k+N /2])WwZ (x[k]-x[k+N/2])WkWmkX[2m+1]=NI2k=0K=0
基2频率抽取FFT算法的原理、过程、矩阵表示、流图形式 基2频率抽取FFT算法 原理：在时域逐次将长序列分解为两组子序列，计算两点序列的DFT将时域转换 到频域，由短序列的DFT按照奇偶顺序逐次合成长序列的DFT。 /2 1 1 0 /2 [ ] [ ] N N k k N mk mk x k W x k W N N − − = = = + /2 1 /2 1 ( /2) 0 0 [ ] [ / 2] N N mk m k N N N k k x k x k N W W − − + = = = + + ( ) /2 1 0 [ ] [ / 2 ( 1) ] N mk N k m x k x k N W − = = + − + 1 0 [ ] [ ] mk N N k X m x k W − = = ( ) /2 1 / 2 0 [2 1] [ ] [ / 2] N k mk N N k X m x k x k N W W − = ( ) + = − + /2-1 / 2 0 [2 ] [ ] [ / 2] N mk N k X m x k x k N W = = + +
基2频率抽取FFT算法时域长序列分解为两个短序列x[k]x[k]Wx[0]X[O]-1 /x[k+ N /2]x[k]Wx[1]X[2]时域到频域转换x[2]X[U]X[0][11 x[0]x[3]X[3]X[11[1 -1 x[1]
基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 = − + 时域长序列分解为两个短序列 [0] 1 1 [0] [1] 1 1 [1] X x X x = − 时域到频域转换 0 4 W = 1 1 4 W = −j x[0] x[3] x[1] x[2] X[3] X[1] X[2] X[0] −1 −1 −1 −1
DFT与频谱关系xi[k]=(1, 2, 2, 11, x2[k]= 1,2,2, 1, 0,0, 0, 0],x3[k]=( 1, 0, 2, 0, 2, 0, 1, 0]三个序列的4点、8点、8点DFT之间存在什么关系？X,[m]={6, -1-j, 0, -1+i)X2[m]={6, 1.7-4.1j, -1-j, 0.3-0.1j, 0, 0.3+0.1j, -1+j, 1.7+4.1]]X,[m]={6, -1-j, 0, -1+i, 6, -1-j, 0, -1+iX2[2m]=Xi[m];m=0,1,2,3X,(ej°)= X,(eig)X3[m]=Xi[m];m=0,1,2,3X3[m]=Xi[m-4]; m=4,5,6,7X,(ej)= X,(ei22)
DFT与频谱关系 x1 [k]={1, 2, 2, 1}，x2 [k]={ 1, 2, 2, 1, 0,0, 0, 0}， x3 [k]={ 1, 0, 2, 0, 2, 0, 1, 0} 三个序列的4点、8点、8点DFT之间存在什么关系？ X1 [m]={6, −1−j, 0, −1+j} X3 [m]={6, −1−j, 0, −1+j, 6, −1−j, 0, −1+j } X2 [m]={6, 1.7−4.1j, −1−j, 0.3−0.1j, 0, 0.3+0.1j, −1+j, 1.7+4.1j} j j 2 1 X X (e ) (e ) = j j2 3 2 X X (e ) (e ) =
FFT算法对称关系时间抽取算法中，时域到频域变换的系数矩阵与频域合成的系数矩阵相同。频率抽取算法中，时域分解的系数矩阵与时域到频域变换的系数矩阵相同。基r时间抽取FFT算法中频域合成的系数矩阵与基r频率抽取FFT算法中时域分解的系数矩阵相同，旋转因子矩阵的形式相同
FFT算法对称关系 ◼ 时间抽取算法中，时域到频域变换的系数矩阵与频域合成的系数矩阵相同。 ◼ 频率抽取算法中，时域分解的系数矩阵与时域到频域变换的系数矩阵相同。 ◼ 基r时间抽取FFT算法中频域合成的系数矩阵与基r频率抽取FFT算法中时域分解的 系数矩阵相同，旋转因子矩阵的形式相同
混合基FFT算法为什么提出混合基FFT？基r时间抽取FFT算法序列的长度N必需满足N=rM若序列长度不满足要求，需要补零，大量补零将降低FFT算法的实际效果。混合基可以根据序列长度确定每级的分解个数，可减少补零的个数，提高FFT算法效率
混合基FFT算法 为什么提出混合基FFT ？ 基r时间抽取FFT算法序列的长度N必需满足N=r M 若序列长度不满足要求，需要补零，大量补零将降低FFT算法的实际效果。 混合基可以根据序列长度确定每级的分解个数，可减少补零的个数，提高FFT算法 效率