离散傅里叶变换快速算法

离散傅里叶变换快速算法(FFT)快速傅里叶变换(FFT)问题的提出基2时间抽取FFT算法基2频率抽取FFT算法IFFT算法的实际应用掌握基2时间抽取FFT算法的基本思想和方法掌握基2频率抽取FFT算法的基本思想和方法掌握实序列FFT计算，以及由N点序列FFT计算2N点序列FFT的方法掌握利用FFT计算IDFT的过程，以及IFFT实现的原理快速傅里叶变换(FFT)重点：基2时间/频率抽取FFT算法的基本原理，FFT蝶形运算流图难点：由短序列的DFT表达相应长序列的DFT的基本原理及方法快速傅里叶变换(FFT)DFTIDFT乘法次数N加法次数N-1DFT

通常x[k]和WNkm都是复数，所以计算一个X[m]的值需要N次复数乘法运算和N-1次复数加法运算。所有的X[m]就要N2次复数乘法运算，N(N-1)次复数加法运算。当N很大时，运算量将是惊人的，如N=1024，则要完成1048576次(一百多万次)运算。Cooley,JamesW.,andJohnW.Tukey,"AnalgorithmforthemachinecalculationofcomplexFourierseries,"Math.Comput.19,297–301(1965)1965年，库利(cooley)和图基(Tukey)首先在《机器计算傅里叶级数的一种算法》文章中提出FFT算法。/view/d5628524192e45361066f549.htmlN/2点DFTN/2点DFTX1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]_X[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]+N/2点DFTN/2点DFTX1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]+X[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]+++----N/2点DFTN/2点DFTX[0]X[4]X[1]X[5]X[2]X[6]X[3]X[7]将DFT长序列分解为短序列，降低运算次数。复数乘法复数加法1个

点DFT

2个点DFT1个蝶形12N/2个蝶形N总计当N很大时，运算量减少了近一半N点有限长序列的DFTN/2点有限长序列的DFTx[1]x[2r+1]x[N-1]x[3]x[0]x[2r]x[N-2]x[2]x[0]x[1]x[2r]x[2r+1]x[N-2]x[N-1]x[2]x[3]x1[0]x1[1]x1[m]x1[N/2-1]x2[0]x2[1]x2[m]x2[N/2-1]旋转因子的可约性m范围如何求？旋转因子的周期性旋转因子的对称性旋转因子周期性可约性对称性4点DFTx1[0]=x[0]x1[1]=x[2]x1[2]=x[4]x1[3]=x[6]4点DFTx2[0]=x[1]x2[1]=x[3]x2[2]=x[5]x2[3]=x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]-1X[0]X[4]W80-1X[1]X[5]W81-1X[2]X[6]W82-1X[3]X[7]W83-1X

[m]前半部分后半部分碟形运算*X1[m]X2[m]x1[0]=x[0]x1[1]=x[2]x1[2]=x[4]x1[3]=x[6]x2[0]=x[1]x2[1]=x[3]x2[2]=x[5]x2[3]=x[7]X1[0]X1[1]X1[2]X1[3]X2[0]X2[1]X2[2]X2[3]-1X[0]X[4]W80-1X[1]X[5]W81-1X[2]X[6]W82-1X[3]X[7]W83x11[0]=x[0]x11[1]=x[4]x12[0]=x[2]x12[1]=x[6]2点DFT2点DFTX11[0]X11[1]X12[0]X12[1]W40W41-1-1x21[0]=x[1]x21[1]=x[5]x22[0]=x[3]x22[1]=x[7]2点DFT2点DFTX21[0]X21[1]X22[0]X22[1]W40W41-1-18点基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-18点基2时间抽取FFT算法流图第一级第二级第三级

这种FFT算法,是在时间上对输入序列的次序是属于偶数还是属于奇数来进行分解的，所以称作按时间抽取的算法(DIT，DecimationinTime)。

二、运算量x[0]WN0X[0]WN0WN0WN2WN0WN0WN0WN2WN0WN1WN2WN3x[4]x[2]x[6]x[1]x[5]x[3]x[7]X[1]X[2]X[3]X[4]X[5]X[6]X[7]-1-1-1-1-1-1-1-1-1-1-1-1当N=8=23时，由3级蝶形运算组成；每级由4个蝶形运算组成；共有12个蝶形运算；每个蝶形运算有1次复乘，2次复加；共有12次复乘，24次复加；当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：复数乘法次数与DFT比较：N点的FFT的运算量：1024点来说，比值为204.8FFT算法特点第一级第二级第三级000001010011100101110111000100010110001101011111FFT算法特点级数

碟形运算的数量:N/2第一级第二级第三级0000010100111001011101110001000101100011010111110

0

0

0

0

0

0

0自然顺序二进制k2k1k0倒位序二进制k0k1k2倒位顺序1

0

0

1

1

0

0

4

2

0

1

0

0

1

0

2

30

1

1

1

1

0

6

4

1

0

0

0

0

1

15

1

0

1

1

0

1

5

6

1

1

0

0

1

1

37

1

1

1

1

1

1

7倒位序规律由按时间抽选法FFT运算流图(书140页图3-6)可知，输出X[m]按正常顺序排列在存储单元，而输入x[k]是按顺序:01010101以N=8为例，说明如下:k0=1(奇)k0=0(偶)k1=0k1=1k1=0k1=1k0k1k2x[000]0x[100]4x[010]2x[110]6x[001]1x[101]5x[011]3x[111]7序号kx[0]x[1]x[2]x[3]x[4]x[5]x[6]x[7]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)不必调换数值交换x[k]与x[]之间数值1.原位计算n表示第n级迭代，m，j表示数据所在的行数输入数据、中间运算结果和最后输出均用同一存储器Xn-1[m]Xn-1[j]第二级的蝶形系数为，蝶形节点的距离为2。第一级的蝶形系数均为，蝶形节点的距离为1。第三级的蝶形系数为，蝶形节点的距离为4。第M级的蝶形系数为，蝶形节点的距离为N/2。级数碟形运算的数量序列倒序序列原位旋转因子分布例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。(书上作业3-5)解：

根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和

x2[k]，则存在

其中x1[k]={1,1,2,1}，x2[k]={-1,-1,1,2}，X1[m]和X2[m]可通过4点的FFT来计算。例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：

X1[m]={5,-1,1,-1},X2[m]={1,-2+3j,1,-2-3j}利用上述公式，可得序列x[k]的DFTX[m]为X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}快速傅里叶变换(FFT)基2时间抽取FFT算法与DFT的运算量对比算法的特点在基-2FFT算法的流图中，当序列长度N=32时，一共有_________级蝶形运算，蝶形个数为________，共完成______次复数加法、_______次复数乘法。若直接完成DFT计算共需要_____次复数加法、______次复数乘法。若输入序列按自然顺序排列，序号为13的输出序列号(倒位序)是_____________。画出N=4基-2FFT时间抽取蝶形流程图。42本节课内容按频率抽选的基-2FFT算法*FFT算法应用433.2按频率抽取(DIF)的基-2FFT算法

—桑德-图基（Sand-Tukey）算法基2时间抽取FFT算法输入序列x[k]按其顺序的偶、奇数分解为越来越短的序列。基2频率抽取(DIF)FFT算法输出序列X[m](也是N点序列)按其顺序的偶、奇来分解为越来越短的序列。44一、算法原理设序列点数N=2L，L为整数。将X[m]按m的奇偶分组前，先将输入x[k]按k的顺序分成前后两半：4546

按m的奇偶将X[m]分成两部分：x1[k]x2[k]47则X[2r]和X[2r+1]分别是x1[k]和x2[k]的N/2点DFT，记为X1[m]和X2[m]，碟形运算为：令-1WNk48x1[0]x1[1]x1[2]x1[3]x2[0]x2[1]x2[2]x2[3]N/2点DFTN/2点DFTx[0]x[7]x[1]x[2]x[3])x[4]x[5]x[6]X1[0]=X[0]X1[1]=X[2]X1[2]=X[4]X1[3]=X[6]X2[0]=X[1]X2[1]=X[3]X2[2]=X[5]X2[3]=X[7]-1-1-1-13NW-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]50N/2仍为偶数，进一步分解：N/2

N/451x3[0]x4[0]x3[1]x4[1]N/4点DFTN/4点DFTx1[0]x1[1]x1[2]x1[3]X3[0]=X1[0]=X[0]X3[1]=X1[2]=X[4]X4[0]=X1[1]=X[2]X4[1]=X1[3]=X[6]-1-152同理：其中：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-1已知有限长序列x[k]

数值为

{1,2,-1,3}，请按频率抽选的基-2FFT(快速傅里叶变换)运算过程求X[m]，并画出蝶形流程图

解：56二、算法特点1.原位计算L级蝶形运算，每级N/2个蝶形。2.蝶形运算距离对N=2L点FFT，输入自然序，输出倒位序，两节点距离：2L-n=N/2n例如N=23=8

：

(1)n=1时的距离为

8/2=4；

(2)n=2

时的距离为

8/4=2;

(3)n=3

时的距离为

8/8=1。0NW1NW2NW3NW-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-158二、算法特点3.运算量级数：log2N每级的蝶形数：N/2每蝶形：复乘1次，复加2次总运算量：

复乘(N*log2N)/2次

复加N*log2N次59(1)相同点

(a).进行原位运算；

(b).运算量相同，均为(N/2)Log2N次复乘，NLog2N次复加。3.DIF法与DIT法的异同60(2)不同点

(a).DIT输入为倒位序，输出为自然顺序；

DIF输入为自然顺序，输出为倒位序；61(b).蝶形运算不同DITDIF62(c)两种蝶形运算的关系

互为转置(矩阵)；将算法流图的所有支路方向都反向，交换输入和输出，即可得到另一种蝶形。

(DIT)1111(DIF)638点序列DIT8点序列DIFX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]X[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]648点序列DIT8点序列DIFX[0]X[6]X[4]X[2]X[1]X[5]X[3]X[7]x[0]x[3]x[1]x[2]x[4]x[5]x[6]x[7]X[0]X[3]X[1]X[2]X[4]X[5]X[6]X[7]x[0]x[6]x[4]x[2]x[1]x[5]x[3]x[7]65FFT算法应用

利用N点复序列的FFT，计算两个N点实序列FFT

利用N点复序列的FFT，计算2N点序列的FFT

利用FFT计算IFFT利用N点复序列的FFT算法计算两个N点实序列FFT2个N点实序列：x[k],h[k]y[k]=x[k]+jh[k]目的：通过一次FFT求出X[m],H[m]构成复序列y*[k]=x[k]–jh[k]利用N点复序列的FFT算法计算两个N点实序列FFT2个N点实序列：x[k],h[k]目的：通过一次FFT求出X[m],H[m]利用N点复序列的FFT算法计算两个N点实序列FFT2个N点实序列：x[k],h[k]目的：通过一次FFT求出X[m],H[m]利用N点复序列的FFT

计算2N点序列的FFT69y[k]是一个长度为2N的序列例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。解：

根据基2时间抽取FFT算法原理，8点序列的DFTX[m]可由两个4点序列的DFTX1[m]和X2[m]表达。如果按照序列x[k]序号的奇偶分解为x1[k]和

x2[k]，则存在

其中x1[k]={1,1,2,1}x2[k]={-1,-1,1,2}

71例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。如何求X1[m]和X2[m]可通过一次的y[m]的DFT来计算。y[m]=x1[k]+jx2[k]={1-j,1-j,2+j,1+2j}x1[k]={1,1,2,1}x2[k]={-1,-1,1,2}

72Y*[(-m)4]={5-j,2+2j,1+j,-4+2j}Y[m]={5+j,-4-2j,1-j,2-2j}例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。73例：试利用N=4基2时间抽取的FFT流图计算8点序列x[k]={1,-1,1,-1,2,1,1,2}的DFT。X[m]={6,-0.293+3.535j,1+j,-1.707+3.535j,4,-1.707-3.535j,1-j,-0.293-3.535j}74利用FFT实现IFFT75IDFT的快速计算方法1.稍微变动FFT程序和参数可实现IFFT76DIF