傅里叶变换02 - 傅里叶变换

#

1. 傅里叶变换

周期为 $𝑇$ 的函数 $𝑓 (𝑥)$ 可以用傅里叶级数来表示，但是无法表示非周期函数。非周期函数可以看做周期 $𝑇 \to \infty$ 的周期函数。当 $𝑇 \to \infty$ 时，则

𝜔 = \frac{2 𝜋}{𝑇} \to 0

代入傅里叶级数中，得到：

\begin{aligned} 𝑓 (𝑥) & = \sum_{𝑛 = - \infty}^{\infty} 𝑑_{𝑛} \cdot 𝑒^{𝑖 𝑛 𝜔 𝑥} \\ = \sum_{𝑛 = - \infty}^{\infty} (\frac{1}{𝑇} \cdot \int_{- \frac{𝑇}{2}}^{\frac{𝑇}{2}} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝑛 𝜔 𝑥}) \cdot 𝑒^{𝑖 𝑛 𝜔 𝑥} \\ = \sum_{𝑛 = - \infty}^{\infty} (\frac{1}{2 𝜋} \cdot 𝜔 \cdot \int_{- \frac{𝑇}{2}}^{\frac{𝑇}{2}} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝑛 𝜔 𝑥}) \cdot 𝑒^{𝑖 𝑛 𝜔 𝑥} \end{aligned}

基于定积分的概念，式 2 可以看做对连续变量 $𝜔^{'}$ 的黎曼和形式。对于连续变量 $𝜔^{'}$ ，将定义区间分为 $𝑚$ 份小区间，每个区间的长度为 $Δ 𝜔$ ，为微小增量。对于第 $𝑛$ 个区间，选取的变量为 $𝜀 = 𝑛 Δ 𝜔$ ，则式 2 可以变换为：

\begin{aligned} 𝑓 (𝑥) & = \sum_{𝑛 = - \infty}^{\infty} 𝑑_{𝑛} \cdot 𝑒^{𝑖 𝑛 𝜔 𝑥} \\ = \sum_{𝑛 = - \infty}^{\infty} (\frac{1}{2 𝜋} \cdot Δ 𝜔 \cdot \int_{- \frac{𝑇}{2}}^{\frac{𝑇}{2}} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝜀 𝑥}) \cdot 𝑒^{𝑖 𝜀 𝑥} \\ = \sum_{𝑛 = - \infty}^{\infty} ((\frac{1}{2 𝜋} \cdot \int_{- \frac{𝑇}{2}}^{\frac{𝑇}{2}} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝜀 𝑥}) \cdot 𝑒^{𝑖 𝜀 𝑥}) \cdot Δ 𝜔 \\ = \int_{- \infty}^{\infty} \frac{1}{2 𝜋} \int_{- \infty}^{\infty} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝜔 𝑥} \cdot 𝑒^{𝑖 𝜔 𝑥} 𝜔 𝜔 \\ = \frac{1}{2 𝜋} \cdot \int_{- \infty}^{\infty} \int_{- \infty}^{\infty} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝜔 𝑥} \cdot 𝑒^{𝑖 𝜔 𝑥} 𝜔 𝜔 \end{aligned}

令 $𝐹 (𝜔)$ 为：

𝐹 (𝜔) = \int_{- \infty}^{\infty} 𝑓 (𝑥) \cdot 𝑒^{- 𝑖 𝜔 𝑥}

则傅里叶变换公式可以表示为：

𝑓 (𝑥) = \int_{- \infty}^{\infty} 𝐹 (𝜔) \cdot 𝑒^{𝑖 𝜔 𝑥} 𝜔 𝜔

其中 $𝐹 (𝜔)$ 为频率为 $𝜔$ 时的线性组合系数。

#

2. 离散傅里叶变换

傅里叶变换与傅里叶级数都是对连续信号进行分析处理的工具，而无法对离散的时间信号或者有限长信号进行分析。为了解决傅里叶变换的局限性，离散傅里叶变换被提出来对离散时间信号进行频谱分析，例如二维图像、离散采样的信号等。

#

2.1. 周期离散信号的表示

对于离散信号 $𝑥 [𝑛]$ ，如果满足：

𝑥 [𝑛] = 𝑥 [𝑛 + 𝑁]

则该信号为一个周期为 $𝑁$ 的信号。其最小正周期为 $𝑁$ ，频率 $𝜔_{𝑜} = 2 𝜋 / 𝑁$ 。

复指数函数 $𝜙 [𝑛] = 𝑒^{𝑖 𝜔_{𝑜} 𝑛}$ 也是周期函数，其中 $𝑛$ 为函数自变量。该函数的周期为 $𝑁$ 。并且，式 7 中的复指数函数都是周期函数，

𝜙_{𝑘} [𝑛] = 𝑒^{𝑖 𝑘 𝜔_{𝑜} 𝑛} = 𝑒^{𝑖 𝑘 \frac{2 𝜋}{𝑁} \cdot 𝑛}, 𝑘 = \pm 0, \pm 1, \pm 2, \dots

fuzhishu 其频率都是 $𝜔_{𝑜}$ 的倍数。

事实上，式 7 中只有 $𝑁$ 个函数是不同。因为函数 $𝜙 [𝑛]$ 为周期函数，其周期为 $𝑁$ ，因此：

𝜙_{𝑘 + 𝑚 𝑁} [𝑛] = 𝜙_{𝑘} [𝑛]

另外，设函数集合 $Φ$ 定义如下：

Φ = {𝑒^{𝑖 𝑘 𝜔_{𝑜} 𝑛} | 𝑘 = 0, 1, 2, \dots, 𝑁 - 1}

定义在函数集 $Φ$ 上的内积为：

⟨ 𝑓 [𝑛], 𝑔 [𝑛] ⟩ = \sum_{𝑘 = 0}^{𝑁 - 1} 𝑓 [𝑛] \cdot 𝑔 [𝑛]

则可以证明：函数集 $Φ$ 是正交函数集。

证明

\begin{aligned} ⟨ 𝜙_{𝑘} [𝑛], 𝜙_{𝑚} [𝑛] ⟩ & = \sum_{𝑖 = 0}^{𝑁 - 1} 𝑒^{𝑖 𝑘 \frac{2 𝜋}{𝑁} 𝑛} \cdot 𝑒^{- 𝑖 𝑚 \frac{2 𝜋}{𝑁} 𝑛} \\ = \sum_{𝑖 = 0}^{𝑁 - 1} 𝑒^{𝑖 (𝑘 - 𝑚) \frac{2 𝜋}{𝑁} 𝑛} \end{aligned}

当 $𝑘 = 𝑚$ 时，有：

\begin{aligned} ⟨ 𝜙_{𝑘} [𝑛], 𝜙_{𝑚} [𝑛] ⟩ & = \sum_{𝑖 = 0}^{𝑁 - 1} 𝑒^{𝑖 (𝑘 - 𝑚) \frac{2 𝜋}{𝑁} 𝑛} \\ = \sum_{𝑖 = 0}^{𝑁 - 1} 𝑒^{𝑖 2 𝜋 0} \\ = \sum_{𝑖 = 0}^{𝑁 - 1} 1 \\ = 𝑁 \end{aligned}

当 $𝑘 \neq 𝑚$ 时，设 $𝛼 = 𝑒^{𝑖 (𝑘 - 𝑚) \frac{2 𝜋}{𝑁}}$ ，则有：

𝛼 \neq 1

根据几何级数公式，有：

\sum_{𝑖 = 0}^{𝑁} 𝛼^{𝑛} = \frac{1 - 𝑎^{𝑁}}{1 - 𝑎}

由于

𝑎^{𝑁} = {(𝑒^{𝑖 2 𝜋 \frac{𝑘 - 𝑚}{𝑁}})}^{𝑁} = 𝑒^{𝑖 2 𝜋 (𝑘 - 𝑚)} = cos ((𝑘 - 𝑚) 2 𝜋) - 𝑖 sin ((𝑘 - 𝑚) 2 𝜋) = 1

因此可得：

\sum_{𝑖 = 0}^{𝑁} 𝛼^{𝑛} = \frac{1 - 𝛼^{𝑁}}{1 - 𝛼} = 0

综上所述：

⟨ 𝜙_{𝑘} [𝑛], 𝜙_{𝑚} [𝑛] ⟩ = {\begin{cases} 𝑁 & , if 𝑘 = 𝑚 \\ 0 & , if 𝑘 \neq 𝑚 \end{cases}

因此，函数集 $Φ$ 是正交函数集。

因此，任意的周期为 $𝑁$ 的离散信号 $𝑥 [𝑛]$ 都可以使用正交函数集 $Φ$ 的线性组合来表示，即：

𝑥 [𝑛] = \sum_{𝑘 = 0}^{𝑁 - 1} 𝑎_{𝑘} \cdot 𝜙_{𝑘} [𝑛]

其中，系数 $𝑎_{𝑛}$ 可以用正交函数的性质表示为：

\begin{aligned} 𝑎_{𝑘} & = \frac{1}{𝑁} \cdot ⟨ 𝑥 [𝑛], 𝜙_{𝑘} [𝑛] ⟩ \\ = \frac{1}{𝑁} \cdot \sum_{𝑛 = 0}^{𝑁 - 1} (𝑥 [𝑛] \cdot 𝑒^{𝑖 𝑘 𝜔_{𝑜} 𝑛}) \end{aligned}

#

3. 快速傅里叶变换

离散傅里叶变换需要求 $𝑁$ 个线性组合系数 $𝑎_{𝑘}$ ，而每个系数 $𝑎_{𝑘}$ 都需要 $𝑁$ 次复数乘法。因此，计算所有 $𝑁$ 个组合系数的算法复杂度为 $𝑂 (𝑛^{2})$ 。

为了解决计算离散傅里叶系数的算法复杂度过高的问题，快速傅里叶变换被提出了。快速傅里叶变换利用分治的思想，将大规模的DFT(discret fourier transform)问题转换为若干个小规模的DFT问题进行递归求解，其算法复杂度为 $𝑂 (𝑛 log 𝑛)$ 。

#

3.1. $𝑁$ 次单位根及其性质

对于复平面上的单位圆，将其 $𝑁$ 等分，得到 $𝑁$ 个等分点的集合，该集合称为 $𝑁$ 次单位根。其中每个点的相位角相差 $\frac{2 𝜋}{𝑁}$ 弧度。该集合中的根可以表示为：

𝑊_{𝑁}^{𝑘} = 𝑒^{𝑖 \frac{2 𝜋}{𝑁} \cdot 𝑘}, 𝑘 = 0, 1, \dots, 𝑁 - 1

#

3.2. 快速傅里叶算法

对于周期为 $𝑁$ 的函数 $𝑥 [𝑛]$ ，其线性组合系数为 $𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑁 - 1}$ 。离散傅里叶变换的线性组合系数 $𝑎_{𝑘}$ 的计算公式如下：

𝑎_{𝑘} = \frac{1}{𝑁} \cdot \sum_{𝑛 = 0}^{𝑁 - 1} (𝑥 [𝑛] \cdot 𝑒^{𝑖 𝑘 𝜔_{𝑜} 𝑛})

其中：

𝜔_{𝑜} = \frac{2 𝜋}{𝑁}

对该公式中的形式进行简化，令

𝛼 = 𝑒^{𝑖 𝑘 𝜔_{𝑜}} = 𝑊_{𝑁}^{𝑘},

且令函数 $𝑓 (𝛼)$ 为：

\begin{aligned} 𝑓 (𝛼) & = \sum_{𝑛 = 0}^{𝑁 - 1} (𝑥 [𝑛] \cdot 𝑒^{𝑖 𝑘 𝜔_{𝑜} 𝑛}) \\ = \sum_{𝑛 = 0}^{𝑁 - 1} (𝑥 [𝑛] \cdot 𝛼^{𝑛}) \end{aligned}

#

3.2.1. 分治法

将函数 $𝑓 (𝑎)$ 分解为：

\begin{aligned} 𝑓 (𝛼) & = 𝑥 [0] \cdot 𝛼^{0} + 𝑥 [1] \cdot 𝛼^{1} + \dots + 𝑥 [𝑁 - 1] \cdot 𝛼^{𝑁 - 1} \\ = (𝑥 [0] \cdot 𝛼^{0} + 𝑥 [2] \cdot 𝛼^{2} + \dots + 𝑥 [𝑁 - 2] \cdot 𝛼^{𝑁 - 2}) \\ + (𝑥 [1] \cdot 𝛼^{1} + 𝑥 [3] \cdot 𝛼^{3} + \dots + 𝑥 [𝑁 - 1] \cdot 𝛼^{𝑁 - 1}) \\ = (𝑥 [0] \cdot 𝛼^{0} + 𝑥 [2] \cdot 𝛼^{2} + \dots + 𝑥 [𝑁 - 2] \cdot 𝛼^{𝑁 - 2}) \\ + 𝛼 \cdot (𝑥 [1] \cdot 𝛼^{0} + 𝑥 [3] \cdot 𝛼^{2} + \dots + 𝑥 [𝑁 - 1] \cdot 𝛼^{𝑁 - 2}) \end{aligned}

令

\begin{aligned} 𝑓_{1} (𝛼) & = (𝑥 [0] \cdot 𝛼^{0} + 𝑥 [2] \cdot 𝛼^{1} + \dots + 𝑥 [𝑁 - 2] \cdot 𝛼^{\frac{𝑁}{2} - 1}) \\ 𝑓_{2} (𝛼) & = (𝑥 [1] \cdot 𝛼^{1} + 𝑥 [3] \cdot 𝛼^{1} + \dots + 𝑥 [𝑁 - 1] \cdot 𝛼^{\frac{𝑁}{2} - 1}) \end{aligned}

则

𝑓 (𝛼) = 𝑓_{1} (𝛼^{2}) + 𝛼 \cdot 𝑓_{2} (𝛼^{2})

根据 $𝑁$ 次方根的性质3，即：

𝑊_{𝑁}^{𝑚 𝑘} = 𝑊_{\frac{𝑁}{𝑚}}^{𝑘}

可以得到：

\begin{aligned} 𝑓 (𝛼) & = 𝑓 (𝑊_{𝑁}^{𝑘}) = 𝑓_{1} (𝑊_{𝑁}^{2 𝑘}) + 𝛼 \cdot 𝑓_{2} (𝑊_{𝑁}^{2 𝑘}) \\ = 𝑓_{1} (𝑊_{\frac{𝑁}{2}}^{𝑘}) + 𝛼 \cdot 𝑓_{2} (𝑊_{\frac{𝑁}{2}}^{𝑘}) \end{aligned}

函数 $𝑓_{1} (𝑊_{\frac{𝑁}{2}}^{𝑘})$ 展开为：

𝑓_{1} (𝑊_{\frac{𝑁}{2}}^{𝑘}) = 𝑥 [0] \cdot 𝑊_{\frac{𝑁}{2}}^{𝑘 \cdot 0} + 𝑥 [2] \cdot 𝑊_{\frac{𝑁}{2}}^{𝑘 \cdot 1} + 𝑥 [4] \cdot 𝑊_{\frac{𝑁}{2}}^{𝑘 \cdot 2} + \dots + 𝑥 [2 ⌊ \frac{𝑁}{2} ⌋] \cdot 𝑊_{\frac{𝑁}{2}}^{𝑘 \cdot 𝑛}

对于周期为 $𝑁$ 的信号 $𝑥 [𝑛]$ ，将其下标 $𝑛$ 为偶数与奇数的信号元素进行分组，可以得到两个子信号，分别为 $𝑥 [2 𝑛]$ 以及x[2 n + 1]，其中 $𝑛$ 满足：

𝑛 \in 𝑍, 且 𝑛 \leq ⌊ \frac{𝑁}{2} ⌋

因此， $𝑓_{1} (𝑊_{\frac{𝑁}{2}}^{𝑘})$ 可以看做是对周期为 $\frac{𝑁}{2}$ 的信号 $𝑥 [2 𝑛]$ 求取系数 $𝑎_{𝑘}$ 过程。同理， $𝑓_{2} (𝑊_{\frac{𝑁}{2}}^{𝑘})$ 可以看为对周期为 $\frac{𝑁}{2}$ 的信号 $𝑥 [2 𝑛 + 1]$ 求取系数 $𝑎_{𝑘}$ 的过程。

从上面可以看出，对于周期为 $𝑇$ 的信号 $𝑥 [𝑛]$ ，求取其离散傅里叶变换系数 ${𝑎_{𝑘} | 𝑘 = 0, 1, \dots, 𝑁 - 1}$ 的过程，可以划分为两个子问题：

求子信号 $𝑥 [2 𝑛]$ 的离散傅里叶变换系数
求子信号 $𝑥 [2 𝑛 + 1]$ 的离散傅里叶变换系数

该流程一直会递归，则到子信号的周期为 $1$ ，此时可以直接求解。

#

3.2.2. 周期性

当对周期为 $𝑇$ 的信号 $𝑥 [𝑛]$ 求离散傅里叶变换的系数时，根据 $𝑁$ 次单位根的对称性，可以发现以下结论：

令 $𝑚 = 𝑘 + \frac{𝑁}{2}$ ，其中 $0 \leq 𝑘 < \frac{𝑁}{2}$ 。根据 $𝑁$ 次单位根的周期性有：

\begin{aligned} 𝑓 (𝑊_{𝑁}^{𝑘 + \frac{𝑁}{2}}) & = 𝑓_{1} (𝑊_{𝑁}^{2 𝑘 + 𝑁}) + 𝑊_{𝑁}^{𝑘 + \frac{𝑁}{2}} \cdot 𝑓_{2} (𝑊_{𝑁}^{2 𝑘 + 𝑁}) \\ = 𝑓_{1} (𝑊_{𝑁}^{2 𝑘} \cdot 𝑊_{𝑁}^{𝑁}) + 𝑊_{𝑁}^{𝑘 + \frac{𝑁}{2}} \cdot 𝑓_{2} (𝑊_{𝑁}^{2 𝑘} \cdot 𝑊_{𝑁}^{𝑁}) \\ = 𝑓_{1} (𝑊_{𝑁}^{2 𝑘} \cdot 1) + 𝑊_{𝑁}^{𝑘 + \frac{𝑁}{2}} \cdot 𝑓_{2} (𝑊_{𝑁}^{2 𝑘} \cdot 1) \\ = 𝑓_{1} (𝑊_{𝑁}^{2 𝑘}) - 𝑊_{𝑁}^{𝑘} \cdot 𝑓_{2} (𝑊_{𝑁}^{2 𝑘}) \\ = 𝑓_{1} (𝑊_{\frac{𝑁}{2}}^{𝑘}) - 𝑊_{𝑁}^{𝑘} \cdot 𝑓_{2} (𝑊_{\frac{𝑁}{2}}^{𝑘}) \\ = 𝑓_{1} (𝑊_{\frac{𝑁}{2}}^{𝑘}) - 𝛼 \cdot 𝑓_{2} (𝑊_{\frac{𝑁}{2}}^{𝑘}) \end{aligned}

因此，当 $𝑚 > \frac{𝑁}{2}$ 时，根据对称性，可以通过子信号 $𝑥 [2 𝑛]$ 与 $𝑥 [2 𝑛 + 1]$ 的离散傅里叶变换系数，可以简单的得到离散傅里叶变换中 $𝑎_{𝑚}$ 的系数值。