问如何计算离散傅立叶变换？

EN

我假设一维DFT/IDFT ...

所有的DFT都使用这个公式：

​

​

实数是变换后的样本值(复数domain)

• x(n)是输入数据样本值)(实数或复数domain)

• N是数据集中

中的样本数/值数

整个过程通常乘以归一化常量c。正如您所看到的，对于单个值，您需要进行N计算，因此对于所有样本，它都是O(N^2)，这很慢。

你还可以在这里找到关于如何用一维变换计算二维变换以及如何计算N-point离散余弦变换，N-point离散余弦变换，等时傅立叶变换的提示。

快速算法

有一些快速算法是基于将这个方程分别拆分为奇数和偶数部分的和(给出2x N/2和)，这也是每个单值的O(N)，但这两部分是相同的方程+/-一些常量调整。因此，可以直接从第一个计算出一半。这将导致每个单一值的O(N/2)。如果你递归地应用它，那么你会得到每一个值的O(log(N))。所以整个东西变成了O(N.log(N))，这很棒，但也增加了一些限制：

输入数据集的大小等于2的幂！

所以它可以递归拆分。对于无效的数据集大小(在音频技术中，有时甚至是相移)，使用最接近更大的2的幂的零填充。看这里：

关于constructing FFT like algorithms的

• mine Complex->Complex domain DFT,DFFT in C++
• some提示

复数

• c = a + i*b
• c是复数，number
• a是它的实部，(Re)
• b是它的虚部，(Im)
• i*i=-1是虚部，

所以计算过程是这样的

添加：

c0+c1=(a0+i.b0)+(a1+i.b1)=(a0+a1)+i.(b0+b1)

multiplication:

c0*c1=(a0+i.b0)*(a1+i.b1)
     =a0.a1+i.a0.b1+i.b0.a1+i.i.b0.b1
     =(a0.a1-b0.b1)+i.(a0.b1+b0.a1)

极地形式

a = r.cos(θ)
b = r.sin(θ)
r = sqrt(a.a + b.b)
θ = atan2(b,a)
a+i.b = r|θ

sqrt

sqrt(r|θ) = (+/-)sqrt(r)|(θ/2)
sqrt(r.(cos(θ)+i.sin(θ))) = (+/-)sqrt(r).(cos(θ/2)+i.sin(θ/2))

real ->复数转换：

complex = real+i.0

notes

不要忘记你需要将数据转换成不同的数组(不是在place)

• normalization常量中) FFT递归是很棘手的(通常像condition)

• do这样的东西也依赖于递归停止不要忘记停止递归如果代码...
• 注意FPU可能会在大数据集上溢出(N很大)
• 这里的FPU<代码>C99是用来计算Niquist的<代码>C103您将了解如何获得Niquist代码

edit1我也强烈推荐你去看这个令人惊叹的视频(我刚找到)：

• But what is the Fourier Transform A visual introduction

它用几何表示描述了(D)FT。我会对其中的一些小东西进行修改，但它仍然非常容易理解。