FFT在低功率微程序控制器中的应用

0 引言
在以前，外围设备是更大的微处理器如特定用途集成电路和DSP中的内存。现在，低微处理器包括了外围设备，这样就有机会在低功耗的情况下进行复杂的运算。本文介绍了在低的微处理器中执行快速傅里叶变换()，其中微处理器包括一周期的硬件乘法器。这个可以实时计算输入电压的频谱。
为了完成此任务，一个模数转换器对输入信号进行采样然后传输到微处理器。微处理器再对样本信号进行256点的，这样就获得输入电压的频谱。为了测试其有效性，微处理器计算频谱的幅值然后实时地传输给示波器。

1 背景
为了确定输入样本信号的频谱信息，需要计算输入样本的离散傅里叶变换(DFT)。离散傅里叶变换定义为：

式中：N是样本点数；X(k)是频谱，与x(n)代表输入样本。利用欧拉方程的一致性将这个求和公式中的输入样本与频谱分离为它们的实部与虚部，可得以下方程式：

因为输入样本只是考虑实部。式(2)与式(3)中的求和公式的第二项消失了，假设有N个样本，直接计算式(2)、式(3)需要2N2次乘法及2N(N-1)次加法。因此256点输入样本的DFT将要求131072次乘法和130560次加法。
已经出现了很多种算法。普通的以基为2的算法连续将DFT分解成2个更小的DFT。为了使其变成可能，N必须分解为2的整数幂。转化为以2为基的FFT的步骤见图1的蝶形计算。从图1的蝶形计算中可观察到，获得基为2的FFT算法的解只需要(N／2)log2N次乘法与Nlog2N次加法。在图l中的值WH通常认为是旋转因子且能够在执行FFT前计算得到。

在图1中，FFT的输入具有特殊的形式。它是具有位倒置下标的原始顺序。因此，当计算基为2的N=8的FFT时，输入数据的记录顺序要求为O(000b)，1(001b)，…，0(000b)，4(100b)，…。
FFT是以正确的顺序作为输出。图1同样揭示了单一的蝶形计算的结果只是FFT的下一阶段的输入。因为计算是在适当的位置中完成的，旧值可以代替新获得值且在计算N点的FFT只是需要2N个变量样本(需要2N个变量是因为每一个变量值都有一个实部与虚部)。
当完成FFT时，结果是以复数为记法的。式(4)和式(5)将复数表示形式转变为以极坐标表示：

在DSP的文章里介绍了很多关于DFT／FFT的优化方法，使其计算速度更快且需要的计算量更少，其中一个比较重要的优化方法(也可能是最容易执行的)。
从观察DFT中可以获得，因为具有N点的实值信号的DFT是以X(N／2)为对称的，因此有：