基于DSP的FFT实现
目录
摘要............................................................................................................................ I 第1章绪论.. (1)
1.1DSP简介 (1)
1.2设计内容 (1)
1.3设计要求 (1)
1.4 设计原理 (1)
1.5 FFT算法的DSP实现过程 (2)
第2章硬件实现 (4)
2.1系统的硬件设计 (4)
2.2原理图的设计 (5)
第3章软件设计 (7)
3.1FFT运算及存储分配 (7)
3.2程序流程图 (8)
第4章系统仿真 (9)
4.1FFT实现的方法 (9)
4.2程序运行结果 (10)
第5章总结 (12)
参考文献 (13)
附录 (14)
摘要
快速傅里叶变换（FFT）是将信号从时域变换到频域的一种方法，广泛应用于各种信号分析领域，文中介绍了FFT算法的基本原理和DSP中FFT算法的编程思想和设计原理及其硬件设计思想，基于TMS320C5502芯片用CCS仿真软件实现了FFT算法，文中以基2FFT为例，简要介绍了算法的实现，并画出了蝶形运行算图。然后编程实现算法，输出波形。
关键字:DSP；CCS仿真软件；FFT
第1章 绪论
1.1 DSP 简介
数字信号处理(Digital Signal Processing ，简称DSP)是一门涉及许多学科而又广泛应用于许多领域的新兴学科。数字信号处理是利用计算机或专用处理设备，以数字的形式对信号进行分析、采集、合成、变换、滤波、估算、压缩、识别等加工处理，以便提取有用的信息并进行有效的传输与应用。数字信号处理是以众多学科为理论基础,它所涉及的范围极其广泛。如数学领域中的微积分、概率统计、随机过程、数字分析等都是数字信号处理的基础工具。它与网络理论、信号与系统、控制理论、通信理论、故障诊断等密切相关。
1.2设计目的
（1）加深对DFT 算法原理和基本性质的理解；
（2）熟悉FFT 的算法原理和FFT 子程序的算法流程和应用； （3）学习用FFT 对连续信号和时域信号进行频谱分析的方法； （4）学习DSP 中FFT 的设计和编程思想；
（5）学习使用CCS 的波形观察器观察波形和频谱情况； （6）简要画出硬件设计电路图。
1.3设计内容
用DSP 汇编语言进行编程，实现FFT 运算，对输入信号进行频谱分析。
1.4设计原理
快速傅氏变换（FFT ）是一种高效实现离散傅氏变换的快速算法，是数字信号处理中最为重要的工具之一，它在声学、语音、电信、和信号处理等领域有着广泛的应用。
对于有限长离散数字信号{x[n]}，0 ≤ n ≤ N-1，其离散谱{x[k]}可以由离散付氏变换（DFT ）求得。可以方便的把它改写为如下形式：
不难看出，WN 是周期性的，且周期为N ，即
()1
,...,1,0][1
0-==∑-=N k W n x k X nk
N
N n
N 的周期性是DFT 的关键性质之一。为了强调起见，常用表达式WN 取代
W 以便明确其周期是N 。
FFT 算法可以分为按时间抽取FFT 和按频率抽取FFT 两大类，输入也有和复数之分，一般情况下，都假定输入序列为复数。FFT 算法利用旋转因子的对称性和周期性，加快了运算速度。用定点DSP 芯片实现FFT 程序时，一个比较重要的问题是防止中间结果的溢出，防止中间结果的溢出的方法是对中间数值归一化。为了避免对每级都进行归一化会降低运算速度，最好的方法是只对可能溢出的进行归一化，而不可能溢出的则不进行归一化。
由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]=N2/2次复数乘法。即比直接计算少作一半乘法。因子（N/2）2表示直接计算（N/2）点DFT 所需要的乘法次数，而乘数2代表必须完成两个DFT 。上述处理方法可以反复使用，即（N/2）点的DFT 计算也可以化成两个（N/4）点的DFT （假定N/2为偶数），从而又少作一半的乘法。这样一级一级的划分下去一直到最后就划分成两点的FFT 运算的情况。
1.5 FFT 算法的DSP 实现过程
DSP 芯片的出现使FFT 的实现方法变得更为方便。由于大多数DSP 芯片都
具有在单指令周期内完成乘法—累加操作，并且提供了专门的FFT 指令，使得FFT 算法在DSP 芯片实现的速度更快。FFT 算法可以分为按时间抽取FFT 和按频率抽取FFT 两大类，输入也有实数和复数之分，一般情况下，都假定输入序列为复数。
()1
,...,1,0][)2(
1
-==
--=∑N k e n x k X nk
N
j N n
π
...
2,1,0,))((±±==++l m W W nk
N
lN k mN n N
1.5.1FFT运算序列的存储分配
FFT运算时间是衡量DSP芯片性能的一个重要指标，因此提高FFT的运算速度是非常重要的。在用DSP芯片实现FFT算法时，应允许利用DSP芯片所提供的各种软、硬件资源。如何利用DSP芯片的有限资源，合理地安排好所使用的存储空间是十分重要的。
1.5.2 FFT运算的实现
用TMS320C54x的汇编程序实现FFT算法主要分为四步：
(1)实现输入数据的比特反转
输入数据的比特反转实际上就是将输入数据进行码位倒置，以便在整个运算后的输出序列是一个自然序列。在用汇编指令进行码位倒置时，使用码位倒置可以大大提高程序执行速度和使用存储器的效率。在这种寻址方式下，AR0存放的整数N是FFT点的一半，一个辅助寄存器指向一个数据存放的单元。当使用位码倒置寻址将AR0加到辅助寄存器时，地址将以位码倒置的方式产生。
(2)实现N点复数FFT
N点复数FFT算法的实现可分为三个功能块，即第一级蝶形运算、第二级蝶形运算、第三级至级蝶形运算。对于任何一个2的整数幂，总可以通过M次分解最后成为2点的DFT计算。通过这样的M次分解，可构成M（即）级迭代计算，每级由N/2个蝶形运算组成。
(3)功率谱的计算
用FFT计算想x(n)的频谱，即计算
X（k）=
X(k)一般是由实部(k)和虚部(k)组成的复数，即
X（k）=(k)+j(k)
因此，计算功率谱时只需将FFT变换好的数据，按照实部实部(k)和虚部(k)求它们的平方和，然后对平方和进行开平方运算。但是考虑到编程的难度，对于求FFT变换后数据的最大值，不开平方也可以找到最大值，并对功率谱的结果没有影响，所以在实际的DSP编程中省去了开方运算。
第2章硬件实现
2.1系统的硬件设计
基于DSP的系统设计过程中，最小系统的设计是整个系统设计的第一步，系统设计总是从最小系统开始，逐步向系统应用范围扩展，最终以DSP为核心的大系统的设计。因此最小系统设计DSP设计的关键。DSP最小系统的设计包括DSP 电源和地线的设计，JTAG仿真口的设计、复位和时钟电路的设计、上拉和下拉引脚的设计等。
图2.1.1 最小系统的设计
芯片介绍
（1）该模块上的资源有32千字FLASH
（2）千字SARAM，544字DARAM，外扩64千字的程序ROM，64千字的数据RAM
（3）两个事件管理器EVA和EVB
（4）可扩展外部存储器总共192K字空间：64K程序存储器，64K字数据存储器空间，64K字I/O寻址空间
（5）看门狗定时模块
（6）19位A/D转换器
（7）控制局域网络CAN模块
串行通信接口SCI模块
（8）16位串行外设SPI接口模块
（9）基于锁相环的时钟发生器
（10）高达40个可单独编程或复用的通用输入/输出引脚GPIO
（11）5个外部中断
（12）电源管理包括3种低功耗模式，能独立地将外设器件转入低功耗工作模式
2.2原理图的设计
DSP最小系统的设计包括DSP电源设计，JTAG仿真口的设计、复位和时钟电路的设计、上拉和下拉引脚的设计等
2.2.1电源电路的设计
电源电路的选择是系统设计的一个重要的部分，设计好坏对系统的影响最大。首先需要注意的是，为了减少电源噪声和互相干扰，数字电路和模拟电路一般要独立供电，数字地和模拟地也要分开，并最终通过一个磁珠在一点连在一起，用TPS7333Q进行3.3V电压的转换对最小系统供电
图2.2.1 电源电路
2.2.2复位电路设计
TMS320C5502内部带有复位电路，因此可以直接RS复位引脚外面接一个上拉电阻即可，这对于简化外围电路，减少电路板尺寸很有用处，但是为了调试方便经常采用手动复位电路。
2.2.3锁相环电路设计
图2.2.3 锁相环电路
2.2.4 JTAG口
JTAG是Joint Test Action Group的简称，又称JTAG口，它是一符合IEEE Std 1149.1边界扫描逻辑标准的标准接口。它主要用于在硬件上对DSP进行实时在线仿真测试和DSP程序的下载，它提供对所连接设备的边界扫描，同时也可以用来测试引脚到引脚的连续性，以及进一步进行DSP芯片的外围器件的操作测试。
第3章 软件实现
3.1 FFT 运算及存储分配
（1）DSP 芯片的出现使FFT 的实现方法变得更为方便，由于大多数DSP 芯片都具有在单指令周期内完成乘法——累加的操作，并提供了专门的FFT 指令，使得FFT 算法在DSP 的实现速度更快。一般，FFT 的算法可分为按时间抽取FFT 和按频率抽取FFT ，输入也有实数和复数之分，一般情况下都假定输入是复数序列。
（2）FFT 运算序列的存储分配
FFT 运算时间是衡量DSP 芯片性能的一个重要指标，因此提高FFT 的运算速度是非常重要的。在用DSP 芯片实现FFT 算法时，应允许利用DSP 芯片所提供的各种软、硬件资源。如何合理的利用DSP 芯片的有限资源，合理的安排DSP 芯片所提供的存储空间相当关键。本设计采用如下所示的存储分配：
0000007F
2060
2062.bss
2063
21FF stack
2200
23FF sine
存储映射寄
存器
暂存单元
堆栈
正弦系数表
20612400
25FF 余弦系数表
cosine
2800
287F
28802C7F 2C80
307F
d_input
fft_data
fft_out
输入数据FFT结果
（实部、虚部）FFT结果（功率谱）
图3.1数据空间分配图
3.2设计流程图
图3.2 最小系统设计流程图
第4章系统仿真
4.1 FFT实现的方法
（1）根据N值，修改rfft_task.asm中的两个常数，如N=64.
K_FFT_SIZE .set 64
K_LOGN .set 6
（2）准备输入数据文件in.dat。输入数据按实部、虚部，实部、虚部，……顺序存放。
（3）汇编、链接、仿真执行，得到输出数据文件out.dat。
（4）根据out.dat作图，就可以得到输入信号的功率谱图。
当N超过1024时，除了修改K_FFT_SIZE和K_LOGN两个常数外，还要增加系数并且修改rfft_task.cmd命令文件。
通过data.pjt完成一个64点FFT程序，输入信号为一正弦波。
操作步骤如下：
（1）进入CCS环境。
（2）打开CCS选择File—New—Source File。
（3）编写源程序代码。
（4）创建工程文件。
（5）点击Project选择Build Options。
（6）在弹出的对话框在设置相应的编译参数，一般情况下，按默认值就可以。（7）在弹出的对话框中选择连接的参数设置，设置传输文件、堆栈的大小以及初始化的方式。
（8）点击Project—Build all，对工程进行编译。
（9）点击File—load program，弹出的对话框中载入debug文件夹下的.out可执行文件。
（10）点击debug—Go M ain回到C程序的入口。
（11）运行程序，观察结果。
4.2程序运行结果
验证输入数据波形，设置参数：Start Address=0x2800，Page=Data，Acquisition Buffer Size=64，Display Data Size=64，DSP Data Type=32-bit signed integer
点击OK，就可以看到输入数据波形：
图4.2.1输入数据波形
全速运行程序，看输出结果，设置波形对话框参数：Start Address=0x2c80，Page=Data，Acquisition Buffer Size=64，Display Data Size=64，DSP Data Type=16-bit signed integer
点击OK，就可以看到FFT输出结果：
图4.2.2 FFT输出结果
第5章总结
DSP芯片具有的特殊软硬件结构和指令系统，使其能高速处理各种数字信号处理算法。并在过程中进一步提高自身的创作、创新水平，扎实基础，扩展所学。并且此次课程设计，基于课程理论知识和网上资料，使我FFT的实现有了更深一步的了解和掌握，对利用CCS软件编程的数字信号处理方法有了进一步的了解。在理论课的基础上进行实验实习，是对本门课程的深入学习和掌握。这样一个课程设计对我们的发展有着极大的帮助！课程设计不仅是对前面所学知识的一种检验，而且也是对自己能力的一种提高。通过这次课程设计使我明白了自己原来知识还比较欠缺，学习是一个长期积累的过程，在以后的工作、生活中都应该不断的学习，努力提高自己知识和综合素质。刚开始时，拿着选定的题目不知如何下手。毕竟课程设计不同于实验课，电路图都要自己设计。静下心来，仔细分析题目，再加上指导老师的说明与提示，心中才有了谱。将整个系统根据不同的功能化分成模块，再分别进行设计，逐个攻破，最后将其整合即可。
回顾起此课程设计，至今我仍感慨颇多，从理论到实践，在这段日子里，可以说得是苦多于甜，但是可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。在设计过程中，我通过查阅大量有关资料，与同学交流经验和自学，并向老师请教等方式，使自己学到了不少知识，也经历了不少艰辛，但收获同样巨大。幸亏老师与同学的帮助，一步步解决了困难。在整个设计中我懂得了许多东西，也培养了我独立工作的能力，树立了对自己工作能力的信心，相信会对今后的学习工作生活有非常重要的影响。而且大大提高了动手的能力，使我充分体会到了在创造过程中探索的艰难和成功时的喜悦。虽然这个设计做的也不太好，但是在设计过程中所学到的东西是这次课程设计的最大收获和财富，使我终身受益。
在此感谢刘伟春老师的细心认真的辅导，让我对DSP有了更深的了解，掌握了一些分析问题和解决问题技巧的方法，同时让我对电路设计有了更好的把握。让我对DSP这门课程有了更深刻的认识，让我对独立做课程设计有了信心，这次课程设计才能顺利完成。
参考文献
[1]戴明桢等编著.TMS320C54X DSP 结构原理及应用. 北京：航空航天大学出版社，第2版，2007；
[2]彭启琮编著.DSP技术的发展与应用.北京：高等教育出版社，2002；
[3]胡广书编著.数字信号处理理论、算法与实现.北京：清华大学出版社，2005；
[4]北京合众达电子技术有限公司编著.SEED-DTK系列实验手册.北京合众达电子技术有限公司出版，2007。
附录源程序
#include "stdio.h"
#include "math.h"
main()
{
int i;
float f[256];
FILE *fp;
if((fp=fopen("d:\\tms320c54\\fft\\sindata", "wt"))==NULL)
{
printf("can't open file!\n");
exit(0);
}
for(i=0;i<=255;i++)
{
f[i]=sin(2*3.1415926*i/256.0);
fprintf(fp, ".word %ld\n",(log)(f[i]*16384));
}
fclose(fp);
}
将生成的数据文件复制到目标系统存储器的语句为d_input .copy sindata 汇编语言程序：
.title "fft.asm"
.mmregs
.include "coeff.inc"
.include "in.inc"
.def start
sine: .usect "sine",512
cosine: .usect "cosine",512
fft_data: .usect "fft_data",1024
fft_out: .usect "fft_out",512
STACK .usect "STACK",10
K_DATA_IDX_1 .set 2
K_DATA_IDX_2 .set 4
K_DATA_IDX_3 .set 8
K_TWID_TBL_SIZE .set 512
K_TWID_IDX_3 .set 128
K_FLY_COUNT_3 .set 4
K_FFT_SIZE .set 64
K_LOGN .set 6
PA0 .set 0
.bss d_twid_idx,1
.bss d_data_idx,1
.bss d_grps_cnt,1
.sect "fft_prg"
.asg AR2,REORDERED
.asg AR3,ORIGINAL_INPUT
.asg AR7,DATA_PROC_BUF
start: SSBX FRCT
STM #STACK+10,SP
STM #sine,AR1
RPT #511
MVPD #sine1,*AR1+
STM #cosine,AR1
RPT #511
MVPD cosine1,*AR1+
STM #d_input,ORIGINAL_INPUT
STM #fft_data,DATA_PROC_BUF
MVMM DATA_PROC_BUF,REORDERED
STM #K_FFT_SIZE-1,BRC ·
RPTBD bit_rev_end-1
STM #K_FFT_SIZE,AR0
MVDD *ORIGINAL_INPUT+,*REORDERED+
MVDD *ORIGINAL_INPUT-,*REORDERED+
MAR *ORIGINAL_INPUT+0B
bit_rev_end:
.asg AR1,GROUP_COUNTER
.asg AR2,PX
.asg AR3,QX
.asg AR4,WR
.asg AR5,WI
.asg AR6,BUTTERFLY_COUNTER
.asg AR7,STAGE_COUNTER
STM #0,BK
LD #-1,ASM
STM #fft_data,PX
STM #fft_data+K_DATA_IDX_1,QX
STM K_FFT_SIZE/2-1,BRC
LD *PX,16,A
RPTBD stage1end-1
STM #K_DATA_IDX_1+1,AR0
SUB *QX,16,A,B
ADD *QX,16,A
STH A,ASM,*PX+
ST B,*QX+
||LD *PX,A
SUB *QX,16,A,B
ADD *QX,16,A
STH A,ASM,*PX+0%
ST B,*QX+0%
||LD *PX,A
stage1end:
STM #fft_data,PX
STM #fft_data+K_DATA_IDX_2,QX
STM #K_FFT_SIZE/4-1,BRC
LD *PX,16,A
RPTBD stage2end-1
STM #K_DATA_IDX_2+1,AR0
SUB *QX,16,A,B
ADD *QX,16,A
STH A,ASM,*PX+
ST B,*QX+
||LD *PX,A
SUB *QX,16,A,B
ADD *QX,16,A
STH A,ASM,*PX+
STH B,ASM,*QX+
MAR *QX+
ADD *PX,*QX,A
SUB *PX,*QX-,B
STH A,ASM,*PX+
SUB *PX,*QX,A
ST B,*QX
||LD *QX+,B
ST A,*PX
||ADD *PX+0%,A
ST A,*QX+0%
||LD *PX,A
stage2end:
STM #K_TWID_TBL_SIZE,BK
ST #K_TWID_IDX_3,d_twid_idx
STM #K_TWID_IDX_3,AR0
STM #cosine,WR
STM #sine,WI
STM #K_LOGN-2-1,STAGE_COUNTER
ST #K_FFT_SIZE/8-1,d_grps_cnt
STM
#K_FLY_COUNT_3-1,BUTTERFLY_COUNTER
ST #K_DATA_IDX_3,d_data_idx stage:
STM #fft_data,PX
LD d_data_idx,A
ADD *(PX),A
STLM A,QX
MVDK d_grps_cnt,GROUP_COUNTER group:
MVMD BUTTERFLY_COUNTER,BRC
RPTBD butterflyend-1
LD *WR,T
MPY *QX+,A
MAC *WI+0%,*QX-,A
ADD
PX,16,A,B ;B:=(QR*WR+QI*WI)+PR
ST
B,*PX ;PR':=((QR*WR+QI*WI)+PR)/2
||SUB *PX+,B
ST B,*QX
||MPY *QX+,A
MAS *QX,*WR+0%,A
ADD *PX,16,A,B
ST B,*QX+
||SUB *PX,B
LD *WR,T
ST B,*PX+