实验五 快速傅立叶变换（FFT）的实现
一、 实验目的
在数字信号处理系统中，FFT作为一个非常重要的工具经常使用，甚至成为DSP运算能力的一个考核因素。FFT是一种高效实现离散付氏变换的算法。离散付氏变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由付氏逆变换到时域。
本实验的目的在于学习FFT算法，及其在TMS320C54X上的实现，并通过编程掌握C54X的存储器管理、辅助寄存器的使用、位倒序寻址方式等技巧，同时练习使用CCS的探针和图形工具。另外在BIOS子目录下是一个使用DSP/BIOS工具实现FFT的程序。通过该程序，你可以使用DSP/BIOS提供的分析工具评估FFT代码执行情况。
二、 实验原理
㈠ 基—2按时间抽取FFT算法
对于有限长离散数字信号{x[n]}，0 ? n ? N-1，其离散谱{x[k]}可以由离散付氏变换
X?k???x[n]en?0N?1?j(2?)nkNk?0,1,...,N?1（DFT）求得。DFT的定义为
可以方便的把它改写为如下形式：
不难看出，WN是周期性的，且周期为N，即
N?1nlN?0(n?mN)(k?)nkWN?WNnkX?k???x[n]WNk?0,1,...,N?1m,l?0,?1,?2...WN的周期性是DFT的关键性质之一。为了强调起见，常用表达式WN取代W以便明确其周期是N。
由DFT的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N点DFT需
116
要（N-1）2次复数乘法和N（N-1）次加法。因此，对于一些相当大的N值（如1024）来说，直接计算它的DFT所作的计算量是很大的。FFT的基本思想在于，将原有的N点序列序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。例如，若N为偶数，将原有的N点序列分成两个（N/2）点序列，那么计算N点DFT将只需要约[(N/2)2 ·2]=N2/2次复数乘法。即比直接计算少作一半乘法。因子（N/2）
2
表示直接计算（N/2）点DFT所需要的乘法次数，而乘数2代表必须完成两个DFT。
上述处理方法可以反复使用，即（N/2）点的DFT计算也可以化成两个（N/4）点的DFT（假定N/2为偶数），从而又少作一半的乘法。这样一级一级的划分下去一直到最后就划分成两点的FFT运算的情况。比如，一个N = 8点的FFT运算按照这种方法来计算FFT可以用下面的流程图来表示：
x(0)W0x(1)W0x(2)W0x(3)x(4)W0x(5)W0x(6)W0x(7)W2X(7)W3X(6)W2X(5)W2X(0)X(1)X(2)W0W1X(3)X(4)
关于蝶形结运算的具体原理及其推导可以参照讲义，在此就不再赘述。
㈡ 实数FFT运算
对于离散傅立叶变换（DFT）的数字计算，FFT是一种有效的方法。一般假定输入序列是复数。当实际输入是实数时，利用对称性质可以使计算DFT非常有效。
一个优化的实数FFT算法是一个组合以后的算法。原始的2N个点的实输入序列组合成一个N点的复序列，之后对复序列进行N点的FFT运算，最后再由N点的复数输出拆散成2N点的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的DFT输出一致。
使用这种方法，在组合输入和拆散输出的操作中，FFT运算量减半。这样利用实数FFT算法来计算实输入序列的DFT的速度几乎是一般复FFT算法的两倍。本实验就用这种方法
117
实现了一个256点实数FFT（2N = 256）运算。
⒈ 实数FFT运算序列的存储分配
如何利用有限的DSP系统资源，合理的安排好算法使用的存储器是一个比较重要的问题。参见FFT实验程序的CMD文件：
MEMORY {
PAGE 0: IPROG: origin = 0x3080, VECT: origin = 0x3000, EPROG: origin = 0x38000,
PAGE 1: USERREGS: origin = 0x60, BIOSREGS: origin = 0x7c, IDATA: origin = 0x80, EDATA: origin = 0xC00, }
SECTIONS {
.vectors: {} > VECT PAGE 0 .sysregs: {} > BIOSREGS PAGE 1 .trcinit: {} > IPROG PAGE 0 .gblinit: {} > IPROG PAGE 0 .bios: {} > IPROG PAGE 0 frt: {} > IPROG PAGE 0 .text: {} > IPROG PAGE 0 .cinit: {} > IPROG PAGE 0 .pinit: {} > IPROG PAGE 0
118
len = 0x1F80 len = 0x80 len = 0x8000 len = 0x1c len = 0x4 len = 0xB80 len = 0x1400 .sysinit: {} > IPROG PAGE 0 .data {} > EDATA PAGE 1 .bss: {} > IDATA PAGE 1 .far: {} > IDATA PAGE 1 .const: {} > IDATA PAGE 1 .switch: {} > IDATA PAGE 1 .sysmem: {} > IDATA PAGE 1 .cio: {} > IDATA PAGE 1 .MEM$obj: {} > IDATA PAGE 1 .sysheap: {} > IDATA PAGE 1 }
从上面的连接定位CMD文件可以了解到，程序代码安排在0x3000开始的存储器中。其中0x3000-0x3080存放中断向量表。FFT程序使用的正弦表、余弦表数据（.data段）安排在0xc00开始的地方。变量(.bss段定义)存放在0x80开始的地址中。另外，本256点实数FFT程序的输入数据缓冲为0x2300-0x23ff，FFT后功率谱的计算结果存放在0x2200-0x22ff中。
⒉ 基二实数FFT运算的算法
该算法主要分为四步：
第一步，输入数据的组合和位倒序
把输入序列作位倒序，是为了在整个运算最后的输出中得到的序列是自然顺序。首先，原始的输入的2N = 256个点的实数序列复制放到标记有“d_input_addr”的相邻单元，当成N = 128点的复数序列d[n]。奇数地址是d[n]的实部，偶数地址是d[n]的虚部。这个过程叫做组合（n是从0到无穷，指示时间的变量，N是常量）。然后，复数序列经过位倒序，存储在数据处理缓冲器中，标记为“fft-data”。
① 如图2，输入实数序列为a[n]，n=0，1，2，3，…，255。分离a[n]成两个序列，如图3所示。原始的输入序列是从地址0x2300到0x23FF，其余的从0x2200到0x22FF的是经过位倒序之后的组合序列：n=0，1，2，3，…，127。 ② d[n]表示复合FFT的输入，r[n]表示实部，i[n]表示虚部： d[n]=r[n]+j i[n]
119
2200h2201h2202h2203h2204h2205h2206h2207h2208h2209h220Ah220Bh22FFh2300h2301h2302h2303h2304h2305h2306h2307h2308h2309h230Ah230Bha[0]a[1]a[2]a[3]a[4]a[5]a[6]a[7]a[8]a[9]a[10]a[11]23FFha[255] 按位倒序的方式存储d[n]到数据处理缓冲中，如图2。
图2
120