快速傅立葉演算法

❶ 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）是做什麼用的

簡單來講，可以講信號從時域變換到頻域進行分析

❾ 諧波分析利用快速傅里葉演算法時會產生頻譜泄露為什麼要加窗函數

加窗函數後可以改變頻譜主瓣和旁瓣的寬度和幅度，使能量更集中，從而減少頻譜泄漏。