数学系的数字信号处理：离散信号和离散傅立叶变换

本专栏：数学系的数字信号处理 的前置知识主要有：数学分析（傅立叶级数的部分），泛函分析（L^p空间的部分）

离散信号和离散傅立叶变换

定义、性质

定义：离散信号
即复数列 \{a_n\}:\mathbb{N}\to\mathbb{C}

若无特别说明，下面均记 S_n 是以 n 为周期的复数列信号全体构成的集合

定义：离散傅立叶变换
设 y=\{y_j\}_{j=0}^{n-1}\in S_n，y 的离散傅立叶变换记为序列 \mathscr{F}_n[y]，简记为 \hat{y}，其第 k 项为
\mathscr{F}_n[y]_k=\hat{y_k}\triangleq \sum\limits_{j=0}^{n-1}y_j\overline{\omega}^{jk}其中 \omega=\exp\{\frac{2\pi i}{n}\}
离散傅立叶变换等效于在列向量 y=(y_0,y_1,\dots,y_{n-1})^T 上左乘 \overline{F_n}，其中
F_n=\begin{pmatrix} 1&1&1&\cdots&1\\ 1&\omega&\omega^2&\cdots&\omega^{n-1}\\ 1&\omega^2&\omega^4&\cdots&\omega^{2(n-1)}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&\omega^{n-1}&\omega^{2(n-1)}&\cdots&\omega^{(n-1)(n-1)}\\ \end{pmatrix}

离散傅立叶逆变换相当于在列向量 y 上左乘矩阵 \frac{F_n}{n}

性质

1. 离散傅立叶变换对应的矩阵是酉矩阵，即
   \frac{F_n}{\sqrt{n}}\frac{\overline{F_n}}{\sqrt{n}}=I_n这意味着 \mathscr{F}^{-1}\mathscr{F}[y]=y

2. 设 y,z\in S_n 且 z_k=y_{k+1}，则 \mathscr{F}[z]_j=\omega^j\mathscr{F}[y]_j

3. 若 y 还是实数列，则 \mathscr{F}[y]_{n-k}=\overline{\mathscr{F}[y]_k}

离散卷积

定义：离散卷积
序列 x,y 的卷积定义为
(x*y)_k=\sum\limits_{n\in\mathbb{Z}}x_{k-n}y_n 若 y,z\in S_n，则 y 与 z 的卷积仍为一个周期数列，其定义为
[y*z]_k\triangleq \sum\limits_{j=0}^{n-1}y_jz_{k-j}

卷积定理
\mathscr{F}[y*z]_k=\mathscr{F}[y]_k\cdot\mathscr{F}[z]_k

快速傅立叶变换（FFT）

快速傅立叶变换（Fast Fourier Transform）是计算离散傅立叶变换的一个良好算法，现简介其思想如下

考虑偶数个数据点，即设 n=2N，则
\hat{y_k}=\sum\limits_{j=0}^{2N-1}y_j\overline{\omega}^{jk}=\sum\limits_{j=0}^{N-1}y_{2j}\overline{\omega}^{2jk}+\sum\limits_{j=0}^{N-1}y_{2j+1}\overline{\omega}^{(2j+1)k}其中等式右端第一项是那些偶数指标对应的各项之和，第二项是奇数指标对应的各项之和

作代换 W=\omega^2，则对 0\leq k\leq 2N-1
\begin{split} \hat{y}_k&=\sum\limits_{j=0}^{N-1}y_{2j}\overline{W}^{jk}+\overline{\omega}^k(\sum\limits_{j=0}^{N-1}y_{2j+1}\overline{W}^{jk})\\ &=\mathscr{F}_N[\{y_0,y_2,\dots,y_{2N-2}\}]_k+\overline{\omega}^k\mathscr{F}_N[\{y_1,y_3,\dots,y_{2N-1}\}]_k \end{split}
下面将 k 的范围限制在 0\leq k\leq N-1 中，则上述形式改写为
\hat{y}_k=\mathscr{F}_N[\{y_0,y_2,\dots,y_{2N-2}\}]_k+\overline{\omega}^k\mathscr{F}_N[\{y_1,y_3,\dots,y_{2N-1}\}]_k\hat{y}_{k+N}=\mathscr{F}_N[\{y_0,y_2,\dots,y_{2N-2}\}]_k-\overline{\omega}^k\mathscr{F}_N[\{y_1,y_3,\dots,y_{2N-1}\}]_k
上述变形是根据 \mathscr{F}[y_{\text{偶部}}]_k 和 \mathscr{F}[y_{\text{奇部}}]_k 的周期均为 n，且 \overline{\omega}^{k+N}=-\overline{\omega}^k；这样一来，我们从逐项计算 0\leq k\leq 2N-1 减少到只需计算 0\leq k\leq N-1 的结果，计算量从 n^2 下降至 5n\log_2{n}
类似地，快速离散傅立叶逆变换公式为
2y_k=\mathscr{F}_N^{-1}[\{\hat{y}_0,\hat{y}_2,\dots,\hat{y}_{2N-2}\}]_k+\overline{\omega}^k\mathscr{F}_N^{-1}[\{\hat{y}_1,\hat{y}_3,\dots,\hat{y}_{2N-1}\}]_k2y_{k+N}=\mathscr{F}_N^{-1}[\{\hat{y}_0,\hat{y}_2,\dots,\hat{y}_{2N-2}\}]_k-\overline{\omega}^k\mathscr{F}_N^{-1}[\{\hat{y}_1,\hat{y}_3,\dots,\hat{y}_{2N-1}\}]_k
当 n 为 2 的整幂时，算法效率最好

离散信号的时不变性

定义：时不变性
设 x\in S_n，信号 x 的时不变算子 T_p 定义如下
[T_p(x)]_k\triangleq x_{k-p},p\in\mathbb{N}线性滤波器 F 称为时不变的，若对任意信号 x 及整数 p，有
F(T_p(x))=T_p(F(x))

线性时不变滤波器的性质

1. 设单位序列 \{e_n\}（即第 n 项为 1，其余为 0 的序列） ，则 T_p(e_n)=e_{n+p}
2. 设 f_n=F(e_n)，则 T_p(f_n)=f_{n+p}
3. f_{k}^{n+p}=f_{k-p}^n

定理：离散线性时不变滤波器的结构
设 F 为离散线性时不变滤波器，则存在绝对收敛的序列 f，使得对任意信号 x ，有 F(x)=f*x，f 称为冲激响应；若非零项无穷多，则称 f 为无限冲激响应；否则称有限冲激响应。

Z 变换

下面我们从 l^2 空间叙述 Z 变换的理论，一个信号即可看做 l^2 空间上的序列

定义：Z 变换
序列 x\in l^2 的 Z 变换定义为从 [-\pi,\pi] 映到复数域 \mathbb{C} 的函数 \hat{x}:
\hat{x}(\phi)=\sum\limits_{j=-\infty}^{\infty}x_je^{-ij\phi}\triangleq \sum\limits_{j=-\infty}^{\infty}x_jz^{-j}其中 z=e^{-i\phi}

注：容易看出，若 \phi=\frac{2\pi k}{n}，则 \hat{x}(\phi) 即为 x 的离散傅立叶变换的第 k 项系数

傅立叶级数与 Z 变换的关系

傅立叶级数可从 L^2 空间中的函数 f(\phi) 获取 l^2 空间中的序列\{x_n\}（即各项系数）
Z 变换即把 l^2 空间中的序列 \{x_n\} 映为 L^2 空间中的函数 f(-\phi)

定理：Z 变换与内积
若 x,y\in l^2，则
\frac{1}{2\pi}<\hat{x},\hat{y}>_{L^2}=_{l^2}

证明
由 paseval 等式
\begin{split} _{l^2}&=\sum\limits_{n=-\infty}^{\infty}x_n\overline{y_n}\\ &=\frac{1}{2\pi}\int_{-\pi}^{\pi}f(\phi)\overline{g(\phi)}\mathrm{d}\phi\\ &=\frac{1}{2\pi}\int_{-\pi}^{\pi}\hat{x}(-\phi)\overline{\hat{y}(-\phi)}\mathrm{d}\phi\\ &=\frac{1}{2\pi}_{L^2} \end{split}

定理：Z 变换与卷积
设 f,x\in l^2，则
\hat{f*x}=\hat{f}\cdot\hat{x}称 \hat{f} 为相应于 F(x)=f*x 的转移函数，记为 \hat{F}

证明思路
\begin{split} (\hat{f*x})(\phi)&=\sum\limits_{n=-\infty}^{\infty}(f*x)(n)e^{-in\phi}\\ &=\sum\limits_{n=-\infty}^{\infty}\sum\limits_{k=-\infty}^{\infty}f_kx_{n-k}\cdot e^{-in\phi}\\ &=\sum\limits_{n=-\infty}^{\infty}\sum\limits_{k=-\infty}^{\infty}f_ke^{-ik\phi}x_{n-k}e^{-i(n-k)\phi}\\ &=\sum\limits_{k=-\infty}^{\infty}f_ke^{-ik\phi}\sum\limits_{n=-\infty}^{\infty}x_{n-k}e^{-(n-k)\phi}\\ &=\sum\limits_{k=-\infty}^{\infty}f_ke^{-ik\phi}\cdot \sum\limits_{m=-\infty}^{\infty}x_me^{-im\phi}\\ &=\hat{f}(\phi)\cdot\hat{x}(\phi) \end{split}

定理
若 F 是序列 f 的卷积算子，则 F^* 是 f^* 的卷积算子，其中 f^*_n\triangleq \overline{f}_{-n}，更多地，\hat{F^*}=\overline{\hat{F}}