fft算法原理学习教案

1、会计学1fft算法原理算法原理第一节第一节 直接计算直接计算DFTDFT的问题及改进途径的问题及改进途径1、问题的提出、问题的提出 设有限长序列设有限长序列x(n)，非零值长度为非零值长度为N，若对若对x(n)进行一次进行一次DFT运算，共需运算，共需多大的运算工作多大的运算工作量量？计算成本计算成本?计算速度计算速度?第1页/共61页2. DFT的运算量的运算量 回忆回忆DFT和和IDFT的变换式：的变换式： 10)(1)()(10 NnWkXNkXIDFTnxNknk10)()()(10 NkWnxnxDFTkXNnnkN1）x(n)为为复数复数， 也为也为复数复数。2）DFT与与IDFT

2、的的计算量相当。计算量相当。nkNjnkNeW 2 注意：注意： 第2页/共61页计算机运算时（编程实现）：计算机运算时（编程实现）： 0k0)1(0100) 1() 1 ()0()0(NNNNWNxWxWxX1k 0111(1)1(1)(0)(1)(1)NNNNXxWxWx NW 2k 0 212(1) 2(2)(0)(1)(1)NNNNXxWxWx NW1Nk0111(1)1(1)(0)(1)(1)NNNNNNNX NxWxWx NW 10)()()(10 NkWnxnxDFTkXNnnkN以以DFT为例：为例： 第3页/共61页复数乘法复数乘法复数加法复数加法一个一个X(k)NN 1N个

3、个X(k)(N点点DFT)N 2N (N 1)实数乘法实数乘法实数加法实数加法一次复乘一次复乘42一次复加一次复加2一个一个X (k)4N2N+2 (N 1)=2 (2N 1)N个个X (k)(N点点DFT)4N 22N (2N 1)10( )NnkNnx n W运算量运算量(a+jb)(c+jd)=(ac-bd)+j(bc+ad)第4页/共61页例：计算一个例：计算一个 N点点DFT ，共需共需N2次复乘次复乘。以做一次。以做一次 复乘复乘1s计，若计，若N =4096，所需时间为所需时间为ss1716777216)4096(2 例：石油勘探，有例：石油勘探，有24个通道的记录，每通道波形记

4、个通道的记录，每通道波形记 录长度为录长度为5秒，若每秒抽样秒，若每秒抽样500点点/秒，秒， 1）每道总抽样点数：）每道总抽样点数：500*5=2500点点 2）24道总抽样点数：道总抽样点数：24*2500=6万点万点 3）DFT复乘运算时间：复乘运算时间：N2=(60000)2=36*108次次ss360010*36)60000(82 第5页/共61页 由于计算量大，且要求由于计算量大，且要求相当大的内存相当大的内存，难以实现实时处理难以实现实时处理，限制了，限制了DFT的应用。长期以来，人们一直在寻求一种能的应用。长期以来，人们一直在寻求一种能提高提高DFT运算速度运算速度的方法。的方

5、法。 FFT便是便是 Cooley & Tukey 在在1965 年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。年提出的的快速算法，它可以使运算速度提高几百倍，从而使数字信号处理学科成为一个新兴的应用学科。第6页/共61页第二节第二节 改善改善DFTDFT运算效率的基本途径运算效率的基本途径knNW 1、利用、利用DFT运算的系数运算的系数 的固有对称性和周期的固有对称性和周期 性，改善性，改善DFT的运算效率。的运算效率。 1）对称性）对称性 2）周期性周期性 3）可约性）可约性第7页/共61页()() nkN n kn N kNNNW

6、WW周期性 nkmnkNmNWW可约性/nknk mNN mWW2jmnkmNe221NjjNee 0/2(/2) 11Nk NkNNNNWWWW 特殊点：nkNW 的特性2jnknkNNWe*()() ()nknkN n kn N kNNNNWWWW对称性NknkNNWWnNnkNNWW第8页/共61页2、将长序列、将长序列DFT利用对称性和周期性分解为短利用对称性和周期性分解为短 序列序列DFT的的思路思路 因为因为DFT的运算量与的运算量与N2成正比的，如果一个成正比的，如果一个大点数大点数N的的DFT能分解为能分解为若干小点数若干小点数DFT的组合的组合，则显然可以达到，则显然可以达到

7、减少运算工作量减少运算工作量的效果。的效果。第9页/共61页N点点DFTN/2点点DFTN/2点点DFTN/4点点DFTN/4点点DFTN/4点点DFTN/4点点DFT.复乘：复乘：2N2222 NN22N22224444 NNNN42N第10页/共61页 FFT算法的基本思想：算法的基本思想： 利用利用DFT系数的特性，合并系数的特性，合并DFT运算中的某些项运算中的某些项 把长序列把长序列DFT短序列短序列DFT，从而减少运算量。从而减少运算量。FFT算法分类算法分类:时间抽选法时间抽选法 DIT: Decimation-In-Time频率抽选法频率抽选法 DIF: Decimation-

8、In-Frequency第11页/共61页第三节第三节 按时间抽选的基按时间抽选的基2-FFT算法算法1、算法原理、算法原理 设输入序列长度为设输入序列长度为N=2M(M为正整数，将该序列为正整数，将该序列按时间顺序的奇偶分解按时间顺序的奇偶分解为越来越短的子序列，称为基为越来越短的子序列，称为基2按时间抽取的按时间抽取的FFT算法。也称为算法。也称为Coolkey-Tukey算法。算法。 其中其中基基2表示：表示：N=2M，M为整数为整数.若不满足这个条件，可以人为地加上若干零值（若不满足这个条件，可以人为地加上若干零值（加零补长加零补长）使其达到）使其达到 N=2M。第12页/共61页先将

9、先将x(n)按按n的奇偶分为两组，作变量置换的奇偶分为两组，作变量置换: 当当n=偶数时，令偶数时，令n=2r; 当当n=奇数时，令奇数时，令n=2r+1; 分组，变量置换分组，变量置换2、算法步骤、算法步骤10)()()(10 NkWnxnxDFTkXNnnkN得到：得到：1,.,0)() 12()()2(221 Nrrxrxrxrx第13页/共61页 带入带入DFT中中 10)()()(NnnkNWnxnxDFTkX 12/0)12(12/02)12()2(NrkrNNrrkNWrxWrx 1010)()(NnnkNNnnkNnnWnxWnx为为奇奇数数为为偶偶数数 12/02212/02

10、1)()(NrrkNkNNrrkNWrxWWrx第14页/共61页所以所以 12/02212/021)()()(NrrkNkNNrrkNWrxWWrxkX由于由于nNnNjnNjnNWeeW2/2/2222 12/02/212/02/1)()(NrrkNkNNrrkNWrxWWrx)()(21kXWkXkN 1, 1 , 02 Nk1, 1 , 0 Nk? ?1, 1 , 02 Nk第15页/共61页 X1(k)、X2(k)只有只有N/2个点，以个点，以N/2为周期；而为周期；而X (k)却有却有N个点，以个点，以N为周期。要用为周期。要用X1(k)、X2(k)表达全部的表达全部的X (k)

11、值，还必须利用值，还必须利用WN系数的系数的周期特性周期特性。rkNkNrNWW2/)2/(2/ 12/02/112/0)2/(2/11)()()2/(NrrkNNrkNrNWrxWrxkNX )()2/()()2/(2211kXkNXkXkNX第16页/共61页后半部分后半部分前半部分前半部分又考虑到又考虑到 的对称性：的对称性：kNWkNkNNNkNNWWWW 2/)2/()2/()2/()2/(2)2/(1kNXWkNXkNXkNN 有：有：1, 1 , 0)()()(221 NkNkkXWkXkX1, 1 , 0)()(221 NkNkkXWkX第17页/共61页后半部分后半部分前半部

12、分前半部分)()()2/(21kXWkXkNXkN )()()(21kXWkXkXkN 1, 1 , 02 Nk)(1kX)(2kXkNW)()(21kXWkXkN )()(21kXWkXkN 蝶形运算流图符号蝶形运算流图符号说明：说明： (1) 左边两路为输入左边两路为输入 (2) 右边两路为输出右边两路为输出 (3) 中间以一个小圆表示加、中间以一个小圆表示加、 减运算（右上路为相加减运算（右上路为相加 输出、右下路为相减输输出、右下路为相减输 出出)1个蝶形运算需要个蝶形运算需要1次复乘，次复乘，2次复加次复加第18页/共61页复数乘法复数乘法复数加法复数加法一个一个N 点点DFTN 2

13、N (N1)一个一个N / 2点点DFT(N / 2)2N / 2 (N / 2 1)两个两个N / 2点点DFTN 2 / 2N (N / 2 1)一个蝶形一个蝶形12N / 2个蝶形个蝶形N / 2N总计总计N2/2 + N/2 N2/2N(N/2-1) + N N2/2运算量减少了近一半运算量减少了近一半 分解后的运算量：分解后的运算量：第19页/共61页)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN 12/, 0 Nk先将先将N=8点的点的DFT分解成分解成2个个4点点DFT：可知：可知：时域上：时域上：x(0),x(2),x(4),x(6)为偶子序列为偶子

14、序列 x(1),x(3),x(5),x(7)为奇子序列为奇子序列 频域上：频域上：X(0)X(3)，由，由X(k)给出给出 X(4)X(7)，由，由X(k+N/2)给出给出例子：求例子：求 N=23=8点点FFT变换变换 按按N=8N/2=4，做做4点的点的DFT：第20页/共61页 N=8点的直接点的直接DFT的计算量为：的计算量为： 复乘：复乘：N2次次 = 64次次 复加：复加：N(N-1)次次 = 87=56次次)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN 12/, 0 Nk 此外，还有此外，还有4个蝶形结，每个蝶形结需要个蝶形结，每个蝶形结需要1次复乘，

15、次复乘，2次复加。次复加。一共是：复乘一共是：复乘4次，复加次，复加8次。次。得到得到X1(k)和和X2(k)需要：需要： 复乘：复乘：(N/2)2+ (N/2)2次次 = 32次次 复加：复加：N/2(N/2-1)+N/2(N/2-1) =12+12 =24次次用分解的方法得到用分解的方法得到X (k)需要：需要： 复乘：复乘：32+4 = 36次次 复加：复加：24+8 = 32次次第21页/共61页N点点DFT的一次时域抽取分解图的一次时域抽取分解图(N=8) 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)

16、X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)38W28W18W08W第22页/共61页 奇奇序序列列、偶偶序序列列、)6()2()4()0(: )(1xxxxrx 奇奇序序列列、偶偶序序列列、同同理理：)7()3()5() 1 (: )(2xxxxrx因为因为4点点DFT还是比较麻烦，所以再继续分解。还是比较麻烦，所以再继续分解。 若将若将N/2(4点点)子序列按奇子序列按奇/偶分解成两个偶分解成两个N/4点点(2点点)子序列。即对将子序列。即对将x1(r)和和x2(r)分解成奇、偶两个分解成奇、偶两个N/4点点(2点点)点的子序列。

17、点的子序列。1 , 0) 1.0()() 12()()2(44131 lllxlxlxlxN此此处处，奇奇序序列列偶偶序序列列设设：1 , 0) 1.0()() 12()()2(46252 lllxlxlxlxN此此处处，奇奇序序列列偶偶序序列列设设：第23页/共61页那么，那么，X1(k)又可表示为又可表示为 14/0)12(2/114/022/11)12()2()(NlklNNllkNWlxWlxkX 14/04/42/14/04/3)()(NllkNkNNllkNWlxWWlx)()(42/3kXWkXKN 1,.1 , 0)()()()()()(442/34142/31 NkNNkNk

18、kXWkXkXkXWkXkX第24页/共61页 14/0)12(2/214/022/22)21()2()(NlklNNllkNWlxWlxkX 14/04/62/14/04/5)()(NllkNkNNllkNWlxWWlx1,.1 , 0)()()()()()(462/54262/52 NkNNkNkkXWkXkXkXWkXkXX2(k)也可以进行相同的分解：也可以进行相同的分解： 注意：通常我们会把注意：通常我们会把 写成写成 。kNW2/kNW2)()(62/5kXWkXKN 第25页/共61页N点点DFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8) 2点点DFT2点点DFT2点

19、点DFT2点点DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)08W28W08W28WX1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)38W28W18W08WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)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)38W28W

20、18W08W第26页/共61页)1()0()()()(32314/04/333xWxWlxlxDFTkXkNlklN )1()0()1()0()1()1()0()0(30233123330233xWxxWxXxWxX 8808WX3(0)X3(1)x(0)=x3(0)x(4)=x3(1)第27页/共61页N点点DITFFT运算流图运算流图(N=8) x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW第28页/共61

21、页3、DITFFT算法与直接计算算法与直接计算DFT运算量的比较运算量的比较22log2NNN 1)、N=2M的的DFT运算可分成运算可分成M级，每一级有级，每一级有N/2个蝶形个蝶形 ，每个蝶形有一次复乘两次复加。，每个蝶形有一次复乘两次复加。NN2log2NN2log2)、所以、所以M级共有级共有 次复乘和次复乘和 次复加。次复加。3)、若直接计算、若直接计算DFT，需需N2次复乘和次复乘和N(N-1)次复加。次复加。显然，当显然，当N较大时，有：较大时，有：例如，例如，N=210=1024时时221048576204.8(/2)log5120NNN第29页/共61页FFT算法与直接计算算

22、法与直接计算DFT所需乘法次数的比较曲线所需乘法次数的比较曲线第30页/共61页4、DITFFT的运算规律及编程思想的运算规律及编程思想 FFT的每级（列）计算都是由的每级（列）计算都是由N个复数数据（输入）两两构个复数数据（输入）两两构成一个蝶型（共成一个蝶型（共N/2个蝶形）运算而得到另外个蝶形）运算而得到另外N个复数数据（输出个复数数据（输出）。）。 当数据输入到存储器以后，每一组运算的结果，当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一仍然存放在这同一组存储器中组存储器中直到最后输出。直到最后输出。例：将例：将x(0)放在单元放在单元A(0)中，将中，将x(4)放在单元放在

23、单元A(1)中，中，W80 放在一个暂存器中。放在一个暂存器中。将将x(0) + W80 x(4) 送回送回A(0)单元单元将将x(0) - W80 x(4) 送回送回A(1)单元单元08WX3(0)X3(1)x(0)x(4)1） 原位运算原位运算 (亦称同址计算亦称同址计算)第31页/共61页x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7) X(0) X(1) X(2) X(3) X(4) X(5) X(6) X(7) 0NW0NW0NW0NW0NW2NW0NW2NW0NW2NW1NW3NW回顾：回顾：N点点DITFFT运算流图运算流图(N=8) 第32页/共6

24、1页 如上所述，如上所述，N点点DITFFT运算流图中，每级都有运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以因子个蝶形。每个蝶形都要乘以因子WNP，称其为称其为旋转因子旋转因子，p称为旋转因子的指数。称为旋转因子的指数。2)旋转因子的变化规律旋转因子的变化规律 观察观察FFT运算流图发现，第运算流图发现，第L级共有级共有2L-1个不同的旋转因子。个不同的旋转因子。N=23=8时的各级旋转因子表示如下：时的各级旋转因子表示如下：L=1时，时，WNp=WN/4J， N/4 =21 =2L， J=0L=2时，时， WNp =WN/2J， N/2 =22 =2L， J=0，1L=3时，时， WN

25、p =WNJ， N =23 =2L， J=0，1，2，3第33页/共61页对对N=2M的一般情况，第的一般情况，第L级的旋转因子为：级的旋转因子为：12,.,1 , 012 LJPNJWWLMLMLMLN 222212,.,1 , 0122 LJNJNPNJWWWLMMLLMJp 2第34页/共61页 设序列设序列x(n)经时域抽选经时域抽选(倒序倒序)后，存入数组后，存入数组X中。如果蝶形运算的两个输入数据相距中。如果蝶形运算的两个输入数据相距B个点个点(B=2L-1)，应用原位计算，则蝶形运算可表示成如下形式：应用原位计算，则蝶形运算可表示成如下形式：pNLLLpNLLLWBJXJXBJX

26、WBJXJXJX)()()()()()(1111 MLJJpLLM,.,2 , 112,.,1 , 021 ，式式中中： 下标下标L表示第表示第L级运算，级运算，XL(J)则表示第则表示第L级运算后数组元素级运算后数组元素X(J)的值。的值。第35页/共61页3) 编程思想及流程图编程思想及流程图开始开始送入送入x(n)和和N=2M调整输入调整输入x(n)的顺序的顺序for(L=1; L=M; L+)B = 2L-1for(J=0; J=B-1; J+)p = J2M-Lfor(k = J; k= N-1; k=k+2L) pNpNWBkXkXBkXWBkXkXkX)()()()()()( 输

27、出结果输出结果结束结束第36页/共61页4）码位倒序码位倒序 由由N=8蝶形图看出：原位计算时，蝶形图看出：原位计算时，FFT输出的输出的X(k)的次序正好是顺序排列的，即的次序正好是顺序排列的，即X(0)X(7),但输入但输入x(n)都不能按自然顺序存入到存储单元中，而是按都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2),x(6) ,x(1),x(5),x(3),x(7)的顺序存入存储单元的顺序存入存储单元，即为乱序输入，顺序输出。即为乱序输入，顺序输出。 这种顺序看起来相当杂乱，然而它是这种顺序看起来相当杂乱，然而它是有规律有规律的。即的。即码位倒读规则码位倒读规则。第

28、37页/共61页自然顺序自然顺序n二进制码表二进制码表示示码位倒读码位倒读码位倒置顺序码位倒置顺序n以以N=8为例：为例：0123456700000101001110010111011100010001011000110101111104261537看出：看出：码位倒读后码位倒读后的顺序刚好是数据送入计算机内的顺序。的顺序刚好是数据送入计算机内的顺序。第38页/共61页x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(

29、1)x(5)x(3)x(7)倒序规律倒序规律第39页/共61页第40页/共61页正序序列已在数组正序序列已在数组A 中，输中，输 入入 NLH= N/2 , j=LH , N1 = N-2j=j-kk=k/2 k=LHjkj=j+k T = A(j) A(i) = A(j) A(j) = Tfor(i=1; i=N1; i+) i j第41页/共61页第四节第四节 按频率抽选的基按频率抽选的基2-FFT算法算法 在基在基2快速算法中，频域抽取法快速算法中，频域抽取法FFT也是一种常用的快速算法，简称也是一种常用的快速算法，简称DIFFFT。 设序列设序列x(n)长度为长度为N=2M，首先将首先

30、将x(n)前后对半分开，得到两个子序列，其前后对半分开，得到两个子序列，其DFT可表示为如下形式可表示为如下形式第42页/共61页 1-NN/2nknN1-N/20nknN1-N0nknNWnxWnxWnxX(k)()()( -1N/20n)2/(-1N/20n)2/()( NnkNknNWNnxWnx -1N/20n-1N/20n)2/()1()(knNkknNWNnxWnx1,.1 , 0 Nk kjkkNNjkNNeeW1222/ 式式中中， 12/01,.1 , 0,)2/(1)()(NnknNkNkWNnxnxkX第43页/共61页:)(k分为两部分分为两部分的奇偶可把的奇偶可把按按

31、kX12/.2 , 1 , 0,12,2 Nrrkrk及及令令为偶数时，为偶数时，K 12/02/12/02) 2/()() 2/()(2NnrnNNnrnNWNnxnxWNnxnxrX为奇数时，为奇数时，K 12/02/12/012)2/()()2/()(12NnrnNnNNnnrNWWNnxnxWNnxnxrX）（第44页/共61页nNW)2/()()(1Nnxnxnx nNWNnxnxnx)2/()()(2 )(nx)2/(Nnx 1,.,1 , 0)2/()()()2/()()(221 NnNnWNnxnxnxNnxnxnx令令 nrNNnnrNNnWnxrXkXWnxrXkX2/12

32、/0222/12/011)()12()()()2()(第45页/共61页DIFFFT一次分解运算流图一次分解运算流图(N=8) 4点点DFT4点点DFTx(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)3NW2NW1NW0NWx1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)第46页/共61页DIFFFT二次分解运算流图二次分解运算流图(N=8) N/4点DFTWN0WN1WN2WN3x(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)

33、X(5)X(3)X(7)WN0WN2WN0WN2N/4点DFTN/4点DFTN/4点DFT第47页/共61页DIFFFT运算流图运算流图(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第48页/共61页 时间抽取算法与频率抽取算法的比较时间抽取算法与频率抽取算法的比较1) 频率抽选法和时间抽选法总的计算量是相同的频率抽选法和时间抽选法总的计算量是相同的NN2log2NN2log复乘：复乘：复加：复加：2) 频率抽取法和时间抽取法一样

34、，都适用于频率抽取法和时间抽取法一样，都适用于原位运原位运 算算， 即蝶形的输入和输出占用同一个存储单元。即蝶形的输入和输出占用同一个存储单元。3) 均存在码位倒序问题。均存在码位倒序问题。4) 频率抽选法和时间抽选法一样，基本运算也是蝶形频率抽选法和时间抽选法一样，基本运算也是蝶形 运算。但两者的蝶形形式略有不同。运算。但两者的蝶形形式略有不同。第49页/共61页第五节第五节 IDFT的快速算法的快速算法IFFT上述上述FFT算法流图也可以用于离散傅里叶逆变换算法流图也可以用于离散傅里叶逆变换(Inverse Discrete Fourier Transform，简称简称IDFT)。比较比较

35、DFT和和IDFT的运算公式：的运算公式：10)(1)()(10 NnWkXNkXIDFTnxNknk10)()()(10 NkWnxnxDFTkXNnnkN1) 旋转因子：旋转因子：kNkNWW 2) 系数：系数：MNN21 ，第50页/共61页DITIFFT运算流图运算流图 WN0WN1WN2WN3WN0WN0N1x(0)x(4)x(2)x(6)x(4)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1N1第51页/共61页DITIFFT运算流图运算流图(防止溢出防止溢出) WN02121x(0)x(4)x(2)x(

36、6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021第52页/共61页 如果希望直接调用如果希望直接调用FFT子程序计算子程序计算IFFT，则可用下面的方法：则可用下面的方法：10101( )( )1( )( )NknNkNknNkx nX k WNx nXk WN对上式两边同时取共轭，得：对上式两边同时取共轭，得：1011( )( )( )NknNkx nX k WDFT X kNN第53页/共61页例例1、如果通用计算机的速度为平均每次复乘需要、如果通用计算机的速度为平均每次