秋实-Allenyou 的小窝

在 OI/XCPC 赛场上，快速傅里叶变换（FFT）算法已被广为运用。然而，在算法竞赛中，对傅里叶变换的讲解大多将其作为点值多项式/系数多项式之间的变换理解。本文将从信号与系统角度入手，提供一个新的理解角度，分析一些算法竞赛中常见的傅里叶变换运用。

前置知识

• 微积分基础
• 级数相关
• 复数基础知识

一些关于表述的约定

• 与数学上常用的不同，在本文中，以 表示虚数单位。
• 在叙述傅里叶变换时，通常用小写字母表示信号的时域表达，如 ，用大写字母表示其对应的傅里叶变换，如

信号与时域表示

既然要从信号与系统的角度入手，首先我们应当考虑什么是信号。

在《信号与系统》的课程中，通常将信号定义为表示消息的物理量。

根据信号在时间上是否连续，我们可将其分为连续时间信号/离散时间信号。

对于连续时间信号，我们常用信号取值与时间的函数 表示，如一个初始为 0，随时间增加而线性递增的连续时间信号可以表示为 。

而对于离散时间信号，则可以对应的用一个数列 表示信号取值与时刻的关系。 例如， 即可表示一个从第 0 时刻开始，在 3、4、5 时刻取值为 1 的离散时间信号。

实际上，我们可以将更多的事物当作信号进行处理。例如，一个多项式 就可以将系数视为一个离散时间信号。

以上两种信号表示方法都着重于通过信号某时刻的取值刻画信号，因此我们也称其为信号的时域表示。对时域表示信号进行分析的方法称为信号的时域分析。

卷积

在信号的处理中，常常需要用到卷积运算。如信号 经过一个系统 处理后的零状态响应信号 即等价于输入信号 与系统的单位冲激响应 的卷积。

当然，本文主要着重于算法竞赛领域，因此以上介绍读者不必理解，感兴趣的读者可以自行查阅相关资料了解。

在此，我们分别对连续时间信号与离散时间信号定义卷积运算 ：

卷积运算满足线性性、交换律、结合律、分配律。

时域表示的不足

虽然信号的时域表示通常更符合直觉，但并非在所有情况下，时域分析都能很容易地对所有信号进行处理。例如如下信号：

如果要将 与 的分量区分开，采用时域分析显然是很难做到这一点的。因此，我们需要先引入更多的数学工具。

频域分析：从傅里叶级数到连续时间傅里叶变换

1807 年，傅里叶（Baron Jean Baptiste Joseph Fourier）在论文《热的传播》中提出了一项新理论，认为可以将任一周期函数表示为无穷多个三角函数之和。后来，在 1829 年，狄利克雷（Johann Peter Gustav Lejeune Dirichlet）进行了严格的推导，提出了狄利克雷条件，证明了满足该条件的周期函数都可以采用傅里叶的方法进行展开。

狄利克雷条件的内容主要包括三条：

• 在一周期内，函数连续，或只有有限个第一类间断点。
• 在一周期内，函数至多有有限个极大值、极小值。
• 在一周期内，函数绝对可积（即绝对值的积分存在且不为无穷）。

今天，我们将傅里叶的展开方法称为函数的傅里叶展开，而上述条件为可采用傅里叶展开的充分不必要条件。

对于可采用傅里叶展开的函数 ，设其周期为 ，应当存在如下展开式：

其中有

其中 表示在任意长度为 的区间内进行积分。

考虑到三角函数的辅助角公式，可以将原式化简为：

根据欧拉公式 可得到：

代入即可得到复指数形式的傅里叶级数：

那么，这个傅里叶级数有什么用呢？

我们以 为例，算出傅里叶级数为：

可以看到，函数周期 ，， 的值即为 分量的大小。我们称 为基频，傅里叶变换正是将信号用频率为 的整数倍的三角/复指数信号分量之和表示，复系数 即表示了分量的幅度、相位。

这种将信号用不同频率分量之和表示的方法，称为信号的频域表示，对频域表示信号的分析方法称为频域分析。

直到现在，我们的傅里叶变换都还是建立在周期信号的基础上。那么，该如何处理非周期信号呢？

一个很自然的想法是，将非周期信号视为一个周期 的周期信号。此时，，应当有

将 视为一个整体 ，就可以得到以下式子：

我们惊喜的发现，上式正符合积分的定义，因此我们将求和和极限转换为积分形式：

这里标记 实际上是强调该处的频率为复数，在拉普拉斯变换中会对此拓展，本文不做讨论

同样的，对 的式子作类似的处理，得到

以上即为非周期信号的连续时间傅里叶变换/反变换公式，其中 称为信号的傅里叶变换，也可称为频谱密度函数。

连续时间傅里叶变换有许多优良的性质，在此挑几条接下来会用到/比较重要的性质列出（证明略，如果有感兴趣的读者可以自行查阅信号与系统相关资料进行了解）。

1. 线性性：
2. 时域卷积定理：
3. 频域卷积定理：

由此我们可以发现一条非常有趣的结论，时域上的卷积运算对应频域上的乘法运算，反之亦然。

抽样：从连续时间傅里叶变换到离散时间傅里叶变换

现在我们有了对连续时间信号进行频域分析的方法，但是在实际工程中，计算机处理的信号往往是数字信号，也即离散时间、离散取值的信号。因此，我们需要对连续时间傅里叶变换进行一些拓展，得到对离散时间信号进行频域分析的方法。

首先，我们研究一个较为简单的离散时间信号 。对于这个信号，我们注意到，对信号谱线作包络线，可以发现这个信号就是以 为抽样间隔，对连续时间信号 进行抽样得到的。由此，我们可以作出猜测，对于任一离散时间信号，都可以视为对某一连续时间信号的抽样。

因此，我们可以通过抽样，将连续时间傅里叶变换转变为离散时间傅里叶变换。

首先我们引入单位冲激信号 ，该信号有如下性质：

• 积分特性：（积分区间需包含零点）
• 抽样特性：
• 采样特性：
• 卷积延时特性：

工程上一种可用的定义为，令 为宽度为 的门信号（在 为 , 其余位置为 ），则

同样的，在离散时间信号中，有单位样值信号：

定义单位冲激串 ，对其作傅里叶变换得 ，其中 。

我们对连续时间信号 作间隔为 的抽样得到样本信号 ，即

作连续时间傅里叶变换，得到

当抽样间隔 过大，抽样角频率 过低时，显然 中各成分会发生混叠，无法还原回原本信号。而 时（ 为原信号各分量频率最大值），抽样信号的频谱密度函数即为对原信号频谱密度函数乘以 后进行周期为 的周期延拓的结果，只需对抽样信号频谱密度函数取包含零点的一个周期，再乘以 ，即可得到原函数的频谱密度函数。

显然， 只在 的位置有取值。令 ，即为一个以 为包络的离散时间信号。

此时我们自然可以想到， 的傅里叶变换（如果有）应当与 存在一定关系。

我们写出 的傅里叶变换的原始形式：

此处交换积分与求和的顺序，得到：

根据单位冲激信号的抽样特性，可以得到：

我们定义数字角频率 ，由 可以得到：

令 ，我们即得到了离散时间傅里叶变换的形式：

同样的，可得到其逆变换为：

注意到 应当为以 为周期的周期函数。

与连续时间傅里叶变换类似，离散时间傅里叶变换也有一些优良的性质，一些接下来会用到/比较重要的性质如下（证明略）。

1. 线性性：
2. 时域卷积定理：

周期延拓：离散时间傅里叶变换的工程化

到此为止，我们已经能够对离散时间信号进行傅里叶变换，求取其频谱密度函数了。但是，我们发现得到的频谱密度函数仍然是连续的，不便于在计算机中处理。这是因为我们实际考虑的信号序列长度仍然是无穷大，导致频谱密度函数的采样间隔无穷小。

既然要在计算机中处理，那么我们的傅里叶变换后的结果也应当是一个离散、有限长度的序列。有限长度这一条暂且放到一边，我们先来回想一下，有什么与傅里叶变换相关，同时输出结果是离散的呢？

对！就是我们最开头使用的傅里叶级数展开！对一个连续时间周期信号作傅里叶级数展开，可以得到一个离散的频谱序列。

由此我们可以自然联想，如果我们输入的离散信号序列也是周期的，那得到的频谱密度函数会不会也是离散的呢？换而言之，就像连续时间傅里叶变换中时域-频域之间卷积-乘法运算的对称性一样，信号与频谱密度函数之间会不会有周期性-离散性的对称呢？

我们假设 是一个以 为周期的离散时间信号序列， 为其中一个周期。

类比单位冲激串，定义单位样值序列 ，对其作傅里叶变换得 ，其中 。

我们则可以构造如下的式子：

作傅里叶变换，得到：

由离散时间傅里叶反变换，得到：

记 ，即有

上式即为离散时间周期序列 的离散时间傅里叶级数展开。

类似的，有：

易得 为一离散时间周期序列。

在工程上，常从实际信号序列中截取一段序列，作为 ，再进行周期延拓，作离散时间傅里叶级数展开，将得到的 称为 的离散傅里叶变换。

应用

在算法竞赛中，傅里叶变换的主要应用点为加速卷积。

例如，某些题目中需计算的式子呈现出两个序列卷积的形式，但直接计算卷积往往有 的复杂度。此时即可将两个序列视为两个有限长离散时间信号的时域表示，对其应用离散时间傅里叶级数展开，得到其频域表示，然后利用时域卷积定理，将时域上的卷积转化为频域上的乘法运算，此时乘法运算可在 时间内完成，复杂度瓶颈来到傅里叶变换部分。

朴素的离散时间傅里叶级数展开计算显然是 的，但 FFT 通过分治思想与蝴蝶变换，实现了在 时间内进行离散时间傅里叶级数展开运算/逆运算，从而将整个计算过程压缩到 时间内。

在此不讨论 FFT 的实现细节，仅从思路上对 FFT 题目的解答作出一种新的解释。

洛谷 P1919 【模板】高精度乘法 | A*B Problem 升级版

本题要求计算两个长整数相乘的结果，直接写运算复杂度 显然超时。

此处设两个整数分别为 与 ，在不考虑进位的情况下，列竖式计算，可以发现竖式计算的过程与序列 卷积计算过程非常相似。因此我们可以先用 FFT 求出 的频域表示，频域相乘后 FFT 逆变换求出相乘后的新序列，最后遍历处理进位即可。

例题待补充

后记

本文写作过程中，来自 Luogu Furry Club 的小伙伴提供了大量帮助。在此感谢 Untitled_unrevised 对初稿的审阅和建设性意见！