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

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

我假设一维DFT / IDFT …

所有DFT都使用以下公式：

• X(k)

  被转换的样本值（复杂域）

• x(n)

  是输入数据样本值（真实或复杂域）

• N

  是数据集中样本/值的数量

通常将整个事情乘以归一化常数

c

。如您所见，对于单个值，您需要进行

N

计算，因此对于所有样本而言，

O(N^2)

这很慢。

在这里我的真正的< - >复杂的领域DFT/IDFT在C++中，你还可以找到如何计算二维与一维变换，以及如何变换计算提示

N-point

DCT，IDCT由

N-point

DFT，IDFT那里。

快速算法

有一些快速算法可以将等式分别分解为 总和的* 奇数 和 偶数
部分（给出总和），这也是每个单个值，但是这两个一半是相同的方程式，但需要不断调整。因此，可以直接从第一个算出一半。这导致每个值。如果您递归地应用它，那么您将获得单个值。所以整个事情变得很棒，但同时也增加了以下限制：


*

2x N/2``O(N)``+/-``O(N/2)``O(log(N))``O(N.log(N))

所有DFFT需要输入数据集的大小等于2的幂！

因此可以递归拆分。零填充到2的最大幂的最接近值用于无效的数据集大小（在音频技术中，有时甚至是相移）。
复数

• c = a + i*b

• c

  是复数

• a

  是它的真实部分（重新）

• 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+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))

真实- >复杂转换：

complex = real+i.0