究竟如何做你计算的快速傅立叶变换？ [英] How exactly do you compute the Fast Fourier Transform?

问题描述

我一直在阅读变换了很多关于快速傅立叶和想了解它的低层次的方面。不幸的是，谷歌和维基百科都没有帮助太大的所有..我有这样5种不同的算法书籍开那些没有帮助，所以尽管。

I've been reading a lot about Fast Fourier Transform and am trying to understand the low-level aspect of it. Unfortunately, Google and Wikipedia are not helping much at all.. and I have like 5 different algorithm books open that aren't helping much either.

我试图找到一些简单的像一个向量[1,0,0,0]的FFT。当然我可以将它插入Matlab的，但不会帮助我了解下面发生了什么事情。此外，当我说我想找到一个向量的FFT，就是等于说我想找到一个向量的DFT只是一个更有效的算法？

I'm trying to find the FFT of something simple like a vector [1,0,0,0]. Sure I could just plug it into Matlab but that won't help me understand what's going on underneath. Also, when I say I want to find the FFT of a vector, is that the same as saying I want to find the DFT of a vector just with a more efficient algorithm?

推荐答案

您说的没错，快速傅里叶变换仅仅是一个名称的任意的算法，计算为O离散傅立叶变换（正log n）的时间，并有几个这样的算法

You're right, "the" Fast Fourier transform is just a name for any algorithm that computes the discrete Fourier transform in O(n log n) time, and there are several such algorithms.

这里的DFT和FFT的最简单的解释，我想他们，也例子小N，这可能会有帮助。 （请注意，有另一种帧间pretations，和其它算法。）

Here's the simplest explanation of the DFT and FFT as I think of them, and also examples for small N, which may help. (Note that there are alternative interpretations, and other algorithms.)

由于 N 数字˚F<子> 0 <子/> F ₁ F ₂ ，... F <子> N-1 的DFT给出了一组不同的 N 的数字。

Given N numbers f₀, f₁, f₂, …, f_N-1, the DFT gives a different set of N numbers.

具体做法是：让我们与欧米茄;是一个原始的 N 的第1（或者在复数或在一些有限域），这意味着，与ω-根; ^N = 1，但没有更小功率为1。你可以认为在F <子> k个的作为多项式P的系数（X）=总和;˚F<子> K X ^K 。在 N 的新号码˚F<子> 0 F ₁ ，...，F <子> N-1 的DFT给出是结果评估多项式在与欧米茄权力;.也就是说，对于每一个的 N 的从0到N-1，新数F <子> N 为P（欧米茄; ^N ）=总和; <子>0≤k≤N-1 F <子> K 和欧米茄; ^NK

Specifically: Let ω be a primitive Nth root of 1 (either in the complex numbers or in some finite field), which means that ω^N=1 but no smaller power is 1. You can think of the f_k's as the coefficients of a polynomial P(x) = ∑f_kx^k. The N new numbers F₀, F₁, …, F_N-1 that the DFT gives are the results of evaluating the polynomial at powers of ω. That is, for each n from 0 to N-1, the new number F_n is P(ωⁿ) = ∑_0≤k≤N-1 f_kω^nk.

[之所以选择与欧米茄;的是，逆DFT有一个很好的形式中，非常类似于在DFT本身。]

[The reason for choosing ω is that the inverse DFT has a nice form, very similar to the DFT itself.]

请注意，要找到这些F公司天真需要O（N ² ）操作。但是，我们可以利用特殊的结构来自与欧米茄，就是我们选择，这使我们能够做到这一点在O（N日志N）。任何这样的算法被称为快速傅立叶变换

Note that finding these F's naively takes O(N²) operations. But we can exploit the special structure that comes from the ω's we chose, and that allows us to do it in O(N log N). Any such algorithm is called the fast Fourier transform.

因此​​，这里的做FFT的一种方式。我会用2N代替n以简化符号。我们有f ₀ F ₁ F ₂ ，...，F <子> 2N-1 ，我们要计算的P（＆欧米加; ⁰ ），P（＆欧米加; ¹ ），... P（＆欧米加; ^2N-1 ），我们可以写出

So here's one way of doing the FFT. I'll replace N with 2N to simplify notation. We have f₀, f₁, f₂, …, f_2N-1, and we want to compute P(ω⁰), P(ω¹), … P(ω^2N-1) where we can write

P（X）= Q（X）+欧米茄; ^N R（X）与

P(x) = Q(x) + ω^NR(x) with

Q（X）= F ₀ + F ₁ X + ... + F <子> N-1 X ^N-1

Q(x) = f₀ + f₁x + … + f_N-1x^N-1

R（X）= F <子> N + F <子> N + 1 X + ... + F <子> 2N-1 X ^{2 N- 1}

R(x) = f_N + f_N+1x + … + f_2N-1x^2N-1

现在这里的事的美感。可观察到与欧米茄的价值; ^{K + N} 是很简单的与AT＆欧米茄价值; ^K ：
P（＆欧米茄; ^{K + N} ）=欧米茄; ^N （Q（欧米茄; ^K ）+欧米茄; ^N R（＆欧米茄; ^K ））= R（欧米茄; ^K ）+欧米茄; ^N Q（与欧米茄; ^K ）。因此，Q和R AT＆欧米茄的评价; ⁰ 到＆欧米茄; ^N-1 足够

Now here's the beauty of the thing. Observe that the value at ω^k+N is very simply related to the value at ω^k:
P(ω^k+N) = ω^N(Q(ω^k) + ω^NR(ω^k)) = R(ω^k) + ω^NQ(ω^k). So the evaluations of Q and R at ω⁰ to ω^N-1 are enough.

这意味着你最初的问题 - 评估2N长期多项式p在2N点与欧米茄; ⁰ 到＆欧米茄; ^2N-1 - 已减少到评估在N点和欧米茄N个项多项式Q和R的两个问题; ⁰ 到＆欧米茄; ^N-1 。所以，运行时间T（2N）= 2T（N）+ O（N）和所有这一切，这使T（N）= O（N日志N）。

This means that your original problem — of evaluating the 2N-term polynomial P at 2N points ω⁰ to ω^2N-1 — has been reduced to the two problems of evaluating the N-term polynomials Q and R at the N points ω⁰ to ω^N-1. So the running time T(2N) = 2T(N) + O(N) and all that, which gives T(N) = O(N log N).

请注意，其他的定义把1 / N或1 /√N的因素。

Note that other definitions put factors of 1/N or 1/√N.

有关N = 2，＆欧米加; = - 1，并傅里叶变换的（A，B）为（A + B，AB）

For N=2, ω=-1, and the Fourier transform of (a,b) is (a+b, a-b).

有关N = 3，ω是1的复杂的立方根，并傅里叶变换的（A，B，C）是（A + B + C，A +bω+Cω ² ，A +bω ² + C-Omega）。 （因为ω ⁴ =ω。）

For N=3, ω is the complex cube root of 1, and the Fourier transform of (a,b,c) is (a+b+c, a+bω+cω², a+bω²+cω). (Since ω⁴=ω.)

有关N = 4，ω= i和傅立叶变换的（A，B，C，D）是（A + B + C + D，A +双向的c-二，A-B + CD，一个-BI-C + DI）。具体地，例如，在你的问题：在DFT上（1,0,0,0）给出（1,1,1,1），不很照亮也许

For N=4 and ω=i, and the Fourier transform of (a,b,c,d) is (a+b+c+d, a+bi-c-di, a-b+c-d, a-bi-c+di). In particular, the example in your question: the DFT on (1,0,0,0) gives (1,1,1,1), not very illuminating perhaps.

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