如何计算离散傅立叶变换？
我一直在试图find一些地方来帮助我更好地理解DFT，以及如何计算它，但无济于事。 所以我需要帮助理解DFT和计算复数。
基本上，我只是寻找关于如何计算DFT的例子，并解释它是如何计算的，因为最后我想创build一个algorithm来计算它。
我假设一维DFT / IDFT …
所有的DFT都使用这个公式：
-
X(k)是变换的样本值（复数域） -
x(n)是input数据样本值（实数域或复数域） -
N是数据集中的采样/值的数量
这整个事情通常乘以标准化常数c 。 正如你所看到的单值，你需要N计算，所以所有的样本都是O(N^2) ，这是很慢的。
在这里， 我真正的复杂域DFT / IDFT在C ++中，你可以find如何计算一维变换二维变换，以及如何计算N-point离散傅里叶变换，IDCT的N-point N-point离散傅里叶变换，IDFT。
快速algorithm
在这里有快速algorithm，基于把这个方程分解为总和的 奇数和偶数部分（这给出2x N/2和），每个单值也是O(N) ，但是这两个半部分是相同的方程+/-一些不断调整。 所以一半可以直接从第一个计算。 这导致每个值O(N/2) 。 如果你recursion地应用这个，那么你得到每个单值的O(log(N)) 。 所以整个事情变成了O(N.log(N))这真棒，但也增加了这个限制：
所有DFFT的需要input数据集的大小等于两个幂！
所以它可以recursion地分割。 零填充到最接近的更大的2的功率用于无效的数据集大小（audio技术有时甚至是相移）。 看这里：
- 我的复杂 – >复杂的域DFT，在C ++中的DFFT
- 关于构造像algorithm一样的FFT的一些提示
复数
-
c = a + i*b -
c是复数 -
a是它的真实部分（Re） -
b是它的虚部（Im） -
i*i=-1是虚数单位
所以计算是这样的
加成：
c0+c1=(a0+i.b0)+(a1+i.b1)=(a0+a1)+i.(b0+b1)
乘法：
c0*c1=(a0+i.b0)*(a1+i.b1) =a0.a1+i.a0.b1+i.b0.a1+iib0.b1 =(a0.a1-b0.b1)+i.(a0.b1+b0.a1)
真实 – >复杂的转换：
complex = real+i.0
[笔记]
- 不要忘记，你需要将数据转换为不同的数组（不适用）
- FFTrecursion的归一化常量是非常棘手的（通常类似于
/=log2(N)也取决于recursion停止条件） - 如果
N=1 or 2不要忘记停止recursion… - 当心大数据集FPU可能溢出（
N很大） - 这里给DFT / DFFT一些见解
- 这里是2D FFT和包装的例子
- 通常用欧拉公式来计算
e^(ix)=cos(x)+i.sin(x)
我一直在阅读Steven W. Smith的“科学家和数字信号处理工程师指南”。 这是一个免费的PDF。 在第12章中，他逐步介绍了FFT的一个实现（具有实数input的复数FFT），并在末尾提供了一个RealFFT（专门针对实际input而修改的FFT）。 还有一章专门介绍复杂的FFT。 这本书有点古老，所以用BASIC和FORTRAN编写的编程例子看起来很古老，但概念很好地解释和说明。
这是一个非常好的例子（恕我直言）： http : //www.phpclasses.org/package/6193-PHP-Compute-the-Fast-Fourier-Transform-of-sampled-data.html
这是一个用PHP编写的FFTalgorithm，也有复杂的数字计算。 在你的情况可能会有所帮助。
当我在做我的工程荣誉项目时，我发现它非常有用。 还有一些好的链接，但目前我没有他们（我目前不在家）。
