准对称离散信道（输入对称信道）

$$\mathbf{q}=\frac{1}{n}{\mathbf{P}}^T{1}_{\mathbf{n}}$$ $$C=-{\mathbf{q}}^T({\log }_2\mathbf{q})+((\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}{)}_1$$

这里 $((\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}{)}_1$ 表示向量 $(\mathbf{P}\odot {\log }_2\mathbf{P})1_{\mathbf{m}}$ 的第一个元素

---

若信道矩阵的行是可排列的，但是列不可排列，如

$$\left[\begin{array}{cccc}\frac{1}{2}& \frac{1}{4}& \frac{1}{8}& \frac{1}{8}\\ \frac{1}{4}& \frac{1}{2}& \frac{1}{8}& \frac{1}{8}\end{array}\right]$$

此时最优输入分布是均匀分布

推导

条件熵 $H(Y\mid X=a_i)$ 对于所有输入 $a_i$ 都相等，所以总条件熵与输入分布无关

$$H(Y\mid X)=H_{mi}$$

此时只需要最大化 $H(Y)$

$$H(Y)=-\sum _{j=1}^{M}p(y_j){\log }_{2}p(y_j)$$

但是由于 $\mathbf{P}$ 中各列不具有可排列性，要使 $p(b_j)=\frac{1}{m}$ ，则可能使输入概率分布的某项概率出现负值，这是办不到的。为了在 $p(a_i)$ 非负的情况下使其最大，可将 $H(Y)$ 中的 $m$ 项分成 $s$ 个子集 $M_1,M_2,\dots$ 每个子集分别有 $m_1,m_2,\dots ,m_s$ 个元素，则

$$H_s(Y)=-\sum _{p(b_j)\in M_1}p(b_j){\log }_{2}p(b_j)\cdots -\sum _{p(b_j)\in M_s}p(b_j){\log }_{2}p(b_j)$$

令第 $k$ 个集合中概率的平均值

$$\bar{p}(b_k)=\frac{{\sum }_{p(b_j)\in M_k}p(b_j)}{m_k}$$

因为 $\bar{p}(b_k)/p(b_j)>0$ ，这里采用放缩 $\ln x\le x-1$

$$\sum _{p(b_j)\in M_k}p(b_j)\ln \frac{\bar{p}(b_k)}{p(b_j)}\le \sum _{p(b_j)\in M_k}p(b_j)\left[\frac{\bar{p}(b_k)}{p(b_j)}-1\right]=\bar{p}(b_k)m_k-\sum _{j\in M_k}p(b_j)=0$$

所以有

$$\sum _{p(b_j)\in M_k}p(b_j){\log }_2\bar{p}(b_k)\le \sum _{p(b_j)\in M_k}p(b_j){\log }_{2}p(b_j)$$

两边加上负号

$$-\sum _{p(b_j)\in M_k}p(b_j){\log }_2\bar{p}(b_k)\ge -\sum _{p(b_j)\in M_k}p(b_j){\log }_{2}p(b_j)$$

所以把子集 $M_k$ 中的 $p(b_j)$ 变成其均值 $\bar{p}(b_k)$ ，将使第 $k$ 个子集中的熵达到最大。因为子矩阵具有可排列性，只要信源 X 呈等概率分布，即可使第 k 个子集中的输出概率相等，即达到其均值。而且每一项都达到最大值，则输出的熵也达到最大

$$H(Y)\le H_s(Y)=-\sum _{k=1}^s{m}_k\bar{p}(b_k){\log }_2\bar{p}(b_k)$$

我怎么感觉怪怪的？这里好像没有考虑到子集之间的关系，就直接默认他们相等了

---

1. 最优输入分布是均匀分布，即 $p(a_i)=1/n$ 对所有 $i$ 成立。

\mathbf{p_a}^* = \frac{1}{n} \mathbf{1_n}

2. 条件熵 $H(Y|X=a_i)$ 对所有输入 $a_i$ 都是相同的。我们称这个值为 $H_0$。 $H_0 = H(Y|X=a_1) = -\sum_{k=1}^m p(b_k|a_1) \log_2 p(b_k|a_1)$。 用矩阵表示（取第一行计算 $H_0$）：

H_0 = - ((\mathbf{P} \odot \log_2 \mathbf{P}) \mathbf{1_m})_1

这里 $((\mathbf{P} \odot \log_2 \mathbf{P}) \mathbf{1_m})_1$ 表示向量 $(\mathbf{P} \odot \log_2 \mathbf{P}) \mathbf{1_m}$ 的第一个元素。 2. 当输入为均匀分布时，输出概率分布 $\mathbf{q} = (q_j)$ 为：

\mathbf{q} = \frac{1}{n} \mathbf{P}^T \mathbf{1_n}

4. 此时的输出熵 $H(Y)_{\text{unif\_in}}$ 为：

H(Y)_{\text{unif_in}} = - \mathbf{q}^T (\log_2 \mathbf{q}) = - \left(\frac{1}{n} \mathbf{P}^T \mathbf{1_n}\right)^T \log_2\left(\frac{1}{n} \mathbf{P}^T \mathbf{1_n}\right)

5. 信道容量 $C = H(Y)_{\text{unif\_in}} - H_0$。

C = - \left(\frac{1}{n} \mathbf{P}^T \mathbf{1_n}\right)^T \log_2\left(\frac{1}{n} \mathbf{P}^T \mathbf{1_n}\right) - \left( - ((\mathbf{P} \odot \log_2 \mathbf{P}) \mathbf{1_m})_1 \right)

C = - \left(\frac{1}{n} \mathbf{P}^T \mathbf{1_n}\right)^T \log_2\left(\frac{1}{n} \mathbf{P}^T \mathbf{1_n}\right) + ((\mathbf{P} \odot \log_2 \mathbf{P}) \mathbf{1_m})_1