求离散信道容量的一般方法

1. $\mathbf{P}\beta =(\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}$
2. $C={\log }_2({1_{\mathbf{m}}}^T{2}^{\beta })$
3. ${\mathbf{p}}_{\mathbf{b}}=(2^{-C})\cdot 2^{\beta }$
4. ${\mathbf{p}}_{\mathbf{b}}={\mathbf{P}}^T{\mathbf{p}}_{\mathbf{a}}$

---

$$\sum _{j=1}^{m}p(b_j|a_i){\beta }_j=\sum _{j=1}^{m}p(b_j|a_i){\log }_{2}p(b_j|a_i)\to {\beta }_j\text{\hspace{1em}(1)}$$

上式对所有 $p(a_i)>0$ 的 $a_i$ 成立，可以列一个 n 元方程组解出所有 ${\beta }_j$

$$C={\log }_2(\sum _{j=1}^m{2}^{{\beta }_j})\to C\text{\hspace{1em}(2)}$$ $$p(b_j)=2^{{\beta }_j-C}\to p(b_j)\text{\hspace{1em}(3)}$$ $$p(b_j)=\sum _{i=1}^{n}p(a_i)p(b_j|a_i)\to p(a_u)\text{\hspace{1em}(4)}$$

需要确认所有的 $p(a_i)$ 大于等于 0，所求的 C 才存在。

---

核心目标：最大化平均互信息

信道容量的定义是：

$$C=\underset{p(a_i)}{\max }I(X;Y)$$

其中，$X$ 是信道输入，$Y$ 是信道输出，$p(a_i)$ 是输入符号 $a_i$ 的概率分布。 平均互信息 $I(X;Y)$ 可以表示为：

$$I(X;Y)=H(Y)-H(Y|X)=-\sum _{j}p(b_j)\log p(b_j)+\sum _{i}p(a_i)\sum _{j}p(b_j|a_i)\log p(b_j|a_i)$$

这里，$p(b_j)$ 是输出符号 $b_j$ 的概率，$p(b_j|a_i)$ 是信道转移概率（即输入 $a_i$ 时输出 $b_j$ 的概率）。 同时，输入概率分布需要满足约束条件：${\sum }_{i=1}^{n}p(a_i)=1$。

---

1. 构造拉格朗日函数

为了解决这个约束优化问题，我们使用 拉格朗日乘数法，引入拉格朗日乘子 $\lambda$，构造拉格朗日函数 $\varphi$：

$$\varphi =I(X;Y)-\lambda \left(\sum _{i=1}^{n}p(a_i)-1\right)$$

将 $I(X;Y)$ 的表达式代入：

$$\varphi =\left[-\sum _{j=1}^{m}p(b_j)\log p(b_j)+\sum _{k=1}^{n}p(a_k)\sum _{j=1}^{m}p(b_j|a_k)\log p(b_j|a_k)\right]-\lambda \left(\sum _{k=1}^{n}p(a_k)-1\right)$$

注意，为了求导方便，这里将求和的索引 $i$ 换成了 $k$。 我们的目标是求 $\frac{\partial \varphi }{\partial p(a_i)}=0$。

---

2. 求偏导并化简

对 $\varphi$ 关于 $p(a_i)$ 求偏导。这里需要用到几个关系：

• $p(b_j)={\sum }_{k=1}^{n}p(a_k)p(b_j|a_k)$，所以 $\frac{\partial p(b_j)}{\partial p(a_i)}=p(b_j|a_i)$。
• $\frac{d}{dx}(\log x)=\frac{1}{x}\log e$ (如果 $\log$ 不是自然对数 $\ln$；如果 $\log$ 是 $\ln$，则 $\log e=1$)。图片中明确指出 $\log x=\ln x\log e$，这说明推导中的 $\log$ 是某个底数的对数，求导时会产生一个 ${\log }_{\text{base}}e$ 的因子。

求导结果：

$$\frac{\partial \varphi }{\partial p(a_i)}=-\left\{\sum _j[p(b_j|a_i)\log p(b_j)+p(b_j|a_i)\log e]\right\}+\sum _{j}p(b_j|a_i)\log p(b_j|a_i)-\lambda =0$$

整理一下：

$$\sum _{j}p(b_j|a_i)\log p(b_j|a_i)-\sum _{j}p(b_j|a_i)\log p(b_j)-\sum _{j}p(b_j|a_i)\log e-\lambda =0$$

利用 ${\sum }_{j=1}^{m}p(b_j|a_i)=1$ (给定输入 $a_i$，所有输出的概率之和为 1)，上式可以化简为：

$$\sum _{j}p(b_j|a_i)\log \frac{p(b_j|a_i)}{p(b_j)}-\log e-\lambda =0$$

移项得到 (4.2.16)：

$$\sum _{j=1}^{m}p(b_j|a_i)\log p(b_j|a_i)-\sum _{j=1}^{m}p(b_j|a_i)\log p(b_j)=\log e+\lambda$$

这个等式的左边其实就是特定输入 $a_i$ 对平均互信息的贡献，记作 $I(a_i;Y)$。这意味着，对于最优的输入分布，所有被使用的输入 $a_i$ (即 $p(a_i)>0$)，其 $I(a_i;Y)$ 的值都应该是一个常数，即 $\log e+\lambda$。

---

3. 引入信道容量 $C$

将 (4.2.16) 两边乘以 $p(a_i)$ 并对 $i$ 求和：

$$\sum _{i}p(a_i)\left[\sum _{j}p(b_j|a_i)\log p(b_j|a_i)-\sum _{j}p(b_j|a_i)\log p(b_j)\right]=\sum _{i}p(a_i)(\log e+\lambda )$$

左边就是平均互信息 $I(X;Y)$。右边因为 $\sum p(a_i)=1$，所以等于 $\log e+\lambda$。 因此，$I(X;Y)=\log e+\lambda$。 由于信道容量 $C$ 是 $I(X;Y)$ 的最大值，所以当达到最大值时，我们有 (4.2.17)：

$$C=\log e+\lambda$$

通常在信息论中，对数的底取 2，单位是比特。所以这里明确写出 $C={\log }_{2}e+\lambda$。这意味着前面推导中的 $\log$ 如果是 ${\log }_2$，那么 $\log e$ 就是 ${\log }_{2}e$。

将 $C$ 代回到 (4.2.16)（并将对数底统一为 2）：

$$\sum _{j}p(b_j|a_i){\log }_{2}p(b_j|a_i)-\sum _{j}p(b_j|a_i){\log }_{2}p(b_j)=C$$

为了简化，引入变量 ${\beta }_j$ (如 (4.2.18) 所示)：

$${\beta }_j={\log }_{2}p(b_j)+C$$

于是上式可以写成 (4.2.19)：

$$\sum _{j=1}^{m}p(b_j|a_i){\log }_{2}p(b_j|a_i)=\sum _{j=1}^{m}p(b_j|a_i){\beta }_j$$

这个条件对于所有使得 $p(a_i)>0$ 的输入 $a_i$ 都必须成立。

---

4. 求解输出概率 $p(b_j)$ 和 $C$

由 (4.2.18) ${\beta }_j={\log }_{2}p(b_j)+C$，可以反解出 $p(b_j)$：

$${\log }_{2}p(b_j)={\beta }_j-C⟹p(b_j)=2^{{\beta }_j-C}$$

利用概率之和为 1 的约束条件 ${\sum }_{j=1}^{m}p(b_j)=1$：

$$\sum _{j=1}^m{2}^{{\beta }_j-C}=1$$ $$2^{-C}\sum _{j=1}^m{2}^{{\beta }_j}=1$$

所以，$2^C={\sum }_{j=1}^m{2}^{{\beta }_j}$。两边取 ${\log }_2$，得到 $C$ 的表达式（图中橙色框）：

$$C={\log }_2\sum _{j=1}^m{2}^{{\beta }_j}$$

最后提到 ” 由 $p(b_j)={\sum }_{i=1}^{n}p(a_i)p(b_j|a_i)$ 求出 $p(a_i)$“。这通常不是直接求解，而是指这些方程组是寻找最优 $p(a_i)$ 的充要条件，实际求解往往需要迭代算法（如 Arimoto-Blahut 算法）。当找到的 $p(a_i)$ 满足概率约束且使上述所有条件成立时，$C$ 就是正确的信道容量。

---

5. 总结 $C$ 的求法

这张图总结了在最优条件下，各个量之间应该满足的关系，也暗示了一个迭代求解的思路：

1. 由 ${\sum }_{j}p(b_j|a_i)\log p(b_j|a_i)={\sum }_{j}p(b_j|a_i){\beta }_j$ 求 ${\beta }_j$： 这个等式 (4.2.19) 应该对所有 $p(a_i)>0$ 的 $a_i$ 成立。等式左边 ${\sum }_{j}p(b_j|a_i)\log p(b_j|a_i)$ 对于给定的信道是一个只依赖于 $a_i$ 的常数。这一步表明 ${\beta }_j$ 的取值要满足这个条件。

2. 由 $C={\log }_2{\sum }_{j=1}^m{2}^{{\beta }_j}$ 求 $C$： 一旦确定了 ${\beta }_j$ (或者在迭代中的当前估计值)，就可以用这个公式计算信道容量 $C$。

3. 由 $p(b_j)=2^{{\beta }_j-C}$ 求 $p(b_j)$： 知道了 ${\beta }_j$ 和 $C$，就可以得到对应的输出概率分布 $p(b_j)$。

4. 由 ${\sum }_{j}p(b_j|a_i)\log p(b_j|a_i)={\sum }_{j}p(b_j|a_i){\beta }_j$ (应为 $p(b_j)={\sum }_{i}p(a_i)p(b_j|a_i)$) 求出 $p(a_i)$，并验证： 这里有点小笔误，图中的公式重复了步骤 1 的。正确的应该是，找到一个输入分布 $p(a_i)$，它能产生步骤 3 得到的 $p(b_j)$ (即满足 $p(b_j)={\sum }_{i}p(a_i)p(b_j|a_i)$)，并且这个 $p(a_i)$ 只在那些满足步骤 1 条件的 $a_i$ 上取非零值。然后验证整个解是否自洽。

整体思路： 整个推导过程是通过拉格朗日乘子法，从最大化互信息的目标出发，推导出最优输入输出概率分布以及信道容量必须满足的一系列条件。实际计算信道容量时，往往采用迭代算法 (如 Arimoto-Blahut 算法)，不断迭代更新 $p(a_i)$ 和 $p(b_j)$ (或相关的量如 ${\beta }_j,C$)，直到这些条件近似满足，从而得到信道容量的数值解。这些图片为你展示了这些迭代算法所依据的数学原理和最优解的特性。

---

可以将图片中描述的求解信道容量 $C$ 的核心方程组用矩阵和向量的形式表示出来，这样可能更清晰和便于记忆。

首先，我们定义相关的向量和矩阵：

• ${\mathbf{p}}_{\mathbf{a}}$: 输入概率分布列向量，维度为 $n\times 1$。

$${\mathbf{p}}_{\mathbf{a}}=\left(\begin{array}{c}p(a_1)\\ p(a_2)\\ ⋮\\ p(a_n)\end{array}\right)$$

• ${\mathbf{p}}_{\mathbf{b}}$: 输出概率分布列向量，维度为 $m\times 1$。

$${\mathbf{p}}_{\mathbf{b}}=\left(\begin{array}{c}p(b_1)\\ p(b_2)\\ ⋮\\ p(b_m)\end{array}\right)$$

• $\mathbf{P}$: 信道转移概率矩阵，维度为 $n\times m$。矩阵的第 $i$ 行第 $k$ 列元素 $P_{ik}=p(b_k|a_i)$ 表示输入为 $a_i$ 时，输出为 $b_k$ 的概率。

$$\mathbf{P}=\left(\begin{array}{cccc}p(b_1|a_1)& p(b_2|a_1)& \cdots & p(b_m|a_1)\\ p(b_1|a_2)& p(b_2|a_2)& \cdots & p(b_m|a_2)\\ ⋮& ⋮& \ddots & ⋮\\ p(b_1|a_n)& p(b_2|a_n)& \cdots & p(b_m|a_n)\end{array}\right)$$

• $\beta$: 一个辅助列向量，维度为 $m\times 1$。

$$\beta =\left(\begin{array}{c}{\beta }_1\\ {\beta }_2\\ ⋮\\ {\beta }_m\end{array}\right)$$

• $C$: 信道容量，是一个标量。
• $1_{\mathbf{k}}$: 元素全为 1 的 $k\times 1$ 列向量。
• ${\log }_2(\cdot )$ 和 $2^{(\cdot )}$: 表示对矩阵或向量中的每个元素进行操作。
• $\mathbf{A}\odot \mathbf{B}$: 表示 Hadamard 积（element-wise product），即矩阵（或向量）$\mathbf{A}$ 和 $\mathbf{B}$ 的对应元素相乘。

我们可以将其改写为矩阵形式：

1. 第一个公式: ${\sum }_{j=1}^{m}p(b_j|a_i){\beta }_j={\sum }_{j=1}^{m}p(b_j|a_i){\log }_{2}p(b_j|a_i)$ 这个公式的左边是矩阵 $\mathbf{P}$ 的第 $i$ 行与向量 $\beta$ 的点积。右边是矩阵 $\mathbf{P}$ 的第 $i$ 行与该行元素取 ${\log }_2$ 后的点积。 我们可以定义一个 $n\times 1$ 的列向量 ${\mathbf{k}}_{\mathbf{P}}$，其第 $i$ 个元素为 $k_{P,i}={\sum }_{j=1}^{m}p(b_j|a_i){\log }_{2}p(b_j|a_i)$。 这个向量可以表示为：${\mathbf{k}}_{\mathbf{P}}=(\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}$。 于是，第一个公式可以表示为：

$$\mathbf{P}\beta =(\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}(1^{\prime })$$

需要注意的是，这个等式仅对那些使得 $p(a_i) > 0$ 的输入 $a_i$ （即第 $i$ 行）成立。

2. 第二个公式: $C={\log }_2({\sum }_{j=1}^m{2}^{{\beta }_j})$ 这可以表示为：

$$C={\log }_2({1_{\mathbf{m}}}^T{2}^{\beta })(2^{\prime })$$

其中 $2^{\mathbf{\beta}}$ 是对向量 $\mathbf{\beta}$ 的每个元素取 $2$ 的幂次。$\mathbf{1_m}^T 2^{\mathbf{\beta}}$ 计算了 $2^{\beta_j}$ 的总和。

3. 第三个公式: $p(b_j)=2^{{\beta }_j-C}$ 这可以表示为元素级的运算：

$${\mathbf{p}}_{\mathbf{b}}=2^{\beta -C{1}_{\mathbf{m}}}$$

或者可以写作：

$${\mathbf{p}}_{\mathbf{b}}=(2^{-C})\cdot 2^{\beta }(3^{\prime })$$

4. 第四个公式: $p(b_j)={\sum }_{i=1}^{n}p(a_i)p(b_j|a_i)$ 这表示输出概率是输入概率通过信道转移的加权和。 $p(b_j)={\sum }_{i=1}^n({\mathbf{p}}_{\mathbf{a}}{)}_i{P}_{ij}$。 这正是矩阵乘法 ${{\mathbf{p}}_{\mathbf{a}}}^T\mathbf{P}$ 的第 $j$ 个元素（如果 ${\mathbf{p}}_{\mathbf{a}}$ 是列向量）。 更常见的写法是：

$${\mathbf{p}}_{\mathbf{b}}={\mathbf{P}}^T{\mathbf{p}}_{\mathbf{a}}(4^{\prime })$$

这里 $\mathbf{P}^T$ 是矩阵 $\mathbf{P}$ 的转置，维度为 $m \times n$。 $\mathbf{P}^T \mathbf{p_a}$ 的结果是一个 $m \times 1$ 的列向量，与 $\mathbf{p_b}$ 维度一致。

总结一下矩阵形式的方程组：

1. $\mathbf{P}\beta =(\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}$ (此条件对 $p(a_i)>0$ 的 $i$ 成立)
2. $C={\log }_2({1_{\mathbf{m}}}^T{2}^{\beta })$
3. ${\mathbf{p}}_{\mathbf{b}}=(2^{-C})\cdot 2^{\beta }$
4. ${\mathbf{p}}_{\mathbf{b}}={\mathbf{P}}^T{\mathbf{p}}_{\mathbf{a}}$

这些方程描述了当信道达到容量 $C$ 时，最优的 ${\mathbf{p}}_{\mathbf{a}}$、${\mathbf{p}}_{\mathbf{b}}$ 和辅助量 $\beta$ 之间必须满足的关系。图片中箭头指示的“求解过程”暗示了这些变量之间的依赖关系，实际求解通常依赖迭代算法 (如 Arimoto-Blahut 算法) 来找到满足这些条件的解。