FFT算法分几种？
FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。 网上有帮助文档: (右上角有点击下载)
实序列的FFT算法
在以上讨论FFT算法中，均假定序列x(l)为复的，但实际问题中的序列大多为实的。当然，我们可以把实序列处理成虚部为零的复序列。因此，就要引进许多零参加运算。这样一来，在机器运算时间和存储单元方面都将造成很大的浪费。在本段中，我们介绍对实序列x(l)应用FFT算法的一个有效方法。
1.同时计算两个实序列的FFT算法
设有N=4的两个实序列x1(l)与x2(l)。为了求得它们的谱X1(m)与X2(m)，我们用此二实序列构造成如下复序列
物探数字信号分析与处理技术
利用上一段的方法，可以求得复序列x(l)的谱X(m)。根据(7-3-1)得到
物探数字信号分析与处理技术
上式中的m用N-m代替，则得
物探数字信号分析与处理技术
将上式两端取共轭，根据对称性有
物探数字信号分析与处理技术
根据DFT的复共轭性质，对于实序列x1(l)与x2(l)，有
物探数字信号分析与处理技术
于是从(7-3-4)得到
物探数字信号分析与处理技术
联立求解(7-3-2)和(7-3-6)便得到
物探数字信号分析与处理技术
例如设有两个N=4点的实序列，
物探数字信号分析与处理技术
我们用它们构造一个N=4点的复序列
物探数字信号分析与处理技术
利用FFT算法求X(m)，m=0，1，2，3(图7-3-1)，
图7-3-1 N=4点的FFT算法流程图
于是得到
物探数字信号分析与处理技术
因此从式(7-3-7)得到
物探数字信号分析与处理技术
物探数字信号分析与处理技术
2.实序列的FFT算法
设有N点的实序列x(l)，l=0，1，2，…，N-1。按照点的奇偶编号，将它们分成N/2个点的两个子序列
物探数字信号分析与处理技术
设x1(l)的谱与x2(l)的谱分别为X1(m)与X2(m)
物探数字信号分析与处理技术
其中
于是可以将实序列x(l)的谱X(m)，用两个子序列x1(l)，x2(l)的谱X1(m)，X2(m)来表示
物探数字信号分析与处理技术
其中
物探数字信号分析与处理技术
注意，x1(l)，x2(l)与X1(m)，X2(m)均以N/2为周期，
利用x1(l)、x2(l)构成如下复序列
物探数字信号分析与处理技术
利用FFT算法可以求得复序列 的谱 。根据(7-3-7)就求得两个实子序列的谱X1(m)与X2(m)
物探数字信号分析与处理技术
有了X1(m)，X2(m)，根据(7-3-10)就可求得X(m)。以上就是用FFT算法求实序列x(l)的谱X(m)的方法。必须指出，用公式(7-3-10)求X(m)时，***，两个实子序列的谱X1(m)，X2(m)及复序列x珓(l)的谱珘X(m)均是以N/2为周期的周期序列;第二，由于x
(l)是实序列，根据DFT的复共轭性质有X(m)=X*(N-m)，m=0，1，…，N/2，故只需求得前(N/2)+1个点的X(m)，就得到全部N个点的X(m)了
例如，有N=8点的实序列，
物探数字信号分析与处理技术
首先，按点的奇偶编号分成两个实子序列，
物探数字信号分析与处理技术
其次用它们构造如下复序列，
物探数字信号分析与处理技术
用FFT算法求此复序列的谱 (图7-3-2)
图7-3-2 N=4点的FFT算法流程图
于是得到:
根据周期性，有
物探数字信号分析与处理技术
根据(7-3-12)式，
物探数字信号分析与处理技术
根据周期性，有
物探数字信号分析与处理技术
故最终由(7-3-10)得到
物探数字信号分析与处理技术
FFT原理的FFT基本原理
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=2^M的情况，另外还有组合数基四FFT来处理一般长度的FFT 设N点序列x(n),,将x(n)按奇偶分组，公式如下图
改写为：
一个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=2^M，将x(n)按前后两部分进行分解，
按K的奇偶分为两组，即
得到两个N/2 点的DFT运算。如此分解，并迭代，总的计算量和时间抽取（DIT）基2FFT算法相同。
算法规律如下：
蝶形结构和时间抽取不一样但是蝶形个数一样，同样具有原位计算规律，其迭代次数成倍减小 时，可采取补零使其成为
，或者先分解为两个p,q的序列，其中p*q=N，然后进行计算。 前面介绍，采用FFT算法可以很快算出全部N点DFT值，即z变换X（z）在z平面单位圆上的全部等间隔取样值。实际中也许①不需要计算整个单位圆上z变换的取样，如对于窄带信号，只需要对信号所在的一段频带进行分析，这时希望频谱的采样集中在这一频带内，以获得较高的分辨率，而频带以外的部分可不考虑，②或者对其它围线上的z变换取样感兴趣，例如语音信号处理中，需要知道z变换的极点所在频率，如极点位置离单位圆较远，则其单位圆上的频谱就很平滑，这时很难从中识别出极点所在的频率，如果采样不是沿单位圆而是沿一条接近这些极点的弧线进行，则在极点所在频率上的频谱将出现明显的尖峰，由此可较准确地测定极点频率。③或者要求能有效地计算当N是素数时序列的DFT，因此提高DFT计算的灵活性非常有意义。
螺旋线采样是一种适合于这种需要的变换，且可以采用FFT来快速计算，这种变换也称作Chirp-z变换。
一维复数序列的快速傅里叶变换（FFT）
设x（N）为N点有限长离散序列，代入式（8－3）、式（8－4），并令 其傅里叶变换（DFT）为
地球物理数据处理基础
反变换（IDFT）为
地球物理数据处理基础
两者的差异只在于W的指数符号不同，以及差一个常数1/N，因此下面我们只讨论DFT正变换式（8－5）的运算量，其反变换式（8－6）的运算是完全相同的。
一般来说，W是复数，因此，X（j）也是复数，对于式（8－5）的傅里叶变换（DFT），计算一个X（j）值需要N次复数乘法和N－1次复数加法。而X（j）一共有N个值（j＝0，1，…，N－1），所以完成整个DFT运算总共需要N2次复数乘法和N（N－1）次复数加法。
直接计算DFT，乘法次数和加法次数都是与N2成正比的，当N很大时，运算量会很大，例如，当N＝8时，DFT需64次复数乘法；而当N＝1024时，DFT所需乘法为1048576次，即一百多万次的复数乘法运算，对运算速度要求高。所以需要改进DFT的计算方法，以减少运算次数。
分析Wjk，表面上有N2个数值，由于其周期性，实际上仅有N个不同的值W0，W1，…，WN－1。对于N＝2m时，由于其对称性，只有N/2个不同的值W0，W1，…，
地球物理数据处理基础
因此可以把长序列的DFT分解为短序列DFT，而前面已经分析DFT与N2成正比，所以N越小越有利。同时，利用ab＋ac＝a（b＋c）结合律法则，可以将同一个Wr对应的系数x（k）相加后再乘以Wr，就能大大减少运算次数。这就是快速傅里叶变换（FFT）的算法思路。
下面，我们来分析N＝2m情况下的FFT算法。
1.N＝4的FFT算法
对于m＝2，N＝4，式（8－5）傅里叶变换为
地球物理数据处理基础
将式（8－7）写成矩阵形式
地球物理数据处理基础
为了便于分析，将上式中的j，k写成二进制形式，即
地球物理数据处理基础
代入式（8－7），得
地球物理数据处理基础
分析Wjk的周期性来减少乘法次数
地球物理数据处理基础
则 代回式（8－9），整理得
地球物理数据处理基础
上式可分层计算，先计算内层，再计算外层时就利用内层计算的结果，可避免重复计算。写成分层形式
地球物理数据处理基础
则X（j1 j0）＝X2（j1 j0）。
上式表明对于N＝4的FFT，利用Wr的周期关系可分为m＝2步计算。实际上，利用Wr的对称性，仍可以对式（8－11）进行简化计算。考虑到
地球物理数据处理基础
式（8－11）可以简化为
地球物理数据处理基础
令j＝j0；k＝k0，并把上式表示为十进制，得
地球物理数据处理基础
可以看到，完成上式N＝4的FFT计算（表8－1）需要N·（m－1）/2＝2次复数乘法和N·m＝8次复数加法，比N＝4的DFT算法的N2＝16次复数乘法和N·（N－1）＝12次复数加法要少得多。
表8－1 N＝4的FFT算法计算过程
注：W0＝1；W1＝－i。
［例1］求N＝4样本序列1，3，3，1的频谱（表8－2）。
表8－2 N＝4样本序列
2.N＝8的FFT算法
类似N＝4的情况，用二进制形式表示，有
地球物理数据处理基础
写成分层计算的形式：
地球物理数据处理基础
则X（j2 j1 j0）＝X3（j2 j1 j0）。
对式（8－14）的X1（k1 k0 j0）进行展开，有
地球物理数据处理基础
还原成十进制，并令k＝2k1＋k0，即k＝0，1，2，3，有
地球物理数据处理基础
用类似的方法对式（8－14）的X2（k0 j1 j0），X3（j2 j1 j0）进行展开，整理得
地球物理数据处理基础
用式（8－16）、式（8－17）逐次计算到X3（j）＝X（j）（j＝0，1，…，7），即完成N＝23＝8的FFT计算，其详细过程见表8－3。
表8－3 N＝8的FFT算法计算过程
注：对于正变换 对于反变换 所
［例2］求N＝8样本序列（表8－4）x（k）＝1，2，1，1，3，2，1，2的频谱。
表8－4 N＝8样本序列
3.任意N＝2m的FFT算法
列出N＝4，N＝8的FFT计算公式，进行对比
地球物理数据处理基础
观察式（8－18）、式（8－19），不难看出，遵循如下规律：
（1）等式左边的下标由1递增到m，可用q＝1，2，…，m代替，则等式右边为q－1；
（2）k的上限为奇数且随q的增大而减小，至q＝m时为0，所以其取值范围为k＝0，1，2，…，（2m－q－1）；
（3）j的上限为奇数且随q的增大而增大，且q＝1时为0，其取值范围为j＝0，1，2，…，（2q－1－1）；
（4）k的系数，在等式左边为2q，等式右边为2q－1（包括W的幂指数）；
（5）等式左边序号中的常数是2的乘方形式，且幂指数比下标q小1，即2q－1；等式右边m对式子序号中的常数都是定值2m－1。
归纳上述规则，写出对于任意正整数m，N＝2m的FFT算法如下：
由X0（p）＝x（p）（p＝0，1，…，N－1）开始：
（1）对q＝1，2，…，m，执行（2）～（3）步；
（2）对k＝0，1，2，…，（2m－q－1）及j＝0，1，2，…，（2q－1－1），执行
地球物理数据处理基础
（3）j，k循环结束；
（4）q循环结束；由Xm（p）（p＝0，1，…，N－1）输出原始序列x（p）的频谱X（p）。
在计算机上很容易实现上述FFT算法程序，仅需要三个复数数组，编程步骤如下：
（1）设置复数数组X1（N－1），X2（N－1）和 （数组下界都从0开始）；
（2）把样本序列x赋给X1，即X1（k）＝x（k）（k＝0，1，…，N－1）；
（3）计算W，即正变换 反变换
（4）q＝1，2，…，m，若q为偶数，执行（6），否则执行第（5）步；
（5）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循环，作
X2（2qk＋j）＝X1（2q－1k＋j）＋X1（2q－1k＋j＋2m－1）
X2（2qk＋j＋2q－1）＝［X1（2q－1k＋j）－X1（2q－1k＋j＋2m－1）］W（2q－1k）
至k，j循环结束；
（6）k＝0，1，2，…，（2m－q－1）和j＝0，1，2，…，（2q－1－1）循环，作
X1（2qk＋j）＝X2（2q－1k＋j）＋X2（2q－1k＋j＋2m－1）
X1（2qk＋j＋2q－1）＝［X2（2q－1k＋j）－X2（2q－1k＋j＋2m－1）］W（2q－1k）
至k，j循环结束；
（7）q循环结束，若m为偶数，输出X1（j），否则输出X2（j）（j＝0，1，…，N－1），即为所求。
fft可分解多少级
2的n-1次方级。
FFT算法的实质是把一长序列的DFT计算分割为较短序列的DFT计算，对于基2算法而言，是把序列每次一分为二，最后分割成两点DFT，也可以采用别的分割法，每次一分为三，四，五等，就得到了基3，基4，基5等算法，其中基4算法由于具备某些优点，应用价值较大。
快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT；快速傅里叶变换是1965年由J.W库利和T.W.图基提出的，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。
fft算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于FFT算法、fft算法的信息别忘了在本站进行查找喔。