TMS320C5502基于DSP的FFT编程设计(5)
信号处理用于诊断检查较为成功的实例，有脑电或心电的自动分析系统、断层成像技术等。断层成像技术是诊断学领域中的重大发明。X射线断层的基本原理是X射线穿过被观测物体后构成物体的二文投影。接收器接收后，再经过恢复或重建，即可在一系列的不同方位计算出二文投影,经过运算处理即取得实体的断层信息,从而大屏幕上得到断层造像。信号处理在生物医学方面的应用正处于迅速发展阶段。
数字信号处理在其他方面还有多种用途，如雷达信号处理、地学信号处理等，它们虽各有其特殊要求，但所利用的基本技术大致相同。在这些方面，数字信号处理技术起着主要的作用。
1.3 DSP设计目的及内容
加深对DFT算法原理和基本性质的理解，熟悉FFT的算法原理和FFT子程序的算法流程和应用，学习用FFT对连续信号和时域信号进行频谱分析的方法；学习DSP中FFT的设计和编程思想，，实现FFT运算，对输入信号进行频谱分析。
2 FFT算法分析
2.1 FFT设计原理
快速傅氏变换（FFT）是一种高效实现离散傅氏变换的快速算法，是数字信号处理中最为重要的工具之一，它在声学、语音、电信、和信号处理等领域有着广泛的应用。
对于有限长离散数字信号{x[n]}，0 n N-1，其离散谱{x[k]}可以由离散付氏变换（DFT）求得。可以方便的把它改写为如下形式：
不难看出，WN是周期性的，且周期为N，即
N的周期性是DFT的关键性质之一。为了强调起见，常用表达式WN取代W以便明确其周期是N。
即W ＝e ，称为蝶形因子式旋转因子。
对于旋转因子W 来说，有如下的对称性和周期性：
对称性：W ＝－W 周期性：W ＝W
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运算的情况。
FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的
图2.1蝶形运算
发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。
设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次复数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+N^2/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。
下一篇：视觉导引车控制系统硬件设计