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

问题描述

我一直在试图找到一些地方帮助我更好地了解DFT和如何计算，但无济于事。所以，我需要帮助理解DFT和它的复数运算。

I've been trying to find some places to help me better understand DFT and how to compute it but to no avail. So I need help understanding DFT and it's computation of complex numbers.

基本上，我只是在寻找如何计算DFT与它是如何计算的，因为在最后一个解释的例子，我希望创建一个算法来计算它。

Basically, I'm just looking for examples on how to compute DFT with an explanation on how it was computed because in the end, I'm looking to create an algorithm to compute it.

推荐答案

我认为维DFT / IDFT ...

I assume 1D DFT/IDFT ...

所有DFT的使用这个公式：

• X（K）转换样本值（复数域）
• X（N）输入数据的采样值（实数或复数域）
• N 是在数据集中的样本/值的数量

• X(k) is transformed sample value (complex domain)
• x(n) is input data sample value (real or complex domain)
• N is number of samples/values in your dataset

这件事通常是归一化常数 C 成倍增加。正如你可以看到单个值则需要 N 计算，所以对所有样品是 O（N ^ 2）这是缓慢的。

This whole thing is usually multiplied by normalization constant c. As you can see for single value you need N computations so for all samples it is O(N^2) which is slow.

下面雷真＆LT; - >复合域DFT / IDFT在C ++中，你还可以找到提示如何计算二维与一维变换转换以及如何计算 N点 DCT，由 IDCT N点 DFT，IDFT那里。

Here mine Real<->Complex domain DFT/IDFT in C++ you can find also hints on how to compute 2D transform with 1D transforms and how to compute N-point DCT,IDCT by N-point DFT,IDFT there.

快速算法

有快速的算法在那里基于分裂这个公式为奇和甚至在和的部分分开（这给 2×N / 2 款项），这也是 O（N）每单价值，但两半是相同的公式 +/- 某个常数的调整。所以一半可以直接从第一个被计算。这导致了 O（N / 2）每一个值。如果应用此递归那么你得到 O（日志（N））每一个值。所以整个事情变得 O（N.log（N））这是真棒，但也增加了这个限制：

There are fast algorithms out there based on splitting this equation to odd and even parts of the sum separately (which gives 2x N/2 sums) which is also O(N) per single value, but the 2 halves are the same equations +/- some constant tweak. So one half can be computed from the first one directly. This leads to O(N/2) per single value. if you apply this recursively then you get O(log(N)) per single value. So the whole thing became O(N.log(N)) which is awesome but also adds this restrictions:

所有DFFT的需要输入数据集的大小等于两个功率!!!

因此​​，它可以递归拆分。零填充到2最接近较大功率用于无效的数据集的大小（在音频技术有时甚至相移）。看看这里：

So it can be recursively split. Zero padding to nearest bigger power of 2 is used for invalid dataset sizes (in audio tech sometimes even phase shift). Look here:

• 矿Complex->复合域DFT，DFFT在C ++
• 在一些提示构建FFT算法一样

• mine Complex->Complex domain DFT,DFFT in C++
• some hints on constructing FFT like algorithms

复数

• C = A + I * B
• C 就是复数
• A 是它的实部（再）
• B 是它的虚部（IM）
• I * I = -1 是虚数单位

• c = a + i*b
• c is complex number
• a is its real part (Re)
• b is its imaginary part (Im)
• i*i=-1 is imaginary unit

这样的计算是这样的

另外：

• 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）

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

实 - >复杂的转换：

• 复杂=真实+ I.0

[注意事项]

• 请不要忘记，你需要将数据转换成不同的阵列（未到位）
• 正常化FFT递归常数是棘手的（ / = LOG2（N））
• 请不要忘记停止递归，如果 N = 1或2 ...
• 当心FPU可在大的数据集（ N 大）
溢出
• 在这里一些见解，以DFT / DFFT
• 在这里 2D FFT和包装的例子

• do not forget that you need to convert data to different array (not in place)
• normalization constant on FFT recursion is tricky (/=log2(N))
• do not forget the stopping recursion if N=1 or 2 ...
• beware FPU can overflow on big datasets (N is big)
• here some insights to DFT/DFFT
• here 2D FFT and wrapping example

这篇关于如何计算离散傅里叶变换？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！