fft算法的基本思想

Ⅰ 一维实序列的快速傅里叶变换（FFT）

通过前面的分析，我们认识到傅里叶变换本身是复数运算，地球物理获取的数据大多数是实数，对于实数的变换原则上可直接套用复序列的FFT算法，但那样是把实数序列当作虚部为零的复数对待，显然需要存储虚部的零并进行无功的运算，既浪费了一倍的计算内存，又降低了约一半的运算速度。

为了不浪费不可不设的虚部内存和必然出现的复数运算，可否将一个实序列分为两个子实序列，分别作为实部与虚部构成一个复数序列，然后用复序列的FFT算法求其频谱，对合成的复序列频谱进行分离和加工得到原实序列的频谱呢？答案是肯定的，实现这一过程思路就是实序列FFT算法的基本思想。

1.实序列的傅里叶变换性质

对于一个N个样本的实序列x（k），其频谱为X（j），用X_r（j）和X_i（j）表示X（j）的实部和虚部， 表示X（j）的共轭，则

证明：已知 则

地球物理数据处理基础

上式两端取共轭，并注意到x（k）是实序列，则

地球物理数据处理基础

这就是实序列的傅里叶变换具有复共轭性。

其同样具有周期性，即

地球物理数据处理基础

2.一维实序列的FFT算法

（1）同时计算两个实序列的FFT算法

已知两个实序列h（k），g（k）（k＝0，1，…，N－1），例如重磁异常平面数据中的两条剖面，或地震勘探中的两道地震记录，可以人为地构成一个复序列：

地球物理数据处理基础

设h（k）的频谱为H（j）＝H_r（j）＋iH_i（j）

g（k）的频谱为G（j）＝G_r（j）＋iG_i（j）

y（k）的频谱为Y（j）＝Y_r（j）＋i Y_i（j）

利用上节的复序列FFT算法，求得Y（j），即Y_r（j）和Y_i（j）已知，来寻找H_r（j），H_i（j），G_r（j），G_i（j）与Y_r（j），Y_i（j）之间的关系。

对式（8－22）作傅里叶变换：

地球物理数据处理基础

由于H（j），G（j）本身是复序列，所以不能仅从上式分离出H（j）和G（j）。应用Y（j）的周期性，容易得到

Y（N－j）＝H（－j）＋iG（－j）

上式取共轭：

地球物理数据处理基础

由于h（k），g（k）为实序列，对上式右端应用复共轭定理，得

地球物理数据处理基础

对式（8－23）展开，得

地球物理数据处理基础

对式（8－24）展开，并应用共轭关系，得

地球物理数据处理基础

把式（8－25）和式（8－26）与Y（j）＝Y_r（j）＋iY_i（j）进行对比，有

地球物理数据处理基础

整理得

地球物理数据处理基础

因此，对于两个实序列，通过构造一个复序列，应用复序列的FFT算法和式（8－28）的分离加工，即可得到两个实序列的频谱。

（2）计算2 N个数据点的实序列FFT算法

设有2N点的实序列u（k）（k＝0，1，…，2N－1），首先按k的偶、奇分成两个子实序列，并构成复序列，即

地球物理数据处理基础

通过调用复序列FFT算法，求得y（k）的频谱为Y（j）。另记h（k），g（k）的频谱为H（j）和G（j）。

利用前面式（8－23）和式（8－24），容易求得

地球物理数据处理基础

下面分析用H（j），G（j）形成u（k）频谱的问题。记u（k）（k＝0，1，…，2 N－1）的频谱为V（j），分析V（j），H（j），G（j）之间的关系，根据定义

地球物理数据处理基础

利用式（8－31）和式（8－34）可换算出u（k）的前N个频谱V（j）（j＝0，1，…，N－1），还要设法求u（k）的后N个频谱V（N＋j）（j＝0，1，…，N－1）。利用实序列其频谱的复共轭和周期性：

（1）H（N）＝H（0），G（N）＝G（0），W^N₁＝－1，得

地球物理数据处理基础

（2）由于u（k）（k＝0，1，…，2N－1）是实序列，同样利用实序列其频谱的复共轭和周期性，用已求出的前N个频谱V（j）表示出后面的N－1个频谱V（N＋j）：

地球物理数据处理基础

由于0<2N－j<N，所以可从V（j）（j＝0，1，…，N－1）中选出V（2N－j）（j＝N＋1，N＋2，…，2 N－1），并直接取其共轭 即可得到V（N＋1）～V（2 N－1），从而完成整个实序列频谱的计算。

总结以上叙述，一维实序列u（k）（k＝0，1，…，2N－1）的FFT计算编程步骤如下：

（1）按偶、奇拆分实序列u（k），并构造复序列：

地球物理数据处理基础

（2）调用复序列的FFT计算y（k）的频谱Y（j）（j＝0，1，…，N－1）；

（3）用下式计算形成h（k），g（k）的频谱H（j）和G（j）；

地球物理数据处理基础

（4）用下式换算实序列u（k）的频谱V（j）（j＝0，1，…，2 N－1）：

地球物理数据处理基础

［例3］求实序列样本u（k）＝｛1，2，1，1，3，2，1，2｝（k＝0，1，…，7）的频谱。

解：按偶、奇拆分实序列u（k），按式（8－37）构造复序列c（j）（j＝0，1，2，3），即

c（0）＝1＋2i； c（1）＝1＋i； c（2）＝3＋2i； c（3）＝1＋2i。

（1）调用复序列FFT求c（j）（j＝0，1，2，3）的频谱Z（k）（k＝0，1，2，3），得

Z（0）＝6＋7i； Z（1）＝－3； Z（2）＝2＋i； Z（3）＝－1。

地球物理数据处理基础

（3）运用公式（8－38）计算H（j），G（j）：

地球物理数据处理基础

（4）根据式（8－39）求出u（k）（k＝0，1，…，7）的8个频谱V（j）（j＝0，1，…，7）：

地球物理数据处理基础

地球物理数据处理基础

由上例可见，完成全部2 N个实序列频谱的计算只需做N次FFT计算，相比直接用复序列的FFT算法节省了约一半的计算量。

Ⅱ 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的公式是什么和算法是怎样实现

二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：
先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：
for (int i=0; i<M; i++)
FFT_1D(ROW[i]，N);
for (int j=0; j<N; 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算法较为常用。 网上有帮助文档: http://www.5doc.com/doc/123035(右上角有点击下载)

Ⅳ 什么是FFT算法DSP是什么

FFT是快速傅里叶变换（ Fast Fourier Transform ）
DSP是数字信号处理 （ Digital Signal Processing ）