《快速傅里叶变换算法原理综述》1400字

快速傅里叶变换算法原理第9页（共22页）快速傅里叶变换算法原理综述1.1傅里叶变换早在1822年，傅里叶（法国数学家）提出了具有深远影响的傅里叶级数，其明确指出，所有处于连续状态的周期信号，均能够进行相应分解，最终可以将若干正弦函数之和给求出来。在具体的频域上，主要用其来对位离散非周期所对应的相关信号进行表示。需要强调的是，傅里叶变换理论能够借助数学公式的推导，将傅里叶级数逐一计算出来。在特定时域区间[t0，t0+T]上的一个可积函数，可用如下公式来表示傅里叶级数：ft=a02其中：an=2Ttbn=2Tt同时，需要说明的是，连续非周期连续时间信号f(t)傅里叶正/反变换可用如下公式来进行表示：F(jω)=-∞∞f(t)ft=12Π-∞最后，依据所输入信号的差异，可将傅里叶变换划分成多种类型：其一为周期性离散时间信号傅里叶变换，其二是周期性连续时间信号傅里叶变换，其三为非周期性连续时间信号傅里叶变换，其四则为非周期性离散时间信号傅里叶变换。各个变换所对应的输入信号如图7所示。图7.四种不同类型的输入信号示意图FPGA实现机械扫描成像声呐的数据处理第10页（共22页）1.2离散傅里叶变换（DFT）针对离散傅里叶变换来考量，实际就是依据已知晓的傅里叶变换值，围绕有限长序列傅里叶变换，以一种合理、高效且规范的方式再次实施有限次点采样，将信号频域进行离散化，因此，即便是在频域中的信号，同样能借助数字运算方法来实施处理，可以提高信号的处理效率和灵活度。在处理信号过程中，对于DFT的相关计算来讲，同样有着十分关键的地位，许多信号的频谱，滤波以及相关性都可以使用这种方法来计算。其中，对离散时间信号f(n)的连续傅里叶变换可以由以下表示：F(ejω)=n=0由上式可以看出，频域内的变量为连续变量，无法在计算机中进行数字计算，所以必须对其进行频谱离散化，最后就可以得到DFT的计算表示为：Fk=n=0N-1若将上式中的e-j2ΠN定义为WNFk=n=0N-1则离散傅里叶反变换的定义就为下式：fn=1N通常，可以将式(3-2-3)和式(3-2-4)称为离散傅里叶变换对。快速傅里叶变换算法原理第11页（共22页）1.3快速傅里叶变换（FFT）对于FFT来考量，实际就是借助WN因子所对应的周期性，结合DFT快速算法来进行各项工作。针对FFT算法来讲，实际就是基于长序列的DFT，然后对其实施相应分解，使其最终成为短序列的DFT；从物理层面来分析，其实际就是一个比较特殊的模拟信号，经ADC采样处理后，便会向数字信号转换；需要强调的是，经采样而最终得到的数字信号，同样可进行FFT变换。为了使FFT运算变得更加简便，一般情况下，N需要取2的整数次方,这样可以使计算量减小许多REF_Ref71530028\r\h[13]。此外，利用旋转因子的特性即可以减少DFT的运算次数REF_Ref71530041\r\h[14]，使DFT在其所有的运算过程中进行简化，形成一系列迭代运算的过程REF_Ref71530062\r\h[15]，使用的比较多的方法便是基2FFT算法。针对2FFT算法来分析，其能够将原先比较长的序列进行分解，使之成为若干短序列，然后在逐一实施DFT运算；此外，通过对WkN的周期性、对称性展开合理化、优质化的合并，便能实现DFT相应运算次数的减少。其中，周期性与对称性可以分别表示为：周期性：WNk还需指出的是，可将基2FFT算法划分成两种类型，一种是时域抽取法 FFT（简称为DIT-FFT），另外一种则为频域抽取法FFT（DIF-FFT），本文根据总体设计需要，最终选择的是时域抽取法FFTREF_Ref71530080\r\h[16]。首先，通过对n的奇、偶数进行准确区分，分解长序列，使之成为2个有着相同长度的子序列。f1k=f2kf2k=f(2k+1)然后分别对这两个子序列进行DFT运算可以得到两个离散的序列，F1K=n=0N/2fF2K=n=0N/2f利用旋转因子的周期性和对称性，进行多项式的转换与求和。FK=F1KFK+N2=F最后便可以N点DFT分为N/2点的DFT，即蝶形运算REF_Ref71530111\r\h[17]，其有助于计算次数的大幅减少REF_Ref71530116\r\h[18]。但需强调的是，伴随N的持续增大，FFT算法与DFT