电子科技大学通信与信息工程学院标准实验报告（实验）课程名称DSP设计与实践电子科技大学教务处制表电 子 科 技 大 学实 验 报 告学生姓名： 学 号 指导教师：实验地点： 实验时间： 一、实验室名称： 科B341 二、实验项目名称：快速傅立叶变换（FFT ）的实现 三、实验学时：4 四、实验原理：基—2按时间抽取FFT 算法对于有限长离散数字信号{x[n]}，0 ≤ n ≤ N-1，其离散谱{x[k]}可以由离散付氏变换（DFT ）求得。

DFT 的定义为可以方便的把它改写为如下形式：不难看出，W N 是周期性的，且周期为N ，即W N 的周期性是DFT 的关键性质之一。

为了强调起见，常用表达式W N 取代W 以便明确其周期是N 。

由DFT 的定义可以看出，在x[n]为复数序列的情况下，完全直接运算N 点DFT 需要（N-1）2次复数乘法和N （N-1）次加法。

因此，对于一些相当大的N 值（如1024）来说，直接计算它的DFT 所作的计算量是很大的。

FFT 的基本思想在于，将原有的N 点序列序列分成两个较短的序列，这些序列的DFT 可以很简单的组合起来得到原序列的DFT 。

例如，若N 为偶数，将原有的N 点序列分成两个（N/2）点序列，那么计算N 点DFT 将只需要约[(N/2)2 ·2]=N 2/2次复数乘法。

即比直接计算少作一半乘法。

因子（N/2）2表示直接计算（N/2）点DFT 所需要的乘法次数，而乘数2代表必须完成两个DFT 。

()1,...,1,0][)2(10-==--=∑N k en x k X nk Nj N n π()1,...,1,0][10-==∑-=N k W n x k X nkNN n ...2,1,0,))((±±==++l m W W nk NlN k mN n N上述处理方法可以反复使用，即（N/2）点的DFT 计算也可以化成两个（N/4）点的DFT （假定N/2为偶数），从而又少作一半的乘法。

这样一级一级的划分下去一直到最后就划分成两点的FFT 运算的情况。

比如，一个N = 8点的FFT 运算按照这种方法来计算FFT 可以用下面的流程图来表示：x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(7)X(6)X(5)X(4)X(3)X(2)X(1)X(0)关于蝶形结运算的具体原理及其推导可以参照讲义，在此就不再赘述。

实数FFT 运算对于离散傅立叶变换（DFT ）的数字计算，FFT 是一种有效的方法。

一般假定输入序列是复数。

当实际输入是实数时，利用对称性质可以使计算DFT 非常有效。

一个优化的实数FFT 算法是一个组合以后的算法。

原始的2N 个点的实输入序列组合成一个N 点的复序列，之后对复序列进行N 点的FFT 运算，最后再由N 点的复数输出拆散成2N 点的复数序列，这2N 点的复数序列与原始的2N 点的实数输入序列的DFT 输出一致。

使用这种方法，在组合输入和拆散输出的操作中，FFT 运算量减半。

这样利用实数FFT 算法来计算实输入序列的DFT 的速度几乎是一般复FFT 算法的两倍。

本实验就用这种方法实现了一个256点实数FFT （2N = 256）运算。

⒈ 实数FFT 运算序列的存储分配如何利用有限的DSP 系统资源，合理的安排好算法使用的存储器是一个比较重要的问题。

参见FFT 实验程序的CMD 文件：MEMORY {PAGE 0: IPROG: origin = 0x3080, len = 0x1F80 VECT: origin = 0x3000, len = 0x80 EPROG: origin = 0x38000, len = 0x8000PAGE 1: USERREGS: origin = 0x60, len = 0x1c BIOSREGS: origin = 0x7c, len = 0x4 IDA TA: origin = 0x80, len = 0xB80 EDATA: origin = 0xC00, len = 0x1400}SECTIONS{.vectors: {} > VECT PAGE 0.sysregs: {} > BIOSREGS PAGE 1.trcinit: {} > IPROG PAGE 0.gblinit: {} > IPROG PAGE 0.bios: {} > IPROG PAGE 0frt: {} > IPROG PAGE 0.text: {} > IPROG PAGE 0.cinit: {} > IPROG PAGE 0.pinit: {} > IPROG PAGE 0.sysinit: {} > IPROG PAGE 0.data {} > EDA TA PAGE 1.bss: {} > IDA TA PAGE 1.far: {} > IDA TA PAGE 1.const: {} > IDATA PAGE 1.switch: {} > IDATA PAGE 1.sysmem: {} > IDATA PAGE 1.cio: {} > IDA TA PAGE 1.MEM$obj: {} > IDA TA 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]按位倒序的方式存储d[n]到数据处理缓冲中，如图2。

图2* 编程技巧：在用C54x进行位倒序组合时，使用位倒序寻址方式可以大大提高程序执行的速度和使用存储器的效率。

在这种寻址方式中，AR0存放的整数N是FFT点数的一半，一个辅助寄存器指向一数据存放的单元。

当使用位倒序寻址把AR0加到辅助寄存器中时，地址以位倒序的方式产生，即进位是从左到右，而不是从右到左。

例如，当AR0 = 0x0060，AR2 = 0x0040时，通过指令：MAR AR2+0B我们就可以得到AR2位倒序寻址后的值为0x0010。

下面是0x0060（1100000）与0x0040（1000000）以位倒序方式相加的过程：1 1 0 0 0 0 01 0 0 0 0 0 0+0 0 1 0 0 0 0实现256点数据位倒序存储的具体程序段如下：bit_rev:STM #d_input_addr,ORIGINAL_INPUT ；在AR3（ORIGINAL_INPUT）中；放入输入地址STM #fft_data,DATA_PROC_BUF ；在AR7（DATA_PROC_BUF）中；放入处理后输出的地址MVMM DA TA_PROC_BUF,REORDERED_DA TA ;AR2（REORDERED_DA TA）;中装入第一个位倒序数据指针STM #K_FFT_SIZE-1,BRCSTM #K_FFT_SIZE,AR0 ;AR0的值是输入数据数目的一半=128RPTB bit_rev_endMVDD *ORIGINAL_INPUT+,*REORDERED_DATA+ ;将原始输入缓冲中的数据;放入到位倒序缓冲中去之;后输入缓冲(AR3)指针加1;位倒序缓冲(AR2)指针也加;一MVDD *ORIGINAL_INPUT-,*REORDERED_DA TA+ ;将原始输入缓冲中的数据;放入到位倒序缓冲中去之;后输入缓冲(AR3)指针减一;位倒序缓冲(AR2)指针加一;以保证位倒序寻址正确MAR *ORIGINAL_INPUT+0B ；按位倒序寻址方式修改AR3 bit_rev_end:注意，在上面的程序中。

输入缓冲指针AR3（即ORIGINAL_INPUT）在操作时先加一再减一，是因为我们把输入数据相邻的两个字看成一个复数，在用寄存器间接寻址移动了一个复数（两个字的数据）之后，对AR3进行位倒序寻址之前要把AR3的值恢复到这个复数的首字的地址，这样才能保证位倒序寻址的正确。

第二步，N点复数FFT在数据处理缓冲器里进行N点复数FFT运算。

由于在FFT运算中要用到旋转因子W N，它是一个复数。

我们把它分为正弦和余弦部分，用Q15格式将它们存储在两个分离的表中。

每个表中有128项，对应从0度到180度。

因为采用循环寻址来对表寻址，128 = 27 < 28，因此每张表排队的开始地址就必须是8个LSB位为0的地址。

参照前面图1 DES 系统的存储区分配，所以我们必须把正弦表第一项“sine_table”放在0x0D00的位置,余弦表第一项“cos_table ”放在0x0E00的位置。

① 根据公式利用蝶形结对d[n]进行N=128点复数FFT 运算，其中所需的正弦值和余弦值分别以Q15的格式存储于内存区以0x0D00开始的正弦表和以0x0E00开始的余弦表中。

我们把128点的复数FFT 分为七级来算，第一级是计算两点的FFT 蝶形结，第二级是计算四点的FFT 蝶形结，然后是八点、十六点、三十二点六十四点、一百二十八点的蝶形结计算。

最后所得的结果表示为： D[k] = F{d[n]} = R[k] + j I[k]其中，R[k]、I[k]分别是D[k]的实部和虚部。

图3② FFT 完成以后，结果序列D[k]就存储到数据处理缓冲器的上半部分，如图3()1,...,1,0][10-==∑-=N k W n d k D nkNN n)2sin()2cos()2(nk Nj nk N eWnk Nj nk Nπππ-==-所示，下半部分任然保留原始的输入序列a[n]，这半部分将在第三步中被改写。