Fourier Transform 2 (DTFT, DFT)

离散时间傅里叶变换 (DTFT)

傅里叶级数和傅里叶变换面向的都是连续函数 $$，但在用计算机处理之前，我们必须将其离散化，因此涉及到了采样操作。

冲激串及其傅里叶变换

上一篇文章 Fourier Transform 1 提到，Dirac $$ 函数能帮助我们采样一个函数值。进一步地，如果要以 $$ 为间隔等距采样一系列函数值，就可以用如下冲激串函数： $$ 下图显示了一个冲激函数与冲激串函数：

截图自 Digital Image Processing，符号与本文有所不同

下面我们求冲激串的傅里叶变换。注意冲激串是周期函数，不是绝对可积的，因此需要用到上一篇文章最后提到的技巧来计算。首先将 $$ 展开为傅里叶级数： $$ 其中： $$

于是 $$ 的傅里叶级数为： $$ 根据傅里叶变换的线性性，我们只需要求每一项的傅里叶变换： $$ 在上一篇文章中我们计算过 Dirac $$ 函数的傅里叶变换 $$，那么根据傅里叶变换的对偶性，有： $$ 因此： $$

这就是 $$ 的傅里叶变换结果。

采样定理

假设每间隔 $$ 对 $$ 做一次采样，得到序列 $$，其中 $$，如下图所示：

截图自 Digital Image Processing，符号与本文有所不同

根据上一节的内容，我们可以用冲激串函数将这个离散的序列写作连续的函数的形式： $$ 换句话说，$$ 就是采样后的函数。于是，一个自然的问题就是：采样操作对函数的傅里叶变换有什么影响呢？也就是说，采样后的函数的傅里叶变换与原函数的傅里叶变换有什么关系呢？

根据卷积定理，由于 $$ 是 $$ 与 $$ 的乘积，因此其傅里叶变换就是 $$ 与 $$ 的卷积，其中 $$ 已经在上一节中计算出来了，即 $$ 式。于是： $$ 由此可以看出，$$ 是一个以 $$ 为周期的连续周期函数，它是 $$ 的多份平移后的副本的叠加。

特别地，假设 $$ 是一个有限带宽的函数，即其傅里叶变换 $$ 仅在一个有限范围 $$ 内不为零。那么：

• 欠采样：周期 $$，平移后的 $$ 之间就会发生重叠，导致相加后在重叠区间内的 $$ 丢失了，这种现象称作混叠 (aliasing)；
• 过采样：周期 $$，那么各个平移后的 $$ 不仅没有重叠，还隔开了一段距离，这段距离上 $$；
• 临界采样：周期 $$，各个平移后的 $$ 刚好不会发生重叠。

下图展示了一个例子，第一行是一个有限带宽函数的傅里叶变换结果，第二、三、四行分别展示了过采样、临界采样和欠采样后，函数的傅里叶变换结果：

截图自 Digital Image Processing，符号与本文有所不同

因此，要想重建出原本的有限带宽函数，我们要避免欠采样，也即采样率需要满足： $$ 其中 $$ 表示信号的最大频率，这就是采样定理。当然，如果原信号本身不是有限带宽的，即不存在最大频率 $$，自然就不可能在采样后完美重建。好在现实中大多数信号可以近似为有限带宽的，因此只要采样率充分高，就能将重建误差控制在可接受范围内。

另外，从上面的图可以看出，当 $$ 满足采样定理时，只需要拿出 $$ 的一个周期并放大 $$ 倍，就能还原 $$： $$ 这里 $$ 相当于是一个理想低通滤波器。

离散时间傅里叶变换

由于 $$ 是 $$ 先采样（即在时域上离散化）、再做傅立叶变换得到的，因此我们称之为离散时间傅里叶变换。在上一节中，我们建立起了 $$ 与 $$ 之间的关系，即 $$ 和 $$ 式，发现了 $$ 其实就是 $$ 的多份平移副本的叠加，并自然引出了采样定理。这一节中，我们欲显式地写出 $$ 与 $$ 之间的变换关系。

对 $$ 做傅里叶变换，得： $$

这就是离散时间傅里叶正变换。

值得注意的是，由于 $$ 是周期函数，因此不能做傅立叶逆变换，否则结果发散。注意到，如果将 $$ 式改写一下： $$ 对比傅里叶级数表达式： $$ 可以发现二者有着相同的形式，也就是说，$$ 式其实就是函数 $$ 的傅里叶级数展开。于是有： $$ 也即： $$ 这就是离散时间傅里叶逆变换。

小结

在开启下一节之前，我们先对这一节的内容做一个小结。在从傅里叶变换推导到离散时间傅里叶变换的过程中，我们对函数的时域表示进行了采样，发现它的频域表示从非周期函数变成了周期函数。那么，基于傅里叶变换在形式上的对称性，容易想到，如果我们对函数的频域表示进行采样，那么它的时域表示应该也会从非周期函数变成周期函数——这不就是从傅里叶变换推导回了傅里叶级数吗？事实上，对比傅里叶级数 $$ 和离散时间傅立叶变换 $$，可以发现二者在形式上的确是对称的。

值得注意的是，时域和频域在周期性/非周期性和离散性/连续性上有着固定的对应关系——时域上周期（非周期）对应频域上离散（连续）；时域上离散（连续）对应频域上周期（非周期）。对于傅立叶级数、傅立叶变换和离散时间傅立叶变换，分别有：

• 傅立叶级数：时域周期连续、频域离散非周期
• 傅立叶变换：时域非周期连续、频域连续非周期
• 离散时间傅立叶变换：时域非周期离散、频域连续周期

于是，剩下的最后一种组合就呼之欲出了，即时域和频域上均是离散周期函数，这就是离散傅立叶变换。进一步地，我们还能立刻想到两种推导离散傅立叶变换的路径——对离散时间傅立叶变换的频域表示采样、或对傅立叶级数的时域表示采样，如下图所示：

离散傅立叶变换 (DFT)

尽管离散时间傅立叶变换在时域上做了离散化，但是在频域上是连续的，计算机依旧无法处理。同理，傅立叶级数频域是离散的，但时域是连续的，也无法处理。因此，我们希望构建时域、频域均为离散序列之间的变换关系，即离散傅立叶变换。

从离散时间傅立叶变换推导

考虑一个长为 $$ 的序列 $$，可以等价地将其视作在 $$ 和 $$ 时取值为零的无限长序列： $$ 对其进行离散时间傅立叶变换得： $$ 由前文可知这是一个连续的、以 $$ 为周期的函数。考虑在每个周期等间隔采样 $$ 个点，即间隔为 $$，得到序列 $$，那么代入上式得： $$ 这就是离散傅立叶正变换。

倘若将序列 $$ 写作连续函数形式： $$ 那么代入离散时间傅立叶逆变换 $$ 式： $$ 这就是离散傅立叶逆变换。

为了与后文的符号统一，我们用 $$ 和 $$ 来代替 $$ 和 $$，就得到了离散傅里叶变换对： $$

矩阵形式

将 $$ 和 $$ 都视作 $$ 维向量，则式 $$ 可以写作矩阵形式。具体而言，记 $$ 为 $$ 次单位复数根，构建矩阵： $$ 简记作 $$，其中 $$ 从 0 开始计数。于是离散傅里叶变换写作： $$ 对于逆变换，可以验证 $$，其中 $$ 表示 $$ 的共轭转置矩阵，因此 $$，故离散傅里叶逆变换写作： $$ 当然，这也可以直接从式 $$ 中看出来。

离散傅里叶变换的性质

记 $$，DFT 具有以下常用性质。

线性性：

$$

平移性质：

$$ 特别地，当 $$ 时，有： $$

周期性：

$$

共轭对称性：若 $$ 是实函数，则 $$ 是共轭对称的（实部偶函数，虚部奇函数），即： $$ 若 $$ 是虚函数，则 $$ 是共轭反对称的（实部奇函数，虚部偶函数），即： $$

循环卷积定理：

$$ 值得注意的是，由于离散傅里叶变换具有周期性，因此这里的卷积是循环卷积，即先将 $$ 与 $$ 进行周期延拓后再做卷积。在下一篇文章中我们将看到，在图像处理中这种卷积模式并不是我们想要的，因此需要做一些额外的操作。

参考资料

1. Rafael C. Gonzalez. Digital Image Processing, Fourth Edition. ↩︎
2. Wikipedia. Discrete-time Fourier transform. https://en.wikipedia.org/wiki/Discrete-time_Fourier_transform ↩︎
3. 彻底搞懂傅里叶变换之实用干货分享(四)-离散傅里叶变换(DFT) - anders的文章 - 知乎 https://zhuanlan.zhihu.com/p/405143684 ↩︎
4. Half_Kettle. 从傅里叶级数（Fourier series）到离散傅里叶变换（Discrete Fourier transform）. https://www.cnblogs.com/yang-ding/p/15925430.html ↩︎
5. 《数字图像处理》图像表征：离散傅里叶变换（DFT）、离散余弦变换（DCT）、主成分分析（PCA） - zhiwei的文章 - 知乎 https://zhuanlan.zhihu.com/p/563668048 ↩︎