快速傅立叶变换（FFT）的实现一、实验目的1. 了解 FFT 的原理及算法；2. 了解 DSP 中 FFT 的设计及编程方法；3. 熟悉 FFT 的调试方法；二、实验原理FFT 是一种高效实现离散付立叶变换的算法，把信号从时域变换到频域，在频域分析处理信息。对于长度为N 的有限长序列x(n)，它的离散傅里叶变换为：(2/)jN nkNWe，称为旋转因子，或蝶形因子。在 x(n)为复数序列的情况下，计算X(k)：对某个 k 值，需要 N 次复数乘法、 (N-1)次复数加法；对所有 N 个 k 值，需要2N次复数乘法和N(N-1)次复数加法。 对于 N 相当大时（如 1024）来说，直接计算它的DFT 所作的计算量是很大的，FFT 的基本思想在于：利用2()jnkNNWe的周期性即：kNkNNWW对称性：/ 2kk NNNWW将原有的 N 点序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的 DFT 。按时间抽取的FFT—— DIT FFT 信号流图如图5.1 所示：图 5.1 时间抽取的FFT — DIT FFT信号流图FFT 算法主要分为以下四步。第一步输入数据的组合和位倒序把输入序列作位倒序是为了在整个运算最后的输出中得到的序列是自然顺序。第二步实现 N 点复数 FFT 第一级蝶形运算；第二级蝶形运算；第三级至log2N 级蝶形运算；FFT 运算中的旋转因子NW 是一个复数，可表示：为了实现旋转因子NW 的运算，在存储空间分别建立正弦表和余弦表，每个表对应从0度到 180 度，采用循环寻址来对正弦表和余弦表进行寻址。第三步功率谱的计算X(k)是由实部( )RXk 和虚部( )IXk组成的复数：( )( )( )RIX kXkjXk； 计算功率谱时只需将FFT 变换好的数据，按照实部( )RXk和虚部( )IXk 求它们的平方和，然后对平方和进行开平方运算。第四步输出 FFT 结果。三、实验内容与步骤１.本实验要求使用FFT 变换求一个时域信号的频域特性，并从这个频域特性求出该信号的频率值，然后使用DSP 汇编语言对FFT 的 DSP 编程。２.将计算机与DES-320PP— A 教学实验系统连接好，打开实验箱电源，然后运行CCS 软件。2. 新建 fft.pjt工程文件，并输入FFT的 DSP程序及命令链接文件。如下：************************************** *Radix-2,DIT,Real-input FFT Program * * fft.asm * ************************************* .mmregs .global reset,start,sav_sin,sav_idx,sav_grp .def start,_c_int00 .data DATA .space 1024 .copy "fft.inc" N ....
