4．1 倒位序及其优化算法
    基2-FTT算法将原始数据倒位序存储，但运算后的结果则按正常顺序输出。原始采样数据放在数组float datalm[16]中，datalm[0]存放第1次读取的A／D转换值，datalm[1]存放第2次读取的A／D转换值，以此类推，可见第n(n=(b3b2b1b0)b)次读取的A／D转换值存放在dataIm[n]中。倒序操作后采样数据存储在float dataRe[16]中，原来第n次读取的A／D转换值存放在datalm[n](n=(b0b1b2b3)b)中。根据样本大小在系统代码段中建立倒序表数组，采用查表方式实现快速倒序操作，与移位操作等方法相比，可明显提高运算速度。
4．2 蝶形运算及其优化算法
    根据基2-FFT算法，N点FFT运算可以分成log2N级，每一级都有N/2个蝶形运算，如图3所示。 

 

    蝶形运算公式的推导过程如下：

    将式(1)化简成实部和虚部的形式，得到：

    可见每个蝶形运算的输出都是由其输入值与某一正弦函数和余弦函数的乘积累加得到的。由式(3)~式(6)编制正弦和余弦表，每次做蝶形运算时可查表加快运算速度。
    基2-FFT算法的基本思想是用3层循环完成全部N点FFT运算：(1)最里层循环处理单独的一个蝶形运算，采用查表方法实现乘法运算；(2)中间层循环完成每一级的N／2个蝶形运算；(3)最外层循环完成log2N级蝶形运算。
    由此可看出：在每一级中，最里层循环完成N／2L个蝶形运算；中间层循环控制最里层循环进行2L-1次运算。因此，中间层循环完成时，共进行2L-1xN／2L=N／2个蝶形运算。实际上最里层和中间层循环完成了第L级计算，最外层则最终完成log2N级蝶形运算。
    需要加以说明的数据是：(1)在第L级中，每个蝶形的两个输入端相距b=2L-1一个点；(2)同一乘数对应着相邻间隔为2L个点的N／2L个蝶形；(3)第L级的2L-1个蝶形因子WPN中的P，可表示为P=jx25-L，其中j=0，1，2，…(2L-1-1)。
    完成16点FFT运算的RAM需求量是128字节，而单片机SST89V58RD2的RAM共1 K字节：显示器每10 ms刷新一次，而单片机SST89V58RD2的时钟频率是40 MHz，完成一次16点FFT运算实际所需时间不到6 ms，因此该系统完全满足FFT运算的时间复杂度和空间复杂度要求。

5 频谱值在VFD上的显示
    系统要求将音频信号频谱划分成14段，每段按14级量化，再使用VFD显示器显示，因此对于FFT运算结果还要作一定转换才能输出到显示器。第n点的FFT运算结果是复数，实部是dataRe[n]，虚部是datalm[i]。该点的模值除以2／N就是对应该频率下信号的幅度(对于第1个点则是除以N)；该点的相位即是对应该频率下信号的相位。最后的结果保存在dataRe[i]中，因为音频信号频谱被划分成14段，所以dataRe[0]和dataRe[15]的值应该舍去。同时，dataRe[i]可能不是整数，而VFD显示器要求每个频段按照14级量化，因此还需将dataRe[i]的值量化成0～14整数，最后输出到VFD电路上显示。

6 结束语
    讨论了单片机实现音响系统频谱显示的快速傅里叶变换算法，针对SST89V58RD2单片机进行算法优化，并详细论述系统的实现方法，结果证明该方法具有可行性。