快速傅立叶变换（FFT）的实现
一、实验目的
1.了解FFT的原理及算法；
2.了解DSP中FFT的设计及编程方法； 3.熟悉FFT的调试方法；
二、实验原理
FFT是一种高效实现离散付立叶变换的算法，把信号从时域变换到频域，在频域分析处理信息。
对于长度为N的有限长序列x(n)，它的离散傅里叶变换为： N?1X(k)??x(n)WNnk n?0WN?e?j(2?/N)nk，称为旋转因子，或蝶形因子。
在x(n)为复数序列的情况下，计算X(k)：
对某个k值，需要N次复数乘法、(N-1)次复数加法；
对所有N个k值，需要N次复数乘法和N(N-1)次复数加法。对于N相当大时（如1024）来说，直接计算它的DFT所作的计算量是很大的， FFT的基本思想在于：
利用WN?e?j(2?)nkN2的周期性即：WNk?Nk?WN
kk?N/2 对称性：WN??WN
将原有的N点序列分成两个较短的序列，这些序列的DFT可以很简单的组合起来得到原序列的DFT。按时间抽取的FFT——DIT FFT信号流图如图5.1所示：
图5.1 时间抽取的FFT—DIT FFT信号流图
FFT算法主要分为以下四步。 第一步 输入数据的组合和位倒序
1
把输入序列作位倒序是为了在整个运算最后的输出中得到的序列是自然顺序。 第二步 实现N点复数FFT
第一级蝶形运算；第二级蝶形运算；第三级至log2N级蝶形运算；
FFT运算中的旋转因子WN是一个复数，可表示：
2?k2?kk?j2?k/NW?e?cos?jsin NNN为了实现旋转因子WN的运算，在存储空间分别建立正弦表和余弦表，每个表对应从0度到180度，采用循环寻址来对正弦表和余弦表进行寻址。
第三步 功率谱的计算
X(k)是由实部XR(k)和虚部XI(k)组成的复数：X(k)?XR(k)?jXI(k)；计算功率谱时只需将FFT变换好的数据，按照实部XR(k)和虚部XI(k)求它们的平方和，然后对平方和进行开平方运算。 第四步 输出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 \N .set 128
LOGN .set 7 sav_grp .usect \sav_sin .set sav_grp+1 sav_idx .set sav_grp+2 OUTPUT .usect \
BOS .usect \TOS .usect \
.copy \ .copy \
.text _c_int00
2
b start nop nop start: STM LD SSBX STM STM STM MVMM STM RPTBD STM LDM READA *AR2+ ADD #1,A READA *AR2+ MAR plend: STM LD MVMM STM STM #N/2-1,BRC LD RPTBD STM SUB ADD STH ST ||LD SUB ADD STH ST ||LD s1end: MVMM STM STM LD RPTBD STM SUB ADD STH ST ||LD SUB ADD STH STH MAR ADD SUB
STH
#TOS,SP #0,DP
FRCT #2*N,BK #INPUT,AR3 #DATA,AR7 AR7,AR2 #N-1,BRC plend-1 #N,AR0 AR3,A *AR3+0B #0,BK #-1,ASM AR7,AR2 #DATA+2,AR3 *AR2,16,A s1end-1 #3,AR0
*AR3,16,A,B *AR3,16,A A,ASM,*AR2+ B,*AR3+ *AR2,A
*AR3,16,A,B *AR3,16,A A,ASM,*AR2+0 B,*AR3+0% *AR2,A AR7,AR2 #DATA+4,AR3 #N/4-1,BRC *AR2,16,A s2end-1 #5,AR0
*AR3,16,A,B *AR3,16,A A,ASM,*AR2+ B,*AR3+ *AR2,A
*AR3,16,A,B *AR3,16,A A,ASM,*AR2+ B,ASM,*AR3+ *AR3+
*AR2,*AR3,A *AR2,*AR3-,B A,ASM,*AR2+
3
SUB ST ||LD ST ||ADD ST ||LD s2end:
STM ST STM STM STM #TWI1,AR5 STM ST STM ST stage:
STM LD ADD STLM MVDK group:
MVMD RPTBD LD MPY MACR ADD ST ||SUB ST ||MPY MASR ADD ST ||SUB LD ST ||MPY bend:
PSHM MVDK MAR MAR BANZD POPM MAR LD SUB STLM STL LD STL LD STL BANZD
*AR2,*AR3,A B,*AR3 *AR3+,B A,*AR2 *AR2+0%,A A,*AR3+0% *AR2,A #512,BK
#128,@sav_sin #128,AR0 #TWI2,AR4 #-3+LOGN,AR7 #-1+N/8,@sav_grp #3,AR6
#8,@sav_idx #DATA,AR2 @sav_idx,A *(AR2),A A,AR3
@sav_grp,AR1 AR6,BRC bend-1 *AR4,T *AR3+,A
*AR5+0%,*AR3-,A *AR2,16,A,B B,*AR2 *AR2+,B B,*AR3 *AR3+,A
*AR3,*AR4+0%,A *AR2,16,A,B B,*AR3+ *AR2,B *AR4,T B,*AR2+ *AR3+,A AR0
sav_idx,AR0 *AR2+0 *AR3+0
group,*AR1- AR0 *AR3- sav_idx,A #1,A,B B,AR6
A,1,sav_idx sav_grp,A A,ASM,sav_grp sav_sin,A A,ASM,sav_sin stage,*AR7-
4
相关推荐：
loading