fft算法,FFT算法
实序列的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运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0; iM; i++)
FFT_1D(ROW[i]，N);
for (int j=0; jN; j++)
FFT_1D(COL[j]，M);
其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。
所以，关键是一维FFT算法的实现。下面讨论一维FFT的算法原理。
【1D-FFT的算法实现】
设序列h(n)长度为N，将其按下标的奇偶性分成两组，即he和ho序列，它们的长度都是N/2。这样，可以将h(n)的FFT计算公式改写如下 ：
(A)
由于
所以，(A)式可以改写成下面的形式：
按照FFT的定义，上面的式子实际上是：
其中，k的取值范围是 0~N-1。
我们注意到He(k)和Ho(k)是N/2点的DFT，其周期是N/2。因此，H(k)DFT的前N/2点和后N/2点都可以用He(k)和Ho(k)来表示
FFT算法分几种？
FFT算法分析FFT算法的基本原理是把长序列的DFT逐次分解为较短序列的DFT。按照抽取方式的不同可分为DIT-FFT（按时间抽取）和DIF-FFT（按频率抽取）算法。按照蝶形运算的构成不同可分为基2、基4、基8以及任意因子（2n,n为大于1的整数），基2、基4算法较为常用。 网上有帮助文档: (右上角有点击下载)
fft可分解多少级
2的n-1次方级。
FFT算法的实质是把一长序列的DFT计算分割为较短序列的DFT计算，对于基2算法而言，是把序列每次一分为二，最后分割成两点DFT，也可以采用别的分割法，每次一分为三，四，五等，就得到了基3，基4，基5等算法，其中基4算法由于具备某些优点，应用价值较大。
快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT；快速傅里叶变换是1965年由J.W库利和T.W.图基提出的，采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。