【文章內(nèi)容簡介】 FT)只是離散傅里葉變換（ DFT）的一種快速計(jì)算方法，其并不是一種新的變換。如前面所講，有限長序列的特點(diǎn)是其頻域可離散化成有限長序列。 DFT 的計(jì)算在信號處理中非常有用，再有，信號的譜分析對通信，圖像傳輸，聲納等都是很重要的。此外，在系統(tǒng)的分析，設(shè)計(jì)和實(shí)現(xiàn)中都會用到 DFT 計(jì)算。但是，在很長一段時(shí)間里，由于 DFT 的計(jì)算量極大，即使采用計(jì)算機(jī)也很難對實(shí)際問題進(jìn)行處理，所以沒有得到真正的運(yùn)用。直到庫利和圖基提出機(jī)器計(jì)算傅里葉級數(shù)的一種算法，并經(jīng)過后來人們的改進(jìn)發(fā)展，完善了一套高 速有效的運(yùn)算方法，使得DFT 的計(jì)算量得到簡化，運(yùn)算時(shí)間一般可以縮短一，二個(gè)數(shù)量級，從而使 DFT 的運(yùn)算在實(shí)踐中得到真正廣泛應(yīng)用。 FFT 的來源 若 x(n)是有限長序列，點(diǎn)數(shù)為 N，其 DFT為 10( ) ( )N nkNkX k x n W????，其中， 2j NNWe??? ， k=0,1,? N1 （ 31） 反變換（ IDFT）為 101( ) ( )N nkNkx n X k WN? ??? ?，其中， n=0,1,? ,N1 （ 32） 二者 的差別只在于 NW 的指數(shù)符號不同，以及差一個(gè)常數(shù)因子 。因而，直接計(jì)算DFT，乘法次數(shù)和加法次數(shù)都是和 2N 成正比的，當(dāng) N 很大時(shí)運(yùn)算量顯而易見，例如，當(dāng) N＝ 8， DFT 需 64 次復(fù)乘，而當(dāng) N＝ 1024 時(shí)， DFT 需一百多萬次復(fù)運(yùn)算，這對實(shí)用性很強(qiáng)的信號處理來說，對計(jì)算速度要求是太高了。 下面討論減少運(yùn)算量的方法。觀察 DFT 的運(yùn)算形式可看出，利用系數(shù) nkNW 的以下特性，就可以減少 DFT 的運(yùn)算量： nkNW 的共軛對稱性 *()nk nkNNWW?? nkNW 的周期性 ( ) ( )nk n N k n k NN N NW W W???? nkNW 的可約性 湖北理工學(xué)院 畢業(yè)設(shè)計(jì) (論文 ) 10 nk nkmN NmWW? ， nknk mNNmWW? 由此可得出 ( ) ( )N k n N n k nkNNNWWW? ? ???， 2 1NNW ?? ， ()2W Nk kNNW? ?? 這樣，通過這些性質(zhì)，使 DFT 運(yùn)算中有些項(xiàng)合并；利用 nkNW 的對稱性，周期性及可約性 ,將較長序列的 DFT 分解成較短序列的 DFT，從而使 DFT 計(jì)算過程轉(zhuǎn)化成許多迭代運(yùn)算過程。而前面已經(jīng)說到， DFT 的運(yùn)算量是與 2N 成正比的，所以 N 越小，運(yùn)算 量越低。 快速傅里葉變換算法正是基于此而發(fā)展起來的。它的運(yùn)算基本上可以分成兩大類，即按時(shí)間抽選法和按頻率抽選法。根據(jù)論文要求，我們只考慮前一種方法。 按時(shí)間抽選（ DIT）的基 2FFT算法（庫利 圖基算法） 算法原理 取序列點(diǎn)數(shù) 2LN? ， L為正整數(shù)。如果不滿足這個(gè)條件，可以加上若干零值點(diǎn)，使達(dá)到這一要求，即為基 2FFT。 對 N 點(diǎn)序列，將 ()xn 按 n的奇偶性分組： 1(2 ) ( )x r x r? ， 2(2 1) ( )x r x r?? ，其中 r=0,1,? , 21N ? 則 DFT 轉(zhuǎn)化成 10( ) [ ( ) ] ( )N nkNnX k D F T x n x n W???? ? 11 22 ( 2 1 )00( 2 ) ( 2 1 )NNr k r kNNrrx r W x r W?? ???? ? ??? 122221200( )( ) ( ) ( )NNr k r kNNrrx r W x r W??????? （ 33） 利用系數(shù) nkNW 的可約性，即 422j NNNW e W????，則 11221 2 1 22200( ) ( ) ( ) ( ) ( )NNr k k r k kN N N NrrX k x r W W x r W X k W X k????? ? ? ??? （ 34） 湖北理工學(xué)院 畢業(yè)設(shè)計(jì) (論文 ) 11 式中 2()Xk與 2()Xk分別是 1()Xr及 2()Xr的 N/2 點(diǎn) DFT： 11221 1 12200( ) ( ) ( 2 )NNr k r kNNrrX k x r W x r W???????? （ 35） 11222 2 22200( ) ( ) ( 2 1 )NNr k r kNNrrX k x r W x r W????? ? ??? （ 36） 由式（ 34）可以看出，一個(gè) N點(diǎn) DFT 分解成兩個(gè) N/2 點(diǎn)的 DFT，它們按（ 34）式又可組合成一個(gè) N點(diǎn) DFT。但是， 1()xr， 2()xr以及 1()Xk， 2()Xk都是 N/2 點(diǎn)的序列，即 r,k 滿足 r,k=0,1,? , 21N ? 。而 X(k)卻有 N點(diǎn)，而用式（ 34）只得 X(k)前一半，要用 1()Xk， 2()Xk來表式全部 X(k)值，還需利用系數(shù)的周期性質(zhì)，即 ()222NrkrkNNWW?? 這樣可得到 1122()21 1 1 12200( ) ( ) ( ) ( )2NNNrk rkNNrrNX k x r W x r W X k?????? ? ? ??? （ 37） 同理可得 22( ) ( )2NX k X k?? （ 38） 式（ 37）、式（ 38）表明后半部段 k 值所對應(yīng)的 1()Xk， 2()Xk與前半部段 k值所對應(yīng)的 1()Xk， 2()Xk分別相等。 在考慮 nkNW 的性質(zhì)： ()22NNk kkN N N NW W W W? ? ? ? （ 39） 這樣，將式（ 37）、式（ 38）、式（ 39）帶入式（ 34）中，就可將 X(k)表示成前后兩段： 前半部分 X(k)， (k=0,1,? , 21N ? ) 12( ) ( ) ( ) kNX k k k WXX?? （ 310） 后半部分 X(k)， (k=0,1,? , 21N ? ) 212( ) ( ) ( )2 2 2NkNN N NX k X k W X k?? ? ? ? ? 12( ) ( )kNX k W X k?? ， k=0,1,? , 21N ? （ 311） 湖北理工學(xué)院 畢業(yè)設(shè)計(jì) (論文 ) 12 這樣，只要求出 0 到 ( 21N ? )區(qū)間的所有 1()Xk， 2()Xk值，即可求出 0 到( 1N? ） 區(qū)間內(nèi)的所有 ()Xk值，這就大大節(jié)省了運(yùn)算。 式（ 310）、（ 311）的運(yùn)算可以用如下的蝶形信號流圖 31表示。 圖 31蝶形運(yùn)算流圖 采用這種表示法，其過程可圖 32說明。圖 32 表示 N=8 的情況，輸出值 X(0)到 X(3)是由式（ 310）給出的，輸出值 X（ 4）到 X（ 7）是由式（ 311）給出。 據(jù)此，一個(gè) N 點(diǎn) DFT 分成兩個(gè) 2N 點(diǎn) DFT時(shí)，若直接計(jì)算 2N 點(diǎn) DFT，則每個(gè) 2N 點(diǎn) DFT 只需要 24N 次復(fù)數(shù)乘法， ( 1)22NN? 次復(fù)數(shù)加法。同時(shí)，把兩個(gè) 2N 點(diǎn)DFT 合成為一個(gè) DFT 時(shí)，有 2N 個(gè)蝶形運(yùn)算，還需要 2N 次復(fù)數(shù)乘法及 N次復(fù)數(shù)加法。因而通過這第一 步分解后，工作量總體得到大幅降低。 既然如此，由于 2LN? ，因而 2N 仍是偶數(shù)，可以更進(jìn)一步把每個(gè) 2N 點(diǎn)子序列按其奇偶性再分成兩個(gè) 4N 點(diǎn)子序列。先將 1()xr進(jìn)行分解： 1314(2 ) ( )(2 1) ( )x l x lx l x l??? ??? （ 312） 其中， l=0,1,? , 41N ? 11442 ( 2 1 )1 1 12200( ) ( 2 ) ( 2 1 )NNlk k lNNlrX k x l W W x l?? ???? ? ??? 1144344 2 400( ) ( )NNlk k kN N Nllx l W W x l W???????? 342( ) ( )kNX k W X k??， k=0,1,? , 41N ? 1()Xk 2()Xk 12( ) ( )kNX k W X k? 12( ) ( )kNX k W X k? 湖北理工學(xué)院 畢業(yè)設(shè)計(jì) (論文 ) 13 且 1 3 42( ) ( ) ( )4 kNNX k X k W X k? ? ?， k=0,1,? , 41N ? 其中 1433 40( ) ( )NlkNlX k x l W??? ? （ 313） 1444 40( ) ( )NlkNlX k x l W??? ? （ 314） 圖 32 將 N點(diǎn) DFT分為兩個(gè) 2N 點(diǎn)的 DFT圖 圖 33給出 N=8 時(shí)，將一個(gè) 2N 點(diǎn)的 DFT分成兩個(gè) 4N 點(diǎn) DFT，由這兩個(gè) 4N點(diǎn) DFT 組合成一個(gè) 2N 點(diǎn) DFT 流圖。 同時(shí)， 2()xr也可以進(jìn)行同樣的分解，得到 1(0) (0)xx? 1(1) (2)xx? 1(2) (4)xx? 1(3) (6)xx? 2(1) (3)xx? 2(0) (1)xx? 2(2) (5)xx? 2(3) (7)xx? 2N 點(diǎn) DFT (1)X (0)X (2)X (3)X (4)X (6)X (7)X (5)X 2N 點(diǎn) DFT 湖北理工學(xué)院 畢業(yè)設(shè)計(jì) (論文 ) 14 2 5 62( ) ( ) ( )kNX k X k W X k?? 2 3 62( ) ( ) ( )4 kNNX k X k W X k? ? ? 其中 11445 2 54400( ) ( 2 ) ( )NNlk lkNNllX k x l W x l W???????? （ 315） 11446 2 64400( ) ( 2 1 ) ( )NNlk lkNNllX k x l W x l W????? ? ??? （ 316） 最后將系數(shù)統(tǒng)一為 22kkNNWW?，則一個(gè) N=8 點(diǎn) DFT 就可分成四個(gè) 2 點(diǎn) DFT，這樣就可得到 34圖。 圖 33 由兩個(gè) 4N 點(diǎn) DFT組合成一個(gè) 2N 點(diǎn) DFT 根據(jù)上面同樣的分析知道，最后剩下的是 2點(diǎn) DFT，對于此例 N=8，就是四個(gè)2點(diǎn) DFT，其輸出為 3()Xk， 4()Xk， 5()Xk， 6()Xk (k=0,1)，這由式（ 313）至（ 316）可以計(jì)算出來。由此可得出一個(gè)按時(shí)間抽選運(yùn)算的大致的 8點(diǎn) DFT 流 圖，如圖 35 所示。 31( 0) ( 0) ( 0)x x x?? 41( 0 ) (1 ) ( 2 )x x x?? 31(1 ) ( 2 ) ( 4 )x x x?? 41(1 ) ( 3 ) ( 6 )x x x?? 4N 點(diǎn) DFT 4N 點(diǎn) DFT 1(0)X 1(1)X 1(2)X 1(3)X 湖北理工學(xué)院 畢業(yè)設(shè)計(jì) (論文 ) 15 圖 34 將一個(gè) N點(diǎn) DFT分成四個(gè) 4N 點(diǎn) DFT 運(yùn)算量 由圖 35 可知，當(dāng) 2LN? 時(shí) (L表示級數(shù) )，每級都由 2N 個(gè)蝶形運(yùn)算組成，每個(gè)蝶形運(yùn)算有一次復(fù)乘，二次復(fù)加，因而每級運(yùn)算都需 2N 次復(fù)乘和 N 次復(fù)加，因此 L級運(yùn)算共需 復(fù) 乘數(shù) 2lo g22f NNm L N?? 復(fù)加數(shù) 2logfa NL N N?? 因?yàn)?0 1NW? ， 4NNWj?? ，這幾個(gè)系數(shù)都不用乘法運(yùn)算。此外，當(dāng) N 較大時(shí)，這些特例相對而言就很少。直接 DFT 算