快速傅里叶变换（FFT）的DSP实现
（天津大学电子信息工程学院）
摘要：本文介绍了快速傅里叶变换（FFT）的快速高效的原理及实现方法，对快速傅立叶变换（FFT）的特点进行了研究和总结。对于快速傅立叶变换（FFT） 在TMS320C54X系列数字信号处理器（DSP）实现中出现的计算溢出等问题进行了分析并提出了解决方法，同时据此使用DSP实现了快速傅立叶变换（FFT）。 关键词：数字信号处理；快速傅立叶变换；反序；计算溢出
1 引言：
傅里叶变换是一种将信号从时域变换到频域的变换方式，在语音处理、图像处理、信号处理领域中都发挥了极大的作用，是一种重要的分析工具。离散傅里叶变换（DFT）是连续傅里叶变换在离散系统中的表现形式，具有非常广泛的应用。但是由于DFT的计算量很大，因此在很长一段时间里其应用受到限制。快速傅里叶变换（FFT）是实现普通离散傅里叶变换的一种高效方法，快速傅里叶变换（FFT）的出现使得傅里叶变换在实际中得到了广泛的应用。
快速傅里叶变换并不是一种新的变换，它是离散傅里叶变换的一种快速算法。它是DSP领域中的一项重大突破。由于考虑了计算机和数字硬件实现的约束条件，研究了有利于机器操作的运算结构，使DSP的计算时间缩短了一到两个数量级，还有效的减少了计算所需的存储容量，FFT技术的应用极大的推动了DSP的理论的技术的发展。
本文中使用的是由TI公司生产的TMS320C54系列的DSP。C54x系列DSP具有很高的操作灵活性和速度。它具有一个先进的修正哈佛结构、专门硬件逻辑的CPU、片内存储器、片内外设和专用的指令集、将C54xCPU和片内存储器与外设配置组合在一起的螺旋结构。这使得该系列可以满足电子市场众多领域的应用要求。
2 DSP在数字信号处理中的优势：
数字信号处理是一门广泛应用于许多领域的新兴学科。20世纪60年代以来，随着计算机和信息技术的飞速发展，数字信号处理技术应用而生并得到迅速广泛的应用。数字信号处理算法运算量大,需要执行大量的乘累加运算。并且常具有某些特定模式，大部分处理时间花在执行相对小循环的操作上。与此同时，还要求处理芯片有专门的接口，具有很高的数据吞吐能力。
DSP芯片，也称数字信号处理器，其特殊的结构可以用来快速的实现各种数字信号处理算法。DSP芯片一般具有如下的主要特点：
（1）在一个指令周期内可完成一次乘法和一次加法。 （2）程序和数据空间分开，可以同时访问指令和数据。
（3）片内具有快速RAM，通常可通过独立的数据总线同时访问两块芯片。 （4）具有低开销或无开销循环及跳转的硬件支持。 （5）快速的中断处理和硬件I/O接口支持。
（6）具有在单周期内操作的多个硬件地址产生器。 （7）可以并行执行多个操作。
（8）支持流水线结构，使取指、译码、取操作数和执行等操作可以重叠执行。
1
3 离散傅立叶变换（DFT）及快速傅里叶变换（FFT）的原理：
离散傅立叶变换可由如下的公式表示出来： X(k)=
N?1n?0?x?n?WknNknN k=0,1,2,…..,N-1
式中，W?e?2???j??kn?N??cos(2?kn2?kn)?jsin() 0?k,n?N?1 NN由于计算一个X(k)值需要N次复数乘法和（N-1）次复数加法，因而计算N个X(k)的值，需要N次复数乘法和Ｎ(N-1)次复数加法。每次复数乘法包括４次实数乘法和２次实数加法，每次复数加法包括两次实数加法，因此计算Ｎ点的DFT共需要４＊N次实数乘法和2N(2N-1)次实数加法。当Ｎ很大时，运算量是很可观的，因此需要使用改进的快速DFT
算法。
快速傅立叶变换（FFT）的基本原理：FFT算法是基于可以将一个长度为Ｎ的序列的离散傅立叶变换逐次分解为较短的离散傅立叶变换来计算这一基本原理的。本文中将使用的是按时间抽取（Decimation-in-Time）的基２FFT算法。使用N/2点DFT的方式获得FFT计算公式如下式：
N/2?122X(k)??r?0x1(r)WrkN/2?WkNN/2?1r?0?x(r)W2rkN/2rk?X1(k)?WN/2X2(k)
k?1,1,2,......,N?1从上式可知，X1(k)和X2(k)的计算分别需要2?N/2?次复数乘法和N(N-2)/2次复数
k加法，而WNX2(k)的计算需要N/2次复数乘法，所以共需要N2?N/2次复数乘法。每
2??次复数乘法包括４次实数乘法和２次实数加法，每次复数加法包括两次实数加法。所以需要
2?N2?N?次实数乘法和2N2?N次实数加法。从乘法和加法的计算量看，FFT算法的计
算量在N较大时相对于DFT算法来说大大减小。
如果继续这个过程，将N点的DFT分解为log2N个DFT，则最后的运算要求Nlog2N次复数乘法运算，比原N次的复数乘法大大降低了运算量（特别对于较大的N）。一个N=8点的FFT运算按照这种方法来计算FFT，可以用下图表示：
24 快速傅里叶变换的DSP实现：
针对C54系列DSP的算法是基2的按时间抽取(DIT)算法。该算法主要分为四步：输入数据的组合和位倒序；N点复数FFT；分离复数FFT的输出为奇部分与偶部分；产生最后的复数结果，以及为防止数据溢出而进行的归一化。
2
开始，最初的2N个实数输入序列保存在4N字的数据处理缓冲区的底部一半。下面按照这四个步骤分别进行说明。
（1）输入数据的组合和位倒序
把输入序列作位倒序，是为了在整个运算最后的输出中得到的序列是自然序列。
首先，将原始输入的2N个点的实数序列复制到相应的存储单元，当成N点的复数序列。存放顺序为实部、虚部。这个过程称为组合。然后对复数序列进行位倒序排序。在用汇编指令执行位码倒置寻址可以大大提高程序执行速度和使用存储器的效率。
（2）实现N点复数FFT
N点复数FFT算法实现可分为三个功能模块，即第一级蝶形运算、第二级蝶形运算、第三级至log2N级蝶形运算。对于任何一个2的整数幂N =2 ，总可以通过M次分解最后为2点的DFT计算，通过这样的M次分解，可以构成M(即log2N)级迭代计算，每级由N／2个蝶形运算组成。每个蝶形运算可由基本迭代运算完成。设蝶形输入为Xm?1(p)和
m
Xm?1(q)，输出
Xm(p)=Xm?1(p)+ Xm?1(q)，
Xm(q)=Xm?1(p)—Xm?1(q)，
式中，m为第m列迭代；p和q为数据所在的行数。在进行运算的过程中，为了避免运算结果的溢出，对于每个蝶形的运算结果右移一位。
在FFT的运算过程中要用到旋转因子，它是一个复数，可表示为
knWN?e?2???j??kn?N??cos(2?kn2?kn)?jsin()，由此可见，可将旋转因子分成正弦和余弦两NN部分。为了实现旋转因子的运算，在存储空间分别建立正弦表和余弦表。旋转因子是以Q15
的格式储存在两个分开的数据表中。每一个表包含有512个值，角度范围从0到?左右。对旋转因子表的存取是通过C54x的一种特殊的寻址方式一—循环寻址进行的，因此，同一个旋转因子表可适应于不同点数的FFT的运算。
（3）分离复数FFT的输出为奇部分与偶部分
分离FFT输出为相关的四个序列：RP、RM、IP、IM，即偶实数、奇实数、偶虚数和奇虚数四部分，以便下一步形成最终结果。对上一阶段的N点复数输出数据D(K)进行运算重组。方法为：
RP[k]=RP[N—k]=0.5*(R[k]+R[N-k])；
RM Fk]=-RM[N—k]=0.5*(R[k]一R[N-k])； IP[k]=IP[N—k]=0.5*(I[k]+I[N—k])； IM[k]= - IM[N—k]=0.5*(I[k]—I[N—k])； RP[0]=R[0]； IP[0]=I [0]；
RM[0]=IM[0]=RM[N/2]=IM[N/2]=0； RP[N/2]=R[N/2]； IP[N/2]=I[N/2]；
3
对应于2N点实输入序列的2N点FFT复输出序列的形成： 利用序列RP[k]，RM[k] IP[k]和IM[k]，按下面等式计算实输入序列a(n)的FFT的输出： AR[k]：AR[2N—k]=RP[k]+COS(k?/N)*IP[k]—sin(k?/N)*RM[k] AI[k]= - AI[2N—k]=IM[k] —COS(k?/N)*RM[k]—sin(k?/N)*IP[k] AR[0]=RP[0]+IP[0]； AI[0]=IM[0]+RM[0]； AR[N]=R[0] — I[0]； AI[N]=0
其中：A[k]=A[2N-k]=AR[k]+j AI[k]=F{a(n)} （4）功率谱计算
由于最后所得的FFT数据是一个复数，为了能方便的在虚拟频谱仪上观察该信号的特征，通常对所得的FFT数据进行处理——取其实部和虚部的平方和，以求得该信号的功率。
（5）FFT实现中的溢出
由于所选用的C54系列的开发板是定点的DSP，因而在用其实现FFT时，应考虑防止中间结果产生溢出的问题。解决这个问题的方法就是对中间数值进行归一化。2点的碟形节可以用下式表示：
KPm?1?Pm?WNQm KQm?1?Pm?WNQm
式中：Pm和Qm是第m级碟形节的两节点；Pm?1和Qm?1是第m+1级碟形节的两节点，且设：
Pm?PRm?jPIm Qm?QRm?jQIm
KWN?e?j2?k/N?cos(2?k/N)?jsin(2?/N)
经过整理后得到：
Pm?1?PRm?URm?j(PIm?UIm) Qm?1?PRm?URm?j(PIm?UIm)
在用DSP实现时，为了计算方便，一般都把输入归一化为QI5表示，即输入的实部和虚部的幅度都小于1。考虑到大多数情况下是实数序列的FFT，所以其最大幅度不超过2，这样可以在每一级用2归一化。运用DSP芯片的移位特性来实现2的归一化，不增加任何运算量。
经归一化后得到：
PRm?URmPI?UIm?jm
22PRm?URmPI?UImQm?1??jm
22Pm?1?实验证明此方法可有效地防止在实现过程中的溢出问题。
4
利用上述运算法则，经过编程，将模拟的输入数据输入到程序，运算结果完全正确，并可在CCS(code composer studio)(DSP软件开发平台)下利用其绘图功能观察到输入输出波形。
5 结束语
数字信号处理算法的特点是对大量数据进行相同的操作，实时性强。DSP芯片是专为信号处理而设计的，是解决实时处理要求的单片可编程微处理器芯片。DSP芯片的出现使数字信号处理算法的实现变得更为方便。它使用灵活，用于实现信号处理任务时，与一般微处理器相比，其速度更快、效率更高，是实现FFT的一种相当理想的工具。
参考文献：
[1] 李健，等. TMS320C54xDSP应用程序设计教程[M] . 北京: 机械工业出版社，2004. [2] 丁玉美，高西全. 数字信号处理[M] . 西安: 西安电子科技大学出版社，2000.
5