FFT是一种DFT的高效算法，称为快速傅里叶变换（fast Fourier transform）。
傅里叶变换是时域一频域变换分析中最基本的方法之一。在数字处理领域应用的
离散傅里叶变换(DFT：Discrete Fourier Transform)是许多数字信号处理方法的基础。
原理简介
由于计算机技术的快速发展，在70年代中期，美国和日本的一些电子设备企业开始设计和生产数字式
傅里叶分析仪，但是由于
离散傅里叶变换的计算量较大，直到DFT的快速算法(FFT)发现之后，有限离散傅里叶变换(DFT)才真正获得了广泛的应用。
FFT是一种DFT的高效算法，称为快速傅里叶变换（fast Fourier transform）。FFT算法可分为按时间抽取算法和按频率抽取算法，先简要介绍FFT的基本原理。从DFT运算开始，说明FFT的基本原理。
DFT的运算为：
式中
由这种方法计算DFT对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中 的周期性和对称性，使整个DFT的计算变成一系列
迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。
分类
FFT基本上可分为两类，时间抽取法和频率抽取法，而一般的时间抽取法和频率抽取法只能处理长度N=2M的情况，另外还有组合数基四FFT来处理一般长度的FFT。
所谓抽选，就是把长序列分为短序列的过程，可在时域也可在频域进行。最常用的时域抽选方法是按奇偶将长序列不断地变为短序列，结果使输入序列为倒序，输出序列为顺序排列，这就是Coolly—Tukey算法。
时间抽取
设N点序列x(n), ,将x(n)按奇偶分组，公式如图2所示：
改写为：
一个N点DFT分解为两个 N/2点的DFT，
其算法有如下规律：
两个4点组成的8点DFT：
四个2点组成的8点DFT：
按时间抽取的8点DFT：
原位计算
当数据输入到存储器中以后，每一级运算的结果仍然储存在同一组存储器中，直到最后输出，中间无需其它存储器。
序数重排
对按时间抽取FFT的原位运算结构，当运算完毕时，这种结构存储单元A(1)、A(2)，…，A(8)中正好顺序存放着X(0)，X(1)，X(2)，…，X(7)，因此可直接按顺序输出，但这种原位运算的输入x(n)却不能按这种自然顺序存入存储单元中，而是按X(0)，X(4)，X(2)，X(6)，…，X(7)的顺序存入存储单元，这种顺序看起来相当杂乱，然而它也是有规律的。当用二进制表示这个顺序时，它正好是“码位倒置”的顺序。
蝶形类型随迭代次数成倍增加。
每次迭代的蝶形类型比上一次蝶代增加一倍，数据点间隔也增大一倍。
频率抽取
频率抽取2FFT算法是按频率进行抽取的算法。
设N=2M，将x(n)按前后两部分进行分解，
按K的奇偶分为两组，即
得到两个N/2 点的DFT运算。如此分解，并
迭代，总的计算量和时间抽取（DIT）基2FFT算法相同。
算法规律如下：
蝶形结构和时间抽取不一样但是蝶形个数一样，同样具有原位计算规律，其迭代次数成倍减小。
组合数基四FFT
N≠2M时，可采取补零使其成为N=2，或者先分解为两个p、q的序列，其中p*q=N，然后进行计算。
Chirp-z变换
前面介绍，采用FFT算法可以很快算出全部N点DFT值，即z变换X（z）在z平面单位圆上的全部等间隔取样值。实际中也许①不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑，②或者对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，这时很难从中识别出极点所在的频率，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的频谱将出现明显的尖峰，由此可较准确地测定极点频率。③或者要求能有效地计算当N是素数时序列的DFT，因此提高DFT计算的灵活性非常有意义。
螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。
应用
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对实数据进行有效计算，下面介绍方法。
一个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)的值。