第2章离散傅里叶变换及其快速算法课件3.ppt

1、2.3 快速傅里叶变换(FFT)一、一、直直接计算接计算DFT的问题及改进的途径的问题及改进的途径二、按时间抽取的基二、按时间抽取的基2FFT算法算法三、三、按频率抽取的基按频率抽取的基2FFT算法算法四、离散傅立叶反变换的快速算法四、离散傅立叶反变换的快速算法 五、五、N为组合数的为组合数的FFT算法算法六、六、Chirpz变换变换一、直接计算DFT的问题及改进的途径v v1.直直接计算接计算DFT的问题的问题v 长度为N的有限长序列x(n)的DFT为v 考虑x(n)为复数序列的一般情况，对某一个k值，直接按(1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。10()(),0,1,

2、1NknNnX kx n WkN(1)X（k）一共有N个点，故完成全部DFT运算，需要N2次复数相乘和N（N-1）次复数相加，在这些运算中，乘法比加法复杂，需要的运算时间多，尤其是复数相乘，每个复数相乘包括4个实数相乘和2个实数相加，例 又每个复数相加包括2个实数相加，所以，每计算一个 X（k）要进行4N次实数相乘和2N+2（N-1）=2（2N-1）次实数相加，因此，整个DFT运算需要4N2实数相乘和2N（2N-1）次实数相加。)()()()()(10nkNemnkNmeNnnkNmmnkNeewRnxIwInxRjwInxIwRnxRkX从上面的分析看到，在DFT计算中，不论是乘法和加法，运

3、算量均与N2成正比。因此，N较大时，运算量十分可观。例，计算N=10点的DFT，需要100次复数相乘，而N=1024点时，需要1048576（一百多万）次复数乘法，如果要求实时处理，则要求有很高的计算速度才能完成上述计算量。反变换IDFT与DFT的运算结构相同，只是多乘一个常数1/N，所以二者的计算量相同。DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比，当N较大时，计算量太大，所以在快速傅里叶变换(简称FFT)出现以前，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后，情况才发生了根本的变化。v2

4、.减少运算量的基本途径减少运算量的基本途径v 显然，把N点DFT分解为几个较短的DFT，可使乘法次数大大减少。v另外，旋转因子 具有明显的周期性和对称性。v其周期性表现为其对称性表现为或者 22()jm lNjmm lNmNNNNWeeW2mN mN mmNNNNNmmNNWWWWWW mNWv二、二、按时间抽取的基按时间抽取的基2FFT算法算法 按n的奇偶把x(n)分解为两个N/2点的子序列。偶数项为一组，偶数项为一组，奇数项为一组。奇数项为一组。12()(2),0,1,12()(21),0,1,12Nx rxrrNx rxrrFFT算法基本上分为两大类时域抽取法FFT(Decimation

5、 In Time FFT,简称DIT-FFT)频域抽取法FFT(Decimation In Frequency FFT,简称DIFFFT)。2,MNM为自然数 1.DIFFFT算法。设序列x(n)的长度为N，且满足v 则x(n)的DFT为101010)()()()()(NnnkNNnnkNNnnkNnnWnxWnxWnxnxDFTkX为奇数为偶数12/02212/02112/0)12(12/02)()()12()2(NrrkNkNNrrkNNrkrNNrrkNWrxWWrxWrxWrx所以 1,1,0),()()()()()()(2112/02/212/02/112/02212/021NkkX

6、WkXWrxWWrxWrxWWrxkXkNNrrkNkNNrrkNNrrkNkNNrrkN由于nNnNjnNjnNWeeW2/2/2222于是，一个N点的DFT被分解为两个N/2点的DFT了，这两个N/2点的DFT再按照上式合并成一个N点DFT。（1）,只有N/2个点，而 却有N个点，要用 ,表达全部 值，还必须利用 系数的周期特性。)(2kX)(kX)(1kX)(1kX)(2kX)(kXWrkNkNrNWW2/)2/(2/12/02/112/0)2/(2/11)()()2/(NrrkNNrkNrNWrxWrxkNX即 ，同样又考虑到 的对称性：kNWkNkNNNkNNWWWW2/)2/()(

7、)2/(11kXkNX)()2/(22kXkNXv将上述三个式子代入式(1),就可将 表达为前后两部分：)(kX12/,1,0),()()(21NkkXWkXkXkN12/,1,0,)()()2/()2/()2/(212)2/(1NkkXWkXkNXWkNXkNXkNkNN(2)(1kX)(2kXkNW)()(21kXWkXkN)()(21kXWkXkN蝶形运算流图符号蝶形运算流图符号(3)v 式（2）、（3）可以用上图的 “蝶形结”来表示。通过上述分解后，每个N/2点DFT只需要(N/2)2=N2/4次复数相乘。依此类推，X1(k)和X2(k)可以继续分下去，这种按时间抽取算法是在输入序列分

8、成越来越小的子序列上执行DFT运算，最后再合成为点的DFT。蝶形信号流图将X1(k)和X2(k)合成X(k)运算可归结为：bWabWaWa+bWa-bW-W1a+bWa-bWWabab蝶 形 运 算的简化(a)(b)图(a)为实现这一运算的一般方法，它需要两次乘法、两次加减法。考虑到-bW和bW两个乘法仅相差一负号，可将图(a)简化成图(b)，此时仅需一次乘法、两次加减法。图(b)的运算结构像一蝴蝶通常称作蝶形运算结构简称蝶形结，采用这种表示法，就可以将以上所讨论的分解过程用流图表示。v 两个两个N/2点的点的DFT需要需要2(N/2)2=N2/2次复乘，再加上次复乘，再加上将两个将两个N/2

9、点的点的DFT合成为合成为N点点DFT时蝶形结前的时蝶形结前的N/2次复乘，一共需要次复乘，一共需要v 次复乘。可见，分解后运算量大约节省了一倍。次复乘。可见，分解后运算量大约节省了一倍。既然这样的分解是有效的，由于既然这样的分解是有效的，由于N/2仍然是偶数，仍然是偶数，因此可以对两个因此可以对两个N/2点的点的DFT再分别作进一步分解。再分别作进一步分解。如右图所示：如右图所示：2/2/)1(2/2/22NNNNN)0(x)2(x)4(x)6(x)0(3X)0(1X)1(1X)2(1X)3(1X)1(3X)0(4X)1(4X02/NW12/NWN/4 点点DFTN/4 点点DFTN=23=

10、8 的例子。v 与第一次分解相同，将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l)，即3241()(2),0,1,1()(21)4x lxlNlx lxl那么，X1(k)又可表示为/4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24()(2)(21)()()()(),0,1,/21NNklklNNiiNNklkklNNNiikNX kxl WxlWx l WWx l Wx kWXk kN式中/4 133/430/4 144/440()()()()()()NklNiNklNix kx l WDFT x lx kx l WDFT x l 同理，

11、由X3(k)和X4(k)的周期性和Wm N/2的对称性 Wk+N/4 N/2=-Wk N/2 最后得到：13/2413/24()()(),0,1,/41(/4)()()kNkNX kXkWXkkNX kNXkWXkv 用同样的方法可计算出25/2625/26()()(),0,1,/41(/4)()kNkNXkXkWXkkNXkNX kWXk其中/4 155/450/4 166/4605262()()()()()()()(2),0,1,/41()(21)NklNiNklNiXkx l WDFT x lXkx l WDFT x lx lxllNx lxl最后剩下的是2点DFT，它可以用一个蝶形结表

12、示：这样，一个8点的完整的按时间抽取运算的流图由于这种方法每一步分解都是按输入时间序列是属于偶数还是奇数来抽取的，所以称为“按时间抽取法”或“时间抽取法”。)1()0()1()0()1()1()0()1()0()0(1202xWxxWxXxWxxWxXoNoN 按时间抽取的按时间抽取的8点点FFTv2.DITFFT算法与直接计算DFT运算量的比较v 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以，M级运算总共需要的复数乘次数为22(2)log22(2)logMANNCMNCN MNN复数加次数为 例如，N=210=1024时221048576204.8(/2)lo

13、g5120NNN图 FFT算法与直接计算DFT所需乘法次数的比较曲线 186.22048102.4102456.951232.025618.312810.7646.4324.0162.782.042.02v )log/(22NNNN FFT算法与直接算法的算法与直接算法的运算量比较运算量比较时间抽取法时间抽取法FFT的运算特点：的运算特点：（1）蝶形运算）蝶形运算（2）原位计算）原位计算（3）序数重排）序数重排（4）蝶形类型随迭代次数成倍增加）蝶形类型随迭代次数成倍增加 （1）蝶形运算）蝶形运算对于N=2M，总是可以通过M次分解最后成为2点的DFT运算。这样构成从x(n)到X(k)的M级运算过

14、程。从上面的流图可看到，每一级运算都由N/2个蝶形运算构成。因此每一级运算都需要N/2次复乘和N次复加，这样，经过时间抽取后M级运算总共需要的运算：复乘 复加 而直接运算时则与N2 成正比。例N=2048，N2=4194304，(N/2)log2N=11264，N2/(N/2)log2N=392.4。FFT显然要比直接法快得多。NNMN2log22NNMN2log（2）原位计算）原位计算 当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器，这叫原位计算。每一级运算均可在原位进行，这种原位运算结构可节省存储单元，降低设备成本，还可节省寻址的时间。

15、v(3)序列的倒序v DITFFT算法的输入序列的排序看起来似乎很乱，但仔细分析就会发现这种倒序是很有规律的。由于N=2M，所以顺序数可用M位二进制数(nM-1nM-2n1n0)表示。图 形成倒序的树状图(N=23)01010101010101(n2n1n0)200004261537100010110001101011111表 顺序和倒序二进制数对照表 图 倒序的变址处理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

16、(1)x(5)x(3)x(7)图 倒序程序框图 I1,N1I JJ KNNYv第一次分偶、奇，根据最低位n0的0、1状态来分，若n0=0，则为偶序列；n0=1则为奇序列，得到两组序列：v000 010 100 110 001 011 101 111v第二次对这两个偶、奇序列再分一次偶、奇序列，这就要根据n1的、状态。若n1=0，则为偶序列；n1=1则为奇序列，得到四组序列：v000 100 010 110 001 101 011 111v同理，再根据n2的、状态来分偶、奇序列，直到不能再分偶、奇时为止。对于N=8,n2已是最高位，最后一次分得结果为v000 100 010 110 001 10

17、1 011 111（4）蝶形类型随迭代次数成倍增加）蝶形类型随迭代次数成倍增加观察8点FFT的三次迭代运算:第一级迭代，有一种类型的蝶形运算系数W08，两个数据点间隔为1第二级迭代，有二种类型的蝶形运算系数W08、W28，参加运算的两个数据点间隔为2。第三级迭代，有四类蝶形运算系数W08、W18、W28、W38，参加运算的两个数据点间隔为4。结论：每迭代一次，蝶形类型增加一倍，数据点间隔也增大一倍。每一级的取数间隔和蝶形类型种类均为2i-1，i=1,2,M。v (5)编程思想及程序框图图 DITFFT运算和程序框图 开 始送入x(n)，MN2 M倒 序L1,M0,B 1P2 M LJk J,N

18、1,2L输 出结 束B 2 L1v 三、频域抽取法三、频域抽取法FFT(DIFFFT)v 在基2快速算法中，频域抽取法FFT也是一种常用的快速算法，简称DIFFFT。v 设序列x(n)长度为N=2M，首先将x(n)前后对半分开，得到两个子序列，其DFT可表示为如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20()()()()()()()2()()2NkNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW/21,(1)1kNkNkWk 偶数 奇数 将X(k)分解成偶数组

19、与奇数组，当k取偶数(k=2r,r=0,1,N/2-1)时/2 120/2 12/20(2)()()2()()2NrnNnNrnNnNXrx nx nWNx nx nW当k取奇数(k=2r+1,r=0,1,N/2-1)时/2 1(21)0/2 1/20(21)()()2()()2NnrNnNnnrNNnNXrx nx nWNx nx nWW 将x1(n)和x2(n)分别代入上两式，可得/2 11/20/2 12/20(2)()(21)()NrnNnNrnNnXrx n WXrx n W图 DIFFFT蝶形运算流图符号 以N=8的频率抽取为例x(0)x(1)x(2)x(3)x(4)x(5)x(6

20、)x(7)-1-1-1-1N/2点DFTa(0)a(1)a(2)a(3)N/2点DFTb(0)b(1)b(2)b(3)WN1WN2WN3X(0)X(2)X(4)X(6)X(1)X(3)X(5)X(7)按频率抽取将8点DFT分解成两个4点DFT按频率抽取将8点DFT分解成四个2点DFT与时间抽取法一样，由于N=2M，N/2仍是一个偶数,这样，一个N=2M点的DFT通过M次分解后，最后只剩下全部是2点的DFT，2点DFT实际上只有加减运算。但为了比较，也为了统一运算的结构，仍用一个系数为W0N 的蝶形运算来表示。频率抽取法的流图是时域抽取法流图的左右翻转。下图是N=8的频率抽取法FFT流图。N=8

21、的按频率抽取FFT运算流图频率抽取法频率抽取法FFT的运算特点：的运算特点：（1）蝶形运算 对于任何一个2的整数幂N=2M，总是可以通过M次分解最后完全成为2点的DFT运算。这样的M次分解，就构成从x(n)到X(k)的M级运算过程。将频率抽取法的流图反转，并将输入变输出，输出变输入，得到的便是时间抽取法流图（反映了时域，频域的对称法）。频率抽取法也共有M级运算（N=2M），其运算量与时间抽取法相同。（2）原位计算 类似于时间抽取法，当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器，所以频域抽取法也可进行原位计算。（3）序数重排 它的输入正好是自然顺序。但它的输出却是码位倒置的顺序。因此运算完毕后，要通过变址运算将码位倒置的顺序转换为自然顺序，然后输出，变址方法同时间抽取法。（4）蝶形类型随迭代次数成倍减少(与时间抽取法相反)第一级迭代中有N/2种蝶形运算系数，参加蝶形运算的两个数据相隔N/2，随后每次迭代，蝶形类形比前一级减少一倍，间距也减少一倍，最后一级迭代，蝶形类形只有一种W0N，数据间隔为1。由这几点规律可以看出，频率抽取法与时间抽到法是两种等价的FFT运算。