DSP-应用实例分析-课件（精品）.pptVIP

8.3 快速傅里叶变换（FFT）的C54X实现方法 8.3.1 FFT基本原理 快速傅里叶变换（FFT）是离散傅里叶变换（DFT）的快速算法，FFT是数字信号处理中最为重要的算法之一，在声学、语音、电信和信号处理等各个领域都有广泛的应用，FFT也成为DSP运算能力的一个考核因素。离散傅里叶变换的目的是把信号由时域变换到频域，从而可以在频域分析处理信息，得到的结果再由傅里叶逆变换到时域。本实例介绍基2按时间抽取的FFT的基本原理及其实现方法，程序基于C54X系列DSP。下面首先介绍FFT基本原理。 式中（有时简写为W）代表。不难看出，是周期性 的，且周期为N，即 来说，由DFT的定义可以看出，在为复数序列的情况下，直接运算N点DFT需要次复数乘法和次复数加法。因此，对于一些相当大的N值（如1024点）来说，直接计算它的DFT的计算量是很大的。一个优化的实数FFT算法是一个组合以后的算法。原始的2N个点的实输入序列组合成一个N点的复序列，然后对复序列进行N 点的FFT运算，最后再由N点复数输出拆散成2N点的复数序列，这2N点的复数序列与原始的2N点的实数输入序列的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算法来计算实输入序列的DFT的速度几乎是一般复FFT算法的两倍。假定序列的点数是2的整数次幂，按上述处理方法， 定义为 因考虑到 可写成： 上式表明，N点DFT可分解为按上式的规则加以组合的两个（N/2）点DFT。如果直接计算（N/2）点的DFT，则不难看出，计算N点DFT需要（N2/2+N）次复数乘法。在N值很大的情况下，这表示可以节约一半左右的计算时间。下面用流程图来说明两个4点DFT变换计算8点DFT的处理方法。计算流程如图8.19所示。输入序列先进行位倒序成偶数项和奇数项得到 对于64点的FFT运算，基于上述的思想，可以将64个点分为32个点，32个点也可继续分为16个点，如此继续分下去，一直分到最基本的两点傅里叶变换，如图8.20所示。 由此可得出8点基2FFT的流程图，如图8.21所示。由图8.21可推出任意2的整数次幂的FFT的流程图。 8.3.2 FFT的C语言实现 由于DSP程序需要首先使用高级语言来模拟算法性能，这里首先给出使用标准C语言实现的时间抽取FFT算法，整个程序编写过程如下。 1. 首先定义一个复数结构。 struct compx {double real，imag}； 2. 定义一个输入数据序列。 struct compx xin[N－1]； 定义N+1为数组长度，是为了以后运算从1开始，方便循环参数的变化。 3. 定义两个复数相乘 struct compx EE(struct compx b1，struct compx b2) { struct compx b3： b3.real=b1.real*b2.real－b1.imag*b2.imag： b3.imag=b1.real*b2.imag+b1.imag*b2.real： return (b3)： } 4. 定义位反函数。 void displace(void)： { …… nv2=N/2： for(i=1：i=nm1：i++) { if(ij) {t=xin[j]：xin[j]=xin[i]：xin[i]=t：} k=nv2： while(kj){j=j－k：k=k/2： { if(ij) {t=xin[j]：xin[j]=xin[i]：xin[i]=t：} k=nv2： while(kj){j=j－k：k=k/2： } j=j+k： } 5. 定义FFT变换的函数。 void FFT(void) {…… for(l=1：l=m：l++) { lt=pow(2，1)： lei=le/2 pi=3 v.real=1.0：v.imag=0.0： w.real=cos(pi/lei)：w.imag=－sin(pi/lei)： for(j=