二进制浮点数 | Javascript 算法与数据结构 | javascript-algorithms 中文文档

傅里叶变换

在其他语言中阅读： 法语。

定义

傅里叶变换（FT）将时间函数（信号）分解为其组成部分的频率，类似于如何用构成和弦的音符的频率（或音高）来表达音乐和弦。

离散傅里叶变换（DFT）将函数的有限等间隔样本序列转换为相同长度的离散时间傅里叶变换（DTFT）序列，后者是频率的复值函数。DTFT采样的间隔是输入序列持续时间的倒数。逆DFT是一个傅里叶级数，使用DTFT样本作为在相应DTFT频率处的复正弦波的系数。它具有与原始输入序列相同的样本值。因此，DFT被认为是原始输入序列的频域表示。如果原始序列跨越了函数的所有非零值，其DTFT是连续的（和周期性的），并且DFT提供了周期的一个循环的离散样本。如果原始序列是周期性函数的一个周期，DFT提供了DTFT周期的所有非零值。

离散傅里叶变换将N个复数序列转换为一个复数序列：

{x_n} = x₀, x₁, x₂ ..., x_N-1

转换为另一个复数序列：

{X_k} = X₀, X₁, X₂ ..., X_N-1

由以下公式定义：

$DFT$

离散时间傅里叶变换（DTFT）是一种傅里叶分析形式，适用于连续函数的均匀间隔样本。术语离散时间指的是变换操作于通常具有时间单位的离散数据（样本）。仅从这些样本中，它产生了一个频率的函数，这是原始连续函数的连续傅里叶变换的周期性求和。

快速傅里叶变换（FFT）是一种算法，它在时间（或空间）周期内对信号进行采样，并将其分解为它的频率分量。这些分量是在不同频率的单个正弦振荡，每个都有自己独特的振幅和相位。

这个变换在下面的图中进行了说明。在图中测量的时间段内，信号包含3个不同的主导频率。

时间和频率域中的信号视图：

FFT

FFT算法计算序列的离散傅里叶变换（DFT）或其逆变换（IFFT）。傅里叶分析将信号从其原始域转换到频域的表示，反之亦然。FFT通过将DFT矩阵分解为稀疏（主要是零）因子的乘积，迅速计算此类变换。因此，它成功地降低了计算DFT的复杂性，从如果直接应用DFT的定义产生的O(n²)，到O(n log n)，其中n是数据大小。

这里是对10、20、30、40和50 Hz余弦波之和的离散傅里叶分析：

FFT

解释

傅里叶变换是迄今为止最深刻的洞察之一。不幸的是，含义被埋藏在复杂的方程中：

傅里叶变换

与其跳入符号，不如亲自体验关键思想。这里有一个简单的比喻：

傅里叶变换能做什么？ 给定一杯奶昔，它找到食谱。
怎么做？ 将奶昔通过过滤器提取每个成分。
为什么？ 食谱比奶昔本身更容易分析、比较和修改。
我们怎么找回奶昔？ 混合成分。

用圆圈思考，而不仅仅是正弦波

傅里叶变换关注的是圆形路径（而不是1维正弦波），欧拉公式是一种巧妙的方式来生成它们：

傅里叶变换

我们必须使用虚指数来绕圈走吗？不，但这很方便且紧凑。当然，我们可以描述我们的路径为在两个维度（实部和虚部）中的协调运动，但不要忘记大局：我们只是在绕圈走。

发现完整的变换

重要的见解：我们的信号只是一系列时间尖峰！如果我们合并每个时间尖峰的食谱，我们应该得到完整信号的食谱。

傅里叶变换逐频率构建食谱：

傅里叶变换

几点注意事项：

N = 我们拥有的时间样本数量
n = 当前考虑的样本（0 ... N-1）
x_n = 时间 n 处信号的值
k = 当前考虑的频率（0 Hertz 到 N-1 Hertz）
X_k = 信号中频率 k 的量（振幅和相位，一个复数）
通常将1/N因子移到反向变换中（从频率回到时间）。虽然这样做是可以的，但我更喜欢在正向变换中使用1/N，因为它给出了时间尖峰的实际大小。你可以在两个变换上甚至使用1/sqrt(N)（向前和向后都会创建1/N因子）。
n/N 是我们已经经历的时间百分比。2 _ pi _ k 是我们的速度（弧度/秒）。e^-ix 是我们向后移动的圆形路径。组合是我们已经移动的距离，以这个速度和时间。
原始傅里叶变换的方程只是说“加复数”。许多编程语言不能直接处理复数，所以你需要将所有东西转换为直角坐标并相加那些。斯图尔特·里夫对傅里叶变换有很好的解释：

Fourier变换的互动指南

定义

解释

参考资料