快速傅立叶变换fft程序设计

《快速傅立叶变换fft程序设计》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、快速傅立叶变换（FFT）程序设计DFT(DiscreteFourierTransformation)是数字信号分析与处理，如图形、语音及图像等领域的重要变换工具，直接计算DFT的计算量与变换区间长度N的平方成正比。当N较大时，因计算量太大，直接用DFT算法进行谱分析和信号的实时处理是不切实际的。快速傅立叶变换(FastFourierTransformation，简称FFT)使DFT运算效率提高1—2个数量级，其原因是当N较大时，对DFT进行了基4和基2分解运算。FFT算法利用DFT系数的对称性、周期性和可约性等性质将长序列的DFT分解

2、为若干个短序列的DFT计算，然后再按一定规则将其合并，从而得到整个的DFT。按时间抽取的基2FFT算法是FFT最常用的一种表现形式。设（=2）点序列的离散傅立叶变换为，则有：(1)(2)式中：=0,1，……,；=0,1,……,。将(=0,1,……,)按的奇偶分成以下两组：将上式带入(1)式并化简，就得到(3)和(4)式。这样N点序列就变为两个点序列和离散傅立叶变换的组合：(3)(4)式中：=0,1,……,，其中(3)式和(4)式可以用下面的碟形节信号流图图1来表示。图12点碟形节对于和可以继续利用(3)和(4)式进一步分解，直到分解为

3、对应图1的基本的两点变换为止。现以8点序列的FFT为例，通过其碟形流图来分析它的数字特点（图2）。图28点按时间抽选法FFT运算流图通过分析，不失一般性，可以得到点序列FFT碟形图的特点如下。这里需要说明的是下面所提到的“同种碟形”即具有相同碟形节系数()的基本两点碟形。(1)点碟形图共有级()(2)对于第()级①不同种基本碟形的种数；②相邻不同种基本碟形的碟形节系数的增量；③同种基本碟形的个数；④相邻同种基本碟形的间距；⑤每个基本碟形中两接点的间距；(3)输入序列为倒序排列，输出序列为自然序排列。为了说明这个特点，将输入输出序列的序

4、号变为2进制，列表1比较。表1输入倒序和输出正序对照表x(n)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)000100010110001101011111X(k)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)000001010011100101110111从表1中不难看出所谓倒序排列就是指序列的2进制表示的序号采用高位加1并且反向进位方式递增的排列。所以在进行FFT之前要对输入序列进行处理，是输出序列按正序排列。简易程序流程图如图3所示：图3FFT程序流程图FFT程序及说明N.set512.glo

5、bal_resave.global_input;存放FFT运算中用到的数据,按二进制反序排列.global_indatr;512点FFT所需数据;------------------------------------------------------------------;反序排列子程序部分;------------------------------------------------------------------_resave：MAR*，AR3LARAR2，#_inputLARAR3，#_indatrLARAR0，#N

6、LARAR4，#(N-1)RESAV1LACC*+，0，AR2SACL*BR0+，AR4BANZRESAV1，*-，AR3MAR*，AR1SBRK#2LARAR0，*-PSHD*RET;------------------------------------------------------------------;FFT应用子程序;------------------------------------------------------------------N.set512;点数M.set9;N=2^M_input.usect

7、".data0"，2*N;输入数据.bss_sintab，N;SIN和COSIN函数的存储表.bss_nom，1;当_nom=1时，FFT需要归一化处理，为0时则不需要.global_fft.global_sintab.global_input.global_nom.text_fft：;--------------------------------------;与C语言兼容的代码部分;--------------------------------------POPD*+;存储返回地址ADDRESSSARAR6，*+;存储AR6SA

8、RAR7，*+;存储AR7SARAR0，*+;存储AR0SARAR1，*;堆栈分布情况：ADDRESS/AR6/AR7/AR0/AR1;ARP=AR1，AR1：AR1LARAR0，#08hLARAR3，*0+，AR3;A