§2.4 快速傅里叶变换 (FFT) 实现
一、实验目的 1. 掌握FFT 算法的基本原理；
2. 掌握用C 语言编写DSP 程序的方法。
二、实验设备 1. 一台装有CCS3.3软件的计算机； 2. DSP 实验箱的TMS320F2812主控板；
3. DSP 硬件仿真器。
三、实验原理
傅里叶变换是一种将信号从时域变换到频域的变换形式，是信号处理的重要分析工具。离散傅里叶变换（DFT ）是傅里叶变换在离散系统中的表示形式。但是DFT 的计算量非常大， FFT 就是DFT 的一种快速算法, FFT 将DFT 的N 2 步运算减少至 ( N/2 )log 2N 步。
离散信号x(n)的傅里叶变换可以表示为
∑=-=1
0][)(N N nk N W n x k X ， N
j N e W /2π-=
式中的W N 称为蝶形因子，利用它的对称性和周期性可以减少运算量。一般而言，FFT 算法分为时间抽取（DIT ）和频率抽取（DIF ）两大类。两者的区别是蝶形因子出现的位置不同，前者中蝶形因子出现在输入端，后者中出现在输出端。本实验以时间抽取方法为例。
时间抽取FFT 是将N 点输入序列x(n) 按照偶数项和奇数项分解为偶序列和奇序列。偶序列为：x(0), x(2), x(4),…, x(N-2)；奇序列为：x(1), x(3), x(5),…, x(N-1)。这样x(n) 的N 点DFT 可写成：
()()∑++∑=-=+-=1
2/0
)12(1
2/0
2122)(N n k
n N
N n nk
N
W n x W
n x k X
考虑到W N 的性质，即
2/)2//(22/)2(2][N N j N j N W e e W ===--ππ
因此有：
()()∑++∑=-=-=1
2/0
2/1
2/0
2
/122)(N n nk
N k
N
N n nk
N W n x W W
n x k X
或者写成：
()()k Z W k Y k X k
N +=)(
由于Y(k) 与Z(k) 的周期为N/2，并且利用W N 的对称性和周期性，即：
k N
N k N W W -=+2/
可得：
()()k Z W k Y N k X k
N -=+)2/(
对Y(k) 与Z(k) 继续以同样的方式分解下去，就可以使一个N 点的DFT 最终用一组2点的DFT 来计算。在基数为2的FFT 中，总共有log 2(N) 级运算，每级中有N/2 个2点FFT 蝶形运算。
单个蝶形运算示意图如下：
以N ＝8为例，时间抽取FFT 的信号流图如下：
x(0)
x(4)
x(2)
x(6)x(1)
x(5)
x(3)
x(7)
X(7)
X(6)X(5)X(4)X(3)X(2)X(1)X(0)
从上图可以看出，输出序列是按自然顺序排列的，而输入序列的顺序则是“比特反转”
方式排列的。也就是说，将序号用二进制表示，然后将二进制数以相反方向排列，再以这个数作为序号。如011变成110，那么第3个输入值和第六个输入值就要交换位置了。本实验中采用了一种比较常用有效的方法完成这一步工作＿＿雷德算法。 四、实验步骤
1. 以64点FFT 的信号流图为例，理解FFT 算法的过程；
2. 在CCS
3.3环境中打开本实验的工程（Example_fft.pjt ），编译并重建 .out 输出文件，然后通过仿真器把执行代码下载到DSP 芯片中；
3. 运行程序；
4. 选择view->graph->time/frequency … 。 设置对话框中的参数: 其中“Start Address ”设为“x_re ”，“Acquisition buffer size ”和“Display Data size ”都设为“64”，并且把“DSP Data Type ”设为“32-bit floating point ”（如图），
设置好后观察输入信号序列的波形（单边指数函数，如图）；
同样方法观察经DFT变换后的输出序列“y_re”的波形，“Start Address”改为“y_re”，其余参数不变（如图）；
5．在Watch窗口中添加i, j, k, m, n, a, b ,c 等变量，在Debug菜单中先“Restart”然后“Go main”，单步运行程序，跟踪FFT算法的过程；（可以跳过程序开始部分对各个数组的赋值代码，方法是在雷德算法的第一行代码前设置断点，然后先单击运行，待程序停在该断点后再单步执行后面的代码，见下图。）
6.修改N的值（应为2的整数次幂，如8，16，32等，最大不超过64），或者修改输入信号x的函数，如直流、正弦、三角等，观察程序运行结果。注意观察图形时，数据块大小要相应更改为当前N值。
五、思考题
1.分析本实验程序中完成位倒序排列的“雷德算法”的原理；
2.思考如何实现实数序列的FFT，它在复数序列的算法基础上还能作哪些优化，
从而进一步降低运算量和所需的存储空间。
六、相关截图
T1.0 傅里叶变换波形图（单边指数函数）T1.1设置相关参数
