fft蝶形算法

第4章快速傅立叶变换问题的提出解决问题的思路与方法基2时间抽取FFT算法基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律基2频率抽取FFT算法FFT算法的实际应用问题的提出4点序列{2，3，3，2}DFT的计算复杂度1,1,0,][][10NmWkxmXkmNNk102332]0[0000NNNN12332]1[321002332]2[6420NNNN12332]3[9630复数加法N(N-1)复数乘法N2如何提高DFT的运算效率?解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。kmNW旋转因子的性质kmNWkmNNmkNmNkN)()(1)周期性2)对称性mkNkmNWW3)可约性mkNNmkNWW2nmknNmkNWW为整数nNWWnmknNmkN/,//解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimationintime)FFT算法12,1,0]12[]2[][Nrrxrxkx基2频率抽取(Decimationinfrequency)FFT算法]12[]2[][mXmXmX基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4点基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],[][][241mmXWmXmXm1,0],[][]2[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算法流图基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第一级第二级第三级算法的计算复杂度复乘次数NN2log2复乘次数NN2NN2log2基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倒序k0k1k2x[k2k1k0]x[000]x[100]x[010]01011]12x[kk0]x[k2k101x[110]x[001]x[101]x[011]x[111]01010101基2频率抽取FFT算法mkNNNkmkNNkWkxWkxmX][][][12/12/0)2/(12/012/0]2/[][NkmNNkmkNNkWNkxWkxmkNmNkWNkxkx]2/[)1(][12/0rkNNkWNkxkxrX2/12/0]2/[][]2[rkNkNNkWWNkxkxrX2/12/0]2/[][]12[rkNNkWNkxkxrX2/12/0]2/[][]2[rkNkNNkWWNkxkxrX2/12/0]2/[][]12[12/1,0Nr3NW-12NW-11NW-10NW-1x[0]x[4]x[1]x[5]x[2]x[6]x[3]x[7]4点DFTX[0]X[6]X[2]X[4]4点DFTX[1]X[3]X[5]X[7]X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2点DFT-1-12NW0NW-1-12点DFT2点DFT2点DFT0NW1NW2NW3NW-1-1-1-1x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]0NW2NW2NW0NWX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]0NW0NW0NW0NW-1-1-1-1-1-1-1-1FFT算法应用利用N点复序列的FFT计算两个N点实序列FFT利用N点复序列的FFT，计算2N点序列的FFT利用FFT计算IFFT利用N点复序列的FFT算法计算两个N点实序列FFTx1[k],x2[k]是实序列，将其构成复序列y[k]=x1[k]+jx2[k]DFT{x1[k]+jx2[k]}=YR[m]+jYI[m]?][1kxDFT?][2kxDFT][][21kjxkxDFT])[(])[(NINRmjYmY]))[(][(])[(][21][1NIINRRmYmYjmYmYkxDFT]))[(][(])[(][21][2NIINRRmYmYjmYmYjkxDFT利用N点复序列的FFT，计算2N点序列的FFTy[k]是一个长度为2N的序列1,1,0]12[][]2[][][21Nkkykxkykxky1,,1,0][][][][][][221221NmmXWmXNmYmXWmXmYmNmN问题：如何利用N点FFT，计算4N点序列的FFT？利用FFT实现IFFTmkNNkWkxkxDFTmX][][][10mkNNmWmXNmXIDFTkx][1][][10mkNNmWmXNkx][1][10步骤：A)将X[m]取共轭]}[{)mXDFTFFTB流图计算用C)对B)中结果取共轭并除以N