快速傅里葉變換

快速傅里葉變換快速傅里葉變換（FFT）是根據(jù)計(jì)算量的最小化原理來設(shè)計(jì)和實(shí)施離散傅里葉變換(DFT)計(jì)算的方法。1965年，庫利（T.W.Cooley）和圖基（J.W.tukey）發(fā)表了著名的《計(jì)算機(jī)計(jì)算傅里葉級(jí)數(shù)的一種算法》論文。從此掀起了快速傅里葉變換計(jì)算方法研究的熱潮。快速傅里葉變換（FFT）的出現(xiàn)，實(shí)現(xiàn)了快速、高效的信號(hào)分析和信號(hào)處理，為離散傅里葉變換(DFT)的廣泛應(yīng)用奠定了基礎(chǔ)。1.1離散傅里葉變換(DFT)的計(jì)算設(shè)x(n)是一個(gè)長度為M的有限長序列，則定義x(n)的N點(diǎn)離散傅里葉變換為其中由于計(jì)算一個(gè)X(k)值需要N次復(fù)乘法和(N-1)次復(fù)數(shù)加法，因而計(jì)算N個(gè)X(k)值，共需N2次復(fù)乘法和N(N-1)次復(fù)加法。每次復(fù)乘法包括4次實(shí)數(shù)乘法和2次實(shí)數(shù)加法，每次復(fù)加法包括2次實(shí)數(shù)加法，因此計(jì)算N點(diǎn)的DFT共需要4N2次實(shí)數(shù)乘法和(2N2+2N·(N-1))次實(shí)數(shù)加法。當(dāng)N很大時(shí)，這是一個(gè)非常大的計(jì)算量。1.2減少DFT計(jì)算量的方法減少DFT的計(jì)算量的主要途徑是利用的性質(zhì)和計(jì)算表達(dá)式的組合使用，其本質(zhì)是減少DFT計(jì)算的點(diǎn)數(shù)N以便減少DFT的計(jì)算量。的性質(zhì)：（1）對(duì)稱性：(2)周期性：(3)可約性：(4)特殊點(diǎn)：選擇其中一個(gè)證明FFT算法是基于可以將一個(gè)長度為N的序列的離散傅里葉變換逐次分解為較短的離散傅里葉變換來計(jì)算這一基本原理的。這一原理產(chǎn)生了許多不同的算法，但它們?cè)谟?jì)算速度上均取得了大致相當(dāng)?shù)母纳?。在這里討論兩類基本的FFT算法。第一類稱為按時(shí)間抽取(Decimation-in-Time)的基2FFT算法第二類稱為按頻率抽取(Decimation-in-Frequency)的基2FFT算法2.1按時(shí)間抽選(DIT)的基-2FFT算法(庫利·圖基算法)這種算法簡稱為時(shí)間抽選FFT算法，其基本出發(fā)點(diǎn)是，利用旋轉(zhuǎn)因子WNk的對(duì)稱性和周期性，將一個(gè)大的DFT分解成一些逐次變小的DFT來計(jì)算。分解過程遵循兩條規(guī)則：①對(duì)時(shí)間進(jìn)行偶奇分解；②對(duì)頻率進(jìn)行前后分解。設(shè)N＝2M，M為正整數(shù)。為了推導(dǎo)方便，取N＝23＝8，即離散時(shí)間信號(hào)為先按n的奇偶分成以下兩組：分別表示為：利用系數(shù)的可約性：上式中的G(k)和H(k)都是N/2點(diǎn)的DFT。有N點(diǎn)．而用上式計(jì)算得到的只是的前一半項(xiàng)數(shù)的結(jié)果，要得到全部的值，還必須應(yīng)用系數(shù)的周期性因?yàn)樗杂缮厦娴墓娇梢缘玫较旅娴男盘?hào)流程圖：前面把原來N點(diǎn)DFT的計(jì)算分解成兩個(gè)N/2點(diǎn)DFT的計(jì)算。照此可進(jìn)一步把每個(gè)N/2點(diǎn)DFT的計(jì)算再各分解成兩個(gè)N/4點(diǎn)DFT的計(jì)算。具體說來，是把{x(0)，x(2)，x(4)，x(6)}和{x(1)，x(3)，x(5)，x(7)}分為{x(0)，x(4)|x(2)，x(6)}和{x(1)，x(5)|x(3)，x(7)}。這樣，原信號(hào)序列被分成{x(0)，x(4)|x(2)，x(6)Ix(1)，x(5)Ix(3)，x(7)}4個(gè)2項(xiàng)信號(hào)。G(k)和H(k)分別計(jì)算如下:因?yàn)镹=8，所以N/4點(diǎn)的DFT就是2點(diǎn)的DFT，不能再分解了。將2點(diǎn)DFT的信號(hào)流程圖移入上圖，得到如圖所示的8點(diǎn)時(shí)間抽選的完整的FFT流程圖。2.2運(yùn)算量分析：如圖所示蝶形的一般形式表示為：其輸入和輸出之間滿足下列關(guān)系：從上式可以看出完成一個(gè)蝶形計(jì)算需一次復(fù)數(shù)乘法和兩次復(fù)數(shù)加法。由按時(shí)間抽選法FFT的流圖可見，共有M級(jí)蝶形，每級(jí)都由N/2個(gè)蝶形運(yùn)算組成，因此總的運(yùn)算量為：大多數(shù)情況下復(fù)數(shù)乘法所花的時(shí)間最多，因此下面僅以復(fù)數(shù)乘法的計(jì)算次數(shù)為例來與直接計(jì)算進(jìn)行比較。直接計(jì)算DFT需要的乘法次數(shù)為αD=N2，于是有例如，當(dāng)N=1024時(shí)，則：205，即直接計(jì)算DFT所需復(fù)數(shù)乘法次數(shù)約為FFT的205倍。顯然，N越大，F(xiàn)FT的速度優(yōu)勢越大。下表列出了不同N值所對(duì)應(yīng)的兩種計(jì)算方法的復(fù)數(shù)乘法次數(shù)和它們的比值。1頻率抽選基2FFT算法頻率抽選基2FFT算法簡稱為頻率抽選，它的推導(dǎo)過程遵循兩個(gè)規(guī)則：①對(duì)時(shí)間前后分；②對(duì)頻率偶奇分。

設(shè)N＝2M，M為正整數(shù)。為推導(dǎo)方便，取N=23＝8。首先，根據(jù)規(guī)則(1)，將x(n)分成前一半和后一半，即x(n)＝{x(0),x(1),x(2),x(3),Ix(4),x(5),x(6),x(7)}這樣雖然包含兩個(gè)N/2點(diǎn)求和公式，但是在每個(gè)求和公式中出現(xiàn)的是WNkn，而不是WN/2kn，因此這兩個(gè)求和公式都不是N/2點(diǎn)的DFT。如果合并這兩個(gè)求和公式，并利用則得：其次，按規(guī)則(2)，將頻率偶奇分，即X(k)={X(0),X(2),X(4),X(6),|X(1),X(3),X(5),X(7)}。如果用X(2r)和X(2r+1)分別表示頻率的偶數(shù)項(xiàng)和奇數(shù)項(xiàng)，則有令得上面兩式所表示的是N/2的DFT。在實(shí)際計(jì)算中，首先形成序列g(shù)(n)和h(n)，然后計(jì)算h(n)WNn，最后分別計(jì)算g(n)和h(n)WNn的N/2點(diǎn)DFT，便得到偶數(shù)輸出點(diǎn)和奇數(shù)輸出點(diǎn)的DFT。計(jì)算流程圖如圖所示。由于N是2的整數(shù)冪，所以N/2仍然是偶數(shù)。這樣，可以將N/2點(diǎn)DFT的輸出再分為偶數(shù)組和奇數(shù)組，也就是將N/2點(diǎn)的DFT計(jì)算進(jìn)一步分解為兩個(gè)N/4點(diǎn)的DFT計(jì)算，其推導(dǎo)過程如下。將g(n)分為前后兩組，得到因?yàn)樗詫?duì)頻率再進(jìn)行偶奇分，則得頻率的偶數(shù)項(xiàng)為頻率的奇數(shù)項(xiàng)為通過類似的推導(dǎo)可得上面4式所表示的計(jì)算都是N/4點(diǎn)的DFT計(jì)算，從而得到下圖所示的形式。將2點(diǎn)DFT的信號(hào)流程圖移入上圖，得到如圖所示的8點(diǎn)頻率抽選的完整的FFT流程圖。3.2運(yùn)算量分析