数字信号处理¶
\begin{align} \end{align}
第一章¶
第二章¶
第三章¶
DTFT¶
所有的变换对都可以当做第一个例子里展现的那样、用坐标变换、换基底的思想来理解。
离散函数，比如$x[n]$可以粗略地理解成无穷可数维空间中的一个点或者向量。连续函数$x(t)$可以粗略地理解成一个无穷不可数维空间中的一个点或者向量。
回想一个$n$维向量$\vec{x}$按一组正交单位基底$\{\vec{e}_n\}$展开 \begin{align} \vec{x} &= X_1 \vec{e}_1 + X_2 \vec{e}_2 + \ldots + X_n \vec{e}_n \\ &= \sum_{k = 1}^n X_k \vec{e}_k \end{align} 其中$X_k$就是$\vec{x}$在基底$\vec{e}_k$上的投影。
正交的意思是$\forall k_1 \neq k_2: \langle \vec{e}_{k_1}, \vec{e}_{k_2} \rangle = 0$且$\forall k: \langle \vec{e}_{k}, \vec{e}_{k} \rangle \neq 0$。
投影$X_k$是这样计算的 \begin{align} X_k &= \langle \vec{e}_k, \vec{x} \rangle \\ &= \vec{e}_k^* \cdot \vec{x} \end{align}
因为$n$维空间线性无关基底的数量是$n$，所以需要$n$个基底来表示$\vec{x}$。
CTFS¶
回想连续周期信号$x(t)$，周期是$f_0^{-1}$，按正交函数系$\{e^{j 2 \pi n f_0 t} | n \in Z\}$展开（证明正交） \begin{align} x(t) &= X_0 e^{j 2 \pi 0 f_0 t} && + X_1 e^{j 2 \pi 1 f_0 t} && + X_2 e^{j 2 \pi 2 f_0 t} + \ldots \\ & && + X_{-1} e^{j 2 \pi (-1) f_0 t} && + X_{-2} e^{j 2 \pi (-2) f_0 t} + \ldots \\ &= \sum_{k=-\infty}^{\infty} X_k e^{j 2 \pi k f_0 t} \end{align} 其中$X_k$就是$x(t)$在基底$e^{j 2 \pi k f_0 t}$上的投影。
投影$X_k$是这样计算的 \begin{align} X_k &= f_0 \langle e^{j 2 \pi k f_0 t}, x(t) \rangle \\ &= f_0 \int_{C}^{C + {1 \over f_0}} \left(e^{j 2 \pi k f_0 t}\right)^* x(t) \,dt \\ &= f_0 \int_{C}^{C + {1 \over f_0}} e^{- j 2 \pi k f_0 t} x(t) \,dt \end{align}
这里我不理解为什么积分的范围只要一个周期。
但是用了Fourier's trick就完全避免了系数问题。
这里有一个$f_0$系数的原因是，正交函数系$\{e^{j 2 \pi n f_0 t} | n \in Z\}$不是归一的。意思是基底的长度不是单位长度（那么基底的长度是多少？），同一个基底内积的结果不是1，而是${1 \over f_0}$。见证明正交。
投影$X_k$好像还可以是这样计算的。这个称为Fourier's trick \begin{align} \color{red}{\int_{C}^{C + {1 \over f_0}}} x(t) \color{red}{e^{-j 2 \pi k f_0 t} \,dt} = \color{red}{\int_{C}^{C + {1 \over f_0}}} \sum_{n=-\infty}^{\infty} X_n e^{j 2 \pi n f_0 t} \color{red}{e^{-j 2 \pi k f_0 t} \,dt} \end{align} 简单来说就是在综合公式的两边同时内积一个$e^{j 2 \pi k f_0 t}$，即同时乘以一个$e^{- j 2 \pi k f_0 t}$再积分。上面的式子交换求和和积分次序，得到 \begin{align} \int_{C}^{C + {1 \over f_0}} x(t) e^{-j 2 \pi k f_0 t} \,dt = \sum_{n=-\infty}^{\infty} X_n \underbrace{\int_{C}^{C + {1 \over f_0}} e^{j 2 \pi n f_0 t} e^{-j 2 \pi k f_0 t} \,dt}_{\begin{cases} 0, &\qquad n \neq k \\ {1 \over f_0}, &\qquad n = k \end{cases}} \end{align} 这里用到了证明正交的结论。所以右边的求和只剩下了$n = k$时的一项 \begin{align} \int_{C}^{C + {1 \over f_0}} x(t) e^{-j 2 \pi k f_0 t} \,dt = {1 \over f_0} X_k \end{align}
关于Fourier's trick，这个技巧是我在Griffiths的Introduction to Quantum Mechanics这本书里看到的。也有人在质疑这个做法。具体为什么可能要学泛函分析。
CTFT¶
回想连续信号$x(t)$按正交函数系$\{e^{j 2 \pi f t} | f \in R\}$展开（证明正交） \begin{align} x(t) = \int_{-\infty}^{\infty} X(j 2 \pi f) e^{j 2 \pi f t} \,df \end{align} 其中$X(j 2 \pi f)$就是$x(t)$在基底$e^{j 2 \pi f t}$上的投影。
投影$X(j 2 \pi f)$是这样计算的 \begin{align} X(j 2 \pi f) &= \langle e^{j 2 \pi f t}, x(t) \rangle \\ &= \int_{-\infty}^{\infty} \left(e^{j 2 \pi f t}\right)^* x(t) \,dt \\ &= \int_{-\infty}^{\infty} e^{- j 2 \pi f t} x(t) \,dt \end{align}
你可能会疑惑为什么不写成$X(f)$而非要写成$X(j 2 \pi f)$。其实$X(f)$也是可以的，但是在拉普拉斯变换中变换域函数写成$X(s)$。为了体现和拉普拉斯变换的关系，即令$s = j 2 \pi f$，拉普拉斯变换域函数$X(s)$退化成傅里叶变换域函数$X(f)$，这里就写作$X(j 2 \pi f)$。
用Fourier's trick算投影 \begin{align} \color{red}{\int_{-\infty}^{+\infty}} x(t) \color{red}{e^{- j 2 \pi f' t} \,dt} = \color{red}{\int_{-\infty}^{+\infty}} \int_{-\infty}^{\infty} X(j 2 \pi f) e^{j 2 \pi f t} \,df \color{red}{e^{- j 2 \pi f' t} \,dt} \end{align} 交换积分次序 \begin{align} \int_{-\infty}^{+\infty} x(t) e^{- j 2 \pi f' t} \,dt &= \int_{-\infty}^{+\infty} X(j 2 \pi f) \underbrace{\int_{-\infty}^{\infty} e^{j 2 \pi f t} e^{- j 2 \pi f' t} \,dt}_{\delta(f - f')}\,df \\ &= X(j 2 \pi f') \end{align}
DTFT¶
把$x[n]$按一个正交函数系$\left\{e^{j 2 \pi f n} \mid f \in [- {1 \over 2}, {1 \over 2}]\right\}$展开（证明正交） \begin{align} x[n] = \int_{- {1 \over 2}}^{1 \over 2} X(e^{j 2 \pi f}) e^{j 2 \pi f n} \,df \end{align}
在任意一个基底$e^{j 2 \pi f n}$上的投影$X(e^{j 2 \pi f})$是这样计算的 \begin{align} X(e^{j 2 \pi f}) = \sum_{k = -\infty}^{+\infty} e^{- j 2 \pi f k} x[k] \end{align}
这里细说的话，$n$是没有量纲的，所以变换过去的$f$也没有量纲。
从信息的角度讲，$x(n T_s)$变成$x[n]$的过程，丢弃了采样间隔这个信息，所以频域自然也不可能凭空出现这个信息。
所有的变换都需要满足原变量和变换域变量的量纲互为倒数的关系（为什么？）
发现$X(e^{j 2 \pi f n})$是周期函数，周期是$1$。
证明$\{e^{j 2 \pi f t} | f \in R\}$是正交归一函数系¶
\begin{align} \left\langle e^{j 2 \pi f_1 t}, e^{j 2 \pi f_2 t} \right\rangle &= \int_{-\infty}^{+\infty} \left(e^{j 2 \pi f_1 t}\right)^* e^{j 2 \pi f_2 t} \,dt \\ &= \int_{-\infty}^{+\infty} e^{- j 2 \pi f_1 t} e^{j 2 \pi f_2 t} \,dt \\ &= \int_{-\infty}^{+\infty} e^{j 2 \pi (f_2 - f_1) t} \,dt \\ &= \int_{-\infty}^{+\infty} e^{- j 2 \pi (f_1 - f_2) t} \,dt \\ &= \delta(f_1 - f_2) \end{align} 最后一步用到了 \begin{align} 1 \mathop{\longleftrightarrow}^{\cal F} \delta(f) \end{align}
证明$\{e^{j 2 \pi n f_0 t} | n \in Z\}$是正交函数系¶
\begin{align} \langle e^{j 2 \pi n_1 f_0 t}, e^{j 2 \pi n_2 f_0 t} \rangle &= \int_{C }^{C + {1 \over f_0}} \left(e^{j 2 \pi n_1 f_0 t}\right)^* e^{j 2 \pi n_2 f_0 t} \,dt \\ &= \int_{C }^{C + {1 \over f_0}} e^{- j 2 \pi n_1 f_0 t} e^{j 2 \pi n_2 f_0 t} \,dt \\ &= \int_{C }^{C + {1 \over f_0}} e^{j 2 \pi (n_2 - n_1) f_0 t} \,dt \\ &= \left.{1 \over j 2 \pi (n_2 - n_1) f_0} e^{j 2 \pi (n_2 - n_1) f_0 t} \right|^{1 \over f_0}_{0} \\ &= {e^{j 2 \pi (n_2 - n_1)} - 1 \over j 2 \pi (n_2 - n_1) f_0} \\ &= \begin{cases} 0, &\qquad n_1 \neq n_2 \\ \textrm{undefined}, &\qquad n_1 = n_2 \end{cases} \end{align} 最后一步用到了$e^{j 2 \pi n} = \cos(2 \pi n) + j \sin(2 \pi n) = 1$。
这里当$n_1 = n_2$的时候出现了一个奇点，但是这是一个可去奇点 \begin{align} \lim_{n \to 0} {e^{j 2 \pi n} - 1 \over j 2 \pi n f_0} &= \lim_{n \to 0} {j 2 \pi \cdot e^{j 2 \pi n} \over j 2 \pi f_0} = {1 \over f_0} \end{align} 所以"不妨"就认为 \begin{align} \langle e^{j 2 \pi n_1 f_0 t}, e^{j 2 \pi n_2 f_0 t} \rangle = \begin{cases} 0, &\qquad n_1 \neq n_2 \\ {1 \over f_0}, &\qquad n_1 = n_2 \end{cases} \end{align}
我不知道为什么可以"不妨"。
所以函数系$\{e^{j 2 \pi n f_0 t} | n \in Z\}$正交，但是不归一，因为同一个基底的自内积不为
证明$\{e^{j 2 \pi f n} | f \in [- {1 \over 2}, {1 \over 2}]\}$是正交函数系¶
\begin{align} \langle e^{j 2 \pi f_1 n}, e^{j 2 \pi f_2 n} \rangle &= \sum_{n = -\infty}^{+\infty} (e^{j 2 \pi f_1 n})^* e^{j 2 \pi f_2 n} \\ &= \sum_{n = -\infty}^{+\infty} e^{- j 2 \pi f_1 n} e^{j 2 \pi f_2 n} \\ &= \sum_{n = -\infty}^{+\infty} e^{j 2 \pi (f_2 - f_1) n} \\ &= \end{align}
采样¶
有两种采样的方法。第一种是用一个周期为$T_s$的单位冲激信号序列 \begin{align} \operatorname{III}(t) = \sum_{n = -\infty}^{+\infty} \delta(t - n T_s) \end{align} 乘原信号，得到理想采样输出信号 \begin{align} \hat{x}(t) &= \operatorname{III}(t) x(t) \\ &= \sum_{n = -\infty}^{+\infty} x(t) \delta(t - n T_s) \\ &= \sum_{n = -\infty}^{+\infty} x(n T_s) \delta(t - n T_s) \end{align}
顺便提一句 \begin{align} \operatorname{III}(t) \mathop{\longleftrightarrow}^{\cal F} \color{red}{1 \over T_s} \sum_{n = -\infty}^{+\infty} \delta\left(f - {n \over T_s}\right) \end{align} 千万别忘记前面的系数。
第二种是直接定义一个离散信号$x[n]$，使 \begin{align} x[n] = x(n T_s) \end{align} 称为实际采样输出信号。
这两种方法的频谱有关联。先看理想采样输出信号的频谱 \begin{align} \hat{X}(j 2 \pi f) &= \int_{-\infty}^{+\infty} \hat{x}(t) e^{- j 2 \pi f t} \,dt \\ &= \int_{-\infty}^{+\infty} \left[\sum_{n = -\infty}^{+\infty} x(t) \delta(t - n T_s)\right] e^{- j 2 \pi f t} \,dt \\ &= \int_{-\infty}^{+\infty} \left[\sum_{n = -\infty}^{+\infty} x(t) \delta(t - n T_s) e^{- j 2 \pi f t}\right] \,dt \\ &= \int_{-\infty}^{+\infty} \left[\sum_{n = -\infty}^{+\infty} x(n T_s) \delta(t - n T_s) e^{- j 2 \pi f n T_s}\right] \,dt \\ &= \sum_{n = -\infty}^{+\infty} \left[\int_{-\infty}^{+\infty} x(n T_s) \delta(t - n T_s) e^{- j 2 \pi f n T_s} \,dt\right] \\ &= \sum_{n = -\infty}^{+\infty} x(n T_s) e^{- j 2 \pi f n T_s} \int_{-\infty}^{+\infty} \delta(t - n T_s) \,dt \\ &= \sum_{n = -\infty}^{+\infty} x(n T_s) e^{- j 2 \pi f n T_s} \\ \end{align}
再来看离散信号$x[n]$的频谱 \begin{align} X(e^{j 2 \pi f}) &= \sum_{n = -\infty}^{+\infty} x[n] e^{- j 2 \pi f n} \end{align} 回想$x[n] = x(n T_s)$，再把两个放在一起对比 \begin{align} \hat{X}(j 2 \pi f) &= \sum_{n = -\infty}^{+\infty} x(n T_s) e^{- j 2 \pi \color{red}{f n T_s}} \\ X(e^{j 2 \pi f}) &= \sum_{n = -\infty}^{+\infty} x(n T_s) e^{- j 2 \pi \color{red}{f n}} \end{align} 很明显，两个频谱就是横向伸缩的关系，也就是$\hat{X}\left(j 2 \pi {f \over T_s}\right) = X(e^{j 2 \pi f})$或者$\hat{X}(j 2 \pi f) = X(e^{j 2 \pi f T_s})$
这里再次表明了离散时间傅里叶变换DTFT中频域函数$X(e^{j 2 \pi f})$的变量$f$是无量纲的。而连续时间傅里叶变换CTFT中频域函数$X(j 2 \pi f)$的变量$f$是有量纲的，量纲是$\rm s^{-1}$。
$z$变换¶
把$x[n]$按一个正交函数系$\{z^n | z \in C\}$展开（证明正交） \begin{align} x[n] = {1 \over j 2 \pi} \oint_C X(z) z^{n-1} \,dz \end{align} 曲线$C$是复平面上的一条简单曲线，必须全部在收敛域ROC中（收敛域是什么），且需要包围零点$z = 0$。
目前我还无法理解这个式子。
$x[n]$在任意一个基底$z^n$上的投影是这样计算的 \begin{align} X(z) = \sum_{n = -\infty}^{+\infty} z^{-n} x[n] \end{align}
可以发现$z$变换和洛朗级数Laurent Series非常相似。式子$X(z) = \sum_{n = -\infty}^{+\infty} z^{-n} x[n]$完全可以理解成一个函数$X(z)$在$0$处作洛朗级数展开。
$0$处洛朗级数的定义是$X(z) = \sum_{n = -\infty}^{+\infty} x_n z^n$。
收敛域ROC¶
既然是洛朗级数，那么展开一定是有收敛域的。必须要保证式子$X(z) = \sum_{n = -\infty}^{+\infty} z^{-n} x[n]$的右半边是有意义的。
比如考虑 \begin{align} x[n] = \begin{cases} 1, &\qquad n = 0 \\ 0, &\qquad {\rm otherwise} \end{cases} \end{align} 那么 \begin{align} \sum_{n = +\infty}^{+\infty} z^{-n} x[n] = z^{-0} = 1 \end{align} 是一个常数，即$X(z) = 1$，已经与$z$无关了，当然收敛域是整个复平面$C$。
收敛的充分必要条件是 \begin{align} \sum_{n = -\infty}^{+\infty} \left|z^{-n} x[n]\right| = C \end{align}
阿贝尔定理¶
对于级数 \begin{align} \sum_{n = 0}^{+\infty} x[n] z^n \end{align} 如果级数在$z_0$处收敛，那么就能保证级数在$\left\{z \mid |z| < |z_0|\right\}$的范围里绝对收敛。把$|z_0|$记作$R$，称为最大收敛半径。
意思是超过这个半径的都不能保证收敛了。所以这个是最大的收敛半径。
所以对于级数 \begin{align} \sum_{n = 0}^{+\infty} x[n] {1 \over z^n} \end{align} 如果级数在$z_0$处收敛，那么就保证级数在$\left\{z \mid |z| > |z_0|\right\}$的范围里为绝对收敛。把$|z_0|$记作$R$，称为最小收敛半径。
意思是低于这个半径的都不保证收敛了。
有限长序列的收敛域¶
有限长序列的定义是 \begin{align} \exists n_1, n_2 \in Z, \forall n \in (-\infty, n_1) \cup (n_2, +\infty): \qquad x[n] = 0 \end{align} 意思是存在一个区间，这个区间之外的$n$都满足$x[n] = 0$。
这样有限长序列的$z$变换就是 \begin{align} X(z) = \sum_{n = n_1}^{n_2} z^{-n} x[n] = \sum_{n = n_1}^{n_2} {1 \over z^n} x[n] \end{align}
需要讨论$X(z)$的展开式是否包含$z$的正阶数项或负阶数项，才能最终确定$0$和$\infty$是否在收敛域中。这里先假设$n_1 < 0, n_2 > 0$ \begin{align} X(z) &= \sum_{n = n_1}^{n_2} z^{-n} x[n] \\ &= \underbrace{{1 \over z^{n_1}} x[n_1] + {1 \over z^{n_1 + 1}} x[n_1 + 1] + \ldots}_{z的正阶数项} + {1 \over z^0} x[0] + \underbrace{\ldots + {1 \over z^{n_2 - 1}} x[n_2 - 1] + {1 \over z^{n_2}} x[n_2]}_{z的负阶数项} \end{align}
对于$z$的负阶数项，$\infty$不是极点，因为在$\infty$处是有限值$0$；$0$是极点，因为在$0$处是无限值$\infty$。所以对每一个$z$的负阶数项而言，收敛域是$C \backslash \{0\}$。
对于$z$的正阶数项，$\infty$是极点，因为在$\infty$处是无限值$\infty$；$0$不是极点，因为在$0$处是有限值$0$。所以对每一个$z$的正阶数项而言，收敛域是$C \backslash \{\infty\}$
对于$z$的0次阶数项，$\infty$和$0$都不是极点。所以收敛域是整个复平面$C$。
所以如果$n_1 \geq 0$，即如果不包含$z$的正数阶项，那么收敛域是$C \backslash \{0\}$，可以包括无穷远点$\infty$。
如果$n_2 \leq 0$，即如果不包含$z$的负数阶项，那么收敛域是$C \backslash \{\infty\}$，可以包含原点$0$。
右边序列的收敛域¶
右边序列的定义是 \begin{align} \exists n_1 \in Z, \forall n < 0: \qquad x[n] = 0 \end{align} 意思是存在一个左边界，使得所有左边界以外的$n$都满足$x[n] = 0$。
如果$n_1 < 0$，那么展开式包含$z$的正阶数项，所以收敛域不包括无穷远点$\infty$。收敛域是$\{z | R < |z|\} \backslash \infty$。
如果$n_1 \geq 0$，那么称为因果序列，那么展开式不包含$z$的正阶数项，所以收敛域能包括无穷远点$\infty$。收敛域是$\{z | R < |z|\}$。
左边序列的收敛域¶
左边序列的定义是 \begin{align} \exists n_2 \in Z, \forall n > 0: \qquad x[n] = 0 \end{align} 意思是存在一个右边界，使得所有右边界以外的$n$都满足$x[n] = 0$。
如果$n_2 > 0$，那么展开式会包含$z$的负阶数项，所以收敛域不包括原点$0$。收敛域是$\{z | 0 < |z| < R\}$。
如果$n_2 \leq 0$，那么展开式不包括$z$的负阶数项，所以收敛域能包括原点$0$。收敛域是$\{z | 0 \leq |z| < R\}$。
双边序列¶
双边序列的定义是 \begin{align} \forall n_0 \in Z^+, \exists n \in \left\{n \middle| |n| > n_0\right\}: \qquad x[n] \neq 0 \end{align} 意思是找不到这样一个区间，使得区间外的所有$n$都满足$x[n] = 0$。
定义的意思是，对于任何一个正整数，都存在另一个绝对值大于它的整数，使得$x[n]$不等于0。意思就是对任何拟划定的区间，都能找到一个区间外的整数$n$，使得$x[n]$不等于0。
可以看做一个左边序列和一个右边序列拼起来。
如果左边序列的最大收敛半径是$R_+$，右边序列的最小收敛半径是$R_-$，那么收敛域是$\{z | R_- < |z| < R_+\}$。
收敛域如果存在的话，是一个圆环。当然也有可能收敛域是空集，如果$R_- \geq R_+$的话。
反变换¶
反变换的定义是 \begin{align} x[n] = {1 \over j 2 \pi} \oint_C X(z) z^{n-1} \,dz \end{align} 曲线$C$是复平面上的一条简单曲线，必须全部在收敛域ROC中，且需要包围原点$z = 0$。
这个定义衍生出了两种计算反变换的方法
- 留数法
- 部分分式法
留数法是严格按照定义来算，适用范围最广，一切形式的$X(z)$函数都可以适用。部分分式法其实可以看做对有理函数的加速，只适用于$X(z)$是有理函数的情况。
留数法¶
$f(z)$的有一个极点$p_0$，那么$f(z)$在$p_0$处的留数的是 \begin{align} \operatorname{Res} (f(z), p_0) = {1 \over j 2 \pi} \oint_\gamma f(z) \,dz \end{align} $\gamma$是仅包含$z_0$的简单曲线。
如果$\gamma$包含了$f(z)$的$n$个极点$\{p_1, p_2, \ldots, p_n\}$，那么 \begin{align} {1 \over j 2 \pi} \oint_\gamma f(z) \,dz = \sum_{k = 1}^{n} \operatorname{Res} (f(z), p_k) \end{align}
由柯西积分定理，$\gamma$外如果有$n$个极点$\{p_1', p_2', \ldots, p_n'\}$，那么 \begin{align} {1 \over j 2 \pi} \oint_{\gamma^-} f(z) \,dz = \sum_{k = 1}^{n} \operatorname{Res} (f(z), p_k') \end{align} 又因为 \begin{align} {1 \over j 2 \pi} \oint_{\gamma^-} f(z) \,dz = - {1 \over j 2 \pi} \oint_\gamma f(z) \,dz \end{align} 所以 \begin{align} {1 \over j 2 \pi} \oint_\gamma f(z) \,dz = - \sum_{k = 1}^{n} \operatorname{Res} (f(z), p_k') \end{align}
也就是说，算围栏积分，既可以用曲线内部的极点留数和也可以用曲线外面的极点留数和，怎么方便怎么来。假如曲线内部包含很多个极点，而曲线外面只有1个极点，那么用曲线外极点留数来算显然更方便。
这里说
$\gamma$外如果有$n$个极点$\{p_1', p_2', \ldots, p_n'\}$
其实等价于说
$\gamma^-$内有$n$个极点$\{p_1', p_2', \ldots, p_n'\}$
观察反变换式子，发现等式右边计算的是$C$内函数$X(z) z^{n-1}$的留数和 \begin{align} {1 \over j 2 \pi} \oint_C X(z) z^{n-1} \,dz = \sum_{i = 1}^{k} \operatorname{Res} (X(z) z^{n-1}, p_i) \end{align} $p_i$指的是$C$内，函数$X(z) z^{n-1}$的极点。
一定要记得$p_i$是函数$X(z) z^{n-1}$的极点，而不是函数$X(z)$的极点。
或者 \begin{align} {1 \over j 2 \pi} \oint_C X(z) z^{n-1} \,dz = - \sum_{i = 1}^{k} \operatorname{Res} (X(z) z^{n-1}, p_i') \end{align} $p_i'$指的是$C$外（$C^-$内），函数$X(z) z^{n-1}$的极点。
部分分式法¶
如果$X(z)$是一个有理函数，那么一定可以拆解成这种形式 \begin{align} X(z) &= \\ \end{align}
证明$\{z^n | z \in Z\}$是正交函数系¶
\begin{align} \langle z_1^n, z_2^n \rangle &= \sum_{n = -\infty}^{+\infty} \left(z_1^n\right)^* z_2^n \\ &= \sum_{n = -\infty}^{+\infty} \left(z_1^*\right)^n z_2^n \\ &= \end{align}
DFT¶
- $f$离散，$F$周期
- $f$连续，$F$非周期
- $f$周期，$F$离散
- $f$非周期，$F$连续
时域函数$f$和变换域函数$F$之间有某种对偶性
例如FS中$f$是周期连续函数，则$F$是离散非周期函数；FT中$f$是非周期连续函数，则$F$是连续非周期函数；DTFT中$f$是非周期离散函数，则$F$是连续周期函数。都无一例外符合这个对偶性。
- $f$离散、周期
- $F$周期、离散
DFT产生的一个重要动机是希望时域和变换域都是离散的。因此时域离散对应了频域周期，频域离散对应了时域周期。所以猜想DFT应该具有
有2种途径可以从上面我们已有的变换推导到DFT
- CTFS
- DTFT
在CTFS中，$f$是周期的但不离散，所以把$f$变成离散的就可以了。
在DTFT中，$f$是离散的但不周期，所以把$f$变成周期的就可以了。
定义 \begin{align} X[k] = \sum_{n = 0}^{N - 1} x[n] e^{- j 2 \pi {k \over N} n} \end{align}
用Fourier's trick解出$x[n]$ \begin{align} \color{red}{\sum_{k = 0}^{N - 1}} X[k] \color{red}{e^{j 2 \pi {n' \over N} k}} = \color{red}{\sum_{k = 0}^{N - 1}} \sum_{n = 0}^{N - 1} x[n] e^{- j 2 \pi {k \over N} n} \color{red}{e^{j 2 \pi {n' \over N} k}} \end{align} 交换右边求和次序 \begin{align} \sum_{k = 0}^{N - 1} X[k] e^{j 2 \pi {k \over N} n'} &= \sum_{n = 0}^{N - 1} x[n] \underbrace{\sum_{k = 0}^{N - 1} e^{- j 2 \pi {k \over N} n} e^{j 2 \pi {k \over N} n'}}_{= N \delta[n' - n]} \end{align} 所以 \begin{align} \sum_{k = 0}^{N - 1} X[k] e^{j 2 \pi {k \over N} n'} &= N x[n'] \end{align}
这边的推导我想了很久很久。发现这里是第一次在分析公式上用Fourier's trick。和在综合公式上的用法有一点不同。
DFT还可以写成矩阵形式 \begin{align} \vec{X} = \left(\begin{matrix} e^{- j 2 \pi {0 \over N} 0} & e^{- j 2 \pi {0 \over N} 1} & \cdots & e^{- j 2 \pi {0 \over N} (N - 1)} \\ e^{- j 2 \pi {1 \over N} 0} & e^{- j 2 \pi {1 \over N} 1} & \cdots & e^{- j 2 \pi {1 \over N} (N - 1)} \\ \vdots & \vdots & \ddots & \vdots \\ e^{- j 2 \pi {N - 1 \over N} 0} & e^{- j 2 \pi {N - 1 \over N} 1} & \cdots & e^{- j 2 \pi {N - 1 \over N} (N - 1)} \\ \end{matrix}\right) \cdot \underbrace{\left(\begin{matrix} x[0] \\ x[1] \\ \vdots \\ x[N - 1] \end{matrix}\right)}_{\vec{x}} \end{align} $\vec{X}$称为$X[k]$的主值序列。$X[k]$就是$\vec{X}$以$N$为周期的无限延拓。同理$\vec{x}$称为$x[n]$的主值序列。$x[n]$是$\vec{x}$以$N$为周期的无限延拓。
从CTFS推到DFT¶
回想CTFS。$x(t)$是一个周期为$f_0^{-1}$的连续函数，按正交函数系$\{e^{j 2 \pi n f_0 t} | n \in Z\}$展开证明正交 \begin{align} x(t) &= \sum_{k=-\infty}^{\infty} X_k e^{j 2 \pi k f_0 t} \end{align} 其中$X_k$就是$x(t)$在基底$e^{j 2 \pi k f_0 t}$上的投影。
投影$X_k$是这样计算的 \begin{align} X_k &= f_0 \int_{C}^{C + {1 \over f_0}} e^{- j 2 \pi k f_0 t} x(t) \,dt \end{align}
现在，假设采样周期是$T_s$，这样在$x(t)$的一个周期$f_0^{-1}$里，会采样$(T_s f_0)^{-1}$个点，记为 \begin{align} N = {1 \over f_0 T_s} \end{align} 这样可以知道$x(t)$在每个采样点上的值。令$t = n T_s$即可 \begin{align} x(\color{red}{n T_s}) &= \sum_{k=-\infty}^{\infty} X_k e^{j 2 \pi k f_0 \color{red}{n T_s}} \end{align} 再用$N = {1 \over f_0 T_s}$的关系 \begin{align} x(n T_s) &= \sum_{k=-\infty}^{\infty} X_k e^{j 2 \pi k \color{red}{1 \over N T_s} n T_s} \end{align} 再用$x[n] = x(n T_s)$，得到 \begin{align} x[n] = \sum_{k=-\infty}^{\infty} X_k e^{j 2 \pi {k \over N} n} \\ \end{align}
但是你会发现一个问题，似乎$X_k$是周期的，而且以$N$为周期，即 \begin{align} \forall k \in Z: \qquad X_k = X_{k + N} \end{align} 这是因为基底是有限的$N$个，而不是无限可数个 \begin{align} \forall k \in Z: \qquad e^{j 2 \pi {k + N \over N} n} = e^{(j 2 \pi {k \over N} n + j 2 \pi n)} = e^{j 2 \pi {k \over N} n} \end{align}
所以 \begin{align} x[n] = \sum_{k = 0}^{N - 1} X_k e^{j 2 \pi {k \over N} n} \\ \end{align}
实际上不一定从$k = 0$求和到$N - 1$。任意一个完整周期都是可以的。
把$X_k = f_0 \int_{C}^{C + {1 \over f_0}} e^{- j 2 \pi k f_0 t} x(t) \,dt$改造一下就可以变成DFT系数 \begin{align} X_k &= f_0 \color{red}{\sum_{n = 0}^{N - 1}} e^{- j 2 \pi {k \over N} n} x(n T_s) \color{red}{T_s} \\ &= {1 \over N T_s} \sum_{n = 0}^{N - 1} e^{- j 2 \pi {k \over N} n} x[n] T_s \\ &= {1 \over N} \sum_{n = 0}^{N - 1} e^{- j 2 \pi {k \over N} n} x[n] \end{align}
这个"改造"的思路是，先把积分变成离散求和。本来积分上下限是$t$从$0$到${1 \over f_0}$，现在离散化之后，采样$N$个点，采样间隔是$T_s$，所以把$dt$变成$T_s$，把上下限从时间量纲（从0s积分到1s）变成序数量纲（从第一个点到最后一个点）。
从DTFT推到DFT¶
可惜的是，上面从CTFS推到DFT的做法是完全可行的，但是现实中没有人这么做。通常的DFT定义把系数$1 \over N$放到综合公式而不是分析公式。从这里能看出DFT是从DTFT推导的。
回忆DTFT的综合公式 \begin{align} x[n] = \int_{- {1 \over 2}}^{1 \over 2} X(e^{j 2 \pi f}) e^{j 2 \pi f n} \,df \end{align} 变成 \begin{align} x[n] &= \color{red}{\sum_{k = 0}^{N - 1}} X(e^{j 2 \pi \color{red}{k \over N}}) e^{j 2 \pi \color{red}{k \over N} n} \color{red}{1 \over N} \\ &= {1 \over N} \sum_{k = 0}^{N - 1} X[k] e^{j 2 \pi {k \over N} n} \end{align} 可以看到果然多了一个系数${1 \over N}$。
"改造"思路和上面一模一样。$f$的范围是$[0, 1]$，又在这个范围里取$N$个点，采样间隔是${1 \over N}$，所以$df = {1 \over N}$，第$k$个采样点从$f$变成$k {1 \over T_s}$。
你可能会好奇凭什么时域采样$N$，频域也正好一样采样$N$个点？一个比较粗略的、不太能使人完全信服的理由是，为了保证$\forall n \in Z: x[n + N] = x[n]$，必须保证$f N \in Z$ \begin{align} \int_{- {1 \over 2}}^{1 \over 2} X(e^{j 2 \pi f n}) e^{j 2 \pi f n} \,df = \int_{- {1 \over 2}}^{1 \over 2} X(e^{j 2 \pi f n}) e^{j 2 \pi f n} \underbrace{e^{j 2 \pi f N}}_{必须是1} \,df \end{align}
循环卷积¶
一般的离散函数卷积的定义是 \begin{align} h[n] * x[n] = \sum_{k = -\infty}^{+\infty} h[k] x[n - k] \end{align} 而循环卷积的定义是 \begin{align} \vec{h} \mathop{*}^{L} \vec{x} = \sum_{k = \color{red}{0}}^{\color{red}{L - 1}} \tilde{h}[k] \tilde{x}[n - k] \end{align} 其中$\tilde{h}[n]$是$\vec{h}$的$L$周期的无限延拓，意思是如果$\vec{h}$里面的元素不足$L$个，就在后端补零直到长度变成$L$，再无限延拓。
也可以写成矩阵相乘形式 \begin{align} \vec{h} \mathop{*}^{L} \vec{x} = \left(\begin{matrix} \tilde{h}[0] & \tilde{h}[-1] & \ldots & \tilde{h}[- (L - 1)] \\ \tilde{h}[1] & \tilde{h}[0] & \ldots & \tilde{h}[- (L - 2)] \\ \vdots & \vdots & \ddots & \vdots \\ \tilde{h}[L - 1] & \tilde{h}[L - 2] & \ldots & \tilde{h}[0] \\ \end{matrix}\right) \cdot \left(\begin{matrix} \tilde{x}[0] \\ \tilde{x}[1] \\ \vdots \\ \tilde{x}[L - 1] \end{matrix}\right) \end{align} 因为$\tilde{h}[n]$是周期$L$的离散函数，所以也可以写成 \begin{align} \vec{h} \mathop{*}^{L} \vec{x} = \left(\begin{matrix} \tilde{h}[0] & \tilde{h}[L - 1] & \ldots & \tilde{h}[1] \\ \tilde{h}[1] & \tilde{h}[0] & \ldots & \tilde{h}[2] \\ \vdots & \vdots & \ddots & \vdots \\ \tilde{h}[L - 1] & \tilde{h}[L - 2] & \ldots & \tilde{h}[0] \\ \end{matrix}\right) \cdot \left(\begin{matrix} \tilde{x}[0] \\ \tilde{x}[1] \\ \vdots \\ \tilde{x}[L - 1] \end{matrix}\right) \end{align}
证明$\{e^{j 2 \pi {k \over N} n} | k \in [0, 1, \ldots N - 1]\}$是正交函数系¶
\begin{align} \langle e^{j 2 \pi {k_1 \over N} n}, e^{j 2 \pi {k_2 \over N} n} \rangle &= \sum_{n = 0}^{N - 1} e^{-j 2 \pi {k_1 \over N} n} e^{j 2 \pi {k_2 \over N} n} \\ &= \sum_{n = 0}^{N - 1} e^{j 2 \pi {k_2 - k_1 \over N} n} \\ &= N \underbrace{\delta[k_2 - k_1]}_{\begin{cases} 0, &\qquad k_2 \neq k_1 \\ 1, &\qquad k_2 = k_1 \end{cases}} \end{align}
FFT¶
回想DFT的运算 \begin{align} X[k] &= \sum_{n = 0}^{N - 1} x[n] e^{- j 2 \pi {k \over N} n} \\ &= \sum_{n = 0}^{N - 1} \Re(x[n]) \Re(\omega_N^{kn}) - \Im(x[n]) \Im(\omega_N^{kn}) + j \left[\Re(x[n]) \Im(\omega_N^{kn}) + \Im(x[n]) \Re(\omega_N^{kn})\right] \end{align}
2个复数相乘，相当于4次实数乘法、2次实数加法。2个复数相加，相当于2次实数加法。
如果不计算计算$\omega_N^{kn}$需要的运算量，假设所有的$\omega_N^{kn}$一开始都算好了摆在那里，算出$\vec{X}$中的一项$X[k]$，就需要$4 N$次实数乘法、$2(2 N - 1)$次加法（减法算加法）。因为$\vec{X}$有$N$项，所以算出整个$\vec{X}$，需要$4 N^2$次乘法、$2 N(2 N - 1)$次加法。
所以普通的DFT算法时间复杂度是$O(n^2)$。
Coolkey-Tukey算法 aka. DIT算法¶
回想DFT \begin{align} X[k] = \sum_{n = 0}^{N - 1} x[n] e^{- j 2 \pi {k \over N} n} \\ \end{align} 可以分成两部分，$n$为偶数、$n$为奇数。 \begin{align} X[k] &= \sum_{n = 0}^{\color{red}{N \over 2} - 1} x[\color{red}{2n}] e^{- j 2 \pi {k \over N} \color{red}{2n}} + \sum_{n = 0}^{\color{red}{N \over 2} - 1} x[\color{red}{2n + 1}] e^{- j 2 \pi {k \over N} \color{red}{(2n + 1)}} \\ &= \underbrace{\sum_{n = 0}^{{N \over 2} - 1} x[2n] e^{- j 2 \pi {k \over \color{red}{N / 2}} n}}_{x[2n]的DFT} + e^{- j 2 \pi {k \over N}} \underbrace{\sum_{n = 0}^{{N \over 2} - 1} x[2n + 1] e^{- j 2 \pi {k \over \color{red}{N / 2}} n}}_{x[2n + 1]的DFT} \end{align}
这样，就把DFT问题分解成了2个DFT问题。只要分别求出$x[2n]$的DFT和$x[2n + 1]$的DFT就可以了。
这样做的好处是，时间复杂度降低了非常多。如果仅仅假设作一次分解，那么原先要作$4 N^2$次实数加法运算、$2N(2N - 1)$次实数乘法，现在分解成两个长度为一半的序列，每个序列自己需要作$4 \left({N \over 2}\right)^2 = N^2$次实数加法运算、$N(N - 1)$次实数乘法，最后合并需要作1次复数乘法、1次复数加法，等价于4次实数乘法、4次实数加法，这样加起来，也就是$N^2 + 4$次实数加法、$N(N - 1) + 4$次实数乘法。
$x[2n]$的DFT和$x[2n + 1]$的DFT里面的元素个数都是只有${N \over 2}$个，所以还可以利用$e^{- j 2 \pi {k \over N}}$的对称性，进一步化简成 \begin{align} X[k] &= \sum_{n = 0}^{{N \over 2} - 1} x[2n] e^{- j 2 \pi {k \over {N / 2}} n} \color{red}{+} e^{- j 2 \pi {k \over N}} \sum_{n = 0}^{{N \over 2} - 1} x[2n + 1] e^{- j 2 \pi {k \over {N / 2}} n} \\ X\left[k + {N \over 2}\right] &= \sum_{n = 0}^{{N \over 2} - 1} x[2n] e^{- j 2 \pi {k \over {N / 2}} n} \color{red}{-} e^{- j 2 \pi {k \over N}} \sum_{n = 0}^{{N \over 2} - 1} x[2n + 1] e^{- j 2 \pi {k \over {N / 2}} n} \\ \end{align}
很显然这是个递归的思想。如果$x[2n]$的长度不是2，那么还可以继续把$x[2n]$分解成$x[4n], x[4n + 2]$，把$x[2n + 1]$分解成$x[4n + 1], x[4n + 3]$。直到最后都变成长度为2的序列。因为长度为2的序列的DFT非常简单，就是加减 \begin{align} X_0 &= x_0 + x_1 \\ X_1 &= x_0 - x_1 \end{align} 也可以写成矩阵形式 \begin{align} \vec{X} = \left(\begin{matrix} 1 & 1 \\ 1 & -1 \\ \end{matrix}\right) \cdot \vec{x} \end{align}
$N = 8$的例子¶
$N = 8$时， \begin{align} \vec{x} = (\begin{matrix} x_0 & x_1 & x_2 & x_3 & x_4 & x_5 & x_6 & x_7 \end{matrix})^T \end{align} 先切成 \begin{align} \vec{x}_1 &= (\begin{matrix} x_0 & x_2 & x_4 & x_6 \end{matrix})^T \\ \vec{x}_2 &= (\begin{matrix} x_1 & x_3 & x_5 & x_7 \end{matrix})^T \\ \end{align} 可以看到$\vec{x}_1$中的元素全部都是$\vec{x}$里下标为偶数的元素，$\vec{x}_2$中的元素全部都是$\vec{x}$里下标为奇数的元素。
再切成 \begin{align} \vec{x}_{1, 1} &= (\begin{matrix} x_0 & x_4 \end{matrix})^T \\ \vec{x}_{1, 2} &= (\begin{matrix} x_2 & x_6 \end{matrix})^T \\ \vec{x}_{2, 1} &= (\begin{matrix} x_1 & x_5 \end{matrix})^T \\ \vec{x}_{2, 2} &= (\begin{matrix} x_3 & x_7 \end{matrix})^T \\ \end{align} 可以看到$\vec{x}_{1, 1}$中的元素全部都是$\vec{x}_1$里下标为偶数的元素，$\vec{x}_{1, 2}$中的元素全部都是$\vec{x}_1$里下标为奇数的元素。对于$\vec{x}_{2, 1}, \vec{x}_{2, 2}$同理。
\begin{align} & \begin{aligned} & \begin{aligned} & \left(\begin{matrix} x_0 \\ x_4 \\ \end{matrix}\right) && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_0 \\ x_4 \\ \end{matrix}\right) \\ \\ & \left(\begin{matrix} x_2 \\ x_6 \\ \end{matrix}\right) && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_2 \\ x_6 \\ \end{matrix}\right) \\ \\ \end{aligned} && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_0 \\ x_2 \\ x_4 \\ x_6 \\ \end{matrix}\right) \\ & \begin{aligned} & \left(\begin{matrix} x_1 \\ x_5 \\ \end{matrix}\right) && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_1 \\ x_5 \\ \end{matrix}\right) \\ \\ & \left(\begin{matrix} x_3 \\ x_7 \\ \end{matrix}\right) && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_3 \\ x_7 \\ \end{matrix}\right) \\ \\ \end{aligned} && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_1 \\ x_3 \\ x_5 \\ x_7 \\ \end{matrix}\right) \\ \end{aligned} && \longrightarrow && \operatorname{DFT} \left(\begin{matrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \\ x_7 \\ \end{matrix}\right) \end{align} 图中的箭头"$\longrightarrow$"都是指蝴蝶型运算。
为什么输出是自然顺序
0 1 2 ... 7但是输入不是呢？输入的顺序怎么得到？做法很简单，就是把自然顺序的
0 1 2 ... 7写成二进制000 001 010 ... 111，然后，每个数字的二进制倒过来，变成000 100 010 ... 111，就成为输入下标的顺序。\begin{align} & {\rm 十进制} && {\rm 二进制} && {\rm 二进制倒序} && {\rm 二进制倒序转十进制} \\ & 0 && 000 && 000 && 0 \\ & 1 && 001 && 100 && 4 \\ & 2 && 010 && 010 && 2 \\ & 3 && 011 && 110 && 6 \\ & 4 && 100 && 001 && 1 \\ & 5 && 101 && 101 && 5 \\ & 6 && 110 && 011 && 3 \\ & 7 && 111 && 111 && 7 \end{align}
这里可以详细运算Coolkey-Tukey算法的时间复杂度。以蝴蝶型运算为单位。我们发现一个"蝴蝶结"需要作1次复数乘法、2次复数加法，等价于4次实数乘法、6次实数加法。对于长度为$N$的序列，会有$\log_2 N$级蝴蝶结，每一级蝴蝶结里面都有${N \over 2}$个蝴蝶结，所以一共有 \begin{align} {N \over 2} \log_2 N \end{align} 个蝴蝶结。所以对于$N$长度的序列，用Coolkey-Tukey算法，需要作$2 N \log_2 N$次实数乘法、$3 N \log_2 N$次实数加法，时间复杂度是$O(n \log_2 n)$。和常规方法比较，是数量级级的效率提升。
def W(N):
return np.e**(- 1j * 2 * np.pi / N)
def fft2(x0, x1):
return [
x0 + x1, # X0
x0 - x1, # X1
]
def fft4(x0, x1, x2, x3):
_X0, _X2 = fft2(x0, x2)
_X1, _X3 = fft2(x1, x3)
return [
_X0 + _X1 * W(4)**0, # X0
_X2 + _X3 * W(4)**1, # X1
_X0 - _X1 * W(4)**0, # X2
_X2 - _X3 * W(4)**1, # X3
]
def fft8(x0, x1, x2, x3, x4, x5, x6, x7):
_X0, _X2, _X4, _X6 = fft4(x0, x2, x4, x6)
_X1, _X3, _X5, _X7 = fft4(x1, x3, x5, x7)
return [
_X0 + _X1 * W(8)**0, # X0
_X2 + _X3 * W(8)**1, # X1
_X4 + _X5 * W(8)**2, # X2
_X6 + _X7 * W(8)**3, # X3
_X0 - _X1 * W(8)**0, # X4
_X2 - _X3 * W(8)**1, # X5
_X4 - _X5 * W(8)**2, # X6
_X6 - _X7 * W(8)**3, # X7
]
Sander-Tukey算法 aka. DIF算法¶
IFFT¶
观察DFT的分析公式和综合公式 \begin{align} X[k] &= \sum_{n = 0}^{N - 1} x[n] e^{\color{red}{-} j 2 \pi {k \over N} n} \\ x[n] &= \color{red}{1 \over N} \sum_{n = 0}^{N - 1} X[k] e^{\color{red}{+} j 2 \pi {k \over N} n} \end{align} 发现DFT和IDFT的差别仅仅就在于
- 综合公式比分析公式多了一个系数${1 \over N}$
- 综合公式里的指数是$+$，分析公式里的指数是$-$
所以有两种办法来做IFFT。
改蝴蝶结的乘系数+最后除以$N$¶
把Coolkey-Tukey中的每个蝴蝶结左下方的相乘系数从$\omega_{N}^{nk}$改成$\omega_{N}^{-nk}$，再在最后乘以一个系数${1 \over N}$。
再次注意$\omega_{N}^{kn}$的定义是$e^{-j 2 \pi {k \over N} n}$。
这样IFFT和FFT的程序其实有很大不同了。
输入先取共轭+最后除以$N$¶
这种方法不需要改程序，只需要在FFT的程序前面插入一个对输入逐个取共轭的程序、在FFT程序的最后追加一个取共轭、一个除以$N$的程序就可以了。
原理非常简单。观察综合公式 \begin{align} x[n] = {1 \over N} \sum_{n = 0}^{N - 1} X[k] e^{j 2 \pi {k \over N} n} \\ \end{align} 右边取两次共轭，交换共轭和求和次序 \begin{align} x[n] &= {1 \over N} \left[\sum_{n = 0}^{N - 1} (X[k] e^{j 2 \pi {k \over N} n} )^*\right]^*\\ &= {1 \over N} \left(\underbrace{\sum_{n = 0}^{N - 1} X[k]^* e^{- j 2 \pi {k \over N} n}}_{\operatorname{DFT}(X[k]^*) }\right)^*\\ \end{align} 可见只要给一个FFT程序输入$X[k]^*$、再给结果取共轭、除以$N$就可以了。非常方便。
数字滤波器¶
设计方法¶
冲击响应不变法¶
使数字滤波器的单位冲激响应$h[n]$处处等于对应模拟滤波器的单位冲击响应的采样点$h(n T_s)$ \begin{align} \forall n \in Z: \qquad h[n] = h(n T_s) \end{align} 即 \begin{align} \forall n \in Z: \qquad \int_{- {1 \over 2}}^{1 \over 2} H(e^{j 2 \pi f}) e^{j 2 \pi f n} \,df = \int_{- \infty}^{+ \infty} H(j 2 \pi f) e^{j 2 \pi f n T_s} \,df \end{align} 但是从上面的这个关系，看不出频谱$H(e^{j 2 \pi f})$和$H(j 2 \pi f)$之间的关系。
时刻记住我们的目的：把模拟滤波器的频谱$H(j 2 \pi f)$转换到数字滤波器的频谱$H(e^{j 2 \pi f})$。所以一定要得到用$H(j 2 \pi f)$表示的$H(e^{j 2 \pi f})$。
回想采样章节，我们发现这个好像就是$x[n] = x(n T_s)$的定义式。而且实际采样$x[n] = x(n T_s)$的频谱和理想采样$\hat{x}(t)$的频谱好像是有某种关联的。这个关联可以写成 \begin{align} H(e^{j 2 \pi f}) = \hat{H}(j 2 \pi {f \over T_s}) \end{align}
再把几个频谱关系放在一起观察 \begin{align} & h[n] && \mathop{\longleftrightarrow}^{\rm DTFT} && H(e^{j 2 \pi f}) \\ & h(t) && \mathop{\longleftrightarrow}^{\rm CTFT} && H(j 2 \pi f) \\ & \hat{h}(t) = \sum_{n = -\infty}^{+\infty} h(t) \delta(t - n T_s) && \mathop{\longleftrightarrow}^{\rm CTFT} && \hat{H}(j 2 \pi f) = {1 \over T_s} \sum_{n = -\infty}^{+\infty} H\left(j 2 \pi \left(f - {n \over T_s}\right)\right) \end{align} 把上面的关联带入最后一个式子，得到 \begin{align} H(e^{j 2 \pi f}) = {1 \over T_s} \sum_{n = -\infty}^{+\infty} H\underbrace{\left(j 2 \pi \left({f \over T_s} - {n \over T_s}\right)\right)}_{横向缩放、平移} \end{align}
很显然，把设计好的模拟滤波器的频率响应函数先横向伸缩变换、再复制搬移，就得到了数字滤波器的频率响应函数。
但是用传输函数更方便，所以
这里推导用的全是频率响应函数而不是传输函数。我觉得也可以一开始就用传输函数推导，即从$s$变换推到$z$变换。