数字信号处理优秀获奖课件第四章PPT

1、4-5线性卷积的FFT算法4-3 DIF的FFT算法4-4 IFFT算法4-2按时间抽取(DIT)的FFT算法4-1 引言4-14-1引言引言一一.DFT.DFT的计算工作量的计算工作量 两者的差别仅在指数的符号和因子1/N. 1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx 通常x(n)和都是复数,所以计算一个 X(k)的值需要N次复数乘法运算,和 次 复数加法运算.那么,所有的X(k)就要N2次复 数乘法运算,N(N-1)次复数加法运算.当N很 大时,运算量将是惊人的,如N=1024,则要完 成1048576 次(一百多万

2、次)运算.这样,难以做到实时处理.nkNW1N一个X(k)的值的工作量,如X(1)1210) 1() 2() 1 () 0() 1 (NNNNNWNxWxWxWxX二二.改进的途径改进的途径 1. 的对称性和周期性nkNW;,)()()(*NknNkNnNnkNnkNnkNWWWWW.),1( 1),1()2/(2/)(2)()(2kNNkNjNNNnkNnNNkNnkNknNNkNnNWWeWWeWWWWWN得:对称性:周期性: 利用上述特性利用上述特性, ,可以将有些项合并可以将有些项合并, ,并并将将DFTDFT分解为短序列分解为短序列, ,从而降低运算次数从而降低运算次数, ,提提高运

3、算速度高运算速度.1965.1965年年, ,库利库利(cooley)(cooley)和图基和图基(Tukey)(Tukey)首先提出首先提出FFTFFT算法算法. .对于对于N N点点DFT,DFT,仅需仅需(N/2)log(N/2)log2 2N N 次复数乘法运算次复数乘法运算. .例如例如N=1024=2N=1024=21010 时，时，需要需要(1024/2)log(1024/2)log2 2 2 21010 =512 =512* *10=512010=5120次。次。5120/1048576=5120/1048576=4.88%4.88% , ,速度提高速度提高2020倍倍4-2

4、4-2 按时间抽取按时间抽取(DIT)(DIT)的的FFTFFT算法算法 库利库利- -图基算法图基算法一一. .算法原理算法原理( (基基2FFT)2FFT)( (一一)N/2)N/2点点DFTDFT1.1.先将 按n的奇偶分为两组作DFT,DFT,设N=2N=2L L ,不足时,可补些零。这样有: n为偶数时: : n为奇数时: :1, 1 , 0 ),() 12(1, 1 , 0 ),()2(2221NNrrxrxrrxrx10)()()(NnnkNWnxnxDFTkX因此，)(nx由于由于: : 所以所以, ,上式可表示为上式可表示为: :1022102110)12(102101022

5、22)()()12()2()()()(NNNNrrkNkNrrkNrkrNrrkNNnNnnkNnkNWrxWWrxWrxWrxWnxWnxkX(n为偶数) (n为奇数)222)/(222NNNWeeWjjN)()()()()(211021012222kXWkXWrxWWrxkXkNrrkkNrrkNNNN 其中,2.2.两点结论: (1) X (1) X (k),X(k),X (k)(k)均为N/2N/2点的DFTDFT。 (2) X(k)=X(2) X(k)=X (k)+W(k)+W X X (k)(k)只能确定出 X(k)X(k)的k= k= 个；即前一半的结果。1 21 2kN1010

6、2210101122222222) 12()()()2()()(NNNNNNNNrrkrrkrrkrrkWrxWrxkXWrxWrxkX1, 1 , 02 N 同理, 这就是说,X1(k),X2(k)的后一半,分别 等于其前一半的值。3.X(k)3.X(k)的后一半的确定的后一半的确定rkkrNNNWW222)()()()()2(1101)(101122222kXWrxWrxkNXNNNNNrrkkrr由于 （周期性）（周期性）, ,所以:)()2(22kXkNX 可可见,X(k)X(k)的后一半，也完全由X X1 1(k)(k), X X2 2 (k)(k)的前一半所确定。 *N点的DFT可

7、由两个N/2点的DFT来计算。kNkNNkNWWWWNN22)()2()2()2(212NkXWNkXNkXNkN1, 1 , 0 ),()(221NkNkkXWkX又由于 , ,所以实现上式运算的流图称作蝶形运算 前一半4.4.蝶形运算蝶形运算 后一半（N/2个蝶形)(前一半)(后一半)1 1 11-1-1)()()()()()(2121kXWkXkXkXWkXkXkNkN)1,()1, 1 ,0(22 N Nk kk kN NN N)()()(21kXWkXkXkN)()()2(21kXWkXkNXkN)(1kX)(2kXkNW由X1(k)、X 2(k)表示X(k)的运算是一种特殊的运算-

8、碟形运算(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数: (3)N/2个蝶形运算的运算量:复乘次数:复加次数: : 5. .计算工作量分析计算工作量分析复乘:复加:4)2(22NN)12(2NN22N)12(NN2NNN222)12(2NNNN22222NNN总共运算量:按奇、偶分组后的计算量： *但是,N N点DFTDFT的复乘为N N2 2 ; ;复加N(N-1);N(N-1);与分解后相比可知,计算工作点差不多减少 一半。 例如 N=8N=8 时的DFT,DFT,可以分解为两个 N/2=4N/2=4点的DFTDFT.具体方法如下:

9、: (1)n(1)n为偶数时,即 分别记作: : )(42/1kXDFTN，得点的进行3 , 2 , 1 , 0)2()()(30430411kWrxWrxkXrrkrrk);6()3(),4()2(),2()1(),0()0(1111xxxxxxxx);6(),4(),2(),0(xxxx (2) n (2) n为奇数时,分别记作:);7()3(),5()2(),3()1(),1()0(2222xxxxxxxx3 , 2 , 1 , 0) 12()()(30430422kWrxWrxkXrrkrrk)(42/2kXDFTN，得点的进行3 , 2 , 1 , 0),()() 4()()()(2

10、121kkXWkXkXkXWkXkXkNkN x1 1(0)=(0)=x(0) (0) x1(1)=(1)=x(2) (2) N/2N/2点点 x1(2)=(2)=x(4) DFT (4) DFT x1(3)=(3)=x(6) (6) x2(0)=(0)=x(1) (1) x2(1)=(1)=x(3) (3) N/2N/2点点 x2(2)=(2)=x(5) (5) DFT DFT x2(3)=(3)=x(7)(7) 1 2 X X1(0)(0)X X1(1)(1)X X1(2)(2)X X1(3)(3)X X2(0)(0)X X2(1)(1)X X2(2)(2)X X2(3)(3)WN2WN1

11、WN0WN3-1-1-1-1X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)(3)(3)对X X (k)(k)和X X (k)(k)进行蝶形运算,前半部为 X(0) X(3),X(0) X(3),后半部分为X(4) X(7)X(4) X(7) 整个过程如下图所示: 由于N=2N=2 L , ,所以 N/2N/2仍为偶数,可以进 一步把每个N/2N/2点的序列再按其奇偶部分 分解为两个N/4N/4的子序列。例如，n为偶数时的 N/2N/2点分解为:( (二二) N/4) N/4点点DFTDFT1, 1 , 0),()

12、2(431Nlxlx1, 1 , 0),() 12(441Nlxlx进行N/4N/4点的DFTDFT,得到klNllkNllkNllkNlWlxWlxkXWlxWlxkXNNNN) 12(2/1014/104422/1014/1033) 12()()()2()()(4444( (偶中偶) )( (偶中奇) )()()(4312kXWkXkXkN1, 1 , 04Nk从而可得到前N/4的X1(k)()()4(4312kXWkXkNXkN后N/4的X1(k)为1, 1 , 04Nk( (奇中偶奇中偶) )104/64/1026104/5104/254444)()12()()()2()(NNNNll

13、kNlkNlllkNllkNWlxWlxkXWlxWlxkX( (奇中奇奇中奇) )同样对n n为奇数时，N/2N/2点分为两个N/4N/4点 的序列进行DFT，则有:14, 1 , 0k; (k)XW(k) X(k) X6kN/252N14, 1 , 0k; (k)XW(k) Xk)4N( X6kN/252N进行碟形运算，得：、由)()(65kXkX 例如,N=8N=8时的DFTDFT可分解为四个N/4N/4的DFT,DFT, 具体步骤如下: :)4()2() 1 ()0()0()0()()()(131313xxxxxxnxrxlx(1) 将原序列x(n)的“偶中偶”部分:构成N/4点DFT

14、，从而得到X3(0), X3(1)。)6()3()1()2()1()0()()()(141414xxxxxxnxrxlx(2) 将原序列x(n)的“偶中奇”部分:构成N/4点DFT，从而得到X4(0), X4(1)。(3) 将原序列x(n)的“奇中偶”部分:)5()2()1()1()0()0()()()(252525xxxxxxnxrxlx构成N/4点DFT，从而得到X5(0), X5(1)。(4) 将原序列x(n)的“奇中奇”部分:)7()3()1()3()1()0()()()(262626xxxxxxnxrxlx构成N/4点DFT，从而得到X6(0), X6(1)。（5）由 X3(0),

15、X3(1), X4(0), X4(1)进行碟形运算, 得到X1(0), X1(1), X1(2), X1(3)。（6）由 X5(0), X5(1), X6(0), X6(1)进行碟形运算, 得到X2(0), X2(1), X2(2), X2(3)。 (0)= (0)= (0) N/4 (1)= (2)= (4) DFT (0)= (1)= (2) N/4 (1)= (3)= (6) DFT (0)= (0)= (1) N/4 (1)= (2)= (5) DFT (0)= (1)= (3) N/4 (1)= (3)= (7) DFT3 13 14 14 15 25 26 26 2 02NN02N

16、NWWWW0123NNNN-1-1-1-2-1-1WWWWX (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566X (0)X (1)X (2)X (3)X (0)X (1)X (2)X (3)11122221X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxxxxxxxxxxxxxxxxxx（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) 。 这样,又

17、一次分解,得到四个N/4N/4点DFT,DFT, 两级蝶形运算,其运算量有大约减少一半 即为N N点DFTDFT的1/41/4。 对于N=8N=8时DFT,N/4DFT,N/4点即为两点DFT,DFT,因此 0,1k ,)()(0,1k ,)()(0,1k ,)()(0,1k ,)()(4/1066104/55104/44104/33lkNlllkNllkNllkNWlxkXWlxkXWlxkXWlxkX 亦即, )4()0() 1 ()0() 1 ()4()0() 1 ()0()0(031233030233xWxxWxXxWxxWxXNN)6()2() 1 ()0() 1 ()6()2()

18、1 ()0()0(041244040244xWxxWxXxWxxWxXNN) 5() 1 () 1 ()0() 1 () 5() 1 () 1 ()0()0(051255050255xWxxWxXxWxxWxXNN)7() 3() 1 ()0() 1 ()7() 3() 1 ()0()0(061266060266xWxxWxXxWxxWxXNN (0) (4) (2) (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X

19、(1)X (2)X (3)X (0)X (1)X (2)X (3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxx因此,8点DFT的FFT的运算流图如下 这种FFTFFT算法,是在时间上对输入序列 的次序是属于偶数还是属于奇数来进行分 解的,所以称作按时间抽取的算法 。 二二. .运算量运算量 由上述分析可知,N=8N=8需三级蝶形运算 N=2 =8,N=2 =8,由此可知,N=2N=2L L 共需L L级蝶形运算, 而且每级都由N/2N/2个蝶形运算 组成,每个蝶 形运算有一次复乘,两次复加。( (DIT

20、DIT) )3 3 因此,N N点的FFTFFT的运算量为复乘: m mF F = =（N/2N/2）L=L=（N/N/2） loglog2 2 N N复加: a aF F =N L=N log =N L=N log2 2 N N 由于计算机的乘法运算比加法运算所 需的时间多得多，故以乘法作为比较基准.如表4-1-1所示(pp.145）。 (0)=(0)=X X0 0(0)(0) X X1 1(0)(0) X X2 2(0) X(0) X3 3(0)(0)=X(0) =X(0) (4)=(4)=X X0 0(1)(1) X X1 1(1) X(1) X2 2(1) X(1) X3 3(1)(1

21、)=X(1)=X(1) (2)=(2)=X X0 0(2)(2) X X3 3(2)(2)=X(2)=X(2) (6)=(6)=X X0 0(3)(3) X X3 3(3)(3)=X(3)=X(3) (1)=(1)=X X0 0(4)(4) X X1 1(4) X(4) X2 2(4) X(4) X3 3(4)(4)=X(4)=X(4) (5)=(5)=X X0 0(5)(5) X X3 3(5)(5)=X(5)=X(5) (3)=(3)=X X0 0(6)(6) X X3 3(6)(6)=X(6)=X(6) (7)=(7)=X X0 0(7)(7) X X1 1(7) X(7) X2 2(7

22、) X(7) X3 3(7)(7)=X(7)=X(7)WWWWN0N0N0N0-1-1-1-1WWWWN0N2N0N2-1-1-1-1WWWWNNNN0123.三三.DIT.DIT的的FFTFFT算法的特点算法的特点 1.1.原位运算输入数据、中间运算结果和最后输出均用同一存储器。xxxxxxxxrNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111),3()6(),2()2(),1 ()4(),0()0(0000XxXxXxXx).7()7(),6()3(),5()5(),4() 1 (0000XxXxXxXx 设用m(m=1,2, ,L)表示第m列; ;用用k,j

23、k,j表示蝶形输入数据所在的（上/下）行数(0,1,2, ,N-1);(0,1,2, ,N-1);这时任何一个蝶形运算可用下面通用式表示， 即 由运算流图可知,一共有N N个输入个输入/ /出出行,一共有loglog2 2 N=LN=L列（级）蝶形运算( (基本迭代运算). ). 所以,当m=1时时, ,则有（前两个蝶形） 00010001)1()0()1()1()0()0(NNWXXXWXXX00010001)3()2()3()3()2()2(NNWXXXWXXX 当m=2时,则有（前两个蝶形） 当m=3时,则有（前两个蝶形） 2112211201120112)3()1()3()3()1()

24、1()2()0()2()2()0()0(NNNNWXXXWXXXWXXXWXXX1223122302230223)5()1()5()5()1()1()4()0()4()4()0()0(NNNNWXXXWXXXWXXXWXXX 可见,在某列进行蝶形运算的任意两个节点( (行)k)k和j j的节点变量 就完全可以确定蝶形运算的结果 ,与其它行( (节点) )无关。 这样,蝶形运算的两个输出值仍可放回蝶形运算的两个输入所在的存储器中,即实现所谓原位运算。每一组( (列) )有N/2N/2个蝶形运算,所以只需N N个存储单元，可以节 省存储单元。)(),(jXkXmm)(),(11jXkXmm 2 2

25、 倒位序规律倒位序规律 由图可知,输出X X(k)(k)按正常顺序排列在存储单元,而输入是按顺序: 这种顺序称作倒位序,即二进制数倒位。）；）；7 (),3 (),5 (),1 (6 (),2(),4(),0 (xxxxxxxxn =00n =10n =01n =11n =01n =1101010101 x xx xx xx xx xx xx xx x),(012nnnx(n2)x(000) 0 乾x(100) 4 兑x(010) 2 离x(110) 6 震x(001) 1巽x(101) 5 坎x(011) 3 艮x(111) 7 坤（偶）（奇） 这是由奇偶分组造成的,以N=8N=8为例 说明

26、如下: 3.3.倒位序实现倒位序实现 输入序列先按自然顺序存入存储单 元,然后经变址运算来实现倒位序排列 设输入序列的序号为n n,二进制为 (n2 n1 n0 )2 , ,倒位序顺序用 表示,其倒位序二进制为(n0 n1 n2 )2 , ,例如 ，N=8N=8时如下表： n 0 00 0 0 0 0 00 0 0 0 0 0 0 0 1 01 0 0 0 1 11 1 0 0 0 4 0 4 2 02 0 1 1 0 00 0 1 1 0 2 0 2 3 03 0 1 1 1 11 1 1 1 0 6 0 6 4 14 1 0 0 0 00 0 0 0 1 1 1 1 5 15 1 0 0

27、1 11 1 0 0 1 5 1 5 6 16 1 1 1 0 00 0 1 1 1 3 1 3 7 17 1 1 1 1 11 1 1 1 1 7 1 7 自然顺序n n 二进制n n n n n n 倒位序二进制n n n n n n 倒位顺序n n2 1 0 0 1 2A(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)x(0) x(4) x(2) x(6) x(1) x(5) x(3) x(7)变址处理方法变址处理方法存储单元自然顺序变址倒位序4.4.蝶形运算两节点的距离蝶形运算两节

28、点的距离: :2m-1 其中,m表示第m列, ,且且m =1, ,L=1, ,L 例如N=8=2N=8=23 3 , ,第一级( (列) )距离为2 21-11-1=1,=1, 第二级( (列) )距离为2 22-12-1=2=2， 第三级( (列) )距离为2 23-13-1=4=4。5.WNr 的确定(仅给出方法) ) 考虑蝶形运算两节点的距离为2m-1 , ,蝶 形运算可表为 Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNr Xm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr 由于N N为已知,所以将r r的值确定即可。 为此，令k=(n2n1n0)2 , ,

29、再再将k= (n2n1n0)2 左移(L-m)位,右边位置补零,就可得到(r)2 的值，即(r)2 =(k)22L-m 。 例如 N=8=2N=8=23 3 (1) (1)k=2 , m=3 的r r值,k=2=(010)2 左移L-m=3-3=0 , r=(010)2=2; (2)k=3 ,m=3 的r r值; ; k= 3=(011)2,左移0位,r=3r=3； (3)(3)k=5 ,m=2的值; ; k=5=(101)2 左移L-m=1=1位 r=(010)2 =2。 6 6.存储单元 存输入序列 (n),n=0,1, ,N-1, (n),n=0,1, ,N-1, 计N N 个单元; ;

30、 存放系数 , r=0,1, , r=0,1, ,（N/2N/2）-1,-1, 需N/2N/2个存储单元； 共计(N+N/2)个存储单元。xr rN NW W4-3 DIF4-3 DIF的的FFTFFT算法算法( (桑德桑德图基算法图基算法) ) 一一. .算法原理算法原理 1.N1.N点DFTDFT的另一种表达形式10)()(NnnkNWnxkX10)(1012/102222)2()()()(NNNNnknNnnkNNNnnkNnnkNWNnxWnxWnxWnx 由于 故 因此 X(k)可表为 nkNnkNWWNnxnxNN1022)2()(, 12jNeWNkkNNW) 1(2nkNnkW

31、NnxnxkXN102)2() 1()()(1, 1 , 0Nk 2.N点DFT按k的奇偶分组可分为两个N/2的DFT 当k k为偶数,即 k=2rk=2r时,(-1)k =1； 当k k为奇数,即 k=2r+1 k=2r+1 时 (-1)k =-1 。 这时 X(k)X(k) 可分为两部分： nrnnrNnNNNWNnxnxWNnxnx22210210)2()()2()()2( rXr1, 1 , 02Nrk k为偶数时： 可见,上面两式均为N/2N/2的DFTDFT。nrnnNrnNnNNNWWNnxnxWNnxnxrX22210)12(10)2()()2()() 12(xxk k为奇数时

32、：1, 1 , 02Nr-1-1)2()(Nnxnx1, 1 ,02NnnNWNnxnx)2()(3.3.蝶形运算进行如下碟形运算：和)2()(NnxnxnNW)2(Nnx)(nx-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 34.N=84.N=8时时, ,按按k k的奇偶分解过程的奇偶分解过程 先蝶形运算，后先蝶形运算，后DFT:DFT:)0( x) 1 ( x)5( x)4( x) 3( x)2( x)7( x)6( x)0(X)2(X)6(X) 1 (X) 3(X)5(X)7(X)4(XDFTN点2DFTN点2 5.5.仿照DITD

33、IT的方法 再将N/2N/2点DFTDFT按k k的奇偶分解为两个N/4N/4点的DFTDFT,如此进行下去,直至分解为2 2点DFTDFT。 (0) X(0) (0) X(0) (1) X(4) (1) X(4) (2) X(2) (2) X(2) (3) X(6) (3) X(6) (4) X(1) (4) X(1) (5) X(5) (5) X(5) (6) X(3) (6) X(3) (7) X(7) (7) X(7)-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 01 12 23 3-1-1-1-1-1-1-1-1W WW WW WW WN NN

34、NN NN N0 02 20 02 2-1-1-1-1-1-1-1-1W WW WW WW WN NN NN NN N0 00 00 00 0 xxxxxxxx例如 N=8N=8时DIFDIF的FFTFFT流图如下： 二二.原位运算原位运算 每级(列)都是由N/2N/2个蝶形运算构 成,即 -1-1W WN Nr rrNmmmmmmWjXkXjXjXkXkX)()()()()()(1111)(1kXm)(1jXm)()()(11jXkXkXmmmrNmmmWjXkXjX)()()(11三三.蝶形运算两节点的距离蝶形运算两节点的距离 一般公式为2L-m =N/2m 例如 N=2N=23 3 =8

35、 =8 ： (1)(1)m=1 时的距离为 8/2=48/2=4； (2) (2)m=2 时的距离为 8/4=2;8/4=2; (3) (3)m=3 时的距离为 8/8=18/8=1。r r的求法的求法： k=(n2 n1 n0 ) , ,左移m-1位, ,右边空出补零, ,得(r)(r)2 2 , ,亦即(r)(r)2 2 =(k) =(k)2 2 2m-1 . .例如,N=8:,N=8:(1)m=1,k=2, k=(010)(1)m=1,k=2, k=(010)2 2 左移0位,(r),(r)2 2=(010)=(010)2 2=2;=2;(2)m=2,k=1, k=(001)(2)m=2

36、,k=1, k=(001)2 2 左移1 1位,(r),(r)2 2=(010)=(010)2 2=2;=2;(3)m=2,k=5, k=(101)(3)m=2,k=5, k=(101)2 2 左移1 1位,(r),(r)2 2=(010)=(010)2 2=2 .=2 .rNmmmmmmmmmWNkXkXNkXNkXkXkX)2()()2()2()()(1111四四. . 的计算的计算 由于DIFDIF蝶形运算的两节点的距离为 N/2m , , 所以蝶形运算可表为：rNW 1. 1.相同点 (1)(1)进行原位运算； (2)(2)运算量相同, ,均为（N/2) Log2N次复乘, ,N Lo

37、g2N次复加。 2.2.不同点 (1)DIT(1)DIT输入为倒位序,输出为自然顺序； DIFDIF正好与此相反。但DITDIT也有输入为自然顺序,输出为倒位序的情况。五五.DIFDIF法与法与DITDIT法的异同法的异同rNmmmWjXkXjX)()()(11rNmmmWjXkXkX)()()(11)(1kXm)(1jXmrNW1(2)(2)蝶形运算不同a.a.(DIT)(DIT)用矩阵表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11rNmmmWjXkXjX)()()(11)()()(11jXkXkXmmm)(1kXm)(1jXmrNW1b.b.(DFT)(DFT)用矩阵表示)(kXm)(jXmrNWrNW)(1kXm)(1jXm=11(3)(3)两种蝶形运算的关系 互为转置（矩阵）； 将流图的所有支路方向都反向, ,交换输入和输出，即可得到另一种蝶形。 a.a.(DIT)(DIT)b.b.(DFT)(DFT)rNWrNW1111rNWrNW 4-4 IFFT4-4 IFFT算法算法一一.稍微变动稍微变动FFT程序和参数可实现程序和参数可实现IFFT nkNNkNnnkNWkXNkXIDFTnxWnxnxDFTkX1010)(1)()()()()( 比较两式可知,