dft演算法

Ⅰ 離散傅里葉變換（DFT）需進行N^2次乘法，N(N-1)次加法這是怎麼算來的哪位舉個簡單的如N=3的例子 謝謝

偶爾碰到你的問題，已經很長時間了，不知道你還是不是需要，要不留給需要的人也好。

其實這個道理很簡單，不用舉例子的（敲公式太麻煩了）

看定義式：

X(K)一共是N個點，每完成一個點的DFT,假設K=1時，把後面的求和式子展開，一共是N個式子，那就是N-1次加法嘍，每個式子都是復數相乘，必然是N次復數乘法了。意思就是計算一次DFT,就需要N次復數乘法和N-1次復數加法，那麼X(K)一共是N個點，計算N次，就需要N*N+N*（N-1）次運算嘍，其中N*N次乘法，N*(N-1)次加法。

因為計算量相當大，所以才出現了FFT...

Ⅱ dft 怎麼計算reaction kinetics

IRC calculations = Intrinsic reaction coordinate calculations
內稟反應坐標計演算法。

例:
The minimum energy paths(MEP) are affirmed by intrinsic reaction coordinate(IRC) calculation and the imaginary vibration modes are discussed.
採用密度泛函(DFT)理論的B3LYP方法,在6-31++G(d,p)水平上按BERNY能量梯度解析全參數優化了HNCO和XCH2OH(X=CH3、NH2、OH、F)反應勢能面上各駐點的幾何構型,分別找到了這4個反應的過渡態,並通過振動頻率分析確認了過渡態結構,通過內稟反應坐標(IRC)計算確認了最低能量反應途徑(MEP)。

Ⅲ 設x(n)={1，0.5，0，0.5，1，1，0.5，0)，用FFT演算法求x(n)的DFT。FFT演算法任選，畫出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行。

例：

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

#define N 1000

/*定義復數類型*/

typedef struct{

double real;

double img;

}complex;

complex x[N], *W; /*輸入序列,變換核*/

int size_x=0;/*輸入序列的大小，在本程序中僅限2的次冪*/

double PI;/*圓周率*/

void fft();/*快速傅里葉變換*/

void initW(); /*初始化變換核*/

void change(); /*變址*/

void add(complex ,complex ,complex *); /*復數加法*/

void mul(complex ,complex ,complex *); /*復數乘法*/

void sub(complex ,complex ,complex *); /*復數減法*/

void output();

int main(){

int i;/*輸出結果*/

system("cls");

PI=atan(1)*4;

printf("Please input the size of x: ");

scanf("%d",&size_x);

printf("Please input the data in x[N]: ");

for(i=0;i<size_x;i++)

scanf("%lf%lf",&x[i].real,&x[i].img);

initW();

fft();

output();

return 0;

}

/*快速傅里葉變換*/

void fft(){

int i=0,j=0,k=0,l=0;

complex up,down,proct;

change();

for(i=0;i< log(size_x)/log(2) ;i++){ /*一級蝶形運算*/

l=1<<i;

(3)dft演算法擴展閱讀：

FFT演算法很多，根據實現運算過程是否有指數因子WN可分為有、無指數因子的兩類演算法。

經典庫利-圖基演算法 當輸入序列的長度N不是素數(素數只能被1而它本身整除）而是可以高度分解的復合數，即N=N1N2N3…Nr時，若N1=N2=…=Nr=2，N=2則N點DFT的計算可分解為N=2×N/2，即兩個N/2點DFT計算的組合，而N/2點DFT的計算又可分解為N/2=2×N/4，即兩個N/4點DFT計算的組合。

依此類推，使DFT的計算形成有規則的模式，故稱之為以2為基底的FFT演算法。同理，當N=4時，則稱之為以4為基底的FFT演算法。當N=N1·N2時，稱為以N1和N2為基底的混合基演算法。

Ⅳ 求序列的4點dft運算

代入公式，X(k)=...，分別將k=0，1，2，3代入計算，得X(0)=2,X(1)=1-j，X(2)=0，X(3)=1+j，再按Parseval定理驗證，能量P= 2 = (4+ 2 +2)/ 4=2

一個給定序列的子序列是從給定序列中去除一些元素，而不改變其他元素之間相對位置而得到的。若序列的項屬於一個偏序集，則單調遞增序列就是其中每個項都大於等於之前的項;若每個項都嚴格大於之前的項，這個序列就是嚴格單調遞增的。類似可定義單調遞減序列。

(4)dft演算法擴展閱讀：

例如，(C,Y,R) 是一個字母的序列：順序是 C 第一，Y 第二，R 第三。序列可以是有限的（就像前面這個例子），也可以是無限的，就像所有正偶數的序列 (2,4,6,...)。有限序列包含空序列( )，它沒有元素。序列中的元素也稱為項，項的個數（可能是無限的）稱為序列的長度。

序列寫作 (a1,a2, ...)。簡單起見，也可以用符號 (an)。

Ⅳ 誰知道DFT和FFT的發展歷史啊

DFT/FFT的發展歷史
離散傅里葉變換（Discrete Fourier Transform，DFT）是數字信號處理最重要的基石之一，也是對信號進行分析和處理時最常用的工具之一。在200多年前法國數學家、物理學家傅里葉提出後來以他名字命名的傅里葉級數之後，用DFT這個工具來分析信號就已經為人們所知。歷史上最偉大的數學家之一。
歐拉是第一個使用「函數」一詞來描述包含各種參數的表達式的人，例如：y = f(x)。他是把微積分應用於物理學的先驅者之一。 給出了一個用實變數函數表示傅立葉級數系數的方程； 用三角級數來描述離散聲音在彈性媒介中傳播，發現某些函數可以通過餘弦函數之和來表達。 但在很長時間內，這種分析方法並沒有引起更多的重視，最主要的原因在於這種方法運算量比較大。直到1965年，Cooley和Tukey在《計算機科學 》發表著名的《機器計算傅立葉級數的一種演算法》論文，FFT才開始大規模應用。
那個年代，有個肯尼迪總統科學咨詢委員會。其中有項研究主題是，對蘇聯核測試進行檢測，Tukey就是其中一員。美國/蘇聯核測試提案的批准，主要取決於不實地訪問核測試設施而做出檢測的方法的發展。其中一個想法是，分析離海岸的地震計情況，這種計算需要快速演算法來計算DFT。其它應用是國家安全，如用聲學探測遠距離的核潛艇。所以在軍事上，迫切需要一種快速的傅立葉變換演算法，這也促進了FFT的正式提出。
FFT的這種方法充分利用了DFT運算中的對稱性和周期性，從而將DFT運算量從N2減少到N*log2N。當N比較小時，FFT優勢並不明顯。但當N大於32開始，點數越大，FFT對運算量的改善越明顯。比如當N為1024時，FFT的運算效率比DFT提高了100倍。在庫利和圖基提出的FFT演算法中，其基本原理是先將一個N點時域序列的DFT分解為N個1點序列的DFT，然後將這樣計算出來的N個1點序列DFT的結果進行組合，得到最初的N點時域序列的DFT值。實際上，這種基本的思想很早就由德國偉大的數學家高斯提出過，在某種情況下，天文學計算（也是現在FFT應用的領域之一）與等距觀察的有限集中的行星軌道的內插值有關。由於當時計算都是靠手工，所以產生一種快速演算法的迫切需要。 而且，更少的計算量同時也代表著錯誤的機會更少，正確性更高。高斯發現，一個富氏級數有寬度N=N1*N2，可以分成幾個部分。計算N2子樣本DFT的N1長度和N1子樣本DFT的N2長度。只是由於當時尚欠東風——計算機還沒發明。在20世紀60年代，伴隨著計算機的發展和成熟，庫利和圖基的成果掀起了數字信號處理的革命，因而FFT發明者的桂冠才落在他們頭上。
之後，桑德（G.Sand）-圖基等快速演算法相繼出現，幾經改進，很快形成了一套高效運算方法，這就是現在的快速傅立葉變換（FFT）。這種演算法使DFT的運算效率提高1到2個數量級，為數字信號處理技術應用於各種信號的實時處理創造了良好的條件，大大推進了數學信號處理技術。1984年，法國的杜哈梅（P.Dohamel）和霍爾曼（H.Hollamann）提出的分裂基塊快速演算法，使運算效率進一步提高。
庫利和圖基的FFT演算法的最基本運算為蝶形運算，每個蝶形運算包括兩個輸入點，因而也稱為基-2演算法。在這之後，又有一些新的演算法，進一步提高了FFT的運算效率，比如基-4演算法，分裂基演算法等。這些新演算法對FFT運算效率的提高一般在50%以內，遠遠不如FFT對DFT運算的提高幅度。從這個意義上說，FFT演算法是里程碑式的。可以說，正是計算機技術的發展和FFT的出現，才使得數字信號處理迎來了一個嶄新的時代。除了運算效率的大幅度提高外，FFT還大大降低了DFT運算帶來的累計量化誤差，這點常為人們所忽略。

分給我吧 哈哈

Ⅵ 數字信號處理計算N點的DFT

只做點提示
x(k) = SIGMA{ x(n)*exp(-j 2*pi*k*n/N) } //注意：只有一項沒m=n不為零，其餘全部為零
= exp(-j2*pi*k*m) // x(m)幅度為1
= cos(2*pi*k*m)-jsin(2*pi*k*m) // 歐拉公式

Ⅶ 如何計算x=的DFT

通常做4個點的FFT，就意味著你在市域上取了4個點的樣本來做。FFT是DFT的快速實現方式，本質是完全一樣的。你的問題應該是在問，如何用兩個4點的FFT結構合起來實現8個點的DFT吧，那麼這個就牽涉到你的蝴蝶是怎樣畫的了，應該不難畫出來，請樓主自己試試。

Ⅷ 如何計算x(n)={4,3,2,1,0}的DFT

程序
x=[4,3,2,1,0]
N = length(x)
n = [0:N-1]
k = [0:N-1]
w = exp(-j*2*pi/N)
nk = n' * k
wnk = w.^(nk)
Xk = x * wnk
結果
x =
4 3 2 1 0
N =
5
n =
0 1 2 3 4
k =
0 1 2 3 4
w =
0.3090 - 0.9511i
nk =
0 0 0 0 0
0 1 2 3 4
0 2 4 6 8
0 3 6 9 12
0 4 8 12 16
wnk =
1.0000 1.0000 1.0000 1.0000 1.0000
1.0000 0.3090 - 0.9511i -0.8090 - 0.5878i -0.8090 + 0.5878i 0.3090 + 0.9511i
1.0000 -0.8090 - 0.5878i 0.3090 + 0.9511i 0.3090 - 0.9511i -0.8090 + 0.5878i
1.0000 -0.8090 + 0.5878i 0.3090 - 0.9511i 0.3090 + 0.9511i -0.8090 - 0.5878i
1.0000 0.3090 + 0.9511i -0.8090 + 0.5878i -0.8090 - 0.5878i 0.3090 - 0.9511i

Xk =
10.0000 2.5000 - 3.4410i 2.5000 - 0.8123i 2.5000 + 0.8123i 2.5000 + 3.4410i

Ⅸ 數字信號處理 DFT DTFT DFS之間什麼區別啊謝謝。。。

1、定義不同： DTFT是離散時間傅里葉變換 ，它用於離散非周期序列分析；DFT只是對一周期內的有限個離散頻率的表示；DFS是周期序列的離散傅里葉級數。

2、DFS是對離散周期信號進行級數展開，DFS是DFT的周期延拓；DFT是將DFS取主值，

3、DTFT是是對序列的FT，得到連續的周期譜，而DFT得到是有限長的非周期離散譜。

(9)dft演算法擴展閱讀：

1、DFT：離散傅里葉變換（Discrete Fourier Transform，縮寫為DFT），是傅里葉變換在時域和頻域上都呈離散的形式，將信號的時域采樣變換為其DTFT的頻域采樣。在形式上，變換兩端（時域和頻域上）的序列是有限長的，而實際上這兩組序列都應當被認為是離散周期信號的主值序列。

即使對有限長的離散信號作DFT，也應當將其看作其周期延拓的變換。

2、DTFT，離散時間傅里葉變換（DTFT，Discrete-timeFourierTransform），是傅里葉變換的一種。也可以叫做序列的傅里葉變換。

3、DFS也即離散傅里葉級數，又稱離散時間傅里葉級數即DTFS，T代表時間。和連續周期信號相比，離散周期信號的離散傅里葉級數的頻譜是周期性的，因為時域的連續對應於頻率的非周期，時域的離散對應於頻率的周期。