基于DSP的FFT算法的实现
摘要
数字信号处理（Digital Signal Processing，简称DSP）是一门涉及许多学科而又广泛应用于许多领域的新兴学科。DS P有两种含义：Digital Signal Processing（数字信号处理 ）、Digital Signal Processor（数字信号处理器）。数字信号处理是利用计算机或专用处理设备，以数字形式对信号进行采集、变换、滤波、估值、增强、压缩、识别等处理，以得到符合人们需要的信号形式。
DSP芯片的出现使FFT的实现方法变得更为方便。由于大多数DSP芯片都具有在单指令周期内完成乘法—累加操作，并且提供了专门的FFT指令，使得FFT算法在DSP芯片实现的速度更快。FFT算法的运算时间是衡量DSP芯片性能的一个重要指标，因此提高FFT算法的运算速度是非常重要的。在用DSP芯片实现FFT算法时，应允许利用DSP芯片所提供的各种软、硬件资源。如何利用DSP芯片的有限资源，合理地安排好所使用的存储空间是十分重要的。
关键词：数字信号处理 FFT算法
Abstract
Digital signal processing (DSP) is involves many disciplines and widely applies in the many domain emerging disciplines. DSP has two kinds of meanings: digital Signal Processing, Digital Signal Processor.The digital signal processing uses the computer or the special-purpose handling equipment, carries compressing and so on gathering, transformation, filter, estimating, value, enhancement, compression, recognition by the digital form ,to obtain the signal form which the people need.
The appearance of DSP chip makes the realization method of FFT becomes more convenient. Since most DSP chips are multiplying and accumulating operations in a single instruction period, and provides a special FFT instruction, the FFT algorithm in the DSP chip to achieve faster.FFT algorithm is an important index to measure the performance of DSP chips, is very important to improve the operation speed of the FFT algorithm. The realization of FFT algorithm in DSP chip, all should be allowed provided by DSP soft, the hardware resources. Limited resources how to use DSP chip, reasonably arrange the storage space used is very important.
Keyword: Digital signal processing FFT algorithm
目 录
第一章 设计思路.....................................................................................1
1.1 DSP芯片介绍.....................................................................................1
1.2 FFT算法的DSP结构 .......................................................................2
第二章 设计原理 ....................................................................................4
2.1 快速傅里叶变换FFT的原理 ...........................................................4
2.2 FFT算法的实现 ................................................................................6
第三章 仿真器调试及模拟结果............................................................ 7
3.1 调试步骤........................................................................................... 7
3.2 模拟仿真结果....................................................................................9
第四章 设计结论...................................................................................12
4.1 心得体会...................... ...................................................................12
参考文献 ................................................................................................13
第一章 设计思路
1.1 DSP芯片介绍
DSP芯片的内部采用程序和数据分开的哈佛结构，具有专门的硬件乘法器，广泛采用流水线操作，提供特殊的DSP指令，可以用来快速的实现各种数字信号处理算法。
C55X数字信号处理器是在C54X的基础上发展起来的新一代低功耗、高性能数字信号处理器。C55X采用了新的半导体工艺，时钟和功耗比C54X系列都有很大的提高，CPU内部增加了大量的功能单元从而增强了DSP的运算能力，相比C54X系列具有更高的性能和更低的功耗。这些特点使之在无线通信领域、电子消费领域、便携式个人数字系统领域以及数字语音压缩电话系统和图像编解码系统中得到更加广泛的应用。
TMS320VC5509A是一款以C55X的CPU为内核的定点DSP芯片。它有两种封装形式，一种是采用144个引脚的塑料四方扁平（LQFP）封装形式；另一种是采用179引脚的球栅阵列（BGA）封装形式。我们实验用的是第一种144个引脚的。
TMS320VC5509A引脚按其功能可分为并行总线引脚、中断和复位引脚、位输入
/输出信号引脚、多通道缓冲串口引脚、I2C引脚、USB引脚、A/D引脚、测试引脚、和电源引脚等几部分。
图1.1 TMS320VC5509A芯片及引脚
1.2 FFT算法的DSP结构
DSP芯片的出现使FFT的实现方法变得更为方便。由于大多数DSP芯片都具有在单指令周期内完成乘法—累加操作，并且提供了专门的FFT指令，使得FFT算法在DSP芯片实现的速度更快。
FFT运算时间是衡量DSP芯片性能的一个重要指标，因此提高FFT的运算速度是非常重要的。在用DSP芯片实现FFT算法时，应允许利用DSP芯片所提供的各种软、硬件资源。如何利用DSP芯片的有限资源，合理地安排好所使用的存储空间是十分重要的。
DSP处理器中的运算/处理功能单元主要包括以下几个部分：
乘法器/乘加器（MAC）、算术逻辑运算单元（ALU）、移位器、数据地址发生器（DAG）、程序定序器、存储器。由于FFT算法主要用到的是乘法器/乘加器（MAC）,所以在这里叙述乘法器/乘加器（MAC）的功能。
在通用微处理器中，乘法是由软件实现的，它其实是由时钟控制的一连串“移位—加法”操作。而对于DSP乘法器，则应具有以下基本基本功能：要求在一个时钟周期里对两个字长为b位的输入由硬件作快速并行乘法；应能通过格式控制来执行无符号或带符号或混合的乘法操作、小数或整数乘法操作以及扩展精度或双精度运算，并有合适的舍位方法；应有输入和输出寄存器，这样可以锁存数据，配合流水线操作。也可不用寄存器，使乘法器在透明方式下工作，这样可以有最小的等待时间。
在数字信号处理的滤波器、FFT、卷积及各种矢量运算中，由于要执行Σb(n)*x(n - k)一类的运算，这类运算的乘法和加法总是同时出现，因此DSP中就希望将乘法器和加法器相结合，在一个时钟周期完成一次乘、加运算，并且累加乘法运算的结果。这样的运算单元称为乘法累加器。
对于乘法累加器，除了要求能在一个时钟周期完成一次乘、加运算外，为了在累加时保证运算精度，还应在累加输出寄存器中包括足够的保护位，因其在2b位的乘法输出宽度之外，所以称为扩展位。扩展位中的逻辑应该能用来预测累加器的溢出，并且能紧急通知作重新定标度操作，即防溢出处理。
第二章 设计原理
2.1 快速傅里叶变换FFT的原理
FFT 并不是一种新的变换，它是离散傅立叶变换（DFT）的一种快速算法。由于我们在计算 DFT 时一次复数乘法需用四次实数乘法和二次实数加法；一次复数加法则需二次实数加法。每运算一个X（k）需要 4N次复数乘法及 2N+2（N-1）=2（2N-1）次实数加法。所以整个 DFT运算总共需要 4N^2 次实数乘法和 N*2(2N-1)=2N(2N-1)次实数加法。如此一来，计算时乘法次数和加法次数都是和 N^2 成正比的，当 N很大时，运算量是可观的，因而需要改进对 DFT 的算法减少运算速度。
其中旋转因子WN 有如下的特性。
对称性： WNk+N/2=-WNk
周期性：WNn(N-k)=WNk(N-n)=WN-nk
利用这些特性，既可以使DFT中有些项合并，减少了乘法积项，又可以将长序列的DFT分解成几个短序列的DFT。FFT就是利用了旋转因子的对称性和周期性来减少运算量的。例如：N为偶数时，先将N点的DFT分解为两个N/2点的DFT，使复数乘法减少一半：再将每个N/2点的DFT分解成N/4点的DFT，使复数乘又减少一半，继续进行分解可以大大减少计算量。最小变换的点数称为基数，对于基数为2的FFT算法，它的最小变换是2点DFT。
由于对称性，WNk+N/2=-WNk。因此，N点DFT可分为两部分：
前半部分：x(k)=x1(k)+WkNx2(k) k=0,1,…,N/2-1 （1）
后半部分：x(N/2+k)=x1(k)-WkNx2(k) k=0,1,…,N/2-1 （2）
从式（1）和式（2）可以看出，只要求出0~N/2-1区间x1(k)和x2(k)的值，就可求出0~N-1区间x(k)的N点值。以同样的方式进行抽取，可以求得N/4点的DFT，重复抽取过程，就可以使N点的DFT用上组2点的 DFT来计算，这样就可以大减少运算量。
在基数为2的FFT中，设N=2M，共有M级运算，每级有N/2个2点FFT蝶形运算，因此，N点FFT总共有MN/2个蝶形运算。在该实验中，程序中将抽样点数N为128，FFT算法进行了7级运算，每级有64个2点FFT蝶形运算，因此，128点FFT总共有448个蝶形运算。
例如：基数为2的FFT，当N=8时，共需要3级，12个基2 DIT FFT的蝶形运算。其信号流程如图2.1所示。
x(0) X(0)
1.
x(4) X(1)
-1
WN0
x(2) X(2)
-1
WN0 WN2
x(6) X(3)
-1 -1
WN0
x(1) X(4)
-1
WN0 WN1
x(5) X(5)
-1 -1
WN0 WN2
x(3) X(6)
-1 -1
WN0 WN2 WN3
x(7) X(7)
-1 -1 -1
图2.1 8点基2 按时间抽取的FFT蝶形运算
时间抽取FFT算法的输入是倒位序的，输出是自然顺序的，在运算之前，要通过变址计算将自然顺序转换成倒位序，然后再输入。
2.2 FFT算法的实现
FFT算法可以分为按时间抽取FFT和按频率抽取FFT两大类，输入也有实数和复数之分，一般情况下，都假定输入序列为复数。
用TMS320C5509A的c语言程序实现FFT算法主要分为四步：
1.实现输入数据的比特反转
输入数据的比特反转实际上就是将输入数据进行码位倒置，以便在整个运算后的输出序列是一个自然序列。在用汇编指令进行码位倒置时，使用码位倒置可以大大提高程序执行速度和使用存储器的效率。在这种寻址方式下，AR0存放的整数N是FFT点的一半，一个辅助寄存器指向一个数据存放的单元。当使用位码倒置寻址将AR0加到辅助寄存器时，地址将以位码倒置的方式产生。
2.实现N点复数FFT
N点复数FFT算法的实现可分为三个功能块，即第一级蝶形运算、第二级蝶形运算、第三级至级蝶形运算。
对于任何一个2的整数幂，总可以通过M次分解最后成为2点的DFT计算。通过这样的M次分解，可构成M（即）级迭代计算，每级由N/2个蝶形运算组成。
3.功率谱的计算
X(k)一般是由实部(k)和虚部(k)组成的复数，即
X（k）=(k)+j(k)
因此，计算功率谱时只需将FFT变换好的数据，按照实部实部(k)和虚部(k)求它们的平方和，然后对平方和进行开平方运算。
4.输出FFT结果
第三章 仿真器调试及模拟结果
3.1 调试步骤
第一步：打开CCS 软件
第二步：切换工作目录到CCS4 程序文件夹（目录不能包含中）
第三步：导入工程（按照图片的顺序操作）
CCS 窗口菜单栏【Project | Import existing CCS/CCE Eclipse Project】选项用于打开已存在的工程，【Import existing CCS/CCE Eclipse Project】选项用于打开CCS v3.3 的工程。
注意在“copy projects into workspace”前打勾，这样就会将项目复制到CCS 程序文件夹下面，则项目就会复制到该文件下。点击打开后，默认设置点击Next，然后点击Finish。
第四步：设为活动工程，链接仿真器配置文件
选择一个工程文件，在工程文件处点击右键，选择“Set as Active Project”
在工程文件处点击右键，选择“Link Files to Project”
仿真器使用的是“MingWei_XDS100”，在“MingWei_XDS100.ccxml”处点击右键选择“Set as Active Target Configuration”和“Set as Default Target Configuration”，然后再双击“MingWei_XDS100.ccxml”，
第五步：运行TI 在线调试,连接仿真器
点击“Target/Launch TI Debugger”完成后连接仿真器，
点击“Target/Connect Target”,然后再点击“Target/Load Program”,注意查找相应的.out文件，程序加载成功后出现如下图所示：
出现“source out found”点击“locate the source file”后查找fft文件，点击“确定”。再点“run”的图标，进行运行。
3.2 模拟仿真结果
运行完成后，再进行Graph设置：
点击“Tools/Graph/Single Time”进行设置。如下所示：
设置Acquisition Buffer Size为128，Dsp Data Type 为16位的整型，Start Address为INPUT，Display Data Size为128得到INPUT的波形图如下所示:
设置Acquisition Buffer Size为64，Dsp Data Type 为16位的整型，Start Address为DATA，Display Data Size为64，得到如下频谱图 ：
点击“Tools/Graph/FFT Magnitude”设置FFT Order为10，得到如下频谱图：
第四章设计结论
4.1心得体会
通过这次DSP课程设计，让我加深对DFT算法原理和基本性质的理解，更加熟悉了FFT的算法原理和FFT子程序的算法流程和应用，掌握了DSP中FFT的设计和编程思想，以及用FFT对连续信号和时域信号进行频谱分析的方法，和使用CCS的波形观察器观察波形和频谱情况。
此次课程设计，在绘制原理图时，对各个元器件的绘制还比较熟练，但对各个DSP芯片的引脚不太熟悉，但通过查找该方面的阅读资料，让我了解到DSP芯片的各个引脚的功能。在仿真器调试的过程，有时会出现无法连接到芯片板上，此时可能是该板已经坏掉，或者是接触不良的原因，按照指导书上的步骤进行操作，得出相应的模拟仿真结果。通过CCS软件中的TOOLS的GRAPH设置相应的参数来观察INPUT输入波形以及通过FFT算法运算后的频谱图。对比参数设置的不同，从而得到的不同的频谱图，分析频谱图的变化，来更加深刻地认知该波形观察器和设置的参数的涵义。
参考文献
1. 彭启琮等，DSP技术的发展与应用，第二版，高等教育出版社，2007
2. 邹彦，DSP原理及应用，第1版，电子工业出版社，2006
3．张雄伟，DSP集成开发与应用实例，第1版，电子工业出版社，2002
4. 张洪涛、万红、杨述斌，数字信号处理，第一版，华中科技大学出版社，2007
5. 董胜、刘柏生，DSP技术及应用，北京大学出版社，2013.3
6. 代少升、黄俊、申敏等，DSP原理及其应用，高等教育出版社，2010.12