快速傅立叶算法

❶ Cooley-Turkey的快速傅里叶算法当时申请专利了吗

由于专利需要解决技术问题，产生技术效果，纯算法是不能申请专利的，只有将该方法应用解决实际问题中，才可以申请专利。比如一种可以提高计算机运算速度的矩阵算法，或者拓扑学中一些路径算法，如果应用到网络中寻求最优传输路径中是可以申请到专利的。
因此快速傅里叶算法如果不结合实际应用，也就申请不到专利。如果真要申请，可以有如下考虑，因为现在来看，快速傅里叶变换在信号处理上应用比较广泛，那么比如实现快速傅里叶变换的电路，处理系统，甚至在光学上的应用装置都是可以申请专利的。
当然，不同国家在专利法的保护客体上有差别，但是大体上基本是共通的，算法不能申请专利这在世界上随便哪个国家都是正常的。

❷ 二维实序列的快速傅里叶变换（FFT）

在地球物理数据处理中，经常遇到处理二维实数据的情况。例如在地震勘探中，对面波勘探数据作频散分析解释时，要将时间－空间域的信息转换为频率－波数域频谱；在重磁异常的滤波或转换中，要将空间域的异常f（x，y）转换为波数域F（ω，υ）等。这些分析都需要进行二维的傅里叶变换（FFT）。

根据傅里叶变换的定义，对于连续二维函数f（x，y），其傅里叶变换对为

地球物理数据处理基础

对于离散的二维序列f_jk（j＝0，1，…，M－1；k＝0，1，…，N－1），其傅里叶变换为

地球物理数据处理基础

1.二维复序列的FFT算法

对于M条测线，每条测线N个测点，构成复序列y_jk（j＝0，1，…，M－1；k＝0，1，…，N－1），根据离散傅里叶公式（8－41），其傅里叶变换为

地球物理数据处理基础

于是，可以分两步套用一维复FFT完成二维复FFT的计算。

（1）沿测线方向计算

对于j＝0，1，…，M－1逐测线套用一维复FFT，执行式（8－43）。定义复数组 则算法为

1）对于j＝0，1，…，M－1，作2）～7）；

2）将y_jk输入A₁（k），即A₁（k）＝y_jk（k＝0，1，…，N－1）；

3）计算W^r，存入W（r），即

4）q＝1，2，…，p（p＝log₂N），若q为偶数执行6），否则执行5）；

5）k＝0，1，2，…，（2^p－q－1）和n＝0，1，2，…，（2^q－1－1）循环，作

A₂（k2^q＋n）＝A₁（k2^q－1＋n）＋A₁（k2^q－1＋n＋2^p－1）

A₂（k2^q＋n＋2^q－1）＝［A₁（k2^q－1＋n）－A₁（k2^q－1＋n＋2^p－1）］·W（k2^q－1）

至k，n循环结束；

6）k＝0，1，2，…，（2^p－q－1）和n＝0，1，2，…，（2^q－1－1）循环，作

A₁（k2^q＋n）＝A₂（k2^q－1＋n）＋A₂（k2^q－1＋n＋2^p－1）

A₁（k2^q＋n＋2^q－1）＝［A₂（k2^q－1＋n）－A₂（k2^q－1＋n＋2^p－1）］·W（k2^q－1）

至k，n循环结束；

7）q循环结束，若p为偶数，将A₁（n）输入到Y_jn，否则将A₂（n）输入到Y_jn（n＝0，1，…，N－1）；

8）j循环结束，得到Y_jn（j＝0，1，…，M－1；n＝0，1，…，N－1）。

（2）垂直测线方向计算

对于n＝0，1，…，N－1逐一套用一维复FFT，执行式（8－44）。即

1）对于n＝0，1，…，N－1，作2）～7）；

2）将Y_jn输入A₁（j），即A₁（j）＝Y_jn（j＝0，1，…，M－1）；

3）计算W^r存入W（r），即

4）q＝1，2，…，p（p＝log₂M），若q为偶数执行6），否则执行5）；

5）j＝0，1，2，…，（2^p－q－1）和m＝0，1，2，…，（2^q－1－1）循环，作

A₂（j2^q＋m）＝A₁（j2^q－1＋m）＋A₁（j2^q－1＋m＋2^p－1）

A₂（j2^q＋m＋2^q－1）＝［A₁（j2^q－1＋m）－A₁（j2^q－1＋m＋2^p－1）］·W（j2^q－1）

至j，m循环结束；

6）j＝0，1，2，…，（2^p－q－1）和m＝0，1，2，…，（2^q－1－1）循环，作

A₁（j2^q＋m）＝A₂（j2^q－1＋m）＋A₂（j2^q－1＋m＋2^p－1）

A₁（j2^q＋m＋2^q－1）＝［A₂（j2^q－1＋m）－A₂（j2^q－1＋m＋2^p－1）］·W（j2^q－1）

至j，m循环结束；

7）q循环结束，若p为偶数，将A₁（m）输入到Y_mn，否则将A₂（m）输入到Y_mn（m＝0，1，…，M－1）；

8）n循环结束，得到二维复序列的傅氏变换Y_mn（m＝0，1，…，M－1；n＝0，1，…，N－1），

所求得的Y_mn是复数值，可以写为

Y_mn＝R_mn＋iI_mn （m＝0，1，…，M－1；n＝0，1，…，N－1）

其中，R_mn，I_mn的值也是已知的。

2.二维实序列的FFT算法

对于二维的实序列，我们把其看作是虚部为零的复序列，套用上述的二维复序列FFT方法来求其频谱算法上也是可行的，但势必会增加大量的无功运算。因此，有必要研究二维实序列FFT的实用算法，同一维实序列FFT的实现思路一样，同样把二维实序列按一定的规律构造成二维复序列，调用二维复序列FFT，然后通过分离和加工得到原实序列的频谱。

例如采样区域有2 M条测线，每条测线有N个点，并且M，N都是2的整数幂，需要计算实样本序列x_jk（j＝0，1，2，…，2 M－1；k＝0，1，2，…，N－1）的傅氏变换：

地球物理数据处理基础

类似于一维实序列FFT的思想，直接建立下面的二维实序列FFT算法：

（1）将一个二维实序列按偶、奇线号分为两个二维子实序列，分别作为实部和虚部组合为一个二维复序列。即令

地球物理数据处理基础

（2）调用二维复FFT过程，求出y_jk的二维傅氏变换Y_mn的复数值：

地球物理数据处理基础

式中：R_mn，I_mn是Y_mn的实部和虚部。

（3）利用R_mn，I_mn换算X_mn的值。

前两步容易实现，下面分析第（3）步的实现。

记h_jk，g_jk的傅氏变换为H_mn，G_mn。根据傅里叶变换的定义，我们导出X_mn与H_mn，G_mn的关系式：

地球物理数据处理基础

式中，H_mn，G_mn为复数，我们用上标r和i表示其实部和虚部，将上式右端实部、虚部分离

地球物理数据处理基础

其中：

地球物理数据处理基础

下面的任务是将H_mn，G_mn各分量与通过二维复FFT求出的R_mn，I_mn值联系起来。为此先给出奇、偶分解性质和类似于一维情况的三个二维傅氏变换性质：

（1）奇偶分解性

任何一个正负对称区间定义的函数，均可唯一地分解为如下偶（even）、奇（odd）函数之和：

地球物理数据处理基础

（2）周期性

地球物理数据处理基础

（3）复共轭性

地球物理数据处理基础

现在我们来建立R_mn，I_mn与H_mn，G_mn的关系。对Y_mn作奇偶分解：

地球物理数据处理基础

根据线性性质

地球物理数据处理基础

对照式（8－54）和式（8－55），得

地球物理数据处理基础

由于h_jk，g_jk是实函数，根据复共轭性质，上面两式对应的奇偶函数相等。即

地球物理数据处理基础

再由奇偶分解性和周期性，得

地球物理数据处理基础

将式（8－57）代入式（8－50），得

地球物理数据处理基础

再利用H_mn，G_mn周期性及复共轭性，可以得到m＝M/2＋1，…，M－1；n＝0，1，…，N－1的傅氏变换，即

地球物理数据处理基础

将式（8－50）中M，N改为M－m，N－n，并将上式代入，得

地球物理数据处理基础

由式（8－58）、式（8－59）和式（8－61）即可得到原始序列x_jk（j＝0，1，…，2M－1；n＝0，1，…，N－1）在m＝0，1，…，M－1；n＝0，1，…，N－1区间的傅氏变换X_mn。

具体二维实序列的FFT算法如下：

（1）令h_jk＝x_2j，k，g_jk＝x_2j＋1，k，形成

y_jk＝h_jk＋ig_jk （j＝0，1，…，2 M－1；n＝0，1，…，N－1）

（2）调用二维复序列FFT过程，即从两个方向先后调用一维复FFT算法式（8－43）和式（8－44），求得y_jk的二维傅氏变换Y_mn的复数值：

Y_mn＝R_mn＋iI_mn （m＝0，1，…，M－1；n＝0，1，…，N－1）

（3）用下列公式由R_mn，I_mn的值换算X_mn的值：

地球物理数据处理基础

地球物理数据处理基础

❸ “DFT、IDFT、FFT、IFFT”各是什么

DFT，即可测试性设计（Design for Testability, DFT）是一种集成电路设计技术，它将一些特殊结构在设计阶段植入电路，以便设计完成后进行测试。电路测试有时并不容易，这是因为电路的许多内部节点信号在外部难以控制和观测。通过添加可测试性设计结构，例如扫描链等，内部信号可以暴露给电路外部。总之，在设计阶段添加这些结构虽然增加了电路的复杂程度，看似增加了成本，但是往往能够在测试阶段节约更多的时间和金钱。

IDFT就是Inverse Discrete Fourier Transform 离散傅里叶逆变换。FFT就是Fast Fourier Transform 快速傅里叶变换。

两者的应用都是将时域中难以处理的信号转换成易于处理的频域信号，分析完成后进行傅里叶反变换即得到原始的时域信号。
两者的异同是：我们知道在数学上用级数来无限逼进某个函数，以便简化计算过程而又不致使误差过大，这样工程上才能应用，否则一些数学模型是无法实现快速求解的。

IDFT：对于有限长的序列我们可以使用离散傅立叶变换，IDFT是对序列傅立叶变换的等距采样。

FFT：并不是与IDFT不相同的另一种变换（即原理是一样的），而是为了减少IDFT运算次数的一种快速算法。它是对IDFT变换式进行一次次的分解，使其成为若干小点数IDFT的组合，从而减小运算量。常用的FFT是以2为基数，它的运算效率高，程序比较简单，使用也十分地方便。

IFFT——Inverse Fast Fourier Transform 快速傅里叶逆变换。

快速傅里叶变换 (fast Fourier transform), 即利用计算机计算离散傅里叶变换（DFT)的高效、快速计算方法的统称，简称FFT。快速傅里叶变换是1965年由J.W.库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显着。

❹ 离散傅里叶变化和快速傅里叶变化的含义

快速傅里叶变换（FFT）属于离散傅里叶变换（DFT）。
快速傅里叶变换是在运算点数为2的N次幂的情况下，对算法作了优化，减少了运算次数，提高了运算速度。

❺ 求快速傅里叶算法的C语言实现代码

这是源于 Numerical Recipes 的关键性的函数，我曾使用过（书本可能有印刷错误，这里给的没有错误）。我不可能给你在这里讲解语句功能，你可以查原书。
isign 1 或 0 是正变换和反变换。调用前，要自己去掉 mean，尾部要自己 padding ( 最简单添0），时间域 和 频率 域 要自己 滤波。 nn 必须是2的整数次方，例如1024，4096。

#define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr
void jfour1(float ya[], unsigned long nn, int isign)
{
unsigned long n,mmax,m,j,istep,i;
double wtemp,wr,wpr,wpi,wi,theta;
float tempr,tempi;
n=nn << 1;
j=1;
for (i=1;i<n;i+=2) {
if (j > i) {
SWAP(ya[j],ya[i]);
SWAP(ya[j+1],ya[i+1]);
}
m=n >> 1;
while (m >= 2 && j > m) {
j -= m;
m >>= 1;
};
j += m;
};
mmax=2;
while (n > mmax) {
istep=mmax << 1;
theta=isign*(6.28318530717959/mmax);
wtemp=sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi=sin(theta);
wr=1.0;
wi=0.0;
for (m=1;m<mmax;m+=2) {
for (i=m;i<=n;i+=istep) {
j=i+mmax;
tempr = wr * ya[j]- wi * ya[j+1];
tempi = wr * ya[j+1] + wi * ya[j];
ya[j] = ya[i] - tempr;
ya[j+1] = ya[i+1] - tempi;
ya[i] += tempr;
ya[i+1] += tempi;
};
wr = (wtemp=wr) * wpr - wi * wpi + wr;
wi = wi * wpr + wtemp * wpi + wi;
};
mmax=istep;
};
}
#undef SWAP
void jrealft(float ya[], unsigned long n, int isign)
{
void jfour1(float ya[], unsigned long nn, int isign);
unsigned long i,i1,i2,i3,i4,np3,n05;
float c1=0.5,c2,h1r,h1i,h2r,h2i;
double wr,wi,wpr,wpi,wtemp,theta;
n05 = n >> 1;
theta=3.141592653589793/(double) (n05);
if (isign == 1) {
c2 = -0.5;
jfour1(ya,n05,1);
} else {
c2=0.5;
theta = -theta;
};
wtemp=sin(0.5*theta);
wpr = -2.0*wtemp*wtemp;
wpi=sin(theta);
wr=1.0+wpr;
wi=wpi;
np3=n+3;
for (i=2;i<=(n>>2);i++) {
i4=1+(i3=np3-(i2=1+(i1=i+i-1)));
h1r = c1 * (ya[i1] + ya[i3]);
h1i = c1 * (ya[i2] - ya[i4]);
h2r = -c2* (ya[i2] + ya[i4]);
h2i = c2 * (ya[i1] - ya[i3]);
ya[i1] = h1r + wr * h2r - wi * h2i;
ya[i2] = h1i + wr * h2i + wi * h2r;
ya[i3] = h1r - wr * h2r + wi * h2i;
ya[i4] = -h1i + wr * h2i + wi * h2r;
wr= (wtemp=wr) * wpr - wi * wpi + wr;
wi=wi * wpr + wtemp * wpi + wi;
};
if (isign == 1) {
ya[1] = (h1r=ya[1]) + ya[2];
ya[2] = h1r-ya[2];
} else {
ya[1] = c1 * ((h1r=ya[1]) + ya[2]);
ya[2]=c1 * (h1r - ya[2]);
jfour1(ya,n05,-1);
}
}

❻ 傅里叶变换有什么用

傅里叶变换是数字信号处理领域一种很重要的算法。要知道傅里叶变换算法的意义，首先要了解傅里叶原理的意义。

傅里叶原理表明：任何连续测量的时序或信号，都可以表示为不同频率的正弦波信号的无限叠加。而根据该原理创立的傅里叶变换算法利用直接测量到的原始信号，以累加方式来计算该信号中不同正弦波信号的频率、振幅和相位。

和傅里叶变换算法对应的是反傅里叶变换算法。该反变换从本质上说也是一种累加处理，这样就可以将单独改变的正弦波信号转换成一个信号。

因此，可以说，傅里叶变换将原来难以处理的时域信号转换成了易于分析的频域信号（信号的频谱），可以利用一些工具对这些频域信号进行处理、加工。最后还可以利用傅里叶反变换将这些频域信号转换成时域信号。

从现代数学的眼光来看，傅里叶变换是一种特殊的积分变换。它能将满足一定条件的某个函数表示成正弦基函数的线性组合或者积分。在不同的研究领域，傅里叶变换具有多种不同的变体形式，如连续傅里叶变换和离散傅里叶变换。

在数学领域，尽管最初傅里叶分析是作为热过程的解析分析的工具，但是其思想方法仍然具有典型的还原论和分析主义的特征。"任意"的函数通过一定的分解，都能够表示为正弦函数的线性组合的形式，而正弦函数在物理上是被充分研究而相对简单的函数类：

1、傅里叶变换是线性算子,若赋予适当的范数,它还是酉算子；

2、傅里叶变换的逆变换容易求出,而且形式与正变换非常类似；

3、正弦基函数是微分运算的本征函数,从而使得线性微分方程的求解可以转化为常系数的代数方程的求解.在线性时不变杂的卷积运算为简单的乘积运算,从而提供了计算卷积的一种简单手段；

4、离散形式的傅里叶的物理系统内,频率是个不变的性质,从而系统对于复杂激励的响应可以通过组合其对不同频率正弦信号的响应来获取；

5、着名的卷积定理指出:傅里叶变换可以化复变换可以利用数字计算机快速的算出(其算法称为快速傅里叶变换算法(FFT))。

正是由于上述的良好性质,傅里叶变换在物理学、数论、组合数学、信号处理、概率、统计、密码学、声学、光学等领域都有着广泛的应用。

(6)快速傅立叶算法扩展阅读

傅里叶生于法国中部欧塞尔（Auxerre）一个裁缝家庭，9岁时沦为孤儿，被当地一主教收养。1780年起就读于地方军校，1795年任巴黎综合工科大学助教，1798年随拿破仑军队远征埃及，受到拿破仑器重，回国后于1801年被任命为伊泽尔省格伦诺布尔地方长官。

傅里叶早在1807年就写成关于热传导的基本论文《热的传播》，向巴黎科学院呈交，但经拉格朗日、拉普拉斯和勒让德审阅后被科学院拒绝，1811年又提交了经修改的论文，该文获科学院大奖，却未正式发表。

傅里叶在论文中推导出着名的热传导方程 ，并在求解该方程时发现解函数可以由三角函数构成的级数形式表示，从而提出任一函数都可以展成三角函数的无穷级数。傅里叶级数（即三角级数）、傅里叶分析等理论均由此创始。

傅里叶由于对传热理论的贡献于1817年当选为巴黎科学院院士。

1822年，傅里叶终于出版了专着《热的解析理论》（Theorieanalytique de la Chaleur ，Didot ，Paris，1822）。这部经典着作将欧拉、伯努利等人在一些特殊情形下应用的三角级数方法发展成内容丰富的一般理论，三角级数后来就以傅里叶的名字命名。

傅里叶应用三角级数求解热传导方程，为了处理无穷区域的热传导问题又导出了当前所称的“傅里叶积分”，这一切都极大地推动了偏微分方程边值问题的研究。

然而傅里叶的工作意义远不止此，它迫使人们对函数概念作修正、推广，特别是引起了对不连续函数的探讨；三角级数收敛性问题更刺激了集合论的诞生。因此，《热的解析理论》影响了整个19世纪分析严格化的进程。傅里叶1822年成为科学院终身秘书。

由于傅里叶极度痴迷热学，他认为热能包治百病，于是在一个夏天，他关上了家中的门窗，穿上厚厚的衣服，坐在火炉边，结果因CO中毒不幸身亡，1830年5月16日卒于法国巴黎。

参考资料来源：网络-傅立叶变换

参考资料来源：网络-傅立叶

❼ “快速傅里叶变换”和“离散傅里叶变换”的主要区别是什么哪个准确

FFT（Fast Fourier Transformation），即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的 发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。
在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+N^2/2。
FFT提高了运算速度，但是，也对参与运算的样本序列作出了限制，即要求样本数为2^N点。离散傅里叶变换DFT则无上述限制。
小结：FFT快，DFT灵活，各有优点，如果满足分析要求，两者准确度相同。

❽ 谁能告诉我快速傅里叶变换（FFT）是做什么用的

简单来讲，可以讲信号从时域变换到频域进行分析

❾ 谐波分析利用快速傅里叶算法时会产生频谱泄露为什么要加窗函数

加窗函数后可以改变频谱主瓣和旁瓣的宽度和幅度，使能量更集中，从而减少频谱泄漏。