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

Question

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

基本上,我只是在寻找有关如何计算DFT的示例,并解释它是如何计算的,因为最后,我正在寻找创建算法来计算它.

Answer 1

我假设一维DFT/IDFT ......

所有DFT都使用这个公式:

• X(k) 是变换样本值(复杂域)
• x(n) 是输入数据样本值(实际或复杂域)
• N 是数据集中的样本/值的数量

整个事情通常乘以归一化常数c.正如您所看到的单值,您需要N计算,因此对于所有样本,O(N^2)它都很慢.

在这里我可以找到有关如何使用1D变换计算2D变换以及如何N-point通过N-pointDFT,IDFT 计算DCT,IDCT的Real < - >复杂域DFT/IDFT的提示.

快速算法

存在快速算法,基于将该等式分别为总和的奇数和偶数部分(其给出总和),其也是每单个值,但是两个半部是相同的等式,一些常数调整.所以可以直接从第一个计算出一半.这导致每单值.如果你递归地应用这个,那么你得到每个单值.所以整个事情变得很棒,但也增加了这些限制:2x N/2O(N)+/-O(N/2)O(log(N))O(N.log(N))

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

所以它可以递归拆分.零填充到最接近的2的较大功率用于无效的数据集大小(在音频技术中有时甚至是相移).看这里:

• 我的Complex->复杂域DFT,CFT中的DFFT
• 关于构造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+i.i.b0.b1
     =(a0.a1-b0.b1)+i.(a0.b1+b0.a1)

真实 - >复杂的转换:

complex = real+i.0

[笔记]

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