原创 嵌入式教程：4-7 快速傅立叶变换（FFT）算法（CCS显示）

了解FFT的作用，掌握FFT 算法的算法原理、计算量和算法特点，实现FFT算法并通过CCS图形窗口查看结果。

官方网站：www.tronlongtech.com

傅里叶变换可以将一个信号从时域变换到频域。时域信号在经过傅立叶变换的分解之后，变为了不同正弦波信号的叠加，我们再去分析这些正弦波的频率，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。

离散傅里叶变换作为信号处理中最基本和最常用的运算，在信号处理领域占有基础性的地位，如果直接按照离散傅里叶变换的公式进行计算，求出N点X(k)需要N^2次复数运算、N(N-1)次复数加法，当N很大时，运算量是非常大的，这对于实时处理是无法接受的。

傅里叶快速算法的提出，使傅里叶变换成为一种真正实用的算法。根据傅立叶变换的对称性和周期性，我们可以将DFT运算中有些项合并。 在计算机上进行的DFT，使用的输入值是时域的信号值，输入采样点的数量决定了转换的计算规模。变换后的频谱输出包含同样数量的采样点，但是其中有一半的值是冗余的，通常不会显示在频谱中，所以真正有用的信息是N/2+1个点。FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的，FFT的过程大大简化了在计算机中进行DFT的过程。

程序流程设计中首先产生测试信号，接着确定FFT基和旋转因子，然后进行FFT和FFT逆变换运算，最后输出FFT结果

本实验中的FFT算法是基于TI提供的数字信号处理库完成的。 DSPLIB 包含优化的、C语言可调用的通用信号处理例程，用于计算密集型实时应用程序。 调用这些例程的运行速度比直接用C语言编写的等效代码快得多，可以缩短应用程序开发时间。实验中使用的是 dsplib_c674x_3_4_0_0 。

在CCS5.5 的安装路径安装DSPLIB后，会有相应的文件夹出现，包含组件库、头文件、测试示例和源码等。

程序使用DSPLIB 的库来进行FFT运算，调用的程序源码和使用说明可以安装DSPLIB后 查看。

调用的FFT函数中：

第一个参数是样本中FFT 的长度；

第二个参数是指向数据输入的指针；

第三个参数是指向复杂旋转因子的指针；

第四个参数是指向复杂输出数据的指针；

第五个参数是指向包含64 个条目的位反转表的指针。如果样本的FFT长度可以表示为 4 的幂；

第六个参数是4，否则 第六个参数是 2 ；

第五个参数是从主FFT开始的样本中的子 FFT偏移索引 。；

第六个参数是样本中主FFT的大小。

程序使用DSPLIB 的库来进行FFT逆变换，调用的程序源码和使用说明可以安装DSPLIB后查看。

调用的IFFT函数中：

第一个参数是样本中FFT 的长度；

第二个参数是指向数据输入的指针；

第三个参数是指向复杂旋转因子的指针；

第四个参数是指向复杂输出数据的指针；

第五个参数是指向包含64 个条目的位反转表的指针 ；

如果样本的FFT长度可以表示为 4 的幂，第六个参数是4，否则第六个参数是2 ；

第七个参数是从主FFT开始的复杂样本中的子FFT偏移索引 ；

第八个参数是样本中主FFT的大小。

FFT和FFT 逆变换函数中的第五个参数brev是指向包含64个表项的位反转表的指针，因此程序中需要提供64个表项，程序中的位反向表是计算出来的，可以通过代码提前转换的。 采用位反转的原因是因为FFT算法的蝶形内部两点交叉使数据以反转的方式输出而不是数字反转顺序。

首先确认二进制数的位数，64个数只需要有6位的二进制位数；

接着将二进制数分成两部分，前五位一部分，最后一位一部分；

最后进行二进制翻转，把最后一位放到最高位，剩下的五位进行翻转依次放入。

数组内存放的依次是0~63的二进制翻转结果，我们可以来看一个例子，

（点击鼠标）以数字5为例，（点击鼠标）转换为二进制数是000101

（点击鼠标）接着进行二进制翻转，将“00010”看为一个部分，“1”看为一个部分，那么将“1”放到第一位，然后将后面的数据翻转过来进行放置即可

（点击鼠标）最后进行十六进制转换得到0x28，所以在数组的第6个数字为0x28。

导入工程，选择Demo文件夹下的对应工程

编译工程，生成可执行文件

将CCS连接实验箱并加载程序

程序加载完成后点击运行程序

运行程序后，程序执行完成后会在断点处停下。

点击"Tools->Graph->Single Time"选择单时域信号图，在弹出的界面设置相关参数，可查看DSP计算的FFT结果。

点击"Tools->Graph->FFT Magnitude"，在弹出的界面设置相关参数，可查看CCS计算的FFT结果。

对比后，可发现CCS和DSP计算的FFT结果相同，

实验结束后，点击红色按钮退出CCS与实验箱的连接，最后实验箱断电即可。