离散傅里叶变换

\begin{matrix}  \end{matrix}

闲谈：按道理来说，离散傅里叶变换只涉及有限点运算，应该比无限点的 DTFT 好学，但学起来却晕得不行😵 究其原因，我在学习时是从 DTFT 入手的，遇到一些不同之处老是转不过来。
所以，我在网上找到了一份很详细的英语资料，从另一个方向学习 DFT。下面我就写写我学习过程中的笔记。

DFT 概述

对于长度为 $N$ 的序列 $x [n]$ ，其离散傅里叶变换 DFT 定义为：

X [k] ≜ \sum_{n = 0}^{N - 1} x [n] e^{- j ω_{k} n} = \sum_{n = 0}^{N - 1} x [n] e^{- j 2 π k n / N}

DFT 的引入

从几何引入 DFT

我们可以将长度为 $N$ 的信号看做一个 $N$ 维向量 $x = [x_{0}, x_{1}, \dots, x_{N - 1}]$ ，每一个 $n$ 对应一个维度。

我们可以定义向量的内积：

⟨ u, v ⟩ ≜ \sum_{n = 0}^{N - 1} u [n] v^{*} [n]

我们可以很容易得出向量内积的几个性质：

$⟨ u, u ⟩ = E_{u}$ （能量）
共轭对称性： $⟨ u, v ⟩ = ⟨ v, u ⟩^{*}$
线性性：
- $⟨ α u + β v, w ⟩ = α ⟨ u, w ⟩ + β ⟨ v, w ⟩$
- $⟨ u, α v + β w ⟩ = α ⟨ u, v ⟩ + β ⟨ u, w ⟩$

我们可以用内积定义向量的范数：

‖ u ‖ ≜ \sqrt{⟨ u, u ⟩} = \sqrt{\sum_{n = 0}^{N - 1} u [n] u^{*} [n]}

有了内积和范数，就可以得到向量的投影：

P_{x} (y) ≜ \frac{⟨ y, x ⟩}{‖ x ‖^{2}} x

上式表示向量 $y$ 在 $x$ 上的投影。有了投影，我们就可以得到信号的正交分解：

x = \sum_{n = 0}^{N - 1} α_{n} s_{n} α_{n} = P_{s_{n}} (x)

其中， ${s_{n}}$ 是一组正交基，满足：

P_{s_{k}} (s_{l}) ≜ \frac{⟨ s_{l}, s_{k} ⟩}{‖ s_{k} ‖^{2}} s_{k} = {\begin{cases} 0, & l \neq k \\ s_{k}, & l = k \end{cases}

我们都知道不同频率的正弦信号在一个周期内相互正交（如果时长不是整周期，则不正交），比如：

x_{1} [n] = A_{1} \sin (\frac{2 π k_{1}}{N} n) x_{2} [n] = A_{2} \sin (\frac{2 π k_{2}}{N} n) k_{1}, k_{2} \in Z 且 0 \leq k_{1}, k_{2} < N

\begin{aligned} ⟨ x_{1}, x_{2} ⟩ & = \sum_{n = 0}^{N - 1} x_{1} x_{2} \\ = A_{1} A_{2} \sum_{n = 0}^{N - 1} \sin (\frac{2 π k_{1}}{N} n) \sin (\frac{2 π k_{2}}{N} n) \\ = \frac{A_{1} A_{2}}{2} \sum_{n = 0}^{N - 1} [\cos (\frac{2 π k_{1}}{N} n - \frac{2 π k_{2}}{N} n) - \cos (\frac{2 π k_{1}}{N} n + \frac{2 π k_{2}}{N} n)] \\ = \frac{A_{1} A_{2}}{2} \sum_{n = 0}^{N - 1} {\cos [\frac{2 π}{N} (k_{1} - k_{2}) n] - \cos [\frac{2 π}{N} (k_{1} + k_{2}) n]} \\ = {\begin{cases} 0, & k_{1} \neq k_{2} \\ \frac{A_{1} A_{2} N}{2}, & k_{1} = k_{2} \end{cases} \end{aligned}

如果我们以 $f_{s}$ 对 $x (t)$ 采样得到 $N$ 点 $x [n]$ ，根据上面的证明，我们能取的谐波频率只能是：

f_{k} = \frac{k}{N} f_{s}, k = 0, 1, 2, \dots, N - 1

于是我们构造如下一组正交基（从正弦推广到e指数）：

s_{k} [n] ≜ e^{j ω_{k} n T} = e^{j 2 π k n / N} ω_{k} ≜ 2 π f_{k} = 2 π k \frac{f_{s}}{N} ， T = \frac{1}{f_{s}}

为了偷懒，我们定义 $W_{N} = e^{- j 2 π / N}$ ，因此 $s_{k} = W_{N}^{- k}$ 。有趣的是，这一组正交基正好均分复平面上的单位圆（如下图所示）。

我们可以证明这是一组正交基：

\begin{aligned} ⟨ s_{k}, s_{l} ⟩ & ≜ \sum_{n = 0}^{N - 1} s_{k} [n] s_{l}^{*} [n] \\ = \sum_{n = 0}^{N - 1} e^{j 2 π (k - l) n / N} \\ = \frac{1 - e^{j 2 π (k - l)}}{1 - e^{j 2 π (k - l) / N}} \\ = {\begin{cases} 0 & k \neq l \\ N & k = l \end{cases} \end{aligned}

我们进一步对 $s_{k}$ 进行正则化：

{\tilde{s}}_{k} [n] ≜ \frac{s_{k} [n]}{\sqrt{N}} ⟨ {\tilde{s}}_{k}, {\tilde{s}}_{l} ⟩ = {\begin{cases} 0 & k \neq l \\ 1 & k = l \end{cases}

信号在 ${\tilde{s}}_{k}$ 上的投影就是 NDFT（Normalized DFT），信号在 $s_{k}$ 上的投影的 $N$ 倍就是 DFT：

X [k] ≜ ⟨ x, s_{k} ⟩ ≜ \sum_{n = 0}^{N - 1} x [n] s_{k}^{*} [n] k = 0, 1, \dots, N - 1 其 中 ， s_{k} [n] ≜ e^{j 2 π k n / N}

$x$ 在 $s_{k}$ 上的投影为：

\frac{⟨ x, s_{k} ⟩}{‖ s_{k} ‖^{2}} = \frac{X [k]}{N}

要从投影恢复回原信号，我们只需要将分解后的向量相加，注意到DFT实际是投影的 $N$ 倍，所以还需要除以 $N$ ：

x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] e^{j 2 π k n / N}

从抽样引入 DFT

回忆我们对模拟信号进行采样的过程，经过采样后，频域进行了周期性延拓。同理，如果我们对频域进行采样，那么时域也进行周期性延拓，证明如下：我们先求解 $δ [n - k N]$ 的离散时间傅里叶变换：

\begin{aligned} a_{k} & = \frac{1}{N} \sum_{n = ⟨ N ⟩} δ [n - k N] e^{- j k ω_{0} n} \\ = \frac{1}{N} \sum_{n = 0}^{N - 1} δ [n - k N] e^{- j k ω_{0} n} \\ = \frac{1}{N} \end{aligned}

\begin{aligned} X (e^{j ω}) & = \sum_{k = - \infty}^{+ \infty} 2 π a_{k} δ (ω - \frac{2 π k}{N}) \\ = \frac{2 π}{N} \sum_{k = - \infty}^{+ \infty} δ (ω - \frac{2 π k}{N}) \end{aligned}

由于时域卷积对应频域相乘，故如果在频域上 $[0, 2 π]$ 内取 $N$ 点，则时域上会以 $N$ 为周期。结合离散时间傅里叶变换（DTFT）：

分 析 公 式 ： X (e^{j ω}) = \sum_{n = - \infty}^{+ \infty} x [n] e^{- j ω n} 综 合 公 式 ： x [n] = \frac{1}{2 π} \int_{2 π} X (e^{j ω}) e^{j ω n} d ω

我们可以得到离散傅里叶变换（DFT）：

X [k] ≜ \sum_{n = 0}^{N - 1} x [n] e^{- j \frac{2 π k}{N} n} x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] e^{j \frac{2 π k}{N} n}

把 $ω$ 替换成 $\frac{2 π k}{N}$ 的过程就相当于在频域取样。为了偷懒，我们定义 $W_{N} = e^{- j 2 π / N}$ ，并改写为：

X [k] ≜ \sum_{n = 0}^{N - 1} x [n] W_{N}^{k n} x [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] W_{N}^{- k n}

从 $X [k]$ 恢复成 $X (e^{j ω})$ 则是通过插值来实现：

\begin{aligned} X (e^{j ω}) & = \sum_{n = 0}^{N - 1} {\frac{1}{N} \sum_{k = 0}^{N - 1} X [k] W_{N}^{- k n}} e^{- j ω n} \\ = \frac{1}{N} \sum_{k = 0}^{N - 1} X [k] \sum_{n = 0}^{N - 1} e^{j \frac{2 π k}{N} n} e^{- j ω n} \end{aligned}

\begin{aligned} \sum_{n = 0}^{N - 1} e^{j \frac{2 π k}{N} n} e^{- j ω n} & = \frac{1 - e^{- j (ω N - 2 π k)}}{1 - e^{- j (ω - 2 π k / N)}} \\ = \frac{e^{- j [(ω N - 2 π k) / 2]}}{e^{- j [(ω N - 2 π k) / 2 N]}} \frac{\sin (\frac{ω N - 2 π k}{2})}{\sin (\frac{ω N - 2 π k}{2 N})} \\ = \frac{\sin (\frac{ω N - 2 π k}{2})}{\sin (\frac{ω N - 2 π k}{2 N})} e^{- j [ω - (2 π k / N)] [(N - 1) / 2]} \end{aligned}

我们定义插值函数为 $Φ (ω)$ ：

\begin{aligned} Φ (ω) & = \frac{\sin (\frac{ω N}{2})}{N \sin (\frac{ω}{2})} e^{- j ω [(N - 1) / 2]} \end{aligned} 特 殊 的 ， Φ (ω) |_{ω = 2 π k / N} = {\begin{cases} 1, & k = 0 \\ 0, & 1 \leq k \leq N - 1 \end{cases}

则插值过程能表示成：

X (e^{j ω}) = \sum_{k = 0}^{N - 1} X [k] Φ (ω - \frac{2 π k}{N})

频谱泄露

从采样的角度去理解的话，对于那些介于采样点之间的频率，从直觉上来讲是无法得到的，但并非如此。

我们可以假设任意一个正弦信号： $x [n] = e^{j ω_{x} n T}$ ，将它与正交基做内积：

\begin{aligned} X (ω_{k}) & = ⟨ x, s_{k}^{*} ⟩ \\ = \sum_{0}^{N - 1} e^{j ω_{x} n T} e^{- j ω_{k} n T} \\ = \sum_{0}^{N - 1} e^{j (ω_{x} - ω_{k}) n T} \\ = \frac{1 - e^{j (ω_{x} - ω_{k}) N T}}{1 - e^{j (ω_{x} - ω_{k}) T}} \\ = e^{j (ω_{x} - ω_{k}) (N - 1) T / 2} \frac{\sin [(ω_{x} - ω_{k}) N T / 2]}{\sin [(ω_{x} - ω_{k}) T / 2]} \end{aligned}

显然，当 $ω_{x} = ω_{k}$ 时， $X (ω_{k}) = N$ ；而当 $ω_{x} \neq ω_{k}$ 时，有：

| X (ω_{k}) | = | \frac{\sin [(ω_{x} - ω_{k}) N T / 2]}{\sin [(ω_{x} - ω_{k}) T / 2]} |

我们之前定义过：

ω_{k} ≜ 2 π k \frac{f_{s}}{N} = 2 π k \frac{1}{T N}, k = 0, 1, \dots, N - 1

我们不妨取 $N = 16$ ， $x = N / 5$ （也就是 $ω_{x} = 2 π \frac{N}{5} \frac{f_{s}}{N}$ ），作出图像：

我们可以看到，最靠近 $N / 5$ 的谱线，也就是 $k = N / 4 = 4$ 的谱线是最高的，另外，其他谱线也有一定的值。这就叫 频谱泄露。

上面是通过公式推导得到的，我们可以用 matlab 来进行验证，最终画出来的图像是一样的。

fs=1;
N=16;
x=N/5;
wx=2*pi*x*fs;
n=[0:N-1];
xn=exp(j*wx*n);
wn=2*pi*n/N;
stem(wn,abs(fft(xn)));

常见 DFT 变换对

\sum_{k = - \infty}^{\infty} δ [n + N k] = {\begin{cases} 1, & if n = 0, \pm N, \pm 2 N, \dots \\ 0, & else. \end{cases} \overset{D F T}{⟷} 1 (period N)

e^{j 2 π k_{0} n / N} \overset{D F T}{⟷} N δ [⟨ k - k_{0} ⟩_{N}]

\cos (\frac{2 π}{N} k_{0} n) \overset{D F T}{⟷} \frac{N}{2} (δ [⟨ k - k_{0} ⟩_{N}] + δ [⟨ k - k_{0} ⟩_{N}])

DFT 的性质

线性性

α g [n] + β h [n] \overset{DFT}{⟷} α G [k] + β H [k]

这个没啥好说的，证明方法和之前傅里叶变换一样。

圆周时移

由于 DFT 本质上是对原信号在时域上进行周期延拓，那么当信号进行时移变换时，实际上是在进行“圆周平移”。

g [⟨ n - n_{0} ⟩_{N}] \overset{DFT}{⟷} W_{N}^{k n_{0}} G [k]

当然，我们也可以简单证明一下：

\begin{aligned} \sum_{n = 0}^{N - 1} x [⟨ n - n_{0} ⟩_{N}] W_{N}^{k n} & = \sum_{n = 0}^{N - 1} x [⟨ n - n_{0} ⟩_{N}] W_{N}^{k (n - n_{0} + n_{0})} \\ = W_{N}^{k n_{0}} \sum_{n = 0}^{N - 1} x [⟨ n - n_{0} ⟩_{N}] W_{N}^{k (n - n_{0})} \\ = W_{N}^{k n_{0}} X [k] \end{aligned}

圆周频移

W_{N}^{- k_{0} n} g [n] \overset{DFT}{⟷} G [⟨ k - k_{0} ⟩_{N}]

对称性

序列	DFT
$x [n] = x_{re} [n] + j x_{im} [n]$	$X [k] = X_{re} [k] + j X_{im} [k]$
$x^{*} [n]$	$X^{*} [⟨ - k ⟩_{N}]$
$x^{*} [⟨ - n ⟩_{N}]$	$X^{*} [k]$
$x_{re} [n]$	$X_{cs} = \frac{1}{2} {X [k] + X^{*} [⟨ - k ⟩_{N}]}$
$j x_{im} [n]$	$X_{ca} [k] = \frac{1}{2} {X [k] - X^{*} [⟨ - k ⟩_{N}]}$
$x_{cs} [n]$	$X_{re} [k]$
$x_{ca} [n]$	$j X_{im} [k]$

乍一看好像很复杂，我们来看看看第 2 条式子的证明👀：

\begin{aligned} \sum_{n = 0}^{N - 1} x^{*} [n] e^{- \frac{2 π k n}{N}} & = {\sum_{n = 0}^{N - 1} x [n] e^{2 π k n / N}}^{*} \\ = {\sum_{n = 0}^{N - 1} x [n] e^{- 2 π (- k) n / N}}^{*} \\ = {\sum_{n = 0}^{N - 1} x [n] e^{- 2 π ⟨ - k ⟩_{N} n / N}}^{*} \\ = X^{*} [⟨ - k ⟩_{N}] \end{aligned}

第 3 条也是类似的。然后由 2、3 就能推导出后面的。

对称性可以用于简化某些特殊的 DFT 计算，考试中比较喜欢考的就是：有一个 $2 N$ 长的实序列，要求用 $N$ 长的 FFT 进行计算（可以用其他简单的辅助运算），过程如下：

圆周卷积定理

g [n] Ⓝ h [n] \overset{D F T}{⟷} G [k] H [k]

直接证明太麻烦了，可以从 DTFT 的卷积性质推导，然后再采样就行。总而言之，凡是看到“圆周”，就要想到对周期信号进行采样。

调制定理

g [n] h [n] \overset{D F T}{⟷} \frac{1}{N} \sum_{ℓ = 0}^{N} G [ℓ] H [⟨ k - ℓ ⟩_{N}]

上一条定理的对偶定理。

对偶定理

g [n] \overset{D F T}{⟷} G [k] G [n] \overset{D F T}{⟷} N g [⟨ - k ⟩_{N}]

这个证起来不难，我就说个大概吧（~~其实是想偷懒~~）

对 $G [n]$ 进行 DFT
先代入 $g [n]$
再交换求和顺序
变量代换（引入了圆周时反）
化简，化简时会用到一条关系式（引入了 $N$ ）：

\sum_{n = 0}^{N - 1} W_{N}^{k n} = {\begin{cases} N, & k = 0 \\ 0, & k \neq 0 \end{cases}

懒得自己算的同学请点击展开

\begin{aligned} \sum_{n = 0}^{N - 1} G [n] W_{N}^{k n} & = \sum_{n = 0}^{N - 1} {\sum_{m = 0}^{N - 1} g [m] W_{N}^{n m}} W_{N}^{k n} \\ = \sum_{m = 0}^{N - 1} {\sum_{n = 0}^{N - 1} g [m] W_{N}^{n (m + k)}} \\ ^{(ℓ = m + k)} & = \sum_{ℓ = 0}^{N - 1} {\sum_{n = 0}^{N - 1} g [⟨ ℓ - k ⟩_{N}] W_{N}^{n ℓ}} \\ = N [⟨ - k ⟩_{N}] \end{aligned}

Parseval 定理

\sum_{n = 0}^{N - 1} g [n] h^{*} [n] = \frac{1}{N} \sum_{k = 0}^{N - 1} G [k] H^{*} [k] 特 殊 的 ， \sum_{n = 0}^{N - 1} | g [n] |^{2} = \frac{1}{N} \sum_{k = 0}^{N - 1} | G [k] |^{2}

证明方法嘛，先将 $h [n]$ 用 $H [k]$ 表示（这一步引入了 $1 / N$ ），然后利用共轭使得 $W_{N}^{- k n}$ 变为 $W_{N}^{k n}$ ，然后交换求和顺序，再把 $g [n]$ 变成 $G [k]$ 。

习题

Tip

5.8 求长度为 $N$ 的如下序列的 $N$ 点 DFT：
（a） $x_{a} [n] = \cos (2 π n / N)$
（b） $x_{b} [n] = \sin^{2} (2 π n / N)$
（c） $x_{c} [n] = \sin^{3} (2 π n / N)$

Note

解：由于是三角函数，所以首先想到的是写成 $e$ 指数的形式再求解。

\begin{aligned} x_{a} [n] & = \frac{1}{2} (e^{j 2 π n / N} + e^{- j 2 π n / N}) \\ x_{b} [n] & = \frac{1 - \cos (2 π 2 n / N)}{2} = \frac{1 - \frac{1}{2} (e^{j 2 π 2 n / N} + e^{- j 2 π 2 n / N})}{2} \\ x_{c} [n] & = \frac{1}{4} [3 \sin (2 π n / N) - \sin (2 π 3 n / N)] \\ = \frac{1}{4} [\frac{3}{2 j} (e^{j 2 π n / N} - e^{- j 2 π n / N}) - \frac{1}{2 j} (e^{j 2 π 3 n / N} - e^{- j 2 π 3 n / N})] \end{aligned}

根据常用 DFT 变换对 $e^{j 2 π k_{0} n / N} \overset{D F T}{⟷} N δ (⟨ k - k_{0} ⟩_{N})$ ，可以直接写出：

\begin{aligned} X_{a} [k] & = \frac{N}{2} [δ (⟨ k - 1 ⟩_{N}) + δ (⟨ k + 1 ⟩_{N})] \\ X_{b} [k] & = \frac{1 - \frac{N}{2} [δ (⟨ k - 2 ⟩_{N}) + δ (⟨ k + 2 ⟩_{N})]}{2} \\ x_{c} [k] & = \frac{1}{4} [\frac{3}{2 j} (δ (⟨ k - 1 ⟩_{N}) - δ (⟨ k + 1 ⟩_{N})) - \frac{1}{2 j} (δ (⟨ k - 3 ⟩_{N}) - δ (⟨ k + 3 ⟩_{N}))] \end{aligned}

Tip

5.14 设 $X [k]$ 是长为 $N$ 的序列 $x [n]$ 的 $N$ 点 DFT， $N$ 为偶数。定义两个长度为 $\frac{N}{2}$ 的序列为：

\begin{matrix} g [n] = \frac{1}{2} (x [2 n] + x [2 n + 1]) \\ h [n] = \frac{1}{2} (x [2 n] - x [2 n + 1]) \\ 0 \leq n \leq \frac{N}{2} - 1 \end{matrix}

若 $g [n]$ , $h [n]$ 的 $N / 2$ 点 DFT 分别是 $G [n]$ , $H [n]$ ，请用 $G [n], H [n]$ 求 $X [n]$

[!NOTE] 解：这题显然是考 DIT-FFT，根据 DIT-FFT 的公式，可以写出：

\begin{aligned} X [k] & = \sum_{r = 0}^{N / 2 - 1} x [2 r] (W_{N}^{2})^{k r} + W_{N}^{k} \sum_{r = 0}^{N / 2 - 1} x [2 r + 1] (W_{N}^{2})^{k r} \\ = \sum_{r = 0}^{N / 2 - 1} x [2 r] W_{N / 2}^{k r} + W_{N}^{k} \sum_{r = 0}^{N / 2 - 1} x [2 r + 1] W_{N / 2}^{k r} \\ = (G [k] + H [k]) + W_{N}^{k} (G [k] - H [k]) k = 0, 1, \dots, N - 1 \end{aligned}

$X [k + \frac{N}{2}] = (G [k] + H [k]) - W_{N}^{k} (G [k] - H [k]) k = 0, 1, \dots, N - 1$

[!TIP] 5.48 序列 ${x [n]} = {2, - 3, 1, 4}$ ， $0 \leq n \leq 3$ ，与下面定义在 $0 \leq n \leq 3$ 进行 4 点圆周卷积：

\begin{matrix} {h_{1} [n]} = {1, 4, - 2, - 3} \\ {h_{2} [n]} = {5, 4 - 4, - 1, 3} \\ {h_{3} [n]} = {- 2, 5, 2, - 4} \\ {h_{4} [n]} = {- 3, 2, - 3, 4} \end{matrix}

计算结果如下：
$\begin{matrix} {y_{a} [n]} = {- 16, - 24, 27, 25} \\ {y_{b} [n]} = {- 13, 5, 1, 7} \\ {y_{c} [n]} = {30, 20, - 29, - 17} \\ {y_{d} [n]} = {25, - 6, - 27, 8} \end{matrix}$

不计算圆周卷积，将结果与圆周卷积配对。

[!NOTE] 解：可以通过求 DFT 来求圆周卷积，不过太麻烦了。可以进行求和：

\begin{matrix} \sum_{n = 0}^{N - 1} x [n] = 4 \\ \sum_{n = 0}^{N - 1} h_{1} [n] = 0 \sum_{n = 0}^{N - 1} y_{a} [n] = 12 \\ \sum_{n = 0}^{N - 1} h_{2} [n] = 3 \sum_{n = 0}^{N - 1} y_{b} [n] = 0 \\ \sum_{n = 0}^{N - 1} h_{3} [n] = 1 \sum_{n = 0}^{N - 1} y_{c} [n] = 4 \\ \sum_{n = 0}^{N - 1} h_{4} [n] = 0 \sum_{n = 0}^{N - 1} y_{d} [n] = 0 \end{matrix}

由于 $\sum x \cdot \sum h_{2} = \sum y_{a}$ 和 $\sum x \cdot \sum h_{3} = \sum y_{c}$ ，所以我们可以判断出：
$x Ⓝ h_{2} = y_{a} x Ⓝ h_{3} = y_{c}$

还有俩个判断不了，我们可以进行交替求和：

\begin{matrix} \sum_{n = 0}^{N - 1} (- 1)^{n} x [n] = 2 \\ \sum_{n = 0}^{N - 1} (- 1)^{n} h_{1} [n] = - 2 \sum_{n = 0}^{N - 1} (- 1)^{n} y_{b} [n] = - 24 \\ \sum_{n = 0}^{N - 1} (- 1)^{n} h_{4} [n] = - 12 \sum_{n = 0}^{N - 1} (- 1)^{n} y_{d} [n] = - 4 \end{matrix}

由于 $\sum (- 1)^{n} x \cdot \sum (- 1)^{n} h_{1} = \sum (- 1)^{n} y_{d}$ 和 $\sum (- 1)^{n} x \cdot \sum (- 1)^{n} h_{4} = \sum (- 1)^{n} y_{b}$ ，所以我们可以判断出：
$x Ⓝ h_{1} = y_{d} x Ⓝ h_{4} = y_{b}$

[!TIP] 5.51 偶数长 $x [n]$ 的 DFT 为 $X [k]$ ，用 $X [k]$ 表示下列序列的 $N$ 点 DFT

\begin{aligned} u [n] & = x [n] - x [⟨ n - \frac{N}{2} ⟩_{N}] \\ v [n] & = x [n] + x [⟨ n - \frac{N}{2} ⟩_{N}] \\ y [n] & = (- 1)^{n} x [n] \end{aligned}

Note

解：考察的是 DFT 的性质。

U [k] = X [k] - (- 1)^{k} X [k] V [k] = X [k] + (- 1)^{k} X [k] Y [k] = X [⟨ k - \frac{N}{2} ⟩_{N}]

FFT 离散傅里叶变换实验