Chap4快速傅立叶变换FFT

1、第四章第四章 快速傅立叶变换快速傅立叶变换FFT算法算法快速傅立叶变换快速傅立叶变换FFT不是一种新的变换不是一种新的变换而是而是DFTDFT的快速算法的快速算法1、直接计算、直接计算DFT的问题及改进的途径的问题及改进的途径1.直接计算直接计算N点点DFT的运算量：的运算量： 次复数加法次复数乘法，需要一个1NN)(X k1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx 次复数加法次复数乘法运算，需要整个) 1N(NNDFT2一次复数乘法需一次复数乘法需4次实数乘法，次实数乘法，2次实数加法；次实数加法；一次复数加法需要一次

2、复数加法需要2次实数加法次实数加法次实数加法次实数乘法运算，需要整个)24(2) 12N(N4NDFT222NNN 从上面的统计可以看出：从上面的统计可以看出：直接计直接计DFT，运算量几乎与，运算量几乎与N2成正成正比，且当比，且当N很大时，运算量相当可观。很大时，运算量相当可观。2.改善途径改善途径(1)根据根据DFT的特性：的特性： 如如 的对称性、周期性、可约性、常数值的对称性、周期性、可约性、常数值(2)DFT运算量与运算量与N平方成正比：平方成正比： 使使N点点DFT分解为更少点数的分解为更少点数的 DFT （这一点也是这一点也是FFT运算的关键）运算的关键）3.FFT算法分成两大

3、类算法分成两大类按时间抽取法（按时间抽取法（DIT）按频率抽取法（按频率抽取法（DIF）knnW2、按时间抽取的基、按时间抽取的基-2 FFT算法算法 设时域序列设时域序列x(n)x(n)的点数的点数N N2 2M M如果不满足，则可以如果不满足，则可以人为地补零至人为地补零至N N为为2 2的幂级数。的幂级数。一、算法原理一、算法原理1.1. 将将N N2 2M M的序列的序列x(n)x(n)按按n n的奇偶分成两组；的奇偶分成两组；) 12()()2()(orxrxrxrxe奇数项一组：偶数项一组：12102Nr， 10102222)()()()()()(NNNNrrkeorrkeeeWr

4、xrxDFTkXoWrxrxDFTkX12102Nk， 2.2.相应的相应的DFTDFT也分成两组也分成两组10)()()(NnnkNWnxnxDFTkX1010)12(222) 12()2(NNrrrkNrkNWrxWrx1010N2222)()(NNNNrrrkekrkeWrxWWrx利用可约性22)()()()(222NokNNerkrkkXWkXWWkXNNN 1, 0Nk3.3.考虑考虑W WN N的周期性，的周期性，X(k)X(k)分成前后两部分；分成前后两部分； 12, 0)(NkkX：前半部分)()(kXWkXokNe 12, 0)2(NkNkX：后半部分)()(kXWkXok

5、Ne 只需要计算两个只需要计算两个N/2N/2点的点的DFTDFT： X X1 1(k)(k)、X X2 2(k)(k)就可求就可求出所有出所有N N点的点的X(k)X(k) 一、算法原理一、算法原理 将将N N2 2M M的序列的序列x(n)x(n)按按n n的奇偶分成两组；的奇偶分成两组； 相应的相应的DFTDFT也分成两组；也分成两组； 考虑考虑W WN N的周期性，的周期性，X(k)X(k)分成前后两部分；分成前后两部分；v 只需要计算两个只需要计算两个N/2N/2点的点的DFTDFT： X X1 1(k)(k)、X X2 2(k)(k)就可求出所就可求出所有有N N点的点的X(k)X

6、(k)运算量：抽取分解一次，运算量约省一半运算量：抽取分解一次，运算量约省一半 由于由于N/2N/2 2 2M M1 1 ，仍然是偶数，则可继续将一个，仍然是偶数，则可继续将一个N/2N/2点序列的点序列的DFTDFT分解为两个分解为两个N/4N/4点的点的DFTDFT；1.1. 继续这样的分解，直至最后是二点的继续这样的分解，直至最后是二点的DFTDFT为止。为止。二、信号流图（蝶形信号流图）二、信号流图（蝶形信号流图）n对N2 2M M如果进行第一次抽取如果进行第一次抽取)()()(21kXWkXkXkN)()()2(21kXWkXkNXkNCABA+BCA-BC蝶形运算符号蝶形运算符号例

7、：以例：以N8为例，第一次抽取分解图为例，第一次抽取分解图N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)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)2.继续分解继续分解图图4.2.3 N点点DFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8) N/4点DFTWN12WN12WN0WN1WN2WN3X1(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(

8、5)X(6)X(7)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN023.继续分解直至继续分解直至2点的点的DFT 图图4.2.4 N点点DITFFT运算流图运算流图(N=8) 由于每次分解都是将序列从时域上按奇偶抽取一分由于每次分解都是将序列从时域上按奇偶抽取一分为二，所以称基为二，所以称基2的算法。的算法。WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 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

9、)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(7)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)三、运算量三、运算量四、四、DIT的基的基2FFT算法的特点算法的特点运算量：运算量：N越大，运算量可减少的更多越大，运算量可减少的更多同址运算（原位运算）同址运算（原位运算）输入数据、中间运算结果和最输入数据、中间运算结果和最后输出均用同一存储器。后输出均用同一存储器。 输入、输出量互不相重，即任一蝶形结的二输入量经蝶形运算后便失输入、输出量互不相重，即任一蝶形

10、结的二输入量经蝶形运算后便失去利用价值，所以可将计算结果存入原输入量的寄存器单元中。去利用价值，所以可将计算结果存入原输入量的寄存器单元中。输入倒位序，输出顺序：输入倒位序，输出顺序：蝶形运算两结点间的蝶形运算两结点间的“距离距离”：蝶形运算系数蝶形运算系数WNk五、时间抽取基五、时间抽取基2FFT算法，用计算机程序来实现：算法，用计算机程序来实现：三级循环：第三级循环：第m级中的级中的2Mm簇中每簇有簇中每簇有2m1个蝶形结个蝶形结六、六、 DIT基基-2 FFT算法流图，用其它流图形式表示：算法流图，用其它流图形式表示： 输入顺位序，输出倒位序输入顺位序，输出倒位序输入顺序输出倒位序输入倒

11、位序输出顺序DIT的基的基2 FFT的两种流程图的两种流程图WN0WN0WN2WN0X(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)WN0WN2WN1WN3WN2WN0WN0WN0WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 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(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X

12、(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)3、频域抽取（、频域抽取（DIF）的基）的基-2 FFT算法算法按频率抽取按频率抽取把输出序列把输出序列X(k)按按k的奇偶分解为越来越短的序列。的奇偶分解为越来越短的序列。 一、算法原理一、算法原理1.(在在X(k)按奇偶分组之前，先按奇偶分组之前，先)将输入序列将输入序列x(n)按前后顺序对半按前后顺序对半分解；分解； 注：这不是频率抽取注：这不是频率抽取10)()(NnknNWnxkX11022)()(NnknNnknNNNWnxWnx10)2(21022)()(NNnNnkNNnknNWnxWnxknNNkNnWnx

13、WnxNN)()(21022knNNknWnxnxN)() 1()(21022.按输出序列按输出序列X(k)中中k的奇偶性的奇偶性将它分为两组将它分为两组为奇数：为偶数：kknrNNnWnxnxrXkXrkN2210)()()2()(,22rnNnNNWnxnx22)()(210nrNNnWnxnxrXkXrkN)12(210)()() 12()(, 122nrnNNnNNWWnxnx22)()(210nNNNWnxnxnxnxnxnx)()()()()()(2221令1022101122)()() 12()()()2(NNnrnNnrnNrXWnxrXrXWnxrX这样，就将这样，就将N点的

14、点的DFT，按，按k的奇偶分解为的奇偶分解为N/2点的点的DFT。点的再分解，直至仍是偶数，可继续往下，由于DFT222. 3NNMknNNknWnxnxkXN)() 1()()(2102二、运算流图二、运算流图1. 按频率抽取的蝶形结运算流图符号按频率抽取的蝶形结运算流图符号)()()(21NnxnxnxnNNWnxnxnx)()()(22nNW)2(Nnx)(nx)(2nx)(1nx2.DIF基基-2FFT第一次分解运算流图第一次分解运算流图(N=8)（图（图4.2.11） N/2点DFTWN0N/2点DFTWN1WN2WN3X(0)x1(0)X(2)X(4)X(6)X(1)X(3)X(5

15、)X(7)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)3.DIF基基-2FFT第二次分解运算流图第二次分解运算流图(N=8)（图（图4.2.12）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)X(5)X(3)X(7)WN0WN2WN0WN2N/4点DFTN/4点DFTN/4点DFT4.DIF基基-2FFT运算流图运算流图(N=8)（图（图4.2.13）WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0

16、WN0WN0X(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)三、运算量：三、运算量：由蝶形结个数来看，与由蝶形结个数来看，与DIT的运算量一致。的运算量一致。四、特点：四、特点：同址运算、蝶形结点同址运算、蝶形结点“距离距离”、系数、系数W等等5、比较、比较DIT与与DIF的蝶形结：的蝶形结：（DIT的蝶形结）的蝶形结）（DIF的蝶形结）的蝶形结）实质上的差异：实质上的差异：DIT：先作复乘，然后加减；：先作复乘，然后加减；DIF：先作加减，然后复乘。：先作加减，然后复乘。CABA+BCA-BCnNW)2(Nnx)

17、(nx)(2nx)(1nx输入顺序，输入顺序，输出倒位序，输出倒位序，DIF的基的基-2 FFT算法算法(8点点)流程图流程图基2 FFT的两种流程图（DIT、DIF）比较： 输入顺序，输入顺序，输出倒位序，输出倒位序，DIT的基的基-2 FFT算法算法(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)WN0WN0WN2WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(

18、4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN04、离散傅立叶反变换、离散傅立叶反变换(IDFT)的快速算法（的快速算法（IFFT）1、IFFT原理原理 比较比较1, 1 , 0 ,)()(10NkWnxkXNnnkN101, 1 , 0 ,)(1)(NknkNNnWkXNnx二者差别：二者差别：knNknNWWi)分散到各级中）因子（一般将MNNii21)2、具体编程实现方法：、具体编程实现方法：按照按照FFT程序过程，将两个参数稍作改动：程序过程，将两个参数稍作改动： （主要是参数主要是参数1/N，W系数上标的负号）系数上标的负号）直接利用现成的直接利用现成的F

19、FT算法原程序来实现算法原程序来实现: P.109X(k)变为变为X*(k) 直接访问直接访问FFT程序程序 结果取共轭，再乘以结果取共轭，再乘以1/N。1)直接访问直接访问FFT程序得程序得x1(n) 将结果倒序排列，再乘以将结果倒序排列，再乘以1/N得得x(n)。注：区别与倒位序注：区别与倒位序 排列排列5、进一步减少运算量的措施、进一步减少运算量的措施一、多类蝶形单元运算一、多类蝶形单元运算减少复数乘法的运算量减少复数乘法的运算量二、旋转因子的生成二、旋转因子的生成三、实序列的三、实序列的FFT算法算法6 分裂基分裂基FFT算法算法一、基一、基4FFT算法算法二、任意基数（二、任意基数（N=p q）7、线性卷积的、线性卷积的FFT算法算法一、两个长度相仿的序列：一、两个长度相仿的序列：x(n)*h(n)(1)计算线性卷积的步骤计算线性卷积的步骤将将x(n)、h(n)补零点，至少为补零点，至少为(N1+N2-1)点；点；计算计算 H(k)=FFTh(n)；计算计算 X(k)=FFTx(n)；计算计算 Y(k)=X(k)Y(k)；计算计算 y(n)=IFFTY(k)。 (2)运算量：运算量：复数加法：复数乘法：共需NNN2l