数字信号处理-时间抽取FFT

数字信号处理(DigitalSignalProcessing)信号与系统系列课程组国家电工电子教学基地离散傅里叶变换快速算法(FFT)问题的提出解决问题的思路与方法基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用——实序列的DFT计算，IDFT的快速计算方法时间抽取FFT问题的提出4点序列{2，3，3，2}DFT的计算复杂度1,1,0,][][10NmWkxmXkmNNk102332]0[0000NNNN]1[3210NNNN]2[6420NNNN]3[9630NNNN(N1)复数乘法N2如何提高DFT的运算效率?时间抽取FFT解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。kmNW946434046444240434241404040404044j1j11111j1j11111旋转因子的性质kmNWkmNNmkNmNkN)()((1)周期性(2)对称性mkNkmNWW(3)可约性mkNNmkNWW2nmknNmkNWW为整数nNWWnmknNmkN/,//时间抽取FFT解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimationintime)FFT算法12,,1,0]12[]2[][Nrrxrxkx基2频率抽取(Decimationinfrequency)FFT算法]12[]2[][mXmXmX时间抽取FFT基2时间抽取FFT算法基2时间抽取FFT算法推导基2时间抽取FFT算法流图基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律时间抽取FFT基2时间抽取FFT算法推导kmNNkWkxmX][][10mrNNrrmNNrWrxWrx)12(12/0212/0]12[]2[rmNNrmNrmNNrWrxWWrx2/12/02/12/0]12[]2[mrNNrmrNNrWrxmXWrxmX2/12/022/12/01]12[][]2[][记时间抽取FFT基2时间抽取FFT算法推导][][][21mXWmXmXmN][][]2/[22/1NmXWNmXNmXNmN121,0Nm因此有:][][21mXWmXmN由于X1[m]和X2[m]隐含有周期性，可得时间抽取FFT基2时间抽取FFT算法推导mNNWmXWmXNmXmX][][1111]2/[][2011j-1-j基2时间抽取FFT算法的基本关系][][][21mXWmXmXmN][][]2/[21mXWmXNmXmN121,0Nm时间抽取FFT基2时间抽取FFT算法流图N=2x[k]={x[0],x[1]}]1[]0[]0[02xWxX]1[]0[]1[12xWxX]0[x]1[x]0[X-102W]1[X]1[]0[02xWx]1[]0[1111]1[]0[xxXX4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]X1[0]X1[1]X2[0]X2[1]2点DFT2点DFT111104W14W02W02WX[0]X[1]X[2]X[3]1,0],[][]2[241mmXWmXmXm1,0],[][][241mmXWmXmXm4点基2时间抽取FFT算法流图x[0]x[2]x[1]x[3]1111X[0]X[2]X[1]X[3]X1[0]X2[0]X1[1]X2[1]04W14W04W04W8点基2时间抽取FFT算法流图4点DFT4点DFTx[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108W18W28W38W3,2,1,0],[][]4[281mmXWmXmXm3,2,1,0],[][][281mmXWmXmXm4点DFT4点DFTx[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108W18W28W38W2点DFT2点DFTx[0]x[4]x[2]x[6]114WX11[0]X11[1]X12[0]X12[1]04W2点DFT2点DFT11X21[0]X21[1]X22[0]X22[1]x[1]x[5]x[3]x[7]14W04W1111x[0]x[4]x[2]x[6]28W08W08W08WX11[0]X11[1]X12[0]X12[1]1111x[1]x[5]x[3]x[7]28W08W08W08WX21[0]X21[1]X22[0]X22[1]8点基2时间抽取FFT算法流图x[0]x[4]x[2]x[6]X[0]X[2]X[1]X[3]111108W08W08Wx[1]x[5]x[3]x[7]X[0]X[2]X[1]X[3]111108W08W08W18W08W38W28W28W28W1111第一级第二级第三级8点基2时间抽取FFT算法流图时间抽取FFT算法的计算复杂度复乘次数NN2log2复乘次数NN2NN2log2时间抽取FFT计算速度的比较N=1024*4;x=rand(N,1);tic;y1=fft(x);t1=toc;fprintf('\nFFTtime=%.6e\n',t1);tic;y2=dftmtx(N)*x;t2=toc;fprintf('DFTtime=%.6e\n',t2);fprintf('FFT/DFT=%.6f%%\n',t1*100/t2);stem(abs(y1-y2),'r.');基2时间抽取FFT算法流图x[0]x[4]x[2]x[6]X[0]X[2]X[1]X[3]111108W08W08Wx[1]x[5]x[3]x[7]X[0]X[2]X[1]X[3]111108W08W08W18W08W38W28W28W28W1111第一级第二级第三级FFT算法流图旋转因子规律PNW第二级的蝶形系数为，蝶形节点的距离为2。4/0,NNNWW第一级的蝶形系数均为，蝶形节点的距离为1。0NW第三级的蝶形系数为，蝶形节点的距离为4。8/38/28/0,,,NNNNNNN级的蝶形系数为，蝶形节点的距离为N/2。)12/(10,,,NNNNx[0]x[4]x[2]x[6]X[0]X[2]X[1]X[3]111108W08W08Wx[1]x[5]x[3]x[7]X[4]X[6]X[5]X[7]111108W08W08W18W08W38W28W28W28W1111倒序运算(Bit-reverseComputations)倒序的实现——变址A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元x[000]x[001]x[010]x[011]x[100]x[101]x[110]x[111]x[000]x[100]x[010]x[110]x[001]x[101]x[011]x[111]自然顺序输入倒序变址x[k2k1k0]][][210kkkxkxkk存储单元数据不对换kk存储单元数据对换x[0]x[4]x[2]x[6]X[0]X[2]X[1]X[3]111108W08W08Wx[1]x[5]x[3]x[7]X[4]X[6]X[5]X[7]111108W08W08W18W08W38W28W28W28W1111原位运算(In-placeComputations)原位运算x[0]x[4]x[2]x[6]x[1]x[5]x[3]x[7]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列存储单元第一级输出第二级输入第二级输出第三级输入X1[0]X1[1]X2[0]X2[1]X3[0]X3[1]X4[0]X4[1]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X5[0]X5[1]X5[2]X5[3]X6[0]X6[1]X6[2]X6[3]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X[0]X[1]X[2]X[3]X[4]X[5]X[6]X[7]A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三级输出时间抽取FFT例：已知x[k]={1,2,3,4}，利用基2-FFT算法流图计算]}[{DFT][kxmX13244622j1022+2j22jDFT{x[k]}={10,2+2j,2,22j}04W14Wx[0]x[3]x[1]x[2]X[3]X[1]X[2]X[0]1111例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和x2[k]，则存在3,2,1,0][][]4[][][][281281mmXWmXmXmXWmXmXmm其中x1[k]={1,1,2,1}，x2[k]={-1,-1,-1,-1}X1[m]和X2[m]可通过4点的FFT来计算。-1-1j-1-1例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。解：x1[k]={1,1,2,1}3-12051-1-1x1[0]=1x1[2]=2x1[1]=1x1[3]=1X1[m]={5,-1,1,-1}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,-1,1,-1}的DFT。x2[k]={-1,-1,-1,-1}X2[m]={-4,0,0,0}3,2,1,0][][]4[][][][281281mmXWmXmXmXWmXmXmmX1[m]={5,-1,1,-1}X[0]=5+(-4)=1X[1]=-1+0=-1X[2]=1+0=1X[3]=-1+0=-1X[4]=5-(-4)=9X[5]=-1-0=-1X[6]=1-0=1X[7]=-1-0=-1X[m]={1-11-19-11-1}时间抽取FFT序列补零,序列插零的DFTx1[k]={1,2,3,4}x2[k]={1,2,3,4,0,0,0,0}x3[k]={1,0,2,0,3,0,4,0}DFT{x1[k]}={10,2+2j,2,22j}DFT{x2[k]}={10,0.41427.2426j,2+2j,2.41421.2426j,2,2.41421.2426j,22j,0.41427.2426j}DFT{x3[k]}={10,2+2j,2,22j,10,2+2j,2,22j}基2时间抽取FFT算法的基本关系][][][21mXWmXmXmN基3时间抽取FFT算法的基本关系][][][][3221mXWmXWmXmXmNmN基4时间抽取FFT算法的基本关系][][][][][433221mXWmXWmXWmXmXmNmNmN