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代表时间。和连续周期信号相比，离散周期信号的离散傅里叶级数的频谱是周期性的，因为时域的连续对应于频率的非周期，时域的离散对应于频率的周期。