郭铁桥 张 磊

（华北电力大学能源动力与机械工程学院，河北 保定 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.