《FFT原理与实现》由会员分享，可在线阅读，更多相关《FFT原理与实现（8页珍藏版）》请在金锄头文库上搜索。
1、FFT原理与实现在数字信号处理中常常需要用到离散傅立叶变换(DFT),以获取信号的频域特征。尽管传统的DFT算法能够获取信号频域特征，但是算法计算量大，耗时长,不利于计算机实时对信号进行处理。因此至DFT被发现以来,在很长的一段时间内都不能被应用到实际的工程项目中，直到一种快速的离散傅立叶计算方法FFT，被发现，离散是傅立叶变换才在实际的工程中得到广泛应用。需要强调的是，FFT并不是一种新的频域特征获取方式，而是DFT的一种快速实现算法。本文就FFT的原理以及具体实现过程进行详尽讲解。DFT计算公式其中x(n)表示输入的离散数字信号序列，WN为旋转因子，X(k)组N点组成的频率成分的相对幅度。
2、一般情况下，假设x(n)来自于低通采样，采样频率为fs，那么X(k)表示了从-fs/2率开始，频率间隔为fs/N,到fs/2-fs/N截至的N个频率点的相对幅度。因为DFT计算得到的一组离散频率幅度只实际上是在频率轴上从成周期变化的，即X(k+N)=X(k)。因此任意取N个点均可以表示DFT的计算效果，负频率成分比较抽象，难于理解，根据X(k)的周期特性，于是我们又可以认为X(k)表示了从零频率开始，频率间隔为fs/N,到fs-fs/N截至的N个频率点的相对幅度。N点DFT的计算量根据(1)式给出的DFT计算公式，我们可以知道每计算一个频率点X(k)均需要进行N次复数乘法和N-1次复数加法，计
3、算N各点的X(k)共需要NT次复数乘法和N*(N-1)次复数加法。当x(n)为实数的情况下，计算N点的DFT需要2*NA2次实数乘法，2*N*(N-1)次实数加法。旋转因子WN的特性1. W的对称性N(砂炉)=吋2. W的周期性N3. W的可约性N根据以上这些性质，我们可以得到式(5)的一些列有用结果傑曲=卩带氐=胖，网捫=_1月普恥二_硝(5)基-2FFT算法推导假设采样序列点数为N=2L,L为整数，如果不满足这个条件可以人为地添加若干个0以使采样序列点数满足这一要求。首先我们将序列x(n)按照奇偶分为两组如下：于是根据DFT计算公式(1)有：#X(k)=DFTX)J=2N-Lii为偶数N-
4、l.ii*奇数=兀(曲+兀)砒NHNTlr=0=工(2训驚+x(2r+l)W?-0AV2-1.V/2-1=工x(2吨+砒Vx(2r+l)2丿=0zOAT/2-lA-/2-1E心)唏+吟力x(2r+l)r=Or=O2-1Nil-1(7)r=0r=0工兀(W議-叱S兀(讪議至此，我们将一个N点的DFT转化为了式(7)的形式，此时k的取值为0到N-1,现在分为两段来讨论，当k为0N12-1的时候，因为x1(r),x2(r)为N/2点的序列，因此，此时式(7)可以写为：X(k)=X(k)+WXi(k)Zr=(LN2l(8)而当k取值为N/2N-l时，k用k+N/2取代，k取值为0N/2-1。对式化简可
5、得：()N/2-1N/2-lZW)临j-0叱丄(口)A-/2-1-v(/XbX(?)jr(x(o)斗门)亠DFTDFT图28点DFT的4点分解根据公式(10),个N点的DFT可以由两个N/2点的DFT运算构成，再结合图1的蝶形信号流图可以得到图2的8点DFT的第一次分解。该分解可以用以下几个步骤来描述：1. 将N点的输入序列按奇偶分为2组分别为N/2点的序列2. 分别对1中的每组序列进行DFT变换得到两组点数为N/2的DFT变换值X1和X23. 按照蝶形信号流图将2的结果组合为一个N点的DFT变换结果根据式(10)我们可以对图2中的4点DFT进一步分解，得到图3的结果，分解步骤和前面一致。最后
6、对2点DFT进一步分解得到最终的8点FFT信号计算流图：图38点DFT的全分解从图2到图3的过程中关于旋转系数的变化规律需要说明一下。看起来似乎向前推一级，在奇数分组部分的旋转系数因子增量似乎就要变大，其实不是这样。事实上奇数分组部分的旋转因子指数每次增量固定为1，只是因为每向前推进一次，该分组序列的数据个数变少了，为了统一使用以原数据N为基的旋转因子就进行了变换导致的。每一次分组奇数部分的系数WN,这里的N均为本次分组前的序列点数。以上边的8点DFT为例，第一次分组N=8,第二次分组N为4，为了统一根据式(4)进行了变换将N变为了8,但指数相应的需要乘以2。N点基-2FFT算法的计算量从图3
7、可以看到N点DFT的FFT变换可以转为log2(N)级级联的蝶形运算，每一级均包含有N/2次蝶形计算。而每一个蝶形运算包含了1次复数乘法，2次复数加法。因此N点FFT计算的总计算量为：复数乘法N/2xlog2(N)复数加法Nxlog2(N)。假设被采样的序列为实数序列，那么也只有第一级的计算为实数与复数的混合计算，经过一次迭代后来的计算均变为复数计算，在这一点上和直接的DFT计算不一致。因此对于输入序列是复数还是实数对FFT算法的效率影响较小。一次复数乘法包含了4次实数乘法，2次实数加法，一次复数加法包含了2次复数加法。因此对于N点的FFT计算需要总共的实数乘法数量为：2xNxlog2(N)；
8、总的复数加法次数为：2xNxlog2(N)。FFT是离散傅立叶变换的快速算法，可以将一个信号变换到频域。有些信号在时域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。这就是很多信号分析采用FFT变换的原因。另外，FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。虽然很多人都知道FFT是什么，可以用来做什么，怎么去做，但是却不知道FFT之后结果是什意思、如何决定要使用多少点来做FFT。现在圈圈就根据实际经验来说说FFT结果的具体物理意义。一个模拟信号，经过ADC采样之后，就变成了数字信号。采样定理告诉我们，采样频率要大于信号频率的两倍，这些我就不在此罗嗦了。采
9、样得到的数字信号，就可以做FFT变换了。N个采样点，经过FFT之后，就可以得到N个点的FFT结果。为了方便进行FFT运算，通常N取2的整数次方。假设采样频率为Fs,信号频率F,采样点数为N。那么FFT之后结果就是一个为N点的复数。每一个点就对应着一个频率点。这个点的模值，就是该频率值下的幅度特性。具体跟原始信号的幅度有什么关系呢？假设原始信号的峰值为A,那么FFT的结果的每个点(除了第一个点直流分量之外)的模值就是A的N/2倍。而第一个点就是直流分量，它的模值就是直流分量的N倍。而每个点的相位呢，就是在该频率下的信号的相位。第一个点表示直流分量(即OHz),而最后一个点N的再下一个点(实际上这
10、个点是不存在的，这里是假设的第N+1个点，也可以看做是将第一个点分做两半分，另一半移到最后)则表示采样频率Fs,这中间被N-1个点平均分成N等份，每个点的频率依次增加。例如某点n所表示的频率为：Fn=(n-1)*Fs/N。由上面的公式可以看出，Fn所能分辨到频率为为Fs/N，如果采样频率Fs为1024Hz，采样点数为1024点，则可以分辨到1Hz。1024Hz的采样率采样102点，刚好是1秒，也就是说，采样1秒时间的信号并做FFT，则结果可以分析到1Hz,如果采样2秒时间的信号并做FFT,则结果可以分析到0.5Hz。如果要提高频率分辨力，则必须增加采样点数，也即采样时间。频率分辨率和采样时间是
11、倒数关系。假设FFT之后某点n用复数a+bi表示，那么这个复数的模就是An-根号a*a+b*b，相位是Pn=atan2(b,a)。根据以上的结果，就可以计算出n点(nfl且n=N/2)对应的信号的表达式为：An/(N/2)*cos(2*pi*Fn*t+Pn)，即2*An/N*cos(2*pi*Fn*t+Pn)。对于n=1点的信号，是直流分量，幅度即为A1/N。由于FFT结果的对称性，通常我们只使用前半部分的结果，即小于采样频率一半的结果。好了，说了半天，看着公式也晕，下面圈圈以一个实际的信号来做说明。假设我们有一个信号，它含有2V的直流分量，频率为50Hz、相位为-30度、幅度为3V的交流信号
12、，以及一个频率为75Hz、相位为90度、幅度为1.5V的交流信号。用数学表达式就是如下：S=2+3*cos(2*pi*50*t-pi*30/180)+1.5*cos(2*pi*75*t+pi*90/180)式中cos参数为弧度，所以-30度和90度要分别换算成弧度。我们以256Hz的采样率对这个信号进行采样，总共采样256点。按照我们上面的分析，Fn=(n-l)*Fs/N，我们可以知道，每两个点之间的间距就是1Hz，第n个点的频率就是n-1。我们的信号有3个频率：OHz、50Hz、75Hz，应该分别在第1个点、第51个点、第76个点上出现峰值，其它各点应该接近0。从图中我们可以看到，在第1点、
13、第51点、和第76点附近有比较大的值。我们分别将这三个点附近的数据拿上来细看：1 点：512+0i2 点：-2.6195E-14-1.4162E-13i3 点：-2.8586E-14-1.1898E-13i50 点：-6.2076E-13-2.1713E-12i51 点：332.55-192i52 点：-1.6707E-12-1.5241E-12i75 点：-2.2199E-13-1.0076E-12i76 点：3.4315E-12+192i77 点：-3.0263E-14+7.5609E-13i很明显，1点、51点、76点的值都比较大，它附近的点值都很小，可以认为是0，即在那些频率点上的信号
14、幅度为0。接着，我们来计算各点的幅度值。分别计算这三个点的模值，结果如下：1点：51251点：38476点：192按照公式，可以计算出直流分量为：512/N=512/256=2；50Hz信号的幅度为：384/(N/2)=384/(256=3；75Hz信号的幅度为192/(N/2)=192/(256/2)=1.5。可见，从频谱分析出来的幅度是正确的。然后再来计算相位信息。直流信号没有相位可言，不用管它。先计算50Hz信号的相位，atan2(-192,332.55)=-0.5236,结果是弧度，换算为角度就是180*(-0.5236)/pi=-30.0001。再计算75Hz信号的相位，atan2(192,3.4315E-12)=1.5708弧度，换算成角度就是180*1.5708/pi=90.0002。可见，相位也是对的。根据FFT结果以及上面的分析计算，我们就可以写出信号的表达式了，它就是我们开始提供的信号。总结：假设采样频率为Fs，采样点数为N,做FFT之后，某一点n(n从1开始)表示的频率为：Fn=(n-1)*Fs/N；该点的模值除以N/2就是对应该频率下的信号的幅度(对于直流信号是除以N)；该点的相位即是
