信号处理原理 笔记 6

离散Fourier变换

DFT

DTFT用于将时域上的内容离散化，但得到的结果在频域上仍然是一个连续的函数，仍然是计算机无法存储和计算的值，因此我们需要将其在频域上也进行离散化，得到离散Fourier变换DFT

由于我们有：

$$X(\omega) = X(\omega + 2\pi)$$

因此我们取一个Nyquist周期$[0, 2\pi]$，将其划分为$N$份，只保留这些特定点上的频谱：

$$\omega_{k} = 0 + k\frac{2\pi}{N}\quad k = 0, 1, \dots, N - 1$$

得到：

$$X(\omega_{k}) = \sum\limits_{n=0}^{L-1}x(n)e^{-j\omega_{k}n} = \sum\limits_{n=0}^{L-1}x(n)e^{-j\frac{2\pi}{N}nk}$$

为了将上述公式写成只与$k$有关的形式，我们记$W_{N} = \exp({-j\frac{2\pi}{N}})$，则有：

$$X(k) = \sum\limits_{n=0}^{L-1}x(n)W_{N}^{nk}$$

于是我们可以定义矩阵$\mathbf{W}\in \mathbb{R}^{N\times L}$，满足$\mathbf{W}_{nk} = W_{N}^{nk}$，则我们对于时域序列$\mathbf{x}^{T} = [x(0), \dots, x(L-1)]$与频域序列$\mathbf{X}^{T} = [X(0), \cdots, X(N - 1)]$，我们有：

$$\mathbf{X} = \mathbf{W}\mathbf{x}$$

N与L的关系

$L$为在时域上采样的数量，在处理数据的过程中可以认为是常数，$N$是我们主动在频域上采样的数量，通常情况下，我们期待$L = N$，如果不等，则我们可以做如下变换：

1. $L < N$：时域序列较短，此时直接在其后方补零即可：

   $$\mathbf{x}_{D} = [\mathbf{x}, \mathbf{0}_{N - L - 1}]$$

   显然这个序列做DFT得到的结果和$\mathbf{x}$是一致的

2. $L > N$：时域序列较长，此时对于时域采样序列做回绕：

   $$\tilde{x}(n) = \sum\limits_{m=0}^{\infty}x(mN + n)\quad n = 0, 1, \dots, N - 1$$

   不容易证明，回绕之后得到的DFT和原序列的DFT是相同的，证明过程见附录

   但是这导致，内容完全不同但是回绕相同的序列，其DFT完全相同

因此，我们在处理过程中，一般取$N = L$

IDFT

有了DFT，我们同样也需要构造IDFT，但是这是简单的，因为DFT的本质是矩阵变换，因此我们只需要对矩阵求逆即可，我们直接给出结果：

$$\tilde{x}(n) = \frac{1}{N}\sum\limits_{k=0}^{L-1}W_{N}^{-nk}X(k)$$

注意到，我们求出的是$\tilde{x}(n)$而并非精确的$x(n)$，这是因为回绕相同的所有序列求出的DFT都是相同的

性质

根据上述讨论，我们在研究性质的过程中，默认$L = N$

显然性质

DFT是离散的、周期的、线性的

实序列的共轭对称性

如果$x(n)$是实序列，那么有：

$$X(k) = X^{*}(N - k)$$

Parsval定理

$$\sum\limits_{n=0}^{N-1}|x(n)|^{2} = \frac{1}{N}\sum\limits_{k=0}^{N-1}|X(k)|^{2}$$

奇偶性与虚实性

• 奇/偶函数的DFT是奇/偶函数
• 实/虚函数的DFT，实部是偶/奇函数，虚部是奇/偶函数，模是偶函数，相位是奇函数
• 偶函数DFT不改变虚实性，奇函数DFT改变虚实性

反褶与共轭

$$\begin{align*} x(n) &\Leftrightarrow X(k) \\ x(-n) &\Leftrightarrow X(-k) \\ x^{*}(n) &\Leftrightarrow X^{*}(-k) \end{align*}$$

对称性

$$\mathrm{DFT}\bigl[X(n)\bigr] = N\tilde{x}(-k)$$

频移与时移

$$\begin{align*} \mathrm{DFT}\bigl[x(n)W_{N}^{-nl}\bigr] &= X(k - l) \\ \mathrm{DFT}\bigl[x(n - m)\bigr] &= W_{N}^{mk}X(k) \end{align*}$$

对这两个性质的证明详见Appendix B

卷积特性

离散序列的线卷积定义详见笔记5，圆卷积定义为：

$$x(n)\otimes y(n) = \sum\limits_{m=0}^{N-1}x(m)y((n - m) \text{ mod } N)$$

则有：

$$\begin{align*} \mathrm{DFT}\bigl[x(n) * y(n)\bigr] &= X(k)\cdot Y(k) \\ \mathrm{DFT}\bigl[x(n)\cdot y(n)\bigr] &= \frac{1}{N}X(k)\otimes Y(k) \\ \mathrm{IDFT}\bigl[X(k) \cdot Y(k)\bigr] &= x(n) \otimes y(n) \end{align*}$$

需要注意的是，DFT和IDFT并不严格一一对应，这是因为回绕的DFT都相同

DFT的快速算法

按照定义式：

$$X(k) = \mathrm{DFT}\bigl[x(n)\bigr] = \sum\limits_{n=0}^{N-1}x(n)W_{N}^{nk}$$

假设我们已经预先计算好了所有的$W_{N}^{nk}$，则计算$\mathbf{X}$复杂度为$O(N^{2})$

根据定义式，$W_{N} = \exp(-j\frac{2\pi}{N})$，因此我们有以下两条性质：

$$\begin{align*} W_{N}^{nk} &= W_{N}^{(nk)\text{ mod }N} \\ W_{N}^{nk + \frac{N}{2}} &= -W_{N}^{nk} \end{align*}$$

于是采用快速Fouier变换（FFT）的计算过程进行加速，具体过程如下：

假设$N = 2R$为偶数，首先将定义式按照奇偶项拆分开

$$\begin{align*} X(k) &= \sum\limits_{r=0}^{R - 1}x(2r)W_{N}^{2rk} + \sum\limits_{r=0}^{R - 1}x(2r + 1)W_{N}^{(2r + 1)k} \\ &= \sum\limits_{r=0}^{R - 1}x(2r)W_{N}^{2rk} + W_{N}^{k}\sum\limits_{r=0}^{R - 1}x(2r + 1)W_{N}^{2rk} \\ \end{align*}$$

并且我们有：

$$\begin{align*} W_{N}^{2rk} &= \exp(-j\frac{2\pi}{N}2rk) \\ &= \exp(-j\frac{2\pi}{R}rk) \\ &= W_{R}^{rk} \end{align*}$$

可以看出，这和DFT变换矩阵的元素形式是一样的，这说明$X_{k}$的奇偶项分别对应的一个DFT

于是我们可以记$g(r) = x(2r)$，$h(r) = x(2r+1)$，有：

$$\begin{align*} X(k) &= \sum\limits_{r=0}^{R - 1}x(2r)W_{N}^{2rk} + W_{N}^{k}\sum\limits_{r=0}^{R - 1}x(2r + 1)W_{N}^{2rk} \\ &= \sum\limits_{r=0}^{R - 1}g(r)W_{R}^{rk} + W_{N}^{k}\sum\limits_{r=0}^{R-1}h(r)W_{R}^{rk} \\ &= \mathrm{DFT}\bigl[g(r)\bigr] + W_{N}^{k}\mathrm{DFT}\bigl[h(r)\bigr] \\ &= G(k) + W_{N}^{k}H(k) \end{align*}$$

注意，上式的定义区间是$[0, R)$而不是$[0, N)$，因为其中使用的变换核的周期（即$W$的下标）是$R$而非$N$，因此应该写作：

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

后半个序列的计算过程为：

$$\begin{align*} X(k + \frac{N}{2}) &= \sum\limits_{r=0}^{R - 1}x(2r)W_{N}^{2r(k + \frac{N}{2})} + W_{N}^{k + \frac{N}{2}}\sum\limits_{r=0}^{R - 1}x(2r + 1)W_{N}^{2r(k + \frac{N}{2})} \\ &= \sum\limits_{r=0}^{R - 1}g(r)W_{R}^{rk}W_{N}^{rN} + W_{N}^{k + \frac{N}{2}}\sum\limits_{r=0}^{R-1}h(r)W_{R}^{rk}W_{N}^{rN} \\ &= \sum\limits_{r=0}^{R - 1}g(r)W_{R}^{rk} - W_{N}^{k}\sum\limits_{r=0}^{R-1}h(r)W_{R}^{rk} \\ &= \mathrm{DFT}\bigl[g(r)\bigr] - W_{N}^{k}\mathrm{DFT}\bigl[h(r)\bigr] \\ &= G(k) - W_{N}^{k}H(k) \end{align*}$$

这说明我们可以通过$\boldsymbol{G(k)}$与$\boldsymbol{H(k)}$计算出全部的$\boldsymbol{X(k)}$，并且复杂度是$O(1)$的

假设按照FFT计算$\mathbf{X}$的时间复杂度为$T(N)$，则有：

$$T(N) = 2T(\frac{N}{2}) + N\cdot O(1) = 2T(\frac{N}{2}) + O(N)$$

因此我们有最终复杂度为$T(N) = O(N\log N)$

Appendix

Appendix A

对回绕性质的证明

Appendix B

TODO