# 匹配滤波实现

其实前面几篇已经讲了好几遍 AWGN 信道理想接收机的实现了，这一篇再拎出来说是为了引出匹配滤波 (matched filter) 的概念。

我们已经知道 MAP 判决准则：

$$\hat{m}=\argmax_{1\le m\le N}[\eta_m+\textbf{r}^T\textbf{s}_m]$$

其中$\textbf{r}^T\textbf{s}_m$ 可以表示为 correlation 的形式

$$\textbf{r}^T\textbf{s}_m=\int_0^Tr(t)s_m(t){\rm d}t$$

这为我们提供了基本的信号接收处理方式，就如下面的图所示。

问题在于，就接收机中模拟部分来看，为了实现向量化，我们需要对$N$ 个基底向量进行积分，这是十分巨大的计算开销。

那么我们有解决办法吗？考虑一个冲激响应为$h_m(t)=s_m(T-t)$ 的滤波器，我们对接收信号进行一个卷积：

$$r(t)*h(t)|_{t=T}=\int_{-\infty}^{\infty}r(\tau)h_m(T-\tau){\rm d}\tau=\int_0^Tr(t)s_m(t){\rm d}t$$

这样即可得到 correlation 的结果。这也就是匹配滤波的思路，下面我们要证明为什么要选择一个这样的滤波器$h_m(t)=s_m(T-t)$。

我们希望能够实现两个输出信噪比最高的滤波器，假定输入信号

$$r(t)=s(t)+n(t)$$

我们使用一个冲激响应$h(t)$ 的滤波器对输入信号进行滤波，得到

$$y(t)=h(t)*r(t)=h(t)*s(t)+h(t)*n(t)=h(t)*s(t)+z(t)$$

设抽样时刻$t=T$，有

$$h(t)*s(t)|_{t=T}=\int_{-\infty}^{\infty}H(f)S(f)e^{j2\pi ft}{\rm d}f|_{t=T}$$

为了便于证明，我们将时域信号转移到频域上。经过滤波的噪声能量满足：

$$\sigma_z^2=\mathbb{E}[z^2(T)]=R_z(0)$$

在频域上，我们能够得到

$$\sigma_z^2=\int_{-\infty}^{\infty}S_N(f)|H(f)|^2{\rm d}f=\frac{N_0}{2}\int_{-\infty}^{\infty}|H(f)|^2{\rm d}f$$

那么考虑 SNR：

$$\begin{aligned} SNR=&\frac{|\int_{-\infty}^{\infty}H(f)S(f)e^{j2\pi ft}{\rm d}f|^2}{\frac{N_0}{2}\int_{-\infty}^{\infty}|H(f)|^2{\rm d}f}\\ \le&\frac{\int_{-\infty}^{\infty}|H(f)|^2{\rm d}f\cdot\int_{-\infty}^{\infty}|S(f)e^{j2\pi fT}|^2{\rm d}f}{\frac{N_0}{2}\int_{-\infty}^{\infty}|H(f)|^2{\rm d}f}\\ =&\frac{2}{N_0}\int_{-\infty}^{\infty}|S(f)e^{j2\pi fT}|^2{\rm d}f \end{aligned}$$

其中从第一步到第二步，有积分形式的 Cauchy-Schwartz 不等式：

$$|\int f(t)g(t){\rm d}t|^2\le\int |f(t)|^2{\rm d}t\cdot\int |g(t)|^2{\rm d}t$$

当且仅当$f(x)$ 和$g(x)$ 线性相关时不等式两边取等。因此，$SNR$ 式取等条件为

$$H(f)=\alpha\cdot S^*(f)e^{-j2\pi ft}\rightarrow h(t)=\alpha s^*(T-t)$$

这个关系可以通过下面的式子给与证明：

$$\begin{aligned} &\int_{-\infty}^{\infty}s^*(T-t)e^{-j2\pi ft}{\rm d}t\\ =&(\int_{-\infty}^{\infty}s(T-t)e^{j2\pi ft}{\rm d}t)^*\\ =&(\int_{-\infty}^{\infty}s(t')e^{-j2\pi f(t'-T)}{\rm d}t')^*\\ =&s^*(f)e^{-j2\pi fT} \end{aligned}$$

此时，匹配滤波输出的信噪比为$2\mathcal{E}/N_0$。

# 最大似然判决的最大错误率联合界

对通信系统进行分析时，我们希望能够得到错误率的精确取值。但是在实际环境中，我们往往难以求解出一个精确的解，甚至整个系统都无法通过能够数值计算的方法表示。

因此，我们希望能够求出通信系统错误率的上界，用以预估系统的性能。

对于工程中使用的 ML 判决准则，其判决域为

$$\mathcal{D}_m=\{\textbf{r}:f(\textbf{r}|\textbf{s}_m)>f(\textbf{r}|\textbf{s}_k),\forall k\neq m\}$$

对应错误的判决域即为其补集$\mathcal{D}_m^c$。考虑一个错误事件$\varepsilon_{m\to m'}$

$$\varepsilon_{m\to m'}=\{\textbf{r}:f(\textbf{r}|\textbf{s}_m\le f(\textbf{r}|\textbf{s}_{k}),\forall k\neq m\}$$

错误事件对应的判决域为错误事件中各个错误判决域的并集：

$$\mathcal{D}_m^c=\bigcup_{\substack{1\le m\le M\\ m'\neq m}}\varepsilon_{m\to m'}$$

符号错误的概率即是落入错误事件对应的判决域的概率

$$\begin{aligned} P_e&=\frac{1}{M}\sum_{m=1}^{M}\int_{\mathcal{D}_m^c}f(\textbf{r}|\textbf{s}_m){\rm d}\textbf{r}\\ &=\frac{1}{M}\sum_{m=1}^MP_{\textbf{r}|\textbf{s}_m}\{\mathcal{D}_m^c\}\\ &=\frac{1}{M}\sum_{m=1}^MP_{\textbf{r}|\textbf{s}_m}\{\bigcup_{\substack{1\le m\le M\\ m'\neq m}}\varepsilon_{m\to m'}\}\\ &\le\frac{1}{M}\sum_{m=1}^M\sum_{\substack{1\le m'\le M\\ m'\neq m}}P_{\textbf{r}|\textbf{s}_m}\{\varepsilon_{m\to m'}\} \end{aligned}$$

上式中放缩一步是由并集的基本性质得到：

$$P(A\cup B)\le P(A) + P(B)$$

在 AWGN 信道上，有

$$P_{\textbf{r}|\textbf{s}_m}\{\varepsilon_{m\to m'}\}=\int_{\varepsilon_{m\to m'}}f(\textbf{r}|\textbf{s}_m){\rm d}\textbf{r}=Q(\sqrt{\frac{d_{m,m'}^2}{2N_0}})$$

即其取决于符号之间的距离。由此我们可以得到 ML 判决的最大错误率。

# 并集带来的不等式

为了更好的估计通信系统的性能，我们需要一些常用的不等式。

最基本的是并集不等式（union bound, Boole's inequality）：

$$Pr\{\bigcup_{k=1}^{N}A_k\}\le\sum_{k=1}^{N}Pr\{A_k\}$$

即并集所对应的事件的概率低于各个事件概率之和。

可以利用概率的性质得到相反的表达式 (reverse union bound)：

$$Pr\{A-\bigcup_{k=1}^NA_k\}\ge Pr\{A\}[1-\sum_{k=1}^NPr(A_k|A)]$$

然而，上面两种不等式得到的上下界是十分粗糙的，往往和实际情况相差甚远。我们考虑在单纯的并集基础上增加一些修正：

$$s_1=\sum_{i=1}^{N}Pr(A_i)\\ s_2=\sum_{i=1}^{N-1}\sum_{j=i+1}^NPr(A_i\cap A_j)\\ ...\\ s_k=\sum_{i_1<i_2<...<i_k}Pr(A_{i_1}\cap A_{i_2}\cap...\cap A_{i_k})$$

对于单纯的并集$s_1$，其相较于真实概率是偏大的，因此我们减去其中交集的修正项$s_2$，得到了一个偏小的结果（下界）。为了修正偏小的结果，我们可以加上修正项$s_3$，得到一个相较于真实概率偏大的结果（上界），以此类推。这样，我们得到了 Bonferroni 不等式：

$$\sum_{i=1}^{2u_2}(-1)^{i-1}s_i\le Pr(\bigcup_{i=1}^NA_i)\le\sum_{i=1}^{2u_1-1}(-1)^{i-1}s_i,\\[2ex] \forall 2u_1-1\le N,2u_2\le N$$

# 对 Q 函数的近似

Q 函数属于难以进行数值计算的函数，因此，很多时候我们希望能够通过一些方法来近似计算 Q 函数。

Q 函数可以表示为无穷级数的形式：

$$Q(x)=\frac{1}{\sqrt{2\pi}x}e^{-x^2/2}(1-\frac{1}{x^2}+\frac{1\cdot 3}{x^3}-\frac{1\cdot 3\cdot 5}{x^5}+...)$$

我们可以使用无穷级数的前几项来近似计算 Q 函数：

$$L_2(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}x}(1-\frac{1}{x^2})\\ U_1(x)=\frac{e^{-x^2/2}}{\sqrt{2\pi}x}\\$$

这样有

$$L_2(x)\le Q(x)\le U_1(x)$$

更精确的，我们可以使用更多项来近似：

$$L_4(x)=\frac{1}{\sqrt{2\pi}x}e^{-x^2/2}(1-\frac{1}{x^2}+\frac{1\cdot 3}{x^3}-\frac{1\cdot 3\cdot 5}{x^5})\\ U_3(x)=\frac{1}{\sqrt{2\pi}x}e^{-x^2/2}(1-\frac{1}{x^2}+\frac{1\cdot 3}{x^3})$$

得到

$$L_4(x)\le Q(x)\le U_3(x)$$

此外，还有一个更加常用的近似：

$$L(x)=\frac{1}{\sqrt{2\pi}x}e^{-x^2/2}(\frac{x^2}{1+x^2})\le Q(x)\le U(x)=\frac{1}{2}e^{-x^2/2}$$

上面的几类近似如图所示，在$x$ 较大时，这些近似都是十分趋近于$Q(x)$ 的。

# 通信系统常见的错误率上下界

前面讲了 ML 判决的错误率上界，考虑

$$P_e\le\underbrace{\frac{1}{M}\sum_{m=1}^M\sum_{\substack{1\le m'\le M\\m'\neq m}}Q(\sqrt{\frac{d_{m,m'}^2}{2N_0}})}_{\rm bound\ 1}$$

利用 Q 函数性质

$$Q(x)\le U(x)=\frac{1}{2}e^{-x^2/2}$$

放缩得到

$$P_e\le\underbrace{\frac{1}{M}\sum_{m=1}^M\sum_{\substack{1\le m'\le M\\m'\neq m}}Q(\sqrt{\frac{d_{m,m'}^2}{2N_0}})}_{\rm bound\ 1}\le\underbrace{\frac{1}{2M}\sum_{m=1}^M\sum_{\substack{1\le m'\le M\\m'\neq m}}\exp(-\frac{d_{m,m'}^2}{4N_0})}_{\rm bound\ 2}$$

这其实是一个比较准的上界，不过考虑到如果$M$ 比较大，那么需要计算的项数将会是非常的多。为了便于表示，我们记

$$X=\exp(-1/(4N_0))$$

这样，bound2 可以转换为

$$T(x)=\sum_{m=1}^M\sum_{\substack{1\le m'\le M\\m'\neq m}}X^{d^2_{m,m'} } = \sum_{ {\rm all\ distinct}\ d} a_d X^{d^2}$$

从而

$$P_e\le\underbrace{\frac{1}{2M}T(X)}_{\rm bound\ 2}$$

不过，我们注意到

$$Q(\sqrt{\frac{d_{m,m'}^2}{2N_0}})\le Q(\sqrt{\frac{d_{min}^2}{2N_0}})\\[2ex] \exp(\frac{d_{m,m'}^2}{2N_0})\le\exp(\frac{d_{min}^2}{2N_0})$$

这样有

$$P_e\le(M-1)Q(\sqrt{\frac{d_{m,m'}^2}{2N_0}})\le\frac{M-1}{2}\exp(-\frac{d_{min}^2}{2N_0})$$

这是一个更加便于计算的上界（minimum distance bound）。

为了衡量几个上界的误差程度，我们以 16-QAM 为例来说明。几种上界的$P_e-\frac{\mathcal{E}_b}{N_0}$ 曲线如图所示。

可见错误率上界 bound 1 十分接近实际错误率，而放缩较多的其他几种上界距离错误率实际值差别较大。

错误率下界相较错误率上界使用较少，一般可以用来衡量在较差的情况下接收机的性能。考虑

$$\begin{aligned} P_e&=\frac{1}{M}\sum_{m=1}^{M}\int_{\mathcal{D}_m^c}f(\textbf{r}|\textbf{s}_m){\rm d}r\\ &\ge\frac{1}{M}\sum_{m=1}^M\max_{\substack{1\le m'\le M\\m'\neq m}}\int_{\varepsilon_{m\to m'}}f(\textbf{r}|\textbf{s}_m){\rm d}\textbf{r}\\ &=\frac{1}{M}\sum_{m=1}^M\max_{\substack{1\le m'\le M\\m'\neq m}}Q(\sqrt{\frac{d_{m,m'}^2}{2N_0}})\\ &=\frac{1}{M}\sum_{m=1}^MQ(\sqrt{\frac{d_{m,m'}^2}{2N_0}})\\ &\ge\frac{N_{min}}{M}Q(\sqrt{\frac{d_{min}^2}{2N_0}}) \end{aligned}$$

这里$N_{min}\le M$，是星座图中满足到附近点距离等于$d_{min}$ 的点的个数。