課件4快速葉變換

1、第4章 快速傅里葉變換(FFT) 第第4章章 快速傅里葉變換快速傅里葉變換 4.1 引言引言 4.2 直接計(jì)算直接計(jì)算DFT的問題及改進(jìn)的途徑的問題及改進(jìn)的途徑 4.3 按時(shí)間抽?。ò磿r(shí)間抽?。―IT）的基）的基2-FFT算法算法（） 4.4 按頻率抽取（按頻率抽?。―IF）的基）的基2-FFT算法算法4.5 離散傅里葉反變換（離散傅里葉反變換（IDFT）的快速計(jì)算方法）的快速計(jì)算方法 4.10 線性卷積的線性卷積的FFT算法算法 第4章 快速傅里葉變換(FFT) 4.1 引引 言言 快速傅里葉變換（快速傅里葉變換（FFT）是離散傅里葉變換）是離散傅里葉變換（DFT）的一種快速算法。）的一種快

2、速算法。 有限長序列在數(shù)字信號處理中占有很重要的地位。有限長序列在數(shù)字信號處理中占有很重要的地位。有限長序列的一個(gè)重要特點(diǎn)是其頻域也可離散化為有限長序列的一個(gè)重要特點(diǎn)是其頻域也可離散化為有限長序列，即可進(jìn)行離散傅里葉變換（有限長序列，即可進(jìn)行離散傅里葉變換（DFT）。）。在數(shù)字信號處理中經(jīng)常需要進(jìn)行在數(shù)字信號處理中經(jīng)常需要進(jìn)行DFT運(yùn)算，例如在運(yùn)算，例如在信號的頻譜分析、系統(tǒng)的分析、設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)信號的頻譜分析、系統(tǒng)的分析、設(shè)計(jì)和實(shí)現(xiàn)中都會(huì)用到用到DFT的計(jì)算。的計(jì)算。 第4章 快速傅里葉變換(FFT) 但是，因?yàn)橹苯佑?jì)算但是，因?yàn)橹苯佑?jì)算DFT的計(jì)算量與變換區(qū)間長度的計(jì)算量與變換區(qū)間長度N

3、的平方成正比，當(dāng)?shù)钠椒匠烧?，?dāng)N較大時(shí)，計(jì)算量太大，所以在快速博較大時(shí)，計(jì)算量太大，所以在快速博里葉變換里葉變換(簡稱簡稱FFT)出現(xiàn)以前，直接用出現(xiàn)以前，直接用DFT算法進(jìn)行譜分算法進(jìn)行譜分析和信號的實(shí)時(shí)處理是不切實(shí)際的。直到析和信號的實(shí)時(shí)處理是不切實(shí)際的。直到1965年發(fā)現(xiàn)了年發(fā)現(xiàn)了DFT的一種快速算法以后，情況才發(fā)生了根本的變化。的一種快速算法以后，情況才發(fā)生了根本的變化。 人們開始認(rèn)識到人們開始認(rèn)識到DFT運(yùn)算的一些內(nèi)在規(guī)律，從而很運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善了一套高速有效的運(yùn)算方法，快地發(fā)展和完善了一套高速有效的運(yùn)算方法， 這就是現(xiàn)這就是現(xiàn)在人們普遍稱之為快速傅里葉變換

4、（在人們普遍稱之為快速傅里葉變換（FFT）的算法。）的算法。 FFT出現(xiàn)后使出現(xiàn)后使DFT的運(yùn)算大大簡化，運(yùn)算時(shí)間一般可縮短一、的運(yùn)算大大簡化，運(yùn)算時(shí)間一般可縮短一、二個(gè)數(shù)量級之多，從而使二個(gè)數(shù)量級之多，從而使DFT的運(yùn)算在實(shí)際中真正得到了的運(yùn)算在實(shí)際中真正得到了廣泛的應(yīng)用。廣泛的應(yīng)用。 第4章 快速傅里葉變換(FFT) 4.2 直接計(jì)算直接計(jì)算DFT的問題及改進(jìn)的途徑的問題及改進(jìn)的途徑 一、直接計(jì)算一、直接計(jì)算DFT的運(yùn)算量的運(yùn)算量 設(shè)設(shè)x(n)為為N點(diǎn)有限長序列，其點(diǎn)有限長序列，其DFT為為 10)()(NnnkNWnxkXk=0, 1, , N-1 （4-1） 反變換（反變換（IDFT）

5、為）為 101( )( )NnkNkx nX k WNn=0, 1, , N-1 （4-2） 二者的差別只在于二者的差別只在于WN的指數(shù)符號不同，以及差的指數(shù)符號不同，以及差一個(gè)常數(shù)乘因子一個(gè)常數(shù)乘因子1/N，所以，所以IDFT與與DFT具有相同的運(yùn)具有相同的運(yùn)算工作量。算工作量。 下面我們只討論下面我們只討論DFT的運(yùn)算量。的運(yùn)算量。10)()(NnnkNWnxkXk=0, 1, , N-1 第4章 快速傅里葉變換(FFT) 一般來說，一般來說，x(n)和和WNnk都是復(fù)數(shù)，都是復(fù)數(shù)，X(k)也是復(fù)數(shù)，也是復(fù)數(shù)，因此每計(jì)算一個(gè)因此每計(jì)算一個(gè)X(k)值，需要值，需要N次復(fù)數(shù)乘法和次復(fù)數(shù)乘法和N

6、-1次復(fù)次復(fù)數(shù)加法。而數(shù)加法。而X(k)一共有一共有N個(gè)點(diǎn)（個(gè)點(diǎn)（k從從0取到取到N-1），所以），所以完成整個(gè)完成整個(gè)DFT運(yùn)算總共需要運(yùn)算總共需要N2次復(fù)數(shù)乘法及次復(fù)數(shù)乘法及N(N-1)次復(fù)次復(fù)數(shù)加法。在這些運(yùn)算中乘法運(yùn)算要比加法運(yùn)算復(fù)雜，需數(shù)加法。在這些運(yùn)算中乘法運(yùn)算要比加法運(yùn)算復(fù)雜，需要的運(yùn)算時(shí)間也多一些。要的運(yùn)算時(shí)間也多一些。10)()(NnnkNWnxkXk=0, 1, , N-1 第4章 快速傅里葉變換(FFT) 解解: 直接計(jì)算直接計(jì)算DFT所需復(fù)乘次數(shù)為（所需復(fù)乘次數(shù)為（N2)21012次，因次，因此用每秒可做此用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，則需要近萬次復(fù)數(shù)乘法的計(jì)算機(jī)

7、，則需要近3000小時(shí)。小時(shí)。 這對實(shí)時(shí)性很強(qiáng)的信號處理來說，要么提高計(jì)算這對實(shí)時(shí)性很強(qiáng)的信號處理來說，要么提高計(jì)算速度，而這樣，對計(jì)算速度的要求太高了。另外，只速度，而這樣，對計(jì)算速度的要求太高了。另外，只能通過改進(jìn)對能通過改進(jìn)對DFT的計(jì)算方法，以大大減少運(yùn)算次數(shù)。的計(jì)算方法，以大大減少運(yùn)算次數(shù)。 例例4-1:根據(jù)式（根據(jù)式（4-1），對一幅），對一幅NN點(diǎn)的二維圖像進(jìn)行點(diǎn)的二維圖像進(jìn)行DFT變換，如用每秒可做變換，如用每秒可做10萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)萬次復(fù)數(shù)乘法的計(jì)算機(jī)，當(dāng)N=1024時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？時(shí)，問需要多少時(shí)間（不考慮加法運(yùn)算時(shí)間）？第4章 快速傅里

8、葉變換(FFT) 二、二、 減少運(yùn)算工作量的途徑減少運(yùn)算工作量的途徑 能否減少運(yùn)算量，從而縮短計(jì)算時(shí)間呢？仔細(xì)觀察能否減少運(yùn)算量，從而縮短計(jì)算時(shí)間呢？仔細(xì)觀察DFT的運(yùn)算就可看出，的運(yùn)算就可看出， 利用系數(shù)利用系數(shù)WNnk的以下固有特性，的以下固有特性，就可減少運(yùn)算量：就可減少運(yùn)算量： （1） WNnk的共軛對稱性的共軛對稱性 nkNnkNWW*)(（2） WNnk的周期性的周期性 ()()nkn N kn k NNNNWWW（3） WNnk的可約性的可約性 mnkmNnkNnmkmNnkNWWWW/,第4章 快速傅里葉變換(FFT) 另外另外 kNNkNNNnkNknNNkNnNWWWWWW

9、)2/(2/)()(, 1, 這樣，利用這些特性，使這樣，利用這些特性，使DFT運(yùn)算中有些項(xiàng)可以合運(yùn)算中有些項(xiàng)可以合并，并能使并，并能使DFT分解為更少點(diǎn)數(shù)的分解為更少點(diǎn)數(shù)的DFT運(yùn)算。由于運(yùn)算。由于DFT的運(yùn)算量是與的運(yùn)算量是與N2成正比的，所以成正比的，所以N越小越有利，因而小越小越有利，因而小點(diǎn)數(shù)序列的點(diǎn)數(shù)序列的DFT比大點(diǎn)數(shù)序列的比大點(diǎn)數(shù)序列的DFT的運(yùn)算量要小。的運(yùn)算量要小。 快速傅里葉變換算法正是基于這樣的基本思想而發(fā)快速傅里葉變換算法正是基于這樣的基本思想而發(fā)展起來的。它的算法形式有很多種，但基本上可以分成展起來的。它的算法形式有很多種，但基本上可以分成兩大類：兩大類： 按時(shí)間抽

10、取按時(shí)間抽取(ecimation in Time，縮寫為，縮寫為DIT)法法 按頻率抽取按頻率抽取(Decimation in Frequency，縮寫為，縮寫為DIF)法法第4章 快速傅里葉變換(FFT) 4.3 按時(shí)間抽取按時(shí)間抽取(DIT)的基的基-2 FFT算法算法 (庫利庫利-圖基算法圖基算法)一、一、 算法原理算法原理 設(shè)序列設(shè)序列x(n)長度為長度為N，且滿足，且滿足N=2L，L為正整數(shù)。為正整數(shù)。按按n的奇偶把的奇偶把x(n)分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的子序列：點(diǎn)的子序列： 12, 1 , 0)() 12()()2(21Nrrxrxrxrx（4-4） 則可將則可將DFT化為化

11、為 111000( ) ( )( )( )( )NNNnknknkNNNnnnnnX kDFT x nx n Wx n Wx n W為偶數(shù)為奇數(shù)第4章 快速傅里葉變換(FFT) 111000( ) ( )( )( )( )NNNnknknkNNNnnnnnX kDFT x nx n Wx n Wx n W為偶數(shù)為奇數(shù)2222/2/2jjNNNNWeeW)()()()()(212/21202/1120kXWkXWrxWWrxkXkNrkNNrkNrkNNr（4-5） 11222(21)001122221200(2 )(21)( )()( )()NNrkrkNNrrNNrkkrkNNNrrxr W

12、xrWx r WWx r W第4章 快速傅里葉變換(FFT) 式中，式中，X1(k)與與X2(k)分別是分別是x1(r)及及x2(r)的的N/2點(diǎn)點(diǎn)DFT： rkNNrrkNNrrkNNrrkNNrWrxWrxkXWrxWrxkX2/1202/212022/1202/11201) 12()()()2()()(（4-6） （4-7） X1(k)，X2(k)只有只有N/2個(gè)點(diǎn)，即個(gè)點(diǎn)，即k=0, 1, , N/2-1。而而X(k)卻有卻有N個(gè)點(diǎn)，即個(gè)點(diǎn)，即k=0, 1, , N-1， 故用故用式（式（4-5）計(jì)算得到的只是計(jì)算得到的只是X(k)的前一半的前一半 的結(jié)果。的結(jié)果。0,1,12Nk第4

13、章 快速傅里葉變換(FFT) rkNNkrNWW2/22/所以所以 )()()(212/120122/12011kXWrxWrxkNXrkNNrkNrNNr（4-8） 同理可得同理可得 )(222kXkNX（4-9） 式（式（4-8）、式（）、式（4-9）說明了）說明了后半部分后半部分k值值（N/2kN-1）所對應(yīng)的所對應(yīng)的X1(k),2(k)分別等于前半部分分別等于前半部分k值值（0kN/2-1）所對應(yīng)的所對應(yīng)的X1(k), X2(k)。 （周期性）（周期性）由于由于第4章 快速傅里葉變換(FFT) 再考慮到再考慮到 的以下性質(zhì)的以下性質(zhì): kNkNNNkNNWWWW2/2把把式（式（4-8

14、）、式（）、式（4-9）、式（、式（4-10）代入）代入式（式（4-5），就可將就可將X(k)表達(dá)為前后兩部分：表達(dá)為前后兩部分： 12, 1 , 0)()()(21NkkXWkXkXkN)()(22221221kXWkXNkXWNkXNkXkNNkN12, 1 , 0Nk（4-10） （4-11） （4-12） kNW第4章 快速傅里葉變換(FFT) 圖圖 4-1 時(shí)間抽選法蝶形運(yùn)算流圖符號時(shí)間抽選法蝶形運(yùn)算流圖符號 12( )( )( ),0,1,12kNNX kX kW Xkk12( )( ),0,1,122kNNNX kX kW Xkkp 蝶形運(yùn)算蝶形運(yùn)算第4章 快速傅里葉變換(FFT

15、) 圖圖 4-2 按時(shí)間抽選將一個(gè)按時(shí)間抽選將一個(gè)N點(diǎn)點(diǎn)DFT分解分解 為兩個(gè)為兩個(gè)N/2點(diǎn)點(diǎn)DFT（N=8） X1(0)X1(1)x1(0) x(0)X(0)X(1)X1(2)X1(3)110NWDFT2點(diǎn)Nx1(1) x(2)x1(2) x(4)x1(3) x(6)X(2)X(3)X2(0)X2(1)x2(0) x(1)X(4)X(5)X2(2)X2(3)DFT2點(diǎn)Nx2(1) x(3)x2(2) x(5)x2(3) x(7)X(6)X(7)1NW2NW3NW11第4章 快速傅里葉變換(FFT) (1)N/2點(diǎn)的點(diǎn)的DFT運(yùn)算量運(yùn)算量: 復(fù)乘次數(shù)復(fù)乘次數(shù):復(fù)加次數(shù)復(fù)加次數(shù):(2)兩個(gè)兩個(gè)N

16、/2點(diǎn)的點(diǎn)的DFT運(yùn)算量運(yùn)算量:復(fù)乘次數(shù)復(fù)乘次數(shù):復(fù)加次數(shù)復(fù)加次數(shù): (3)N/2個(gè)蝶形運(yùn)算的運(yùn)算量個(gè)蝶形運(yùn)算的運(yùn)算量:復(fù)乘次數(shù)復(fù)乘次數(shù):復(fù)加次數(shù)復(fù)加次數(shù): p運(yùn)算量運(yùn)算量復(fù)乘復(fù)乘:復(fù)加復(fù)加:總共運(yùn)算量總共運(yùn)算量: *N點(diǎn)點(diǎn)DFT的復(fù)乘為的復(fù)乘為N2 ;復(fù)加復(fù)加N(N-1);與分解后相比可知與分解后相比可知,計(jì)算工作點(diǎn)差不多減少計(jì)算工作點(diǎn)差不多減少 一半。一半。22()24NN(1)22NN22222NN(1)2NN2N22NN22(1) / 2222NNNNN2(1)22NNNN第4章 快速傅里葉變換(FFT) 由于由于N=2L，因而，因而N/2仍是偶數(shù)，可以進(jìn)一步把每個(gè)仍是偶數(shù)，可以進(jìn)一步

17、把每個(gè)N/2點(diǎn)子序列再按其奇偶部分分解為兩個(gè)點(diǎn)子序列再按其奇偶部分分解為兩個(gè)N/4點(diǎn)的子序列。點(diǎn)的子序列。 1314(2 )( )0,1,1(21)( )4xlx lNlxlx l（4-13） 14, 1 , 0)()()()() 12()2()(42/31404/42/1404/3140)12(2/114022/11NkkXWkXWlxWWlxWlxWlxkXkNNllkNkNNllkNNlklNNllkN例如，先將例如，先將x1(r)進(jìn)行分解：進(jìn)行分解：第4章 快速傅里葉變換(FFT) 且且 13/24( )( ),0,1,144kNNNXkXkWXkk式中：式中： 1404/441404

18、/33)()()()(NllkNNllkNWlxkXWlxkX（4-14） （4-15） 圖圖4-3給出給出N=8時(shí)，將一個(gè)時(shí)，將一個(gè)N/2點(diǎn)點(diǎn)DFT分解成兩個(gè)分解成兩個(gè)N/4點(diǎn)點(diǎn)DFT， 由這兩個(gè)由這兩個(gè)N/4點(diǎn)點(diǎn)DFT組合成一個(gè)組合成一個(gè)N/2點(diǎn)點(diǎn)DFT的流圖。的流圖。 第4章 快速傅里葉變換(FFT) 圖圖 4-3 N/2點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/4點(diǎn)點(diǎn)DFT DFT4點(diǎn)NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點(diǎn)NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)

19、X1(3)1102/NW12/NW第4章 快速傅里葉變換(FFT) x2(r)也可進(jìn)行同樣的分解：也可進(jìn)行同樣的分解： )()(4)()()(62/5262/52kXWkXkNXkXWkXkXkNkN14, 1 , 0Nk式中：式中： 1404/21404/661404/21404/55) 12()()()2()()(NllkNNllkNNllkNNllkNWlxWlxkXWlxWlxkX 將系數(shù)統(tǒng)一為將系數(shù)統(tǒng)一為 ，則一個(gè)，則一個(gè)N=8點(diǎn)點(diǎn)DFT就可分就可分解為四個(gè)解為四個(gè)N/4=2點(diǎn)點(diǎn)DFT，如圖如圖4-4所示所示。2/2kkNNWW第4章 快速傅里葉變換(FFT) 圖圖 4-4 一個(gè)一個(gè)

20、N=8點(diǎn)點(diǎn)DFT分解為四個(gè)分解為四個(gè)N/4點(diǎn)點(diǎn)DFT DFT4點(diǎn)NX3(0)X3(1)x3(0) x1(0) x(0)x3(1) x1(2) x(4)X1(0)X1(1)DFT4點(diǎn)NX4(0)X4(1)x4(0) x1(1) x(2)x4(1) x1(3) x(6)X1(2)X1(3)110NW2NWX(0)X(1)X(2)X(3)DFT4點(diǎn)NX5(0)X5(1)x5(0) x2(0) x(1)x5(1) x2(2) x(5)X2(0)X2(1)DFT4點(diǎn)NX6(0)X6(1)x6(0) x2(1) x(3)x6(1) x2(3) x(7)X2(2)X2(3)11X(4)X(5)X(6)X(7

21、)0NW1NW2NW3NW11110NW2NW第4章 快速傅里葉變換(FFT) 根據(jù)上面同樣的分析知道，利用四個(gè)根據(jù)上面同樣的分析知道，利用四個(gè)N/4點(diǎn)的點(diǎn)的DFT及兩級蝶形組合運(yùn)算來計(jì)算及兩級蝶形組合運(yùn)算來計(jì)算N點(diǎn)點(diǎn)DFT，比只用一次分解，比只用一次分解蝶形組合方式的計(jì)算量又減少了大約一半。蝶形組合方式的計(jì)算量又減少了大約一半。 對于對于N=8時(shí)的時(shí)的DFT, N/4點(diǎn)即為兩點(diǎn)點(diǎn)即為兩點(diǎn)DFT,因此因此 133/40144/40155/40166/40( )( ), 0,1( )( ), 0,1( )( ), 0,1( )( ), 0,1lkNllkNllkNllkNlXkx l WkXkx

22、 l WkXkx l WkXkx l Wk第4章 快速傅里葉變換(FFT) 式中，式中， , 故上式不需要乘法。故上式不需要乘法。0122121NjjWeeW可得：可得：00332310332300442410442400552515525(0)(0)(1)(0)(4)(1)(0)(1)(0)(4)(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)(0)(0)(1)(1)(5)(1)(0)(1)(1)NNNNNXxW xxW xXxW xxW xXxW xxW xXxW xxW xXxW xxW xXxW xx0006626106626(5)(0)(0)(1)(3)(7)(1)(0)

23、(1)(3)(7)NNNW xXxW xxW xXxW xxW x第4章 快速傅里葉變換(FFT) 這種方法的每一步分解，都是這種方法的每一步分解，都是按輸入序列在時(shí)間上的次序按輸入序列在時(shí)間上的次序是屬于偶數(shù)還是屬于奇數(shù)來分解是屬于偶數(shù)還是屬于奇數(shù)來分解為兩個(gè)更短的子序列，所以稱為兩個(gè)更短的子序列，所以稱為為“按時(shí)間抽取法按時(shí)間抽取法”。 圖圖 4-5 N=8 按時(shí)間抽取的按時(shí)間抽取的FFT運(yùn)算流圖運(yùn)算流圖（） x(0)X(0)x(4)X(1)10NWx(2)X(2)x(6)X(3)10NW0NW2NW11x(1)X(4)x(5)X(5)10NWx(3)X(6)x(7)X(7)10NW0NW

24、2NW110NW1NW2NW3NW1111第4章 快速傅里葉變換(FFT) 二、二、 運(yùn)算量運(yùn)算量 由按時(shí)間抽取法由按時(shí)間抽取法FFT的流圖可見，當(dāng)?shù)牧鲌D可見，當(dāng)N=2L時(shí)，共時(shí)，共有有L級蝶形，級蝶形， 每級都由每級都由N/2個(gè)蝶形運(yùn)算組成，每個(gè)蝶形個(gè)蝶形運(yùn)算組成，每個(gè)蝶形需要一次復(fù)乘、需要一次復(fù)乘、 二次復(fù)加，因而每級運(yùn)算都需二次復(fù)加，因而每級運(yùn)算都需N/2次次復(fù)乘和復(fù)乘和N次復(fù)加，這樣次復(fù)加，這樣L級運(yùn)算總共需要級運(yùn)算總共需要 復(fù)乘數(shù)復(fù)乘數(shù) 22log22logFFNNmLNaNLNN復(fù)加數(shù)復(fù)加數(shù) 第4章 快速傅里葉變換(FFT) 由于計(jì)算機(jī)上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的由于計(jì)算機(jī)

25、上乘法運(yùn)算所需的時(shí)間比加法運(yùn)算所需的時(shí)間多得多，故以乘法為例，直接時(shí)間多得多，故以乘法為例，直接DFT復(fù)數(shù)乘法次數(shù)是復(fù)數(shù)乘法次數(shù)是N2，F(xiàn)FT復(fù)數(shù)乘法次數(shù)是復(fù)數(shù)乘法次數(shù)是(N/2) log2N。 直接計(jì)算直接計(jì)算DFT與與FFT算算法的計(jì)算量之比為法的計(jì)算量之比為 22222loglog22NNNNNNLN（4-20） 第4章 快速傅里葉變換(FFT) 當(dāng)當(dāng)N=2048時(shí)，這一比值為時(shí)，這一比值為372.4，即直接計(jì)算，即直接計(jì)算DFT的運(yùn)算量的運(yùn)算量是是FFT運(yùn)算量的運(yùn)算量的372.4倍。當(dāng)點(diǎn)數(shù)倍。當(dāng)點(diǎn)數(shù)N越大時(shí)，越大時(shí)，F(xiàn)FT的優(yōu)點(diǎn)更為的優(yōu)點(diǎn)更為明顯明顯(見書中見書中P150.表表4-1)

26、。 第4章 快速傅里葉變換(FFT) 三、按時(shí)間抽取的三、按時(shí)間抽取的FFT算法的特點(diǎn)算法的特點(diǎn) 1. 原位運(yùn)算（同址運(yùn)算）原位運(yùn)算（同址運(yùn)算） 從從圖圖4-5可以看出這種運(yùn)算的每級（每列）計(jì)算都是由可以看出這種運(yùn)算的每級（每列）計(jì)算都是由N/2 個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代個(gè)蝶形運(yùn)算構(gòu)成的，每一個(gè)蝶形結(jié)構(gòu)完成下述基本迭代運(yùn)算：運(yùn)算： rNmmmrNmmmWjXkXjXWjXkXkX)()()()()()(1111（4-21a） （4-21b） 式中，式中，m表示第表示第m列迭代，列迭代，k, j為數(shù)據(jù)所在行數(shù)。式（為數(shù)據(jù)所在行數(shù)。式（4-21）的）的蝶形運(yùn)算蝶形運(yùn)算如圖如

27、圖4-7所示，由一次復(fù)乘和兩次復(fù)加（減）組成。所示，由一次復(fù)乘和兩次復(fù)加（減）組成。 第4章 快速傅里葉變換(FFT) 圖圖 4-7 按時(shí)間抽選的蝶形運(yùn)算結(jié)構(gòu)按時(shí)間抽選的蝶形運(yùn)算結(jié)構(gòu)1rNWXm1(k)Xm1( j)Xm(k) Xm1(k) Xm1( j)Xm( j) Xm1(k) Xm1( j)rNWrNW 在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)在某列進(jìn)行蝶形運(yùn)算的任意兩個(gè)節(jié)點(diǎn)(行行)k和和j的節(jié)點(diǎn)變的節(jié)點(diǎn)變量量 ，就完全可以確定蝶形運(yùn)算的結(jié)果，就完全可以確定蝶形運(yùn)算的結(jié)果 與其它行與其它行(節(jié)點(diǎn)節(jié)點(diǎn))無關(guān)。這樣無關(guān)。這樣, 蝶形運(yùn)算的兩個(gè)輸出值仍可放蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入

28、所在的存儲(chǔ)器中回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,即實(shí)現(xiàn)所謂原位運(yùn)即實(shí)現(xiàn)所謂原位運(yùn)算。每一組算。每一組(列列)有有N/2個(gè)蝶形運(yùn)算個(gè)蝶形運(yùn)算, 所以只需所以只需N個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，可以節(jié)省存儲(chǔ)單元?？梢怨?jié)省存儲(chǔ)單元。11( ),( )mmXkXj( ),( )mmXkXj第4章 快速傅里葉變換(FFT) 由由圖圖4-5的流圖看出，某一列的任何兩個(gè)節(jié)點(diǎn)的流圖看出，某一列的任何兩個(gè)節(jié)點(diǎn)k和和j的節(jié)點(diǎn)變的節(jié)點(diǎn)變量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為下一列量進(jìn)行蝶形運(yùn)算后，得到結(jié)果為下一列k, j兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，兩節(jié)點(diǎn)的節(jié)點(diǎn)變量，而和其他節(jié)點(diǎn)變量無關(guān)，因而可以采用原位運(yùn)算，即某一列的而和其他節(jié)點(diǎn)變量無關(guān)

29、，因而可以采用原位運(yùn)算，即某一列的N個(gè)數(shù)據(jù)送到存儲(chǔ)器后，經(jīng)蝶形運(yùn)算，其結(jié)果為下一列數(shù)據(jù)，它們個(gè)數(shù)據(jù)送到存儲(chǔ)器后，經(jīng)蝶形運(yùn)算，其結(jié)果為下一列數(shù)據(jù)，它們以蝶形為單位仍存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間以蝶形為單位仍存儲(chǔ)在這同一組存儲(chǔ)器中，直到最后輸出，中間無需其他存儲(chǔ)器。也就是蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸無需其他存儲(chǔ)器。也就是蝶形的兩個(gè)輸出值仍放回蝶形的兩個(gè)輸入所在的存儲(chǔ)器中。每列的入所在的存儲(chǔ)器中。每列的N/2 個(gè)蝶形運(yùn)算全部完成后，再開始個(gè)蝶形運(yùn)算全部完成后，再開始下一列的蝶形運(yùn)算。這樣存儲(chǔ)器數(shù)據(jù)只需下一列的蝶形運(yùn)算。這樣存儲(chǔ)器數(shù)據(jù)只需N個(gè)存儲(chǔ)單元。下一級個(gè)存儲(chǔ)單元。下一級的運(yùn)算

30、仍采用這種原位方式，只不過進(jìn)入蝶形結(jié)的組合關(guān)系有所的運(yùn)算仍采用這種原位方式，只不過進(jìn)入蝶形結(jié)的組合關(guān)系有所不同。不同。 這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。這種原位運(yùn)算結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。 第4章 快速傅里葉變換(FFT) 2. 倒位序規(guī)律倒位序規(guī)律 由由圖圖4-5的流圖看出，按原位計(jì)算時(shí)，的流圖看出，按原位計(jì)算時(shí)，F(xiàn)FT的輸出的輸出X(k)按正常順序排列在存儲(chǔ)單元中，即按按正常順序排列在存儲(chǔ)單元中，即按X(0)，X(1)，X(7)的順序排列，但是這時(shí)輸入的順序排列，但是這時(shí)輸入x(n)卻不是按卻不是按自然順序存儲(chǔ)的，而是按自然順序存儲(chǔ)的，而是按x(0)，x(4)，

31、 ， x(7)的順序的順序存入存儲(chǔ)單元，看起來好像是存入存儲(chǔ)單元，看起來好像是“混亂無序混亂無序”的，實(shí)際上的，實(shí)際上是有規(guī)律的，稱之為倒位序。是有規(guī)律的，稱之為倒位序。 這是由奇偶分組造成的這是由奇偶分組造成的,以以N=8為例為例 說明如下說明如下:第4章 快速傅里葉變換(FFT) 造成倒位序的原因是輸入造成倒位序的原因是輸入x(n)按標(biāo)號按標(biāo)號n的偶奇的不斷分組。的偶奇的不斷分組。 如果如果n用二進(jìn)制數(shù)表示為用二進(jìn)制數(shù)表示為(n2n1n0)2（當(dāng)（當(dāng)N=8=23時(shí)，二進(jìn)制為三時(shí)，二進(jìn)制為三位），位）， 第一次分組，由第一次分組，由圖圖4-2看出，看出，n為偶數(shù)（相當(dāng)于為偶數(shù)（相當(dāng)于n的二進(jìn)

32、制的二進(jìn)制數(shù)的最低位數(shù)的最低位n0=0）在上半部分，）在上半部分，n為奇數(shù)（相當(dāng)于為奇數(shù)（相當(dāng)于n的二進(jìn)制數(shù)的二進(jìn)制數(shù)的最低位的最低位 n0=1）在下半部分。）在下半部分。 下一次則根據(jù)次最低位下一次則根據(jù)次最低位n1為為“0”或是或是“1”來分偶奇（而不管原來的子序列是偶序列還是奇序來分偶奇（而不管原來的子序列是偶序列還是奇序列），列）， 如此繼續(xù)分下去，直到最后分成如此繼續(xù)分下去，直到最后分成N個(gè)長度為個(gè)長度為1的子序列。的子序列。 圖圖4-8的樹狀圖描述了這種分成偶數(shù)子序列和奇數(shù)子序列的過程。的樹狀圖描述了這種分成偶數(shù)子序列和奇數(shù)子序列的過程。 第4章 快速傅里葉變換(FFT) 圖圖4-

33、8 描述倒位序的樹狀圖描述倒位序的樹狀圖 x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n0第4章 快速傅里葉變換(FFT) 3.倒位序?qū)崿F(xiàn)倒位序?qū)崿F(xiàn) 輸入序列先按自然順序存入存儲(chǔ)單元輸入序列先按自然順序存入存儲(chǔ)單元,然后經(jīng)變址運(yùn)算來然后經(jīng)變址運(yùn)算來實(shí)現(xiàn)實(shí)現(xiàn)倒位序排列倒位序排列。 設(shè)輸入設(shè)輸入序列的序號為序列的序號為n, 二進(jìn)制為二進(jìn)制為(n2 n1 n0 )2 , 倒位序倒位序順序用順序用 表示表示,其其倒位序倒位序二進(jìn)制為二進(jìn)制為(n0 n1 n2 )2 , 例如例如 ，N=8時(shí)如下表：

34、時(shí)如下表：表表4-2 碼位的倒位序（碼位的倒位序（N=8）自然順序（n） 二進(jìn)制數(shù) 倒位序二進(jìn)制數(shù) 倒位序順序（） 0123456700000101001110010111011100010001011000110101111104261537第4章 快速傅里葉變換(FFT) 圖圖 4-9 倒位序的變址處理倒位序的變址處理 (N=8)存儲(chǔ)單元自然順序輸入變址倒位序A(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章 快速傅里葉

35、變換(FFT) 4. 蝶形運(yùn)算兩節(jié)點(diǎn)的蝶形運(yùn)算兩節(jié)點(diǎn)的“距離距離” 以以圖圖4-5的的8點(diǎn)點(diǎn)FFT為例，其輸入是倒位序的，輸為例，其輸入是倒位序的，輸出是自然順序的。出是自然順序的。 其第一級（第一列）每個(gè)蝶形的兩其第一級（第一列）每個(gè)蝶形的兩節(jié)點(diǎn)間節(jié)點(diǎn)間“距離距離”為為1， 第二級每個(gè)蝶形的兩節(jié)點(diǎn)第二級每個(gè)蝶形的兩節(jié)點(diǎn)“距距離離”為為2， 第三級每個(gè)蝶形的兩節(jié)點(diǎn)第三級每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為為4。 由此類推得，對由此類推得，對N=2L點(diǎn)點(diǎn)FFT，當(dāng)輸入為倒位序，當(dāng)輸入為倒位序， 輸輸出為正常順序時(shí)，其第出為正常順序時(shí)，其第m級運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)級運(yùn)算，每個(gè)蝶形的兩節(jié)點(diǎn)“距離距離”為

36、為2m-1。 第4章 快速傅里葉變換(FFT) 5. WNr的確定的確定 由于對第由于對第m級運(yùn)算，一個(gè)級運(yùn)算，一個(gè)DFT蝶形運(yùn)算的兩節(jié)點(diǎn)蝶形運(yùn)算的兩節(jié)點(diǎn)“距距離離”為為2m-1， 因而式（因而式（4-21）可寫成）可寫成: rNmmmmmrNmmmmWkXkXkXWkXkXkX)2()()2()2()()(1111111（4-22a） （4-22b） 為了完成上兩式運(yùn)算，還必須知道系數(shù)為了完成上兩式運(yùn)算，還必須知道系數(shù)Nr的變的變換規(guī)律：換規(guī)律： 把式（把式（4-22）中蝶形運(yùn)算兩節(jié)點(diǎn)中的第一個(gè)節(jié)點(diǎn)）中蝶形運(yùn)算兩節(jié)點(diǎn)中的第一個(gè)節(jié)點(diǎn)標(biāo)號值，即標(biāo)號值，即k值表示成值表示成L位（注意位（注意N=2

37、L）二進(jìn)制數(shù)；）二進(jìn)制數(shù)； 第4章 快速傅里葉變換(FFT) 把此二進(jìn)制數(shù)乘上把此二進(jìn)制數(shù)乘上2L-m，即將此，即將此L位二進(jìn)制數(shù)左移位二進(jìn)制數(shù)左移L-m位（注意位（注意m是第是第m級運(yùn)算），把右邊空出的位置補(bǔ)零，級運(yùn)算），把右邊空出的位置補(bǔ)零， 此數(shù)即為所求此數(shù)即為所求r的二進(jìn)制數(shù)。的二進(jìn)制數(shù)。 從從圖圖4-5看出，看出，WNr因子最后一列有因子最后一列有N/2種，順序種，順序?yàn)闉?， 其余可類推。其余可類推。 (1)012,NNNNWWW 6.存儲(chǔ)單元存儲(chǔ)單元 存輸入序列存輸入序列 需需N個(gè)存儲(chǔ)單元，存?zhèn)€存儲(chǔ)單元，存放系數(shù)放系數(shù) 需需N/2個(gè)存儲(chǔ)單元；個(gè)存儲(chǔ)單元； 共計(jì)需共計(jì)需 個(gè)存儲(chǔ)單元

38、。個(gè)存儲(chǔ)單元。( )(0,1, ,-1)x n nN(r=0,1, ,N/2 - 1)rNW32N第4章 快速傅里葉變換(FFT) 四、四、 按時(shí)間抽取的按時(shí)間抽取的FFT算法的其他形式流圖算法的其他形式流圖 對于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸系對于任何流圖，只要保持各節(jié)點(diǎn)所連的支路及傳輸系數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，數(shù)不變，則不論節(jié)點(diǎn)位置怎么排列所得流圖總是等效的，所得最后結(jié)果都是所得最后結(jié)果都是x(n)的的DFT的正確結(jié)果，只是數(shù)據(jù)的提的正確結(jié)果，只是數(shù)據(jù)的提取和存放的次序不同而已。這樣就可得到按時(shí)間抽取的取和存放的次序不同而已。這樣就可得到按時(shí)間抽取的FF

39、T算法的若干其他形式流圖。算法的若干其他形式流圖。 將將圖圖4-5中和中和x(4)水平相連的所有節(jié)點(diǎn)和水平相連的所有節(jié)點(diǎn)和x(1)水平相連水平相連的所有節(jié)點(diǎn)位置對調(diào)，再將和的所有節(jié)點(diǎn)位置對調(diào)，再將和x(6)水平相連的所有節(jié)點(diǎn)與水平相連的所有節(jié)點(diǎn)與和和x(3)水平相連的所有節(jié)點(diǎn)對調(diào)，其余諸節(jié)點(diǎn)保持不變，水平相連的所有節(jié)點(diǎn)對調(diào)，其余諸節(jié)點(diǎn)保持不變，可得圖可得圖4-10的流圖。的流圖。圖圖4-10與圖與圖4-5的蝶形相同，運(yùn)算量也的蝶形相同，運(yùn)算量也一樣，不同點(diǎn)是：一樣，不同點(diǎn)是： 第4章 快速傅里葉變換(FFT) 數(shù)據(jù)存放的方式不同，圖數(shù)據(jù)存放的方式不同，圖4-5是輸入倒位序、輸出自是輸入倒位序、

40、輸出自然順序，圖然順序，圖4-10是輸入自然順序、輸出倒位序；是輸入自然順序、輸出倒位序；3210,NNNNWWWW,20NNWW3120,NNNNWWWW取用系數(shù)的順序不同，圖取用系數(shù)的順序不同，圖4-5的最后一列是按的最后一列是按 的順序取用系數(shù)，且其前一列所用系的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)中具有偶數(shù)冪的那些系數(shù)（例如數(shù)是后一列所用系數(shù)中具有偶數(shù)冪的那些系數(shù)（例如）；圖）；圖4-10是最后一列是按是最后一列是按的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用的順序取用系數(shù)，且其前一列所用系數(shù)是后一列所用系數(shù)的前一半。系數(shù)的前一半。 經(jīng)過簡單變換，也可得輸入與輸出都是按自

41、然經(jīng)過簡單變換，也可得輸入與輸出都是按自然順序排列的流圖以及其他各種形式的流圖順序排列的流圖以及其他各種形式的流圖 。第4章 快速傅里葉變換(FFT) 圖圖 4-10 時(shí)間抽取、時(shí)間抽取、 輸入自然順序、輸入自然順序、 輸出倒位序的輸出倒位序的FFT流圖流圖 0NW0NW0NW2NW1110NW10NW2NW1111X(0)x(0)X(4)x(1)X(2)x(2)X(6)x(3)X(1)x(4)X(5)x(5)X(3)x(6)X(7)x(7)110NW0NW2NW1NW3NW11第4章 快速傅里葉變換(FFT) 4.4 按頻率抽?。ò搭l率抽取（DIF）的基）的基 -2 FFT算法（桑德算法（桑

42、德-圖基算法）圖基算法） 一、一、 算法原理算法原理 仍設(shè)序列點(diǎn)數(shù)為仍設(shè)序列點(diǎn)數(shù)為N=2L，L為正整數(shù)。在把輸出為正整數(shù)。在把輸出X(k)按按k的奇偶分組之前，先把輸入序列按前一半、后一半分開的奇偶分組之前，先把輸入序列按前一半、后一半分開（不是按偶數(shù)、（不是按偶數(shù)、 奇數(shù)分開），奇數(shù)分開）， 把把N點(diǎn)點(diǎn)DFT寫成兩部分。寫成兩部分。 1112002112220012/20( )( )( )( )( )2( )2NNNnknknkNNNNnnnNNNnknkNNnnNNknkNNnX kx n Wx n Wx n WNx n Wx nWNx nx nWWk=0, 1, , N-1 第4章 快速

43、傅里葉變換(FFT) 由于由于 ，故，故 ，可得，可得21NNW kNkNW) 1(2/nkNNnkWNnxnxkX1202) 1()()( k=0, 1, , N-1 當(dāng)當(dāng)k為偶數(shù)時(shí)，為偶數(shù)時(shí)，(-1)k=1；k為奇數(shù)時(shí)，為奇數(shù)時(shí)，(-1)k=-1。因此，按。因此，按k的奇偶可將的奇偶可將X(k)分為兩部分分為兩部分: nrNNnnkNNnWNnxnxWNnxnxrX2/12021202)(2)()2(12, 1 , 0Nr為前一半輸入與后一半輸入之和的為前一半輸入與后一半輸入之和的N/2點(diǎn)點(diǎn)DFT第4章 快速傅里葉變換(FFT) nrNNnnNrnNNnWWNnxnxWNnxnxrX2/1

44、20)12(1202)(2)() 12(12, 1 , 0Nr為前一半輸入與后一半輸入之差再與為前一半輸入與后一半輸入之差再與WNn之積的之積的N/2點(diǎn)點(diǎn)DFT.nNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr令：令：第4章 快速傅里葉變換(FFT) 圖圖 4-14 按頻率抽取蝶形運(yùn)算流圖符號按頻率抽取蝶形運(yùn)算流圖符號 1x(n)x(n N / 2)nNWx(n) x(n N / 2)x(n) x(n N / 2)nNWnNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr第4章 快速傅里葉變換(FFT) 這樣可把一個(gè)這樣可把一個(gè)N點(diǎn)點(diǎn)

45、DFT按按k的奇偶分解為兩個(gè)的奇偶分解為兩個(gè)N/2點(diǎn)的點(diǎn)的DFT。 N=8時(shí)，上述分解過程示于圖時(shí)，上述分解過程示于圖4-15。 圖圖 4-15 按頻率抽取，將按頻率抽取，將N點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)點(diǎn)DFT的組合的組合 X(0)X(2)110NWDFT2點(diǎn)NX(4)X(6)X(1)X(3)DFT2點(diǎn)NX(5)X(7)1NW2NW3NW11x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第4章 快速傅里葉變換(FFT) 由于由于N=2L，N/2仍是一個(gè)偶數(shù)，因而可以將每個(gè)仍是一個(gè)偶數(shù)，因而可以將每個(gè)N/2點(diǎn)點(diǎn)DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將的輸出再分解為

46、偶數(shù)組與奇數(shù)組，這就將N/2點(diǎn)點(diǎn)DFT進(jìn)一步分解為兩個(gè)進(jìn)一步分解為兩個(gè)N/4 點(diǎn)點(diǎn)DFT。 圖圖4-16示出了這示出了這一步分解的過程。一步分解的過程。 這樣的分解可以一直進(jìn)行到第這樣的分解可以一直進(jìn)行到第L次（次（N=2L），第），第L次實(shí)際上是做兩點(diǎn)次實(shí)際上是做兩點(diǎn)DFT，它只有加減運(yùn)算。，它只有加減運(yùn)算。 然而，為然而，為了有統(tǒng)一的運(yùn)算結(jié)構(gòu)，仍然用一個(gè)系數(shù)為了有統(tǒng)一的運(yùn)算結(jié)構(gòu)，仍然用一個(gè)系數(shù)為WN0的蝶形運(yùn)的蝶形運(yùn)算來表示，這算來表示，這N/2個(gè)兩點(diǎn)個(gè)兩點(diǎn)DFT的的N個(gè)輸出就是個(gè)輸出就是x(n)的的N點(diǎn)點(diǎn)DFT的結(jié)果的結(jié)果X(k)。圖圖4-17表示一個(gè)表示一個(gè)N=8 完整的按頻率抽完整的按頻率抽取的基取的基-2 FFT運(yùn)算結(jié)構(gòu)。運(yùn)算結(jié)構(gòu)。 第4章 快速傅里葉變換(FFT) 圖圖 4-16 按頻率抽取的第二次分解按頻率抽取的第二次分解 DFT4點(diǎn)N110NW2NWx(0)x(1)x(2)x(3)11x(4)x(5)x(6)x(7)0NW1NW2NW3NWDFT4點(diǎn)NDFT4點(diǎn)NDFT4點(diǎn)NX(0)X(4)X(2)X(6)X(1)X(5)X(3)X