一种FFT算法的设计和实现

 

　　傅里叶变换能将满足一定条件的某个函数表示成三角函数（正弦和/或余弦函数）或者它们的积分的线性组合。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。初傅里叶分析是作为热过程的解析分析的工具被提出的。信号的一些特性在时域总是表现得不明显，通过傅里叶算法，将其变换到频域，其特性就一目了然。

    在计算机系统中，实际上是以离散傅立叶变换(DFT)的方式处理数据。由于DFT的运算量比较大，并不适用于嵌入式控制系统，所以实际应用中常使用DFT 的快速算法一快速傅立叶变换(FFT)。虽然FFT 比DFT的计算量减少了很多，但用普通单片机来实现FFT多点、实时运算还是比较困难的。DSP(数字信号处理器)具有运算速度快和高的特点，恰好满足FFT的要求，能较好地解决这个问题。

　　数字信号处理（Digital Signal Processing,简称DSP）是一门涉及许多学科而又广泛应用于许多领域的新兴学科。20世纪60年代以来，随着计算机和信息技术的飞速发展，数字信号处理技术应运而生并得到迅速的发展。数字信号处理是一种通过使用数学技巧执行转换或提取信息，来处理现实信号的方法，这些信号由数字序列表示。在过去的二十多年时间里，数字信号处理已经在通信等领域得到极为广泛的应用。德州仪器、Freescale等半导体厂商在这一领域拥有很强的实力。其工作原理是接收模拟信号，转换为0或1的数字信号。再对数字信号进行修改、删除、强化，并在其他系统芯片中把数字数据解译回模拟数据或实际环境格式。它不仅具有可编程性，而且其实时运行速度可达每秒数以千万条复杂指令程序，远远超过通用微处理器，是数字化电子世界中日益重要的电脑芯片。它的强大数据处理能力和高运行速度，是值得称道的两大特色。

　　1 快速傅里叶变换的原理

    非周期性连续时间信号x(t)的傅里叶变换可以表示为

 

  

 

    式中计算出来的是信号x(t)的连续频谱。但是，在实际的控制系统中能够得到的是连续信号x(t)的离散采样值x(nT)。因此需要利用离散信号x(nT)来计算信号x(t)的频谱。

    有限长离散信号x(n)，n=0，1，…，N-1的DFT定义为：

  

 

    可以看出，DFT需要计算大约N2次乘法和N2次加法。当N较大时，这个计算量是很大的。利用WN的对称性和周期性，将N点DFT分解为两个N／2点的 DFT，这样两个N／2点DFT总的计算量只是原来的一半，即(N／2)2+(N／2)2=N2／2，这样可以继续分解下去，将N／2再分解为N／4点 DFT等。对于N=2m 点的DFT都可以分解为2点的DFT，这样其计算量可以减少为(N／2)log2N次乘法和Nlog2N次加法。图1为FFT与DFT-所需运算量与计算点数的关系曲线。由图可以明显看出FFT算法的优越性。

　　Drive Fitness Test 驱动器健康检测技术，是IBM公司为其PC赢哦俺开发的数据保护技术，它通过使用DFT程序访问IBM硬盘里的DFT微代码对硬盘进行检测，可以让用户方便快捷地检测硬盘的运转状况。DFT微代码可以自动对错误事件进行登记，并将登记数据保存在硬盘的保留区域中。DFT微代码还可以实时对硬盘进行物理分析，如通过读取伺服位置错误信号来计算出盘片交换、伺服稳定性、重复移动等参数，并给出图形供用户或技术人员参考。这是一个全新的观念，硬盘子系统的控制信号可以被用来分析硬盘本身的机械状况。

    将x(n)分解为偶数与奇数的两个序列之和，即

 

  

 

    x1(n)和x2(n)的长度都是N／2，x1(n)是偶数序列，x2(n)是奇数序列，则

 

   

 

    其中X1(k)和X2(k)分别为x1(n)和x2(n)的N／2点DFT。由
于X1(k)和X2(k)均以N／2为周期，且WN k+N/2=-WN k，所以X(k)又可表示为：

 

 

   
    上式的运算可以用图2表示，根据其形状称之为蝶形运算。依此类推，经过m-1次分解，将N点DFT分解为N／2个两点DFT。图3为8点FFT的分解流程。

 

 

    FFT算法的原理是通过许多小的更加容易进行的变换去实现大规模的变换，降低了运算要求，提高了与运算速度。FFT不是DFT的近似运算，它们完全是等效的。

　　2 快速傅里叶算法在TMS320LF2407上的实现

    根据FFT算法的特点，处理器要在一个指令周期内完成乘和累加的工作，因为复数运算要多次查表相乘才能实现。其二就是间接寻址，可以实现增／减1个变址量，方便各种查表方法。再次，FFT变换的输入序列x(n)是按所谓的码位倒序排列的，处理器要有反序间接寻址的能力。DSP控制器专门设计了特有的反序间接寻址，并能在一个指令周期内完成乘和累加的运算。因此，对数字信号的分析处理，DSP比其它的处理器有的优势。本文采用TI公司C2000系列TMS320LF2407芯片来实现FFT算法。

    TMS320LF2407定点DSP是一款专为工业控制、电机控制和数字信号处理等用途而设计的DSP，具备单周期乘加指令，具有FFT反序间接寻址功能，运行速度为40MIPS。为了充分利用DSP芯片特有的反序间接寻址等功能，FFT算法程序采用汇编语言编写，主程序采用C语言，因此程序具有良好的兼容性和可扩展性。

    主程序流程图如图4所示。系统初始化主要完成DSP的系统控制和状态寄存器、等待状态发生器控制寄存器、中断寄存器等的必要设置。

    本程序采样函数为：x=sin(20πt)，采样频率为640Hz。

    输入数据波形如图5所示。一般情况下，我们只关心信号频域的幅度谱。幅度谱|X(k)|2的计算：X(k)=XR(k)+jX(k)，|X(k)2|=|Xr(k)|2+|Xi(k)|2。FFT计算结果的信号幅度谱|X(k)|2如图6所示。

    输入信号频率是10Hz，根据公式f=kfs／N，f是原始信号的频率，k表示峰值出现的位置，fS是采样频率，N是计算的点数，从幅度谱中看出，峰值出现在k=1处，那么，f=1×640／64=10，与原始信号的实际频率一致，说明计算结果正确。

 

 

　　3 快速傅里叶变换（FFT）的应用

　　FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。

    FFT在生产实践和科学研究中有着广泛的应用。图7为FFT的典型应用方案。下面简单介绍一下FFT的应用领域。

 

 

    (1)频谱分析。对各类旋转机械、电机、机床等机器的主体或部件进行实际运行状态下的频谱分析，可以提供设计数据和检验设计结果，或者找寻震源和诊断故障，保证设备的安全运行等。在声纳系统中，为了寻找海洋水面船只或潜艇，需要对噪声信号进行频谱分析，以提供有用信息，判断舰艇运行速度、方向、位置、大小等。

    (2)滤波。滤波是FFT广泛的应用，它使对波形的频率分量滤波变得十分简单。比如对采样信号进行FFT后，去掉不需要的频率分量，再进行FFT反变换，就得到滤波后的期望信号。

    (3)电力监控系统的谐波分析。电力监控系统的谐波分析，需要对采样数据进行FFT运算，然后通过液晶屏或其它人机界面重新绘画出来，以方便技术人员掌握电力的质量。

　　4 总结

    实验证明，此程序在TMS320LF2407定点DSP中运行良好，速度快且运算结果十分可靠，其用于一般的信号处理和工业控制都能满足和实时的要求，具有较高的学术价值和良好的应用前景。其次，掌握FFT，学会在空域和频域中同时思考问题，很多时候可以让我们使用简单的方法来解决复杂的问题。