1、快速傅里葉變換第1頁，共47頁，2022年，5月20日，10點21分，星期三1.引言FFT不是一種新算法,只是DFT的一種快速算法。 Cooley和Tukey在1965年發表的“機器計算傅里葉級數的一種算法” 桑德和圖基的快速算法的出現。 第2頁，共47頁，2022年，5月20日，10點21分，星期三2.直接計算DFT的問題及改進的途徑DFT和IDFT的變換公式二者的差別就在于WN的指數符號不同，以及相差一個常數乘因子1/N。每計算一個X(k)值，需要N次復數乘法，以及（N-1）次復數加法，而X(k)一共有N個值點，因此完成整個DFT運算總共需要N2次復數乘法，N（N-1）次復數加法。(4.1

2、) (4.2)第3頁，共47頁，2022年，5月20日，10點21分，星期三復數運算實際上是由實數運算來完成的，因此(4.1)式可寫成可以看出，一次復數乘法需要4次實數乘法和2次實數加法，一次復數加法需要2次實數加法。因此，每計算一個X(k)值，需要4N次實數乘法，以及2N2（N-1）2（2N1）次實數加法，整個DFT運算總共需要4N2次實數乘法，2N（2N-1）次實數加法。 (4.3)第4頁，共47頁，2022年，5月20日，10點21分，星期三存在問題：直接計算DFT，乘法次數和加法次數都是和N2成正比。當N很大時，運算量很大，例如，N=8時，需要64次復乘，N1024時，需要104857

3、6次復乘。第5頁，共47頁，2022年，5月20日，10點21分，星期三減少DFT運算工作量的途徑：利用WNnk的固有特性。（1） WNnk的對稱性：（2） WNnk的周期性：（3） WNnk的可約性：可以得出實際辦法：（1）用上述特性對項合并（2）將長序列的DFT分解為短序列的DFT，減小N值。第6頁，共47頁，2022年，5月20日，10點21分，星期三對稱性與周期性第7頁，共47頁，2022年，5月20日，10點21分，星期三四點的DFT進行化簡，得第8頁，共47頁，2022年，5月20日，10點21分，星期三將該矩陣的第二列和第三列交換，得由此得出第9頁，共47頁，2022年，5月20

4、日，10點21分，星期三 快速傅里葉變換正是基于這樣的思想發展進來的，主要分為兩大類：DIT：按時間抽選DIF：按頻率抽選第10頁，共47頁，2022年，5月20日，10點21分，星期三3.按時間抽選的基2FFT算法3.1算法原理先設序列點數為，按n的奇偶進行分解將DFT化為第11頁，共47頁，2022年，5月20日，10點21分，星期三利用系數的可約性，即得(4.5)(4.6)(4.7)第12頁，共47頁，2022年，5月20日，10點21分，星期三應用系數的周期性,可得再考慮性質把(4.8),(4.9),(4.10)代入(4.5)式，將X(k)表達成前后兩部分，前部分為后部分為(4.8)(

5、4.9)(4.10)(4.11)(4.12)第13頁，共47頁，2022年，5月20日，10點21分，星期三 這樣，4.11、12式只要0-(N/2-1)區間的所有X1(k)和X2(k)的值，即可求0到(N-1)區間所有X(k)值。4.11和4.12式用蝶形圖表示。第14頁，共47頁，2022年，5月20日，10點21分，星期三N8的情況如圖所示:第15頁，共47頁，2022年，5月20日，10點21分，星期三 分析：每個蝶形運算需要一次復數乘法及兩次復數加（減）法。通過分解后運算工作量差不多減少到一半。第16頁，共47頁，2022年，5月20日，10點21分，星期三進一步把N/2點子序列再按

6、奇偶部分分解為兩個N/4點的子序列且其中第17頁，共47頁，2022年，5月20日，10點21分，星期三圖43，給出N8時，在分解為兩個N/4點DFT，由兩個N/4點DFT組合成N/2點DFT的流圖。第18頁，共47頁，2022年，5月20日，10點21分，星期三X2(k)也可進行同樣分解：其中第19頁，共47頁，2022年，5月20日，10點21分，星期三一個N8點DFT就可分解為四個N/42點DFT如圖第20頁，共47頁，2022年，5月20日，10點21分，星期三序列按奇偶分解標號變化討論（N8）1、第一次分解：兩個N/2點序列：第21頁，共47頁，2022年，5月20日，10點21分，

7、星期三2、第二次分解，每個N/2點子序列按其奇偶分解為兩個N/4點子序列第22頁，共47頁，2022年，5月20日，10點21分，星期三3、最后是2點的DFT 對于例子N8，就是4個N/42點的DFT。 如： 其中這種方法的每一步分解都是按輸入序列在時間上的次序是屬于偶數還是屬于奇數來分解為兩個更短的子序列，所以稱為“按時間抽選法”。第23頁，共47頁，2022年，5月20日，10點21分，星期三3.2 運算量分析（1）直接DFT復數算法次數是N2（2）FFT復數乘法次數是（N/2）*L 當N=2L時，一共有L級蝶形，每級有N/2個蝶形運算組成，一個蝶形運算有1次復乘，2次復加運算。DFT和F

8、FT算法的計算量之比為結論：FFT比DFT更優越，當N越大時，優點更明顯。第24頁，共47頁，2022年，5月20日，10點21分，星期三第25頁，共47頁，2022年，5月20日，10點21分，星期三第26頁，共47頁，2022年，5月20日，10點21分，星期三3.3 按時間抽選的FFT算法特點1.原位運算 每個蝶形結構完成下述基本迭代運算： 4.21的蝶形運算如圖47所示。第27頁，共47頁，2022年，5月20日，10點21分，星期三 蝶形的兩個輸出值仍放回蝶形的兩個輸入值所在的存儲器中，中間不需要其他的存儲器。每列的N/2個蝶形運算完成后，再開始下一列的蝶形運算，這樣存儲數據就只要N

9、個存儲單元。 下一級的蝶形運算仍采取這樣的原位運算，只不過進入蝶形的組合關系有所不同。第28頁，共47頁，2022年，5月20日，10點21分，星期三2.倒位序規律第29頁，共47頁，2022年，5月20日，10點21分，星期三3.倒位序的實現：通過變址運算完成第30頁，共47頁，2022年，5月20日，10點21分，星期三4.存儲單元輸入序列N個單元系數N/2個單元第31頁，共47頁，2022年，5月20日，10點21分，星期三3.4按時間抽選的FFT算法的其它形式流程圖對于任何流圖，只要保持各節點所連的支路和傳輸系數不變，則不論節點怎么排列所得的流圖總是等效的，只是數據的提取和存放的次序不

10、同而已。因此就可以有按之間抽取的FFT算法的若干形式。第32頁，共47頁，2022年，5月20日，10點21分，星期三第33頁，共47頁，2022年，5月20日，10點21分，星期三第34頁，共47頁，2022年，5月20日，10點21分，星期三第35頁，共47頁，2022年，5月20日，10點21分，星期三第36頁，共47頁，2022年，5月20日，10點21分，星期三4.按頻率抽選（DIF）的基2FFT算法（桑德圖基算法）DIF算法是將輸出序列X（K）按其順序的奇偶分解為越來越短的序列。仍設序列的點數為N2L,L為整數。先將輸入序列按n的順序分為前后兩半。第37頁，共47頁，2022年，5

11、月20日，10點21分，星期三當k為偶數時，(-1)k=1;當k為偶數時，(-1)k=-1。因此按k的奇偶可將X(k)分為兩部分。第38頁，共47頁，2022年，5月20日，10點21分，星期三令則第39頁，共47頁，2022年，5月20日，10點21分，星期三令則第40頁，共47頁，2022年，5月20日，10點21分，星期三可以用蝶形運算來表示第41頁，共47頁，2022年，5月20日，10點21分，星期三N8時，按k分解結果如圖第42頁，共47頁，2022年，5月20日，10點21分，星期三5.離散傅里葉反變換IDFT的快速計算方法DFT和IDFT的變換公式比較可知，只要把DFT運算中的

12、每一個系數WNnk變成WN-nk ，最后再乘常數1/N，則以上所有按時間抽選或按頻率抽選的FFT都可以拿來運算IDFT。第43頁，共47頁，2022年，5月20日，10點21分，星期三上面的方法比較簡單，但是要稍微改動FFT的程序和參數才能實現，下面的方法不改變FFT的程序計算IFFT：對DFT的反變換公式取共軛只要先將X(k)取共軛，然后直接利用FFT子程序，最后將結果取共軛，并乘以1/N，就可以得到x(n)的值。第44頁，共47頁，2022年，5月20日，10點21分，星期三例：假設一次復乘的時間為1 s，而且假定一個DFT總共需要的時間由計算所有乘法所需的時間確定。1）直接計算一個1024點的DFT需要多少時間？2）計算基2FFT需要多少時間？解：1）tN2106s1.05s 2)基2FFT復乘的次數為(N/2)log2N=5120 t5120106s5.12ms第45頁，共47頁，2022年，5月20日，10點21分，星期三例：對一個連續時間信號xa(t)進行采樣，在1s內采集了4096個數據，1）若采樣后沒有產生頻譜混疊，則信號xa(t)的最高頻率時多少？2）若計算采樣信號的4096點的DFT，頻譜之間的頻率間隔是多少Hz