当前位置：文江博客话题详情

到底如何计算快速傅立叶变换？

发布于 2024-09-08 20:53:32 字数 215 浏览 0 评论 0原文

我已经阅读了很多有关快速傅里叶变换的内容，并试图了解它的低级方面。不幸的是，谷歌和维基百科根本没有多大帮助……而且我打开了大约 5 本不同的算法书籍，它们也没有多大帮助。

我试图找到像矢量 [1,0,0,0] 这样简单的东西的 FFT。当然，我可以将其插入 Matlab，但这无助于我了解底层发生的情况。另外，当我说我想求一个向量的 FFT 时，这是否等同于说我想用更有效的算法求一个向量的 DFT？

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

高速公鹿 2024-09-15 20:53:32

你是对的，“快速傅里叶变换”只是任何在 O(n log n) 时间内计算离散傅里叶变换的算法的名称，并且有多种这样的算法。

这是我认为的 DFT 和 FFT 最简单的解释，还有小 N 的示例，可能会有所帮助。（请注意，存在替代解释和其他算法。）

离散傅里叶变换

给定 N 个数字 f₀、f₁、f₂, …, f_N-1，DFT 给出一组不同的 N 数字。

具体来说：令 ω 为 1 的原N根（无论是在复数中还是在某个有限域中），这意味着 ω^N=1 但不小于 1 的幂是 1。您可以将 f_k 视为多项式 P(x) = Σf_kx^k 的系数。 DFT 给出的 N 个新数字 F₀、F₁、...、F_N-1 是评估多项式 的 ω 次幂的结果。也就是说，对于从 0 到 N-1 的每个 n，新数 F_n 为 P(ωⁿ) = Σ_0≤k≤N-1 f_kω^nk。

$\displaystyle F_n=P(\omega^n)=\sum_{k=0}^ {N-1}f_k\omega^{nk}$

[选择 ω 的原因是逆 DFT 具有很好的形式，与 DFT 本身非常相似。]

请注意，发现这些 F 天真地进行 O(N²) 操作。但是我们可以利用来自我们选择的 ω 的特殊结构，这使我们能够在 O(N log N) 中完成它。任何这样的算法都称为快速傅里叶变换。

快速傅里叶变换

这是进行 FFT 的一种方法。我将用 2N 替换 N 以简化符号。我们有 f₀、f₁、f₂、...、f_2N-1，我们想要计算 P(ω⁰), P(ω¹), … P(ω^2N-1) 我们可以在其中写

P(x) = Q(x) + ω^NR(x) 与
Q(x) = f₀ + f₁x + …+ f_N-1x^{N- 1}
R(x) = f_N + f_N+1x + …+ f_2N-1x^2N-1

现在这就是事情的美妙之处。观察 ω^k+N 处的值与 ω^k 处的值非常简单地相关：
P(ω^k+N) = ω^N(Q(ω^k) + ω^NR(ω ^k)) = R(ω^k) + ω^NQ(ω^k)。因此，Q 和 R 在 ω⁰ 到 ω^N-1 处的评估就足够了。

这意味着您最初的问题 - 在 2N 个点 ω⁰ 到 ω^2N-1 处评估 2N 项多项式 P - 已简化为两个在 N 点 ω⁰ 到 ω^N-1 处评估 N 项多项式 Q 和 R 的问题。因此，运行时间 T(2N) = 2T(N) + O(N) 等等，得出 T(N) = O(N log N)。

DFT 示例

请注意，其他定义使用 1/N 或 1/√N 因子。

对于N=2，ω=-1，(a,b)的傅立叶变换为(a+b,ab)。

对于 N=3，ω 是 1 的复立方根，(a,b,c) 的傅立叶变换为 (a+b+c, a+bω+cω², a+ bω²+cω)。（因为 ω⁴=ω。）

对于 N=4 且 ω=i，(a,b,c,d) 的傅立叶变换为 (a+b+c+d, a+双-c-di、a-b+cd、a-bi-c+di)。特别是，您问题中的示例： (1,0,0,0) 上的 DFT 给出 (1,1,1,1)，可能不是很有启发性。

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.

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

Discrete Fourier transform

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

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.

$\displaystyle F_n=P(\omega^n)=\sum_{k=0}^{N-1}f_k\omega^{nk}$

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

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.

Fast Fourier Transform

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) + ω^NR(x) with
Q(x) = f₀ + f₁x + … + f_N-1x^N-1
R(x) = f_N + f_N+1x + … + f_2N-1x^2N-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.

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

Examples of DFT

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

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

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 ω⁴=ω.)

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.

回复收藏 0 原文