作者：phy-东西
审核：水缸

问题描述

“注水定理”解决的是信息论中的一个基本问题：以总容量最大化为目标的AWGN信道功率分配方案优化。该问题描述如下：有 $K$ 个并联 AWGN 信道且噪相互声独立，噪声功率依次为 $σ^2_1,σ^2_2,··· ,σ^2_K$ 。总功率受限于 $P$ ，求出使 $K$ 个并联信道功率最大化的功率分配方案。

写做优化问题格式为：

$\begin{aligned} &\max_{p_1, \dots , p_K}\sum^{K}_{k=1} \log_2 \left(1 + \frac{p_k}{\sigma ^2_k}\right)\\ \mathrm{s.t.}&\sum^K_{k = 1}p_k \le P\\ &p_k \ge 0, \ \ \ k = 1, 2, \dots , K\end{aligned} \tag{1.1}$

一个简单的证明

在这一节中我们给出一个比较便于理解的推导。

有的人可能觉得直接将所有功率分配到最好的（噪声功率最小的）信道里就可以，但信道容量的表达式是 $C_k = \log_2 (1 + p_k / σ^2_k)$ ，随功率增加，增长的幅度越来越小，这种想法启发我们每次将功率分配到容量增长幅度最大的信道中。

假设我们已有一个初始功率分配方案 $p^{(0)}_1 ,p^{(0)}_2 , \dots ,p^{(0)}_K$ ，满足：

$\sum^K_{k = 1}p^{(0)}_k < P, \ \ \ p^{(0)}_{k} \ge 0, \ \ \ k = 1, 2, \dots , K$

显然 $p^{(0)}_1 = p^{(0)}_2 = \dots = p^{(0)}_K = 0$ 也是一个合理的初始化方案。假设一正数 $(P - \sum^K_{k=1}p^{(0)}_k) \ge \delta > 0$ ，代表接下来要分配的功率。把 $\delta$ 功率分配到第 $k$ 个信道中，则信道容量增加：

$\Delta C = \log_2 \left( 1 + \frac{p^{(0)}_k + \delta}{\sigma^2_k}\right) - \log_2 \left(1 + \frac{p^{(0)}_k}{\sigma^2_k}\right) = \log_2 \left(1 + \frac{\delta}{p^{(0)}_k + \sigma^2_k}\right)\tag{2.1}$

不难发现应该将功率分配到 $p^{(0)}_k + \sigma^2_k$ 最小的信道中。如果每次选取的 $\delta$ 尽可能小，则将功率完全分配后，一部分信道的功率分配满足 $\sigma^2_k +p_k$ 为定值，对于另一部分较差的（噪声功率较大的）信道， $σ^2_k$ 大于该定值，则不分配功率，即：

$p_k = \max \{0, p^* - \sigma^2_k\}\tag{2.2}$

其中 $p^⋆$ 满足 $\sum^K_{k = 1}p_k = P$ 。

如果对于某一个分配方案若 $p_i + \sigma^2_i > p_j + \sigma^2_j$ ，我们置 $\delta = \min\{p_i, (p_i + \sigma^2_i - p_j - \sigma^2_j)/2\}$ ，对于状态 $p^{(0)}_i = p_i - \delta, p^{(0)}_j = p_j$ ，根据之前的推导，把 $\delta$ 分配到信道 $j$ 比分配给信道 $i$ 能获取更多的信道容量。重新分配后 $p_i + \sigma^2_i = p_j + \sigma^2_j$ 或 $p_i = 0$ （此时 $\sigma_i^2 \ge p_j + \sigma^2_j$ ）。

一个严谨的证明

我们重写 $(1.1)$ 为：

$\begin{aligned}&\min_{p_1, \dots, p_K} - \sum^K_{k = 1}\ln\left( 1 + \frac{p_k}{\sigma^2_k}\right)\\ \mathrm{s.t.}&\sum^K_{k = 1}p_k - P \le 0\\ &-p_k \le 0,\ \ \ k = 1, 2, \dots, K \end{aligned}\tag{3.1}$

$−\ln(·)$ 是一个凸（convex）函数，即目标函数是一个凸函数，同样的，也不难证明可行域 $(p_1, p_2, \dots, p_K)\in \mathcal{P}$ 是凸的。即该优化问题是一个凸优化问题，拉格朗日函数为：

$\begin{aligned} &\mathcal{L}(p_1, p_2, \dots, p_K; \lambda_0, \lambda_1, \dots, \lambda_K) \\ &= -\sum^K_{k = 1} \ln \left(1 + \frac{p_k}{\sigma^2_k}\right) + \lambda_0 \left( \sum^K_{k = 1} p_k - P \right) - \sum^K_{k = 1}\lambda_k p_k \end{aligned} \tag{3.2}$

其 KKT 条件为：

$\frac{\partial \mathcal{L}}{\partial p_k} = - \frac{1}{\sigma^2_k + p_k} + \lambda_0 - \lambda_k = 0, \ \ \ k = 1, 2, \dots, K \tag{3.3a}$

$\lambda_k \ge 0, \ \ \ k = 0, 1, 2, \dots, K\tag{3.3b}$

$\sum^K_{k = 1}p_k \le P\tag{3.3c}$

$\lambda_0 \left( \sum^K_{k = 1}p_k - P\right) = 0\tag{3.3d}$

$p_k \ge 0, \ \ \ k = 1, 2, \dots, K\tag{3.3e}$

$\lambda_k p_k = 0, \ \ \ k = 1, 2, \dots, K\tag{3.3f}$

式 $(3.3\mathrm{a})$ 可以重写为：

$\begin{aligned}\lambda_k = \lambda_0 - \frac{1}{\sigma^2_k + p_k} \\ p_k = \frac{1}{\lambda_0 - \lambda_k} - \sigma^2_k \end{aligned}\tag{3.4}$

如果 $\sum^K_{k=1} p_k < P$ ，则 $\lambda_0 = 0, \lambda_k = -1/(\sigma^2_k + p_k)<0$ ，与 $(3.3\mathrm{b})$ 矛盾。故 $\sum^K_{k = 1} p_k = P$ ，由 $p_k$ 非负性可知 $p_k$ 不全为零。

不妨假设 $\sigma^2_1 \le \sigma^2_2 \le \dots \le \sigma^2_K$ ，因为 $p_k$ 不可能全为零，对应的 $λ_k$ 为零，对于这些 $p_k > 0, λ_k = 0$ 的信道：

$p_k = \frac{1}{\lambda_0 - \lambda_k} - \sigma^2_k = \frac{1}{\lambda_0} - \sigma^2_k \tag{3.5}$

如果 $λ_k > 0$ ，则 $p_k = 0$ ，有：

$\lambda_k = \lambda_0 - \frac{1}{\sigma^2_k + p_k} = \lambda_0 - \frac{1}{\sigma^2_k} \tag{3.6}$

由于 $σ^2_k$ 单调递增，则有：

$\lambda_K \ge \lambda_{K-1} \ge \dots \ge \lambda_k > 0,\ \ \ p_K = p_{K-1} = \dots = p_k = 0 \tag{3.7}$

即上文所提到的，对于好的信道（ $λ_k = 0$ ），分配功率 $p_k$ 满足 $p_k +σ^2_k = 1/\lambda_0$ 为定值，对于差的信道（ $\lambda_k > 0$ ，应当注意的是 $(3.7)$ 指出，如果噪声功率为 $\sigma_k$ 的信道是差信道，则噪声功率更大的信道也是差信道），则不分配功率，直到功率分配尽为止。 $1 / \lambda_0$ 即上文的 $p^⋆$ 。

连续并联信道的注水定理

对于某一变换域（如频域上）的有色噪声 $σ^2 (f)$ ，注水问题的优化可以写作：

$\begin{aligned} &\min_{p(f)} - \int^{f_h}_{f_l}\log_2 \left( 1 + \frac{p(f)}{\sigma^2 (f)}\right) \mathrm{d}f\\ \mathrm{s.t.}&\int^{f_h}_{f_l}p(f)\mathrm{d}f\le P\\ &p(f)\ge 0, \ \ \ f_l \le f \le f_h \end{aligned}\tag{4.1}$

构造拉格朗日泛函：

$\begin{aligned}&\mathcal{L}[p(f),\lambda_0 ,\lambda_1 (f)] \\ = &-\int^{f_h}_{f_l} \ln \left( 1 + \frac{p(f)}{\sigma^2 (f)}\right) \mathrm{d}f + \lambda_0 \left( \int^{f_h}_{f_l} p(f)\mathrm{d}f\right) - \lambda_1 (f)p(f) \end{aligned}\tag{4.2}$

其 KKT 条件为：

$\delta \mathcal{L} = \int^{f_h}_{f_l}\left(\lambda_0 - \frac{1}{\sigma^2 (f) + p(f)}\right) \delta p(f)\mathrm{d}f - \lambda_1 (f)\delta p(f) = 0, \ \ \ \forall \delta p(f) \tag{4.3a}$

$\int^{f_h}_{f_l} p(f)\mathrm{d}f \le P \tag{4.3b}$

$\lambda_0 \ge 0,\lambda_1 (f)\ge 0, \ \ \ f_l\le f \le f_h \tag{4.3c}$

$\lambda_0 \left(\int^{f_h}_{f_l} p(f) \mathrm{d}f-P\right) = 0 \tag{4.3d}$

$p(f)\ge 0, \ \ \ f_l\le f \le f_h \tag{4.3e}$

$\lambda_1 (f)p(f) = 0, \ \ \ f_l\le f \le f_h \tag{4.3f}$

上式中 $\delta p(f)$ 是 $p(f)$ 的变分。

当 $\lambda_1 (f) > 0$ 时（类似于前文的“差信道”）， $p(f) ≡ 0$ ，进而有 $\delta p(f) = 0$ 。反之当 $p(f) > 0$ 时， $\lambda_1 (f) ≡ 0$ （类似于前文的“好信道”），此时 $p(f) = \frac{1}{\lambda} − σ^2 (f)$ 。综上：