快速傅里葉變換的c++實(shí)現(xiàn)

郭鐵橋 張 磊

（華北電力大學(xué)能源動(dòng)力與機(jī)械工程學(xué)院，河北 保定 071003）

引言

傅里葉變換是一種譜分析的方法，在數(shù)學(xué)與工程技術(shù)分析中有著廣泛的應(yīng)用。本文從傅里葉變換的原理介紹開始，然后介紹適合計(jì)算機(jī)上運(yùn)算的離散傅里葉變換即DFT（discrete Fourier transform），而由于普通離散傅里葉變換在計(jì)算機(jī)上進(jìn)行多點(diǎn)運(yùn)算時(shí)，運(yùn)算量過大，人們開始從算法中進(jìn)行研究，發(fā)明了效率更高的計(jì)算傅里葉變換的方法，即FFT（Fast Fourier transform），為了使讀者更好的理解FFt，本文給出了一個(gè)基2的N點(diǎn)FFt程序。

1 離散傅里葉變換的定義

我們的計(jì)算機(jī)只能處理離散的數(shù)據(jù)，在機(jī)械工程上數(shù)據(jù)采集卡采集來的數(shù)據(jù)也都是離散的，要對(duì)這些數(shù)據(jù)進(jìn)行分析就要用到離散的傅里葉變換，離散的傅里葉變換的定義如下：

對(duì)長度為 N的復(fù)數(shù)序列 A0,A1，AN-1稱

為序列{Ak}的離散傅里葉變換DFT（discrete Fourier transform）。離散傅里葉變換有時(shí)也稱為有限傅里葉變換。這里i=，WN=exp(2πi/N)。

2 快速傅里葉變換

顯然按由{Ak}按插值的方法求{xj}需要N 2次復(fù)數(shù)乘法運(yùn)算。由于一般情況下人們可以主動(dòng)選擇N使之滿足一定的條件，以此為基礎(chǔ)建立的快速傅里葉變換（Fast Fourier transform）FFt算法可以大大減少復(fù)數(shù)乘法的計(jì)算量。比如當(dāng)取N=2r時(shí)，N2=22r=4r，建立的FFt算法的復(fù)量運(yùn)算量為O(Nlog2N)=r2r。當(dāng)N很大時(shí)，運(yùn)算量的節(jié)省是顯著的。

FFT算法有效地利用WkN=exp(2πik/N)的周期性。它具有運(yùn)算量少，穩(wěn)定性好和精確度高等優(yōu)點(diǎn)。由于WjNN=1，j為整數(shù)Wk+lN=WkNWlN設(shè) N 可表示為 N=r×s，r，s為整數(shù)(2.1)

簡記 j=（j1，j0），其中 j=j1×r+j0j1=0，1，…s-1；j0=0，1，…r-1 (2.2)

簡記 k=（k0，k1），其中 k=k1×s+k0k1=0，1，…r-1，k0=0，1，…s-1(2.3)

這時(shí)

我們知道直接計(jì)算{xj}需要N2個(gè)復(fù)數(shù)運(yùn)算，若分兩步計(jì)算，在（2.6）中k0是固定的，可將WN-(j0k0+j0k1)看成一個(gè)復(fù)數(shù)完成（2.6）共需要r2s=Nr次復(fù)數(shù)運(yùn)算。從序列A1(j0,k0)計(jì)算序列 x(j1,j0)，即完成（2.7），共需要 r2s=Ns次復(fù)數(shù)運(yùn)算。故由{Ak}求{xj}共需N(r+s)次復(fù)數(shù)運(yùn)算。如果將N分解成N=r1r2…rm逐次重復(fù)上述過程可以看出共需要復(fù)數(shù)運(yùn)算為N(r1+r2+…+rm)若考慮 N=rm，ri=r，i=1,2，…m，則復(fù)數(shù)運(yùn)算總量為

特別當(dāng)r=2時(shí)，則復(fù)數(shù)運(yùn)算總量為2Nlog2N當(dāng)N充分大時(shí)，N2和2Nlog2N相比差別是很大的。比如當(dāng)N=216=65536

即該算法的運(yùn)算量只有N2的2048分之一，因此計(jì)算量的節(jié)約是巨大的。

3 基2的FFT算法c++程序?qū)崿F(xiàn)

基2的FFT的算法的講解在計(jì)算方法的書上有詳細(xì)的講解，這里不再累述。以下給出c++的完整程序，此程序在vc6.0中可以直接應(yīng)用。

結(jié)論

本文主要介紹了實(shí)現(xiàn)FFT的c++算法的，本程序可以直接在vc6.0上運(yùn)行現(xiàn)在代入八個(gè)點(diǎn)進(jìn)行測試，把 1，1+i，2+i，3+2i，1+2i,0,2,-1+i代入，得到9+7i，-2.1213+0.5355i，2，0.7071+5.9497i，1+i，2.1213-0.5355i，-4，-0.7071-3.9497i。結(jié)果正確。

[1]蔣長錦，蔣勇.快速傅里葉變換及c程序[M].合肥：中國科技大學(xué)出版社，2004.

[2]徐萃薇，孫繩武.計(jì)算方法引論[M].北京：高等教育出版社，2002.