如何计算离散傅立叶变换? [英] How to compute Discrete Fourier Transform?

问题描述

我一直试图找到一些地方来帮助我更好地理解 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.

推荐答案

我假设 1D 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.

此处挖掘真实<->C++ 中的复杂域 DFT/IDFT，您还可以找到有关如何计算的提示2D 变换与 1D 变换以及如何通过 N-point DFT,IDFT 计算 N-point DCT,IDCT.

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.

快速算法

有一些快速算法基于将这个方程分别拆分为和的奇数和偶数部分(这给出了2x N/2 和)，每个值也是 O(N)，但两半是相同的方程 +/- 一些常数调整.所以一半可以直接从第一个计算出来.这导致每个值 O(N/2).如果您递归地应用它，那么每个值都会得到 O(log(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 的幂！！！

所以可以递归拆分.零填充到最接近的 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:

• 在 C++ 中挖掘 Complex->Complex domain DFT,DFFT
• 关于构建类似算法的 FFT 的一些提示

复数

• c = a + i*b
• c 是复数
• a 是它的真实部分 (Re)
• 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+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(r|θ) = (+/-)sqrt(r)|(θ/2)
sqrt(r.(cos(θ)+i.sin(θ))) = (+/-)sqrt(r).(cos(θ/2)+i.sin(θ/2))

真实 ->复杂转换:

complex = real+i.0

[注释]

• 不要忘记您需要将数据转换为不同的数组(不在位)
• FFT 递归的归一化常数很棘手(通常类似于 /=log2(N) 也取决于递归停止条件)
• 如果N=1 or 2，不要忘记停止递归......
• 当心 FPU 可能会在大数据集上溢出(N 很大)
• 此处DFT/DFFT 的一些见解
• 此处2D FFT 和包装示例
• 通常欧拉公式用于计算e^(ix)=cos(x)+i.sin(x)
• here 如何获取 FFT 中每个值的频率? 你找到了如何获得 Niquist 频率

• do not forget that you need to convert data to different array (not in place)
• normalization constant on FFT recursion is tricky (usually something like /=log2(N) depends also on the recursion stopping condition)
• do not forget to stop the 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
• usually Euler's formula is used to compute e^(i.x)=cos(x)+i.sin(x)
• here How do I obtain the frequencies of each value in an FFT? you find how to obtain the Niquist frequencies

[edit1] 另外，我强烈建议您观看这个精彩的视频(我刚刚发现):

• 但是什么是傅立叶变换的视觉介绍

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

It describes the (D)FT in geometric representation. I would change some minor stuff in it but still its amazingly simple to understand.

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