FFT在嵌入式系统上的实现

FFT在嵌入式系统上的实现吴杰摘要：FFT在信号处理方面有的独特的优势，本文通过对FFT的研究完成了FFT算法C语言实现，并基于Matlab及TMS320的实验结果证实了程序的正确性和可行性。关键词：FFTMatlabTMS320FPGA1引言FFT，即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。对于在计算机系统或者说数字系统中应用离散傅立叶变换，有了巨大的进步，FFT使得傅氏变换应用于实际硬件系统成为可能。自20世纪FFT问世以来，人们对它的探索就没有停止，其在通信、工程控制、空间探索、军事各个方面都有着巨大的应用，因此FTT被称为信号处理的领袖。近年来随着科技的进步，在通信领域，在消费类电子领域，无论是3G网络，数字电视、电话，还是手持设备如手机、PDA、GPS、MP4，对数据尤其是语音图像的处理的要求越来越高，因此就需要人们对信号处理系统进行进一步的研究与提高，这就对现有系统提出了三点要求：1.快速处理数据的能力2.便于携带，成本低3.兼容性无论通信还是语音视频图像处理，都需要快速、同步，因此需要对信号数据的处理快速的完成；同时系统需要便携，消费类电子的发展使得人们需要在手上看电视，而不是背着电视或电脑；同时系统需要与现有的系统兼容，包括软硬件两个方面。综合以上考虑，FFT和嵌入式系统如ARM的结合无疑是一种满意的方案。FFT本身的快速处理数据的能力与小巧而资源丰富的嵌入式结合无疑能满足这些要求，同时现有嵌入式系统的发展使得我们可以容易的与现有其他系统兼容，如可以采用嵌入式Linux系统，这样可以很方便的实现与现有环境的结合与升级。总之，FFT在嵌入式系统上的实现，实现了信号处理快速算法与便携硬件、内核、嵌入式系统的紧密结合，对其进行研究与实现无疑有着重大的意义。2FFT算法的C语言实现我们知道N点FFT运算可以分成LOGN2级，每一级都有N/2个碟形。DITFFT的基本思想是用3层循环完成全部运算(N点FFT)。第一层循环：由于N=2m需要m级计算,第一层循环对运算的级数进行控制。第二层循环：由于第L级有2L-1个蝶形因子（乘数），第二层循环根据乘数进行控制，保证对于每一个蝶形因子第三层循环要执行一次，这样，第三层循环在第二层循环控制下，每一级要进行2L-1次循环计算。第三层循环：由于第L级共有N/2L个群，并且同一级内不同群的乘数分布相同，当第二层循环确定某一乘数后，第三层循环要将本级中每个群中具有这一乘数的蝶形计算一次，即第三层循环每执行完一次要进行N/2L个碟形计算。可以得出结论：在每一级中，第三层循环完成N/2L个碟形计算；第二层循环使第三层循环进行2L-1次，因此，第二层循环完成时，共进行2L-1*N/2L=N/2个碟形计算。实质是：第二、第三层循环完成了第L级的计算。几个要注意的数据：①在第L级中，每个碟形的两个输入端相距b=2L-1个点。②同一乘数对应着相邻间隔为2L个点的N/2L个碟形。③第L级的2L-1个碟形因子WPN中的P，可表示为p=j*2m-L，其中j=0，1，2，...，（2L-1-1）。用C语言实现如下：voidfft(){inti=0,j=0,k=0,l=0;complexup,down;bitrev();for(i=0;ilog2_of(size_x);i++)//i为阶数i=log2_of(N)=0,1,2,3,...,(v-1){/*一级蝶形运算*/l=(1i);//l=1,2,4,8,...,2^(v-1)蝶形运算两点间距离for(j=0;jsize_x;j+=(1l)){/*一组蝶形运算*/for(k=0;kl;k++){/*一个蝶形运算*/mul(x[j+k+l],W[size_x*k/2/l],&up);add(x[j+k],up,&up);mul(x[j+k+l],W[size_x*k/2/l],&down);sub(x[j+k],down,&down);x[j+k]=up;x[j+k+l]=down;}}}}3MATLAB实现FFT算法的仿真通过测试用例结果的对比可以看出一般情况下FFT对于信号的影响。3.1输入信号及过程定义x=pi/(N_STEP/2)*[0:N_STEP-1];%x=0..2piinN_FFTpointsy=sin(5*x)+2*cos(10*x);%SignalY=fft(y,N_FFT);%FFTP=Y.*conj(Y);%abs(Y).^2;3.2测试用例对比图1正弦信号和一个余弦信号的图2增加fft的点数正弦信号和一个余弦信号的叠加图1中第1个图是原始时域信号。第2个图（右上）就是fft变化后的频谱的图。图3（左下）是实际的频谱。图4是图3的半对数坐标。图1中的步长（step）即数据点数和fft点数是一致的。如果增加fft的点数（分辨率resolution）那就相当于把原始数列加补足的0项（因为实际处理的数据很可能不是正好fft的点数），图2中增加了fft的点数。图2中第1个图（左上）是原始信号，第2个图（右上）就是fft变化后的频谱的图，由于增加了fft的点数，这样一来，由采样引起了毛刺似的东西。第3、4图是对这种效应的处理--加窗，类似于一种滤波器，它的作用是减少因采样引起的误差。第6个图就是加了窗后的最终效果虽然还是又噪声但是相对第2个图已经好很多了。第1个图的信号其实就是两个频率信号的叠加，所以最后在频域上就应该得到两个峰。图2这个例子是知道了输入信号的特征才可以得出的模拟。如果不知道输入信号的情况，那处理的结果就不知道是否有问题。所以图2相当于考虑兼容性，是信号处理的一般流程。当然我们可以把图2中的输入信号换成声音或者视频，例如我们加入了噪音，实验结果见图3。图3这个时候第1个图（左上）里面就是噪音了，如果是视频信号，则就是雪花。可以加滤波器来处理，显然在频域处理才是方便的、直观的。比如图2中输入信号叠加函数为：y=sin(5*x)+2*cos(10*x);假设其中的2*cos(10*x)是噪声项。在图2的第6个图中得到的频域就是右面的那个峰,那只要把右面的这个峰给去掉,再ifft回去,原来的信号就好多了.4FFT算法的移植算法移植在CodeComposerStudio中完成，基于TMS320调试成功，完成后工程中包含的所有文件如图4所示：图4工程中主要文件的作用如下：库文件：RTS.LIB,作用：提供主文件的函数。头文件：board.h,type.h作用：提供主文件中的宏定义部分。汇编文件：Bit_rev.asm、Fft.asm、Initcfft.asm、Power.asm、Rfft.asm、Unpack.asm、Vectors.asm。Bit_rev.asm：第一步，对最原始的输入数据进行位翻转后的从新排序。Initcfft.asm：设置变量、缓存和平台。Rfft.asm：进行函数调用，把FFT计算按步骤组合起来。Vectors.asm：设置中断向量。Fft.asm：第二步，对翻转后的数据进行FFT计算。Unpack.asm：第三、四步，把输入数据分成实数的偶数部分RP[k]，实数的奇数部分RM[k]，虚数的偶数部分IP[k]和虚数的奇数部分IM[k]，计算出RFFT。Power.asm：第五步，用来做计算结果的输出。输入如图5的正弦信号，输出的波形如图6所示。图5正弦输入1.dat图6输出波形对照3.2中的测试用例，可以看出，试验结果和Matlab模拟结果基本一致。我们进行与DSK相连接的实验，我们可以通过A/D，D/A的转换把输入信号进行FFT变换。图7输入波形a图8输入波形b图9输出波形c计算一下系统的采样率：f(s)/N=采样频率即为2048Hz/1024）=2Hz，可以说明在输出时横坐标轴上的每两点之间的数值为2，我们看到输出波形c的的横坐标为8，8与采样频率相乘应为输入波形b中的横坐标值，这可以判断出我们计算的FFT结果是正确的。5应用效果分析把信号生产的数据输入到MS320里面的fft处理输出的数据和MATLAB的数据比较看，FFT算法调试成功。FFT运算结果的精度与输入数据的位数及运算过程中的位数有关,同时和数据的表示形式也有很大关系。一般来说,浮点方式比定点方式精度高。而在定点计算中,存储器数据的位数越大,运算精度越高,使用的存储单元和逻辑单元也越多。在实际应用中,应根据实际情况折衷选择精度和资源。本设计通过MATLAB进行仿真证明：其实现的变换结果与MATLAB工具箱中的FFT函数相比,信噪比可以达到65db以上,完全可以满足一般工程的实际应用要求。考虑速度等一些列因素，可以直接基于MS320直接做个示波器，实时信号进去，频谱就出来，设置一下就处理。直接就可以放到FPGA上面，直接可进入市场销售。参考文献[1]丁玉美,高西全.数字信号处理[M].西安电子科技大学出版社,1995.[2]赵曙光.可编程逻辑器件原理开发和应用[M].西安电子科技大学出版社,2001.