离散傅里叶变换(DFT)入门笔记:从有限长信号到频域分析
来源标题:Notes on the discrete Fourier transform (DFT)
这篇笔记讲解离散傅里叶变换(DFT)的基本概念:对只有 N 个采样点的有限长离散信号,可将其视为周期信号的一个周期并借助 DTFS 求出复指数级数系数,从而绕开 DTFT 在频率上连续、难以在计算机上计算和存储的问题。文中还说明 DTFT 是频率的连续函数,必须选择在哪些频率点上求值。
以下正文由 AI 翻译自 Hacker News(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
关于这个话题,在上一篇 文章中, 我们已经看到离散时间傅里叶级数(DTFS)和变换(DTFT)如何用于分析无限长的周期和非周期离散信号。现在,该转向实际的数字信号处理了——这里的信号不仅是离散的,而且长度有限。 假设我们有一个信号的 N 个采样点——也就是一个包含 N 个数的列表: 我们想要分析这个信号中存在的频率;换句话说,就是找出一组复指数级数的系数,使得这些复指数能够重构该信号。一种选择是假设 x[n] 是一个无限长信号,在我们的 N 个采样点之外取值为零,然后计算它的 DTFT: 然而,这是频率 w 的连续函数,在实际计算机上很难计算;我们无法对所有的 w 都求值并存储,因此必须选择对哪些 w 进行计算。我们很快会看到这个选择是如何做出的。 但看待这个问题还有另一种方式。我们只有信号 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 的 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])。 在我之前关于单位复根 的文章中, 我们已经看到单位复根的幂如何构成 \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 的整数次幂所形成的向量可以汇集为一个矩阵: 在关于单位复根的 文章中, 我们已经证明这个矩阵的各行构成 \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**(kn), 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——即给定 X[k] 重构 x[n] 的公式。第一种方法是回到 DTFS,其重构公式为: 回想一下我们的约定是 X[k]=Na_k。因此: 这就是逆离散傅里叶变换公式。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。