fft蝶形算法.ppt

《fft蝶形算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章快速傅立叶变换问题的提出解决问题的思路与方法基2时间抽取FFT算法基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律基2频率抽取FFT算法FFT算法的实际应用问题的提出4点序列{2，3，3，2}DFT的计算复杂度复数加法N(N-1)复数乘法N2如何提高DFT的运算效率?解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子的周期性、对称性、可约性。旋转因子的性质1)周期性2)对称性3)可约性解决问题的方法将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来

2、实现整个序列的DFT。基2时间抽取(Decimationintime)FFT算法基2频率抽取(Decimationinfrequency)FFT算法基2时间抽取FFT算法流图N=2x[k]={x[0],x[1]}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-1X[0]X[1]X[2]X[3]4点基2时间抽取FFT算法流图8点基2时间抽取FFT算法流图4点DFT4点DFTx[0]x[2]x[4]x[6]x[1]x[3]x

3、[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-14点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-18点基2时间抽取FFT算法流图基2时间抽取FFT算法第一级第二级第三级算法的计算复杂度复乘次数

4、复乘次数NN2基2时间抽取FFT算法流图第一级第二级第三级FFT算法流图旋转因子规律第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。倒序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算法3NW-12NW-11NW-10NW-1x[0]x

5、[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]0NW2NW2NW0N

6、WX[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]利用N点复序列的FFT，计算2N点序列的FFTy[k]是一个长度为2N的

7、序列问题：如何利用N点FFT，计算4N点序列的FFT？利用FFT实现IFFT步骤：A)将X[m]取共轭C)对B)中结果取共轭并除以N