今天的低功耗微控制器(μC)也开始集成原先只存在于大型微处理器、ASIC和DSP中的外设功能，使我们有可能以很低的功耗实现复杂的算术运算。本文讨论一种快速傅立叶变换(FFT)应用，并在一个含有单周期硬件乘法器的低功耗μC上实现该应用。
这个FFT应用实时计算一路输入电压(图1中的VIN)的频谱。为完成该任务，用一片模数转换器(ADC)对VIN进行采样，获得的采样传送给μC。然后，μC对这些采样执行256点FFT运算，获得输入电压的频谱。为便于检测，μC将计算出的频谱数据传送给PC，由PC实时显示出来。
图1. 利用FFT应用计算输入电压的频谱。
该FFT应用的固件针对MAXQ2000系列中的一款16位、低功耗μC用C语言编写。有兴趣的读者可以下载(ZIP，2.4kb)该项目的固件和电路原理图。
背景知识
为确定输入信号采样的频谱，我们需要对这些输入采样进行离散傅立叶变换(DFT)。DFT的定义如下：
其中N是采样的数量，X(k)是频谱，x(n)是一组输入采样。利用欧拉等式展开求和符，并分离输入采样和频谱的实部和虚部，得到以下等式：
式2和3中，求和符中第二项的消失是由于输入采样全部为实数。假定我们有N个采样，直接计算式2和3需要2N2次乘法和2N(N - 1)次加法。这样，我们的256点输入采样DFT将需要进行131,072次乘法和130,560次加法运算。我们还是将注意力转向FFT吧！
有多种FFT算法可供使用。本应用采用普通的radix-2算法，继续将DFT分解为两个更小的DFT。为此，N必须是2的指数。这种radix-2 FFT算法的步骤可归纳如图2所示的蝶型运算。观察这些蝶型运算我们可以发现，radix-2算法仅需(N / 2)log2(N)次乘法和Nlog2(N)次加法。图2中用到的参数WN就是通常所谓的“旋转因子”，可以在执行算法前预先计算出来。
图2. 利用蝶型运算实现N = 8的FFT。