快速傅里叶变换武汉理工大学数字信号处理

1、第第5章章快速傅里叶变换快速傅里叶变换(FFT)Fast FourierTransforming快速付里叶变换快速付里叶变换FFT 有限长序列通过离散傅里叶变换 (DFT)将其频 域离散化成有限长序列.但其计算量太大(与N的平方成正比）, 很难 实时地处理问题 , 因 此 引 出 了 快 速 傅 里 叶 变 换(FFT) . FFT 并 不 是 一 种 新 的 变 换 形 式 ,它 只 是 DFT 的 一 种 快快 速速 算算 法法 . 并 且 根 据 对 序 列 分 解 与 选 取 方 法 的 不 同 而 产 生 了 FFT 的 多 种 算 法 . FFT 在 离 散 傅 里 叶 反 变 换

2、 、 线 性 卷 积 和 线 性 相 关 等 方 面 也 有 重 要 应 用.。二、FFT产生故事 当时加文(Garwin)在自已的研究中极需要一个计算付里叶变换的快速方法。他注意到图基(J.W.Turkey)正在写有关付里叶变换的文章，因此详细询问了图基关于计算付里叶变换的技术知识。图基概括地对加文介绍了一种方法，它实质上就是后来的著名的库利(Cooley J.W)图基算法。在加文的迫切要求下，库利很快设计出一个计算机程序。1965年库利-图基在、Mathematic of Computation 杂志上发表了著名的“机器计算付里级数的一种算法”文章，提出一种快速计算DFT的方法和计算机程序

3、-揭开了FFT发展史上的第一页，促使FFT算法产生原因还有1967年至1968年间FFT的数字硬件制成，电子数字计算机的条件， 使DFT的运算大简化了。直接计算DFT的问题及改进的基本途径1.比较DFT与IDFT之间的运算量10)()()(NnknNDFTWnxkXnx1, 1 , 0Nk101( )( )( )NIDFTknNkX kx nX k WN 1, 1 , 0Nn其中x(n)为复数， 也为复数所以。knNjknNeW22.以DFT为例，计算DFT复数运算量 计算一个X(k)(一个频率成分)值，运算量为例k=1则要进行N次复数乘法 (N-1)次复数加法所以，要完成整个DFT运算，其计

4、算量为：N*N次复数相乘和次复数相乘和N*(N-1)次复数加法次复数加法10)() 1 (NnnNWnxX3.一次复数乘法换算成实数运算量 复数运算要比加法运算复杂，需要的运算时间长。 一个复数乘法包括4个实数乘法个实数乘法 和和2个实数加法个实数加法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad) 4次实数乘法2次实数加法 每运算一个X(k)的值，需要进行4N次实数相乘和 2N+2(N-1)=2(2N-1)次实数相加.整个DFT运算量为： 4N2次实数相乘和次实数相乘和2N(2N-1)次实数相加次实数相加.由此看出： 直接计算DFT时，乘法次数与加法次数都是和N2成比例的。当N很

5、大时，所需工作量非常可观。)Re)(ImIm)(Re) Im)(ImRe)(Re)(10knNknNNnknNknNWnxWnxjWnxWnxkX例子 例1:当N=1024点时，直接计算DFT需要： N2=220=1048576次，即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲，它对计算速度有十分苛刻的要求-迫切需要改进DFT的计算方法，以减少总的运算次数。 例2：石油勘探，24道记录，每道波形记录长度5秒，若每秒抽样500点/秒，每道总抽样点数=500*5=2500点24道总抽样点数=24*2500=6万点DFT运算时间=N2=(60000)2=36*108次二、改善D

6、FT运算效率的基本途径利用DFT运算的系数 的固有对称性和周期性，改善DFT的运算效率。1. 合并法：合并DFT运算中的某些项。2. 分解法： 将长序列DFT利用对称性和周期性，分解为短序列DFT。knNW利用DFT运算的系数 的固有对称性 和周期性，改善DFT的运算效率knNWknNW的对称性：*()()knnkN n kNNNWWWknNW的周期性：()()knn N kn N kNNNWWW1)()(22kjkNNjkNNeeW因为：1, 1 , 0Nk1)()(22njNnNjNnNeeW1, 1 , 0Nn由此可得出：nkNknNNkNnNWWW)()()(1sincos)(222/

7、jeWNNjNN2()NkkNNWW例子 例:1454)54(494WWWW1898178258WWWW利用以上特性,得到改进DFT直接算法的方法.合并法： 合并DFT运算中的有些项 对虚实部而言 所以带入DFT中：*()()knk NnNNWWknNnNkNWWReRe)(knNnNkNWWImIm)(分解成虚实部1010Re)(ImIm)(ReIm)(ImRe)(Re)(NnnkNnkNNnnkNnkNWnxWnxjWnxWnxkX展开：1010Im)Re(Im)(Re)()(NnnkNnkNNnnkNWjWnxjnxWnxkX代入DFT中nkNnNkNnkNWnNxnxWnNxWnxRe

8、)(Re)(ReRe)(ReRe)(Re)(nkNnNkNnkNWnNxnxWnNxWnxIm)(Im)(ImIm)(ImIm)(Im)(knNnNkNWWReRe)(knNnNkNWWImIm)(根据：有：合并有些项 由此找出其它各项的类似归并方法：乘法次数可以减少一半。例：1545) 15(515Re)4(Re) 1 (ReRe)4(Re) 1 (Re) 15 (ReRe) 1 (ReWxxWxxWxWx结论2、将长序列DFT利用对称性和周期性分解为短序列DFT-思路 因为DFT的运算量与的运算量与N2成正比的成正比的 如果一个大点数N的DFT能分解为若干小点数DFT的组合，则显然可以达到

9、减少运算工作量的效果。2、将长序列DFT利用对称性和周期性分解为短序列DFT-方法22)()()(NNNkXkXkX把N点数据分成二半：其运算量为：2)2(N2)2(N2N再分二半：44)()(NNkXkX44)()(NNkXkX+=22N2)4(N2)4(N2)4(N2)4(N+=24N这样一直分下去，剩下两点的变换两点的变换。2、将长序列DFT利用对称性和周期性分解为短序列DFT-结论 快速付里时变换(FFT)就是在此特性基础上发展起来的，并产生了多种FFT算法，其基本上可分成两大类： 按抽取方法分： 时间抽取法(DIT);频率抽取法(DIF) 按“基数”分：基-2FFT算法；基-4FFT

10、算 法；混合基FFT算法；分裂基FFT算法 其它方法：线性调频Z变换(CZT法)按时间抽取的基-2 FFT算法Decimation-in-Time(DIT)(Coolkey-Tukey)一、算法原理 设输入序列长度为N=2M(M为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。 其中基数2-N=2M，M为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到 N=2M例子 设一序列设一序列x(n)的长度为的长度为L=9,应加零补长为应加零补长为 N=24=16 应补应补7个零值。个零值。 0 1 2 3

11、4 5 6 7 8 9 10 11 12 13 14 15 nx(n)二、算法步骤1.分组，变量置换分组，变量置换DFT变换：10)()(NnknNWnxkX0,1kN先将x(n)按n的奇偶分为两 组，作变量置换:当n=偶数时，令n=2r;当n=奇数时，令n=2r+1;得到：x(2r)=x1(r); x(2r+1)=x2(r);r=0N/2-1; 则可得其DFT为两部分：前半部分前半部分：后半部分后半部分：( )1( )2( )kNX kX kW Xk0,/2 1kN(/2)1( )2( )kNX kNX kW Xk2.代入DFT中)( 2)( 1) 12 ()2 ()()rxDFTrxDFT

12、rxDFTrxDFTnxDFTkX（生成两个子序列x(0),x(2)x(2r)偶数点x(1),x(3)x(2r+1)奇数点12/, 0Nr代入DFT变换式：/2 1/2 12(21)00/2 1/2 10022221/2/222)(2 )(21)1( )2( )()()rkNNrkrkNNrrNNrrjrjNNkkNNNNNWWX kxr WxrWx rxrWeeWW（3.求出子序列的DFT上式得：/2/2/2 1/2 1120012/2 1/2 111/2/200/2 1/2 122/2/200)( )( )( )( )( )( )(2 )( )( )(20,1/112)NNrrkNNNrk

13、rkNNrrNNrkrrkkNNkNkNrrrNX kx rxrXkW XkXkx r Wxr WXkxrWWxrWWkWN（其中：12/, 0Nk4.结论 一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：12)( )( )0,1/ 21kNX kXkW XkNDFTkN（又合成 点中的前半部分 再应用W系数的周期性，求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。5.求出后半部的表示式/2 1/2 1(/2)11/21/2100/2 1/2 1(/2)22/22(/2)/2/2/2200()( )( )( )2()( )( )(

14、)2rkr kNNr NkrkNNrrNNr NkrkNNrNNNrNXkx r Wx r WX kNXkx r Wx r WX kWW看出：后半部的k值所对应的X1(k),X2(k)则完全重复了前半部分的k值所对应的X1(k),X2(k)的值。/2)12/2( )( )( )NkNkkNNkNNNWWX kX kW X kWW（又后半部分：6.结论2频域中的N个点频率成分为：)()()2/()()()(2121kXWkXNkXkXWkXkXkNkN后半部分：前半部分：结论：只要求出（0N/2-1）区间内的各个整数k值所对应的X1(k),X2(k)值，即可以求出(0N-1)整个区间内全部X(k

15、)值，这就是FFT能大量节省计算的关键。7.结论3由于N=2M，因此N/2仍为偶数，可以依照上面方法进一步把每个N/2点子序列，再按输入n的奇偶分解为两个N/4点的子序列，按这种方法不断划分下去，直到最后剩下的是2点DFT，两点DFT实际上只是加减运算加减运算。) 1 ()0() 1 () 1 ()0()0(2,)()(10 xxXxxXNWnxkXNnknN时三、蝶形结即蝶式计算结构也即为蝶式信号流图上面频域频域中前/后半部分表示式可以用蝶形信号流图表示。X1(k)X2(k)kNW)()(21kXWkXkN)()(21kXWkXkN作图要素：作图要素：(1)左边两路为输入左边两路为输入(2)

16、右边两路为输出右边两路为输出(3)中间以一个小圆表示加、中间以一个小圆表示加、减运算（右上路为相加输减运算（右上路为相加输出、右下路为相减输出出、右下路为相减输出)(4)如果在某一支路上信号需要进行如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。将相乘的系数标在箭头旁。(5)当支路上没有箭头及系当支路上没有箭头及系数时，则该支路的传输比数时，则该支路的传输比为为1。例子：求 N=23=8点FFT变换 （1）先按）先按N=8-N/2=4，做做4点的点的DFT：)()() 2/()()()(2121kXWkXNkXkXWkXkXk

17、NkN12/, 0Nk先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(2),x(4),x(6)为偶子序列 x(1),x(3),x(5),x(7)为奇子序列 频域上：X(0)X(3)，由X(k)给出 X(4)X(7),由X(k+N/2)给出(a)比较N=8点直接DFT与分解2个4点DFT的FFT运算量N=8点的直接直接DFT的计算量为：N2次(64次）复数相乘,N(N-1)次(8(8-1)=56次)复数相加.共计120次。（b)求 一个蝶形结需要的运算量要运算一个蝶形结，需要一次乘法 ， 两次加法。)(2kXWkN)()() 2/()()()(2121kXWkXNkXkXWkX

18、kXkNkN（c）分解为两个N/2=4点的DFT的运算量分解2个N/2点（4点）的DFT：) 12 ()2 ()rxDFTrxDFTkX（偶数其复数相乘为复数相加为奇数其复数相乘为复数相加为22）（N）（122NN22）（N）（122NN次。共计为次，（次，复数相加为复数相乘为5624) 123222NNN(d)用2个4点来求N=8点的FFT所需的运算量再将N/2点（4点）合成N点(8点)DFT时，需要进行N/2个蝶形运算)()() 2/()()()(2121kXWkXNkXkXWkXkXkNkN12/, 0Nk还需N/2次（4次）乘法 及 次(8次）加法运算。22N)(2kXWkN计算量。分

19、解就可以节省约一半次。看出仅做一次共计为次复数加法次复数乘法）共需求点所以68,322) 12(,36221(22)(8222NNNNNNNNNkXFFT(e)将N=8点分解成2个4点的DFT的信号流图 4点DFTx(0)x(2)x(4)x(6)4点DFTx(1)x(3)x(5)x(7)08W18W28W38WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)偶数序列奇数序列3821282118210821) 3 () 3 (3) 2() 2(2) 1 () 1 (1) 0() 0(0WXXXWXXX

20、WXXXWXXX）（）（）（）（如：X(4)X(7)同理x1(r)x2(r)(2)N/2(4点)-N/4(2点)FFT(a)先将先将4点分解成点分解成2点的点的DFT： 因为4点DFT还是比较麻烦，所以再继续分解。 若将N/2(4点)子序列按奇/偶分解成两个N/4点（2点）子序列。即对将x1(r)和x2(r)分解成奇、偶两个N/4点（2点）点的子序列。奇序列、偶序列、) 6() 2() 4() 0(: )(1xxxxrx奇序列、偶序列、同理：)7() 3 () 5 () 1 (: )(2xxxxrx1014012()()2(4131，），在此（）奇序列（）偶序列若设：LNLLXLxLxLx10

21、14012()()2(5252，），在此（）奇序列（）偶序列同理：LNLLXLxLxLx(b)求2点的DFT11/4 1/4 12(21)11/21/2003/2413/24225/2625/26( )( )(2 )(21)( )( )01/4)( )( )( )( )( )( )(/4)( )DFTNNLkLkNNLLkNkNkNkNx rX kX kxL WxLWXLWXLLX kNXLWXLx rx kXLWXLx kNXLWXL 可分解为：（其中，同理： （同样，也可分解为：）（c)一个2点的DFT蝶形流图2点DFT2点DFTx(0)x(4)x(2)x(6)X3(0)X3(1)X4(0

22、)X4(1)X1(0)X1(1)X1(2)X1(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(41431404314143140431XWXXXWXXXWXXXWXX其中（d)另一个2点的DFT蝶形流图2点DFT2点DFTx(1)x(5)x(3)x(7)X5(0)X5(1)X6(0)X6(1)X2(0)X2(1)X2(2)X2(3)04W14W) 1 () 1 () 1 () 0() 0() 2() 1 () 1 () 1 () 0() 0() 0(61452604526145260452XWXXXWXXXWXXXW

23、XX其中同理：(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，则这里用到对称性这是一蝶形结代入上面流图可知： 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x(0)、x(4)为例。(b)2个1点的DFT蝶形流图 1点DFTx(0)1点DFTx(4)X

24、3(0)X3(1)02W进一步简化为蝶形流图：02WX3(0)X3(1)x(0)x(4)4()0()4()0() 1 ()4()0()4()0()0(023023xxxWxXxxxWxX其中：(4)一个完整N=8的按时间抽取FFT的运算流图 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2四、FFT算法中一些概念 （1）“级级”概念概念 将N 点DFT先分成两个N/2点DFT，再是四个N/4

25、点DFT直至N/2个两点DFT.每分一次称为“一”级运算。 因为N=2M所以N点DFT可分成M级 如上图所示依次m=0,m=1.M-1共M级（2）“组组”概念概念 每一级都有N/2个蝶形单元，例如：N=8,则每级都有4个蝶形单元。每一级的N/2个蝶形单元可以分成若干组，每一组具有相同的结构，相同的 因子分布，第m级的组数为：rNW12mN例：N=8=23，分3级。m=0级,分成四组,每组系数为m=1级,分成二组,每组系数为m=2级,分成一组,每组系数为080204/WWWN28082012/02/,WWWWWWNNNN382818083210,WWWWWWWWNNNN(3) 因子的分布rNW1

26、21 , 0,3 , 2 , 102101001238281808828081404408022mkkkkkWmWWWWkWmWWWWkWmWWkWmm级的系数为看出：第，级，级，级，由上可知：结论：每由后向前（结论：每由后向前（m由由M-1-0级）推进一级）推进一级，则此系数为后级系数中偶数序号的那一半。级，则此系数为后级系数中偶数序号的那一半。（4）按时间抽取法2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT2点DFT两个2点DFT两个2点DFT两个2点DFT两个2点DFT两个4点DFT两个4点DFT两个N/2点DFTX1(k).X2(k)X(k) 由于每一步分解都是

27、基于在每级按输入时间序列的次序是属于偶数还是奇数来分解为两个更短的序列，所以称为“按时间抽取法”.x(n)五、按时间抽取的FFT算法与直接计算DFT运算量的比较 由前面介绍的按时间抽取的FFT运算流图可见： 每级都由N/2个蝶形单元构成，因此每一级运算都需要N/2次复乘和N次复加（每个结加减各一次）。这样（N=2M)M级运算共需要： 复乘次数： 复加次数： 可以得出如下结论：按时间抽取法所需的复乘数和复加数都是与成正比。而直接计算DFT时所需的复乘数与复加数则都是与N2成正比.(复乘数md=N2,复加数ad=N(N-1)N2)NFNMNm2log22NFNMNa2logNN2log例子 看N=

28、8点和N=1024点时直接计算DFT与用基2-按时间抽取法FFT的运算量。4.102102227.224648loglog1020102222NNNNNNN看出：当N较大时，按时间抽取法将比直接法快一、二个数量级之多。六、按时间抽取FFT算法的特点 根据DIT基2-FFT算法原理，能得出任何N=2m点的FFT信号流图，并进而得出FFT计算程序流程图。最后总结出按时间抽取法解过程的规律。 1.原位运算（in-place) 2.码位倒读规则1.原位运算（in-place) 原位运算的结构，可以节省存储单元，降低设备成本。 定义：当数据输入到存储器以后，每一组运算的结果，仍然存放在这同一组存储器中直

29、到最后输出。02Wx(0)x(4)X3(0)X3(1)中放在一个暂存器中放在单元中，将放在单元例：将RWAxAx08) 1 ()4()0()0(单元送回单元送回将) 1 ()4()0()0()4()0(0808AxWxAxWx例子 例：N=8 FFT运算,输入:x(0)x(4)x(2)x(6)x(1)x(5)x(3)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)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)=x(0)A(1)=x(1)A(2)=x(2)A(3)=x(3)A(4)=

30、x(4)A(5)=x(5)A(6)=x(6)A(7)=x(7)180818084,32,1WRWRWRWR暂存器R1R1R1R1R1R2R1R1R2R2R3R4看出：用原位运算结构运算后，A(0)A(7)正好顺序存放X(0)X(7),可以直接顺序输出。2.码位倒读规则 我们从输入序列的序号及整序规律得到码位倒读规则。由N=8蝶形图看出：原位计算时，FFT输出的X(k)的次序正好是顺序排列的，即X(0)X(7),但输入x(n)都不能按自然顺序存入到存储单元中，而是按x(0),x(4),x(2), x(6).的顺序存入存储单元即为乱序输入乱序输入，顺序输出顺序输出。这种顺序看起来相当杂乱，然而它是

31、有规律的。即码位倒读规则。例子以N=8为例：01234567000001010011100101110111自然顺序二进制码表示码位倒读码位倒置顺序00010001011000110101111104261537看出：码位倒读后的顺序刚好是数据送入计算机内的顺序。整序重排子程序具体执行时，只须将1与4对调送入，3与6对调送入，而0，2，5，7不变，仅需要一个中间存储单元。n01234567n04261537 在实际运算时，先按自然顺序将输入序列存入存储单元，再通过变址运算将自然顺序变换成按时间抽取的FFT算法要求的顺序。变址的过程可以用程序安排加以实现-称为“整序”或“重排”（采用码位倒读）且

32、注意：(1)当n=n时，数据不必调换；(2)当nn时，必须将原来存放数据x(n)送入暂存器R，再将x(n)送入x(n),R中内容送x(n).进行数据对调。(3)为了避免再次考虑前面已调换过的数据，保证调换只进行一次，否则又变回原状。nn时，调换。七、按时间抽取的FFT算法的若干变体1.思路思路 对于任何流图，只要保持各节点所连续的支路及其传输系数不变，则不论节点位置怎么排列所得流图总是等效的，最后所得结果都是x(n)的离散付里叶变换的正确结果。只是数据的提取和存放的次序不同而已。(2)输入是自然顺序而输出是乱序将原先中与x(4)水平相邻的所有节点跟x(1)水平相邻的所有节点位置对调；将原先中与

33、x(6)水平相邻的所有节点跟x(3)水平相邻的所有节点位置对调，其余诸节点保持不变，则可得：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(3)X(5)X(7)它与输入是乱序，输出顺序比较，看出：相同点：运算量一样；不同点：第一是数据存入方式不同；第二是取用系数的顺序不同。(2)输入和输出都是自然顺序对输入自然顺序，输出乱序的第二级，第三级节点作调整，可得输入输出都是顺序，无需数据重排：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（1）它失掉了“原位运

34、算”的性质。（2）为了变换N点数据，至少需要2N个复数单元。在内存比较紧张时，而对输入数据整序并不困难时一般不用。为了争取速度，才采取这种变体。基-2按频率抽取的FFT算法Decimation-in-Frequency(DIF)(Sander-Tukey)一、算法原理 设输入序列长度为N=2M(M为正整数，将该序列的频域的输出序列X(k)(也是M点序列，按其频域频域顺序的奇偶分解奇偶分解为越来越短的子序列，称为基2按频率抽取的FFT算法。也称为Sander-Tukey算法。二、算法步骤1.分组分组DFT变换：10)()(NnknNWnxkX1,0Nk已证明频域上X(k)按k的奇偶分为两组，在时

35、域上x(n)按n的顺序分前后两部分，现将输入x(n)按n的顺序分前后两部分:前半子序列x(n),0nN/2-1;后半子序列x(n+N/2),0nN/2-1;例：N=8时，前半序列为：x(0),x(1),x(2),x(3); 后半序列为： x(4),x(5),x(6),x(7); 则由定义输出（求DFT）2.代入DFT中112()2001122()200122022222)( ) ( )()2( )()2 ( )()211NNNnknknkNNNnnNNNnknkNNnnNNknkNNnNkNNjkkNj kNNNkNNX kx n Wx n Wx nWNx n Wx nWNx nx nWWkW

36、WeekW（偶数时又奇数时3. 变量置换变量置换-1）又代入令，令分偶数时，频率的偶数部当置换分成两部分，进行变量的奇偶将按2/2/2222/2212/012/02(12, 1 , 0)2()() 2(216 , 4 , 2 , 0)2()()(12, 1 , 02, 1)(nkNnkNjnkNjnkNnkNnkNNnnkNNnkNNWeeWWNkWNnxnxkXkkNkWNnxnxkXNkkkWkkXk12/, 0Nk一半。点，所以其运算量降低序列只有由于求得。（序列的可以通过的偶数部分的频域可见：（则设一个新序列：后一半序列前一半序列2)()()()(12, 1 , 0) )() 2(12

37、2 , 1 , 0),2()()()()(12, 1 , 0)2()() 2(11112/12/0112/12/0NnxkDFTXnxkXnxNkkXWnxkXNnNnxnxnxnxnxNkWNnxnxkXnkNNnnkNNn）又代入令，令分奇数时，频率的奇数部同理：当）（2/2/2222/21212/012/02(12, 1 , 0)2()() 12(1217 , 5 , 3 , 1)2()()(12, 1 , 012, 1nkNnkNjnkNjnkNnkNknNNnnkNNnkNNWeeWWNkWNnxnxkXkkNkWNnxnxkXNkkkWk一半。点，所以其运算量降低序列只有由于求得。

38、（序列的可以通过的奇数部分的频域可见：（则设一个新序列：后一半序列前一半序列2)()()()(12, 1 , 0) )() 12(122 , 1 , 0,)2()()()()(12, 1 , 0)2()() 12(22122/12/0222/12/0NnxkDFTXnxkXnxNkkXWnxkXNnWNnxnxnxnxnxNkWWNnxnxkXnkNNnnNnkNnNNn4.结论 一个N点的DFT被分解为两个N/2点DFT。X1(k),X2(k)这两个N/2点的DFT按照：DFTNNkkXkXkXkkkkNkkXkXNNDFTNkXkXkX点又合成分别代入再用，即先求出点点点1, 1 , 0,

39、) 12() 2()(12, 212/1 , 0) () (2/2/) 12() 2()(2121可见：如此分解，直至分到2点的DFT为止。12, 1 , 0)2()()() (12, 1 , 0)2()()() (2/12/02/12/0222/12/02/12/011NkWWNnxnxWnxkXNkWNnxnxWnxkXnkNNnnNnkNNnnkNNnnkNNn三、蝶形流图表示蝶形单元：时域时域中，前后半部表示式用蝶形结表示。x(n)x(n+N/2)nNW)() 2/()(1nxNnxnx)()2/()(2nxWNnxnxnN与时间抽取法的推演过程一样，由于N=2L,N/2仍为偶数，所以

40、可以将N/2点DFT的输出X(k)再分为偶数组和奇数组，这样就将一个N/2点的DFT分成两个N/4点DFT的输入，也是将N/2点的DFT的输入上、下对半分后通过蝶形运算而形成，直至最后为2点DFT。例子：求 N=23=8点DIF （1）先按）先按N=8-N/2=4，做做4点的点的DIF：nNWNnxnxnxNnxnxnx)2()()()2()()(21先将N=8DFT分解成2个4点DFT：可知：时域上：x(0),x(1),x(2),x(3)为前半序列 x(4),x(5),x(6),x(7)为后半序列产生新的子序列： x1(n)、 x2(n) 频域上：X(0),X(2),X(4),X(6)由x1

41、(n)给出 X(1),X(3),X(5),X(7),由x2(n)给出将N=8点分解成2个4点的DIF的信号流图 4点DFTx(0)x(1)x(2)x(3)4点DFTx(4)x(5)x(6)x(7)X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)X1(k)前半部分序列后半部分序列nNnNnNnNWxxxWxxxWxxxWxxxxxxxxxxxxxxx)7 () 3 (3,)6 () 2(2,)5 () 1 (1,)4() 0 (0) 7 () 3 (3),6 () 2(2),5 () 1 (1),4() 0 (022221111）（）（）（）（）（）（）（）（如：08W18W28

42、W38Wx1(n)x2(n)X2(k)(2)N/2(4点)-N/4(2点)FFT(a)先将先将4点分解成点分解成2点的点的DIF： 因为4点DIF还是比较麻烦，所以再继续分解。后半部分序列、前半部分序列、) 3 () 2() 1 () 0(: )(11111xxxxnx10140)2()()()2()(411311，），在此（）（若设：LNLLxWNnxnxLxNnxnxnN后半部分序列、前半部分序列、同理：) 3 () 2() 1 () 0(: )(22222xxxxnx10140)2()()()2()(622522，），在此（）（同理：LNLLxWNnxnxLxNnxnxnN（b)一个2点

43、的DIF蝶形流图2点DFT2点DFTx1(0)x1(1)x1(2)x1(3)x3(0)x3(1)x4(0)x4(1)X(0)X(4)X(2)X(6)08W28W) 3 () 1 () 1 (,) 2() 0() 0(113113xxxxxx其中(c)另一个2点的DIF蝶形流图2点DFT2点DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)X(1)X(5)X(3)X(7)08W28W(3)将N/4（2点）DFT再分解成2个1点的DFT(a)求2个一点的DFT021022120202120230202020231021 , 0; 1 , 0)4()0()4()0

44、() 1 ()4()0()4()0()0()()(2WWknWWWWWxWxWxWxXWxWxWxWxXWnxkXnknknkNnkNnnkN，其中，则这里用到对称性这是一蝶形结代入上面流图可知： 最后剩下两点DFT,它可分解成两个一点DFT，但一点DFT就等于输入信号本身，所以两点DFT可用一个蝶形结表示。取x3(0)、x3(1)为例。(b)2个1点的DFT蝶形流图 1点DFTx3(0)1点DFTx3(1)X(0)X(4)02W进一步简化为蝶形流图：02WX(0)X(4)x3(0)x3(1)(4)一个完整N=8的按频率抽取FFT的运算流图 x(0)x(1)x(2)x(3)x(4)x(5)x(

45、6)x(7)38W28W18W08W08W08W08W08W08W08W28W28WX(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)12/0NNNWW其中旋转因子，共有m=0m=1m=2(5)DIF的特点(a)输入自然顺序，输出乱序且满足码位输入自然顺序，输出乱序且满足码位倒置规则。倒置规则。(b)根据时域、频域互换，可知：根据时域、频域互换，可知：输入乱序，输出自然顺序。输入乱序，输出自然顺序。（6）DIF与DIT比较 相同之处： （1）DIF与DIT两种算法均为原位运算。 （2）DIF与DIT运算量相同。 它们都需要算法是两种等价的与次复加次复乘FFTDITDIFNaNmN

46、FNF22loglog2（6）DIF与DIT比较2 不同之处：（1）DIF与DIT两种算法结构倒过来。DIF为输入顺序，输出乱序。运算完毕再运行“二进制倒读”程序。DIT为输入乱序，输出顺序。先运行“二进制倒读”程序，再进行求DFT。（2）DIF与DIT根本区别：在于蝶形结不同。DIT的复数相乘出现在减法之前减法之前。DIF的复数相乘出现在减法之后减法之后。IFFT运算方法 以上所讨论的FFT的运算方法同样可用于IDFT的运算，简称为IFFT。即快速付里叶反变换。从IDFT的定义出发，可以导出下列二种利用FFT来计算FFT的方法。一、利用FFT计算IFFT的思路 将下列两式进行比较IDFTFFTNWWDFTWnxnxDFTkXWkXNkXIDFTnxnkNnkNNknkNNknkN算法都可以拿来运算或频率抽取抽取）那么以上讨论的时间（将运算结果都除以改成运算中的每个