电路板克隆51单片机的水表控制系统设计

    虽然在实现FFT方面已有很好的芯片来解决其运算速度及RAM容量的问题，但由于单片机的成本相对比较低。因此讨论在单片机中实现FFT算法具有现实意义。最后本文还给出了用单片机实现FFT在雷达检测中的应用。

    1 基数为2的FFT算法

    FFT的输出与DFT的输出是一致的，但冗余的计算在FFT中已被减去，使得其计算速度比较快。对于N-点的傅里叶变换，DFT需要的计算复杂度是N2，而FFT需要的计算复杂度是N/2log2N。因此当N比较大时，使用FFT做傅里叶变换将会大大减少计算量。比如做64点的DFT需要4096的计算复杂度，而使用FFT只需要192的计算复杂度。在单片机中，当使用别的优化方法时，FFT的计算需要更少的时间。

    在本文中，使用FFT时，我们关心的是如何减少为了存储中间数据所需要的临时内存空间。pcb抄板在执行FFT时，输入数据和输出数据将以比特倒序的方式存储。在顺序与倒序之间改变时，每一数据点与数据集里的另一数据点的位置相换是由将样本系列的顺序倒置决定的。例如，在16点的FFT变换，样本存储的地址是001 b将与存储在100 b位置上的样本互换。具有倒序字节的位置是和没有倒序字节的位置是相等的，比如0110 b是不互换位置的。计算FFT的顺序是由FFT的输入或输出是否需要以倒序保存决定的。

    2 对输入数据加窗

    FFT变换可以作用在具有有限时间长度的数据，但是对此数据集进行一个假设：就是周期的，且无限次重复。当样本数据以这种方式重复时，最后一个样本（下标[N-1]）是紧接着下一周期中的第一个样本（[0]）的。电路板克隆如图1所示，当数据在整个样本集中不是周期性的，则当对整个样本做FFT时会导致不连续性。正因为这样，数据在进行FFT变换前通常需要加窗。加窗使得样本集变成周期性且去掉在第一个样本与最后一个样本之间的不连续。由于加窗改变了输入数据，在频域上它将产生一些噪声。加窗会将信号的能量伸展到几个点上。能量分布会削弱信号的峰值。大部分信号的原始内容存储在主要部分里，当一部分发生旁瓣泄漏（如图2所示），主要部分的宽度和旁瓣的高度由应用在信号的加窗算法决定。一些窗函数及其性能如表1所示。为计算N点FFT的加窗函数的系数的一些方程如表2所示。更多关于加窗算法与他们的参数参见文献[2]。

    窗性能

    时域加窗

    加窗的影响

    3 FFT优化

    已经出现了很多优化FFT的方法。而这些优化方法的目的都是为了使得计算速度增快且尽可能的减少存储数据所需要的RAM。

    我们都知道，计算FFT的一个重要方法是蝶式方法。但是蝶式计算的每一次迭代都需要一个复杂的乘法（总共是四次的长整数乘法）。长整数乘法需要很多处理内存来完成。但是我们仔细观察会发现其中一些乘法是不需要的，并且是可以省去的。特别是，当乘数为零时，结果将为零和当乘数为1时，相乘的结果将不变。