Information and Entropy (7) Processes

Abstract. 在上一节的基础上继续讨论一些通信过程的性质。

• Information, Loss and Noise

我们讨论的处理过程具有如下特点：

• Discrete. 输入是一组互斥事件集，每时每刻只会有一个发生，输出是另一个互斥事件集。
• Finite. 上述两个事件集均为有限集。
• Memoryless. 当前输出只取决于当前输入，和之前的输入没有关系。
• Nondeterministic. 对于相同的输入可能输出不同的结果（“噪声”）。
• Lossy. 从输出中无法反推输入。

大概是总结了之前的 Communication System 的特点。

下面几节感觉很平凡，均为常识内容，我们直接跳到第三节。

Information, Loss and Noise

和上一节相同，我们定义输入的信息量为

$$\begin{array}{}\text{(1)}& I=\sum p(A_i)\log \left(\frac{1}{p(A_i)}\right)\end{array}$$

输出的信息量为

$$\begin{array}{}\text{(2)}& J=\sum p(B_i)\log \left(\frac{1}{p(B_i)}\right)\end{array}$$

然后上一节还记述了对输入的不确定度的期望

$$\begin{array}{}\text{(3)}& L=\sum _j\sum _{i}p(A_i,B_j)\log \left(\frac{1}{p(A_i|B_j)}\right)\end{array}$$

这个值称为 loss，相应的，对输出的不确定度

$$\begin{array}{}\text{(4)}& N=\sum _j\sum _{i}p(A_i,B_j)\log \left(\frac{1}{p(B_j|A_i)}\right)\end{array}$$

称为 noise。

假设 $W$ 是输出端可以识别到输入端变化的最大速率，那么

$$\begin{array}{}\text{(5)}& C=W{M}_{max}\end{array}$$

称为这个过程的 capacity。

上一节我们已经推导过了

$$\begin{array}{}\text{(6)}& M=I-L=J-N\end{array}$$

因此有

$$\begin{array}{}\text{(7)}& J=I-L+N\end{array}$$

或者简明地用下面的这个图来表示这个 discrete memoryless process 中的信息流动

原论文中的记号 在 Shannon 的原论文中记号和这里不太一样，简单记录一下：

• 输入的概率分布称为 $x$，输出的概率分布称为 $y$。
• $H(x)\leftarrow I,H(y)\leftarrow J,H_y(x)\leftarrow L,H_x(y)\leftarrow N,R\leftarrow M$。

Example. 回忆我们在第 4 节中提到的 Hamming Code，在推导纠错码长度下界的过程中我们利用码距得到了

$$\begin{array}{}\text{(8)}& 2^n\times m\le 2^m\end{array}$$

接下来我们从信息熵的角度推导这个下界。

要求总是能够检查错误，也就是 $L=0$，即

$$\begin{array}{}\text{(9)}& I+N=J\end{array}$$

这里的输入信息量只能是原来的 $01$ 串的信息量，即 $n$，而 noise 只可能是反转 $m$ 个位置之一，也就是噪声的熵为 $N={\log }_{2}m$。输出是一个长度为 $m$ 的串，但是信息熵未必是 $m$，因为显然这里 $2^m$ 种情况不是都能取到的。

于是有

$$\begin{array}{}\text{(10)}& I+N=n+{\log }_{2}m=J\le m\Rightarrow n+{\log }_{2}m\le m\end{array}$$

即上述不等式取对数的形式。

---

可能这个项目就到这里为止了。后面全是统计力学，量子力学之类的东西，不想看了。