FFT原理

DFT变换则说明对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息。所以只要时间序列足够长，采样足够密，频域采样也就可较好地反映信号的频谱趋势，所以FFT可以用以进行连续信号的频谱分析。当然，这里作了几次近似处理：1）用离散采样信号的傅立叶变换来代替连续信号的频谱，只有在严格满足采样定理的前提下，频谱才不会有畸变，否则只是近似；2）用有限长序列来代替无限长离散采样信号。 线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:将长为N2的序列x(n)延长到L,补L-N2个零将长为N1的序列h(n)延长到L,补L-N1个零如果L≥N1+N2-1,则圆周卷积与线性卷积相等,此时,可有FFT计算线性卷积,方法如下:a.计算X(k)=FFT[x(n)]b.求H(k)=FFT[h(n)]c.求Y(k)=H(k)Y(k) k=0～L-1d.求y(n)=IFFT[Y(k)] n=0～L-1可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。计算表明,L>32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性,因此,也称上述圆周卷积方法为快速卷积法 信号是实数序列,任何实数都可看成虚部为零的复数,例如,求某实信号y(n)的复谱,可认为是将实信号加上数值为零的虚部变成复信号(x(n)+j0),再用FFT求其离散付里叶变换。这种作法很不经济,因为把实序列变成复序列,存储器要增加一倍,且计算机运行时,即使虚部为零,也要进行涉及虚部的运算,浪费了运算量。合理的解决方法是利用复数据FFT对实数据进行有效计算,下面介绍两种方法。（1）一个N点FFT同时计算两个N点实序列的DFT设x1(n),x2(n)是彼此独立的两个N点实序列,且X1(k)=DFT[x1(n)]，X2(k)=DFT[x2(n)]可通过一次FFT运算同时获得X1(k),X2(k)。算法如下：首先将x1(n),x2(n)分别当作一复序列的实部及虚部,令x(n)=x1(n)+jx2(n)通过FFT运算可获得x(n)的DFT值 X(k)=DFT[x1(n)]+jDFT[x2(n)]=X1(k)+jX2(k)利用离散付里叶变换的共轭对称性X1(K)=1/2*[X(k)+[X(N-k)共轭]]X2(K)=1/2*[X(k)-[X(N-k)共轭]]有了x(n)的FFT运算结果X(k),由上式即可得到X1(k),X2(k)的值。

基础原理讲述：FFT（快速傅里叶变换）：FFT算法是DFT算法的改良版，而DFT是FFT的离散化。理解FFT，就从傅里叶变换到DFT再到FFT的思路进行推导。笔者也会按照这样的思路进行讲解推导。傅里叶变换：傅里叶变换是傅里叶级数的推广，所以在谈傅里叶变换之间，先说一下傅里叶级数。在大学期间学习无穷级数有相关基础的同学可以跳着看。傅里叶级数：傅里叶级数是把类似波的函数表示成简单正弦波的方式，更严肃来说的话：对于满足狄利克雷定理的周期函数，其傅里叶级数是由一组简单的振荡函数加权和表示的，表示周期函数为正弦波和余弦波之和。和或谐波（谐波频率是原周期信号频率整数倍的波），可以用谐波分析开确定每一个谐波的相位和幅度。傅里叶级数中就可能有无限谐波数。对于函数的傅里叶级数的部分但不是所有的谐波求和会产生该函数的近似值，例如：傅里叶级数前几个谐波用于方波就会产生方波的近似值。方波（表示为蓝点）近似为其第六部分和（表示为紫点），由方波傅里叶级数的前六项（表示为箭头）求和形成。每个箭头从其左侧所有箭头的垂直总和开始（即先前的部分总和）方波的傅立叶级数的前四个部分和。随着更多谐波的添加，部分和会收敛到（变得越来越像）