返回资讯中心
外部精选
软件工程
#开发者实时流

离散傅里叶变换(DFT)入门:从有限长信号到频域分析

来源标题:Notes on the discrete Fourier transform (DFT)

文章介绍离散傅里叶变换(DFT)的由来:处理有限长离散信号时,直接计算 DTFT 会得到频率的连续函数,难以在计算机上实现,因此转而假设这 N 个样本构成周期信号的一个周期,用 DTFS 求系数。文中还提到后续将说明如何选择要计算的频率点。

Hacker News 最新kouosi2026/11/22 · 今天24 分钟阅读

以下正文由 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] 的离散傅里叶变换。这里的“变换”一词可能有点令人困惑——毕竟我们只是在用级数系数——那是不是直接叫“级数”更合适?也许吧,不过在数学中,transform(变换)有一个相当宽泛的含义,即“一种取一个数学对象并产生另一个对象的映射”;从这个意义上说,这里用“变换”是恰当的,因为我们取一个对象 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**(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——即已知 X[k] 重建 x[n] 所用的公式——有两种等价的做法。第一种做法是回到 DTFS,那里的重建公式是:回忆一下我们的约定是 X[k]=Na_k。因此:这就是逆离散傅里叶变换公式。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →