Newshot

离散傅里叶变换(DFT)笔记

Translation(model translation, not the source's own text)

关于离散傅里叶变换(DFT)的笔记

在上一篇关于这个主题的文章中,我们看到了离散时间傅里叶级数(DTFS)和变换(DTFT)如何用于分析无限长的周期和非周期离散信号。现在,是时候转向现实的数字信号处理了,其中信号不仅是离散的,而且在时间上也是有限的。

分析信号样本

假设我们有一个信号的 N 个样本——它是一个包含 N 个数字的列表:

我们想要分析这个信号中存在的频率;换句话说,找到能够重建该信号的复指数级数中的系数。一种选择是假设 x[n] 是一个无限域信号,在我们的 N 个样本之外取值为零,然后计算它的 DTFT:

然而,这是频率 w 的连续函数,因此在实际计算机上难以计算;我们无法对所有 w 求值并存储它,所以我们必须选择对哪些 w 进行计算。我们很快就会看到这个选择是如何做出的。

离散傅里叶变换(DFT)

但看待这个问题还有另一种方式。我们只有信号 x 的 N 个样本,因此我们可以假设它们代表一个周期信号的一个周期。在这种情况下,我们可以使用 DTFS;回想一下,级数的系数是:

正如我们在关于 DTFS 的文章中所看到的,这个级数可以用来精确地重建一个离散的周期信号。由于我们的信号 x[n] 是有限的,并且我们假设它只是一个周期信号的一个周期,这意味着我们也可以使用 DTFS 精确地重建 x[n]。

这就是离散傅里叶变换(DFT)背后的核心洞见。首先,按照惯例 [1] 我们定义:

这被称为 x[n] 的离散傅里叶变换。这里的“变换”一词可能有点令人困惑——毕竟,我们只是在使用级数系数——那么直接说“级数”不是更恰当吗?也许吧,尽管在数学中,变换有一个非常一般的含义,即“一种将一个数学对象映射为另一个对象的操作”;在这个意义上,“变换”在这里是恰当的,因为我们取一个对象——x[n],并产生另一个对象——X[k]。

此外,DFT 和 DTFT 密切相关。回想一下我们之前说过的,DTFT 难以计算是因为 w 是一个连续变量?那么,DFT 给了我们一种将该变量采样到离散域中的方法:

所以 DFT 可以看作是对 DTFT 的恰好 N 个等间隔采样。

计算 DFT

由于本文的目标 specifically 是演示将傅里叶分析应用于离散数字信号的可计算方法,下面是计算信号 DFT 的 Python 代码:


        def dft(x):
    """Return X[k] = sum_n x[n] exp(-2 pi i k n / N)."""
    N = len(x)
    n = np.arange(N)
    X = np.empty(N, dtype=complex)
    for k in range(N):
        weights = np.exp(-2j * np.pi * k * n / N)
        X[k] = np.sum(x * weights)
    return X
      

不难看出这段代码与 X[k] 的数学公式之间的对应关系。Python 的 Numpy 代码默认是向量化的,因此对于每个 k,weights 数组是整体计算的(因为 n 是索引数组 [0..N-1])。

DFT 与单位复根

在我之前关于单位复根的文章中,我们看到了单位复根的幂如何构成 \mathbb{C}^n 的正交基。现在让我们展示这一事实与 DFT 之间美妙的理论联系。

回想一下,N 次单位复根可以写为:

由于所有 z_k 都只是 w=z_1=e^{i2\pi/N} 的幂,我们可以将它们写为:

单位复根的共轭本身就是单位复根:

由于 z_k^* 与 z_{N-k} 相同,所以当我们枚举所有单位复根时,我们也在枚举它们的共轭,只是顺序相反。

考虑到这一点,让我们记 [2] \omega=z_1^*=e^{-i2\pi/N},并考察序列:

将 \mu_N 逐元素取 0 到 N-1 的整数次幂所形成的向量可以收集到一个矩阵中:

文章标题:离散傅里叶变换(DFT)笔记

正文: 在单位根那篇文章中,我们已经证明了这个矩阵的各行在 \mathbb{C}^N 上构成一组正交基。换句话说,\mathbb{C}^N 中的任意向量都可以表示为 F 的各行的线性组合。

希望你能看出这要往哪里去!让我们把信号 x[n] 看作 \mathbb{C}^N 中的列向量。x 的 DFT 可以通过用矩阵 F 乘以 x 来计算:

花一分钟说服自己这是对的,针对某个特定的行 k 走一遍乘法过程,例如 X[2] 是通过 F 的第三行(从 0 开始计数)与 x[n] 做行列乘法计算出来的。

我们的 F 被称为傅里叶矩阵或 DFT 矩阵。之前我们已经见过直接计算 DFT 的 Python 代码;这里是一个通过矩阵乘法方式实现它的版本:


        def dft_matrix(N):
    """Construct F[k, n] = W_N**(k*n), where W_N = exp(-2 pi i / N)."""
    # W_N is a primitive N-th root of unity: W_N**N = 1.
    # Its powers give all N roots of z**N - 1 = 0.
    root = np.exp(-2j * np.pi / N)
    indices = np.arange(N)
    # Rows correspond to frequency bins k; columns to sample indices n.
    exponents = np.outer(indices, indices)
    return root**exponents

def dft_via_matrix(x):
    """Compute the DFT as F @ x with the Fourier matrix"""
    return dft_matrix(len(x)) @ x
      

不过,这不仅是计算上的便利,还有理论上的优雅。当初我们讨论连续傅里叶级数时,已经看到三角函数(或者——等价地——复指数)如何为平方可积函数构成一组正交基。

在这里,我们在离散时间中看到了类似的线性代数联系——由复单位根的幂构成的向量在 \mathbb{C}^N 中构成一组正交基,因此可以用来表示任意长度为 N 的复数序列。

这就引出了下一个话题:从 DFT 表示中重建信号。

逆 DFT:重建信号

有两种等价的方法来求逆 DFT——即在给定 X[k] 的情况下重建 x[n] 所用的公式。第一种方法是回到 DTFS,其重建公式为:

回忆一下我们的约定是 X[k]=Na_k。因此:

这就是离散傅里叶逆变换公式。

现在来看看另一种方法,因为它以一种富有启发性的方式运用了我们的线性代数解释。

回忆傅里叶矩阵 F,并考虑 F_c——即每个元素都是 F 对应元素共轭的同一个矩阵。如果:

用 F 乘以 F_c 会发生什么?

我们在单位根那篇文章中已经看到,这相当于:

换句话说:

其中 I 是单位矩阵。由于 F 是方阵,任何与它相乘得到单位矩阵的矩阵就是它的逆:

回忆一下向量形式:

根据我们对 F^{-1} 的定义:

以及求和形式:

这与我们从 DTFS 得到的重建公式相同。在数学中,用不同方法得到相同结果总是一个好兆头!

这里的线性代数解释很清晰:由单位根的幂构成的向量在 \mathbb{C}^N 上构成一组正交基。因此,每个向量 x\in\mathbb{C}^N 都可以表示为这些向量的线性组合。此外,这个变换是可逆的,原始向量可以通过用 F^{-1} 左乘其 DFT 向量 X 来重建。

示例

是时候来一个完整演算的示例了;这个示例的完整 Python 代码可在 GitHub 上获取;读一读它的 main 函数,注释写得很详细。

回忆上一篇文章中我们用过的采样三角信号;这里,让我们使用单个周期:

采样三角信号 - 单个周期
采样三角信号 - 单个周期

在代码中,这只是一个数字数组:


        x = np.array([0, 1, 2, 3, 2, 1, 0, -1, -2, -3, -2, -1]) / 3
      

文章标题:离散傅里叶变换(DFT)笔记

正文: 使用前面展示的代码计算该信号的 DFT,会得到以下数值;请记住 X[k] 由复数组成,因此我们将其表示为幅度-相位对。相位仅对非零系数显示,因为零的相位是未定义的 [3]:

采样三角信号 - 其 DFT 表示
采样三角信号 - 其 DFT 表示

显然,使用矩阵乘法方法计算 DFT 会得到完全相同的数值。而要重建信号,我们乘以计算得到的 IDFT 矩阵即可还原出原始信号。重建结果与原始信号精确匹配,任何差异都可归因于浮点舍入误差。

高效计算 DFT

示例代码中还包含另一种计算该信号 DFT 的方法——调用 NumPy 的 fft.fft 函数。这指的是快速傅里叶变换,它被认为是 20 世纪最重要的算法之一。通过利用傅里叶矩阵 F 的结构,FFT 以 O(N \log N) 次运算计算乘积 F\cdot x,而直接矩阵-向量乘法需要 O(N^2) 次运算。我计划在以后的文章中介绍其工作原理。

附录:频谱泄漏

仔细观察上面示例部分使用的信号,我们会发现它实际上是一个采样三角波的一个完整周期。这很方便,因为重复该块就能重现原始三角波。但当采样只覆盖周期的一部分时会发生什么?

以三角波的前 10 个采样为例:

截断的采样三角波 - 仅前 10 个采样
截断的采样三角波 - 仅前 10 个采样

如果我们朴素地对此信号进行周期延拓,事情就对不上了(每个周期末尾都会出现跳变)。当然,我们仍然可以计算其 DFT;以下是我们将得到的系数:

截断采样三角波的 DFT
截断采样三角波的 DFT

虽然系数仍然以共轭对的形式出现(因为采样是实数),但原始三角波的频率不再与 DFT 的频率 bin 重合,因此它们的贡献会分散到多个 bin 中。这被称为频谱泄漏。

通过应用 IDFT,我们仍然可以完美地重建原始的 10 采样信号!所以,如果我们只需要重建,频谱泄漏不是问题;但如果我们要做频率分析,它会在某种程度上扭曲情况,添加了底层三角波中并不真正存在的频率——只是为了解释不连续性。在实际的信号处理中,这类问题通常通过在采样后对信号应用特殊的窗函数来解决——这些窗函数通过在边缘处将信号渐缩至接近零来帮助减轻泄漏。

如需评论,请给我发邮件。

The translation is machine-generated and individual terms may be off. Nothing is rewritten or cut; the original is authoritative.

Published by Hacker News
This site only summarises and aggregates; copyright stays with the original author. Headlines and summaries follow the source — where they differ, the original wins.
Read the original ↗