fft原理
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。
- 中文名 fft原理
- 外文名 FFT principle
- 类型 运算公式
基本原理
FFT是一种DFT的高效算法，称为快速傅立叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。
运算方式
式中
由这种方法计算DFT对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中
的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。
FFT基本上可分为两类，时间抽取法和频率抽取法，而一般的时间抽取法和频率抽取法只能处理长度N=2^M的情况，另外还有组合数基四FFT来处理一般长度的FFT
fft原理 时间抽取
设N点序列x(n),N=2^M,将x(n)按奇偶分组，公式如下图
改写为：
一个N点DFT分解为两个 N/2点的DFT，
FFT应用
FFT计算IDFT
DFT变换则说明对于时间有限的信号（有限长序列），也可以对其进行频域采样，而不丢失任何信息。所以只要时间序列足够长，采样足够密，频域采样也就可较好地反映信号的频谱趋势，所以FFT可以用以进行连续信号的频谱分析。
当然，这里作了几次近似处理：
1）用离散采样信号的傅立叶变换来代替连续信号的频谱，只有在严格满足采样定理的前提下，频谱才不会有畸变，否则只是近似；
2）用有限长序列来代替无限长离散采样信号。
FFT计算线性卷积
线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。
以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:
将长为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-1
d.求y(n)=IFFT[Y(k)] n=0～L-1
可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。计算表明,L>32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性,因此,也称上述圆周卷积方法为快速卷积法
FFT计算相关函数
互相关和自相关函数的计算可利用FFT实现。由于离散付里叶变换隐含着周期性，所以用FFT计算离散相关函数也是对周期序列而言的。直接做N点FFT相当于对两个N点序列x(n)、y(n)作周期延拓，作相关后再取主值（类似圆周卷积）。而实际一般要求的是两个有限长序列的线性相关，为避免混淆，需采用与圆周卷积求线性卷积相类似的方法，先将序列延长补0后再用上述方法。
实数序列FFT
信号是实数序列,任何实数都可看成虚部为零的复数,例如,求某实信号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)的值。