傅里叶变换是一种将时域信号变换为频域信号的积分变换形式。在频域分析中，信号的频率及对应的幅值、相位（统称为频谱）反映了系统的性能。快速傅里叶变换（Fast Fou-rier Transform，FFT）是离散傅里叶变换（Discrete Fourier Transform，DFT）的快速实现方法，是数字信号处理（DSP）中的重要算法之一。

1.快速傅里叶变换的基本原理

非周期连续时间信号x（t）的傅里叶变换为

上式计算出来的是信号x（t）的连续频谱。实际系统中经常得到的是信号x（t）的离散采样值x（nT）（T为采样周期，n=0，1，…，N-1），简记为x（n）。N点采样值频谱取样的谱间距为

那么序列x（n）的离散傅里叶变换为

式中，X（k）是时间序列x（n）的频谱；W_N称为蝶形因子或旋转因子。对于N点时域采样值，经过离散傅里叶变换计算，可以得到N个频谱条。每计算一个X（k）值需要N次复数相乘和N-1次复数相加，对于N个X（k）应重复计算N次。离散傅里叶变换共需要计算N²次复数乘法和N（N-1）复数次加法，在N较大（例如N=1024）时，这个计算量很大，为此需要采用快速离散傅里叶变换。

序列x（n）按序号n的奇偶可以分成两组，即

x₁（n）=x（2n）

x₂（n）=x（2n+1），n=0，1，…，N/2-1

所以，x（n）的离散傅里叶变换可写为

由此可得(www.daowen.com)

X（k）=X₁（k）+W^k_NX₂（k），k=0，1，…，N/2-1 （15-19）

式中

X₁（k）和X₂（k）分别是x₁（n）和x₂（n）的N/2点DFT。上面的推导表明，一个N点的DFT可以分解为两个N/2点的DFT，而这两个N/2点的DFT又可以合成一个N点的DFT，但上面给出的公式仅能得到X（k）的前N/2点的值，要用X₁（k）和X₂（k）来表示X（k）的后半部分，还必须运用蝶形因子W_N的周期性与对称性，即

因此，X（k）的后N/2点可以表示为

由此可见，一个N点的DFT可以分解为两个N/2点的DFT，每个N/2点的DFT又可以分解为两个N/4点的DFT。依此类推，当N为2的整数次幂（N=2^M）时，由于每分解一次降低一次幂阶，所以通过M次分解，最后全部成为一系列2点DFT运算。这样计算量可以减为（N/2）log₂N个乘法运算和Nlog₂N个加法运算，比DFT的计算量大大减轻。以上就是按时间抽取的FFT算法。式（15-19）和（15-21）表示的运算称为蝶形运算。

2.FFT的实现

例15-1 时间抽取的FFT算法DSPC语言实现实例。

FFT运算函数与主函数为

由于上述代码中调用了pow、log、cos及sin函数，该函数所在的C文件应包含头文件math.h。调用FFT函数进行FFT运算时，需要提供的参数为FFT运算点数、时域序列的实部与虚部。另外，FFT函数包含的函数finv（N，Xr，Xi）为倒序运算，函数代码如下。

可以通过CCS软件调试该程序，并用其中的View＞Graph＞Time/Frequency菜单功能，显示变量INPUT与DATA图形，观察FFT的效果。