快速傅里葉變換的c++實現

郭鐵橋 張 磊

（華北電力大學能源動力與機械工程學院，河北 保定 071003）

引言

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

1 離散傅里葉變換的定義

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

對長度為 N的復數序列 A0,A1，AN-1稱

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

2 快速傅里葉變換

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

FFT算法有效地利用WkN=exp(2πik/N)的周期性。它具有運算量少，穩定性好和精確度高等優點。由于WjNN=1，j為整數Wk+lN=WkNWlN設 N 可表示為 N=r×s，r，s為整數(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)

這時

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

特別當r=2時，則復數運算總量為2Nlog2N當N充分大時，N2和2Nlog2N相比差別是很大的。比如當N=216=65536

即該算法的運算量只有N2的2048分之一，因此計算量的節約是巨大的。

3 基2的FFT算法c++程序實現

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

結論

本文主要介紹了實現FFT的c++算法的，本程序可以直接在vc6.0上運行現在代入八個點進行測試，把 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。結果正確。

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

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