Infomation and Entropy (4 ~ 5) Errors & Probablities
Abstract. 两章好像都没有什么深刻的内容，所以写一起。摘录一些有价值的内容。
Chapter 4. Error 讲了 error detection and correction。其中一个重点是 Hamming 码，一种很妙的朴素编码，可以纠正一位的错误。
Chapter 5. Probability 讲了一些基础的概率。
Errors
显然传输信息的时候会发生损失或者混入噪音，这是一个需要解决的问题。两个关键的步骤是错误的 Detection 和 Correction
Hamming Distance
Definition.(Hamming Distance) 对于两个等长的字符串 $S$ 和 $S’$，定义他们的 Hamming Distance 为
$$
\#\{S_i \ne S’_i\}
$$
错误的 effect 即为输入和输出的 Hamming Distance。
那么如果想要做 Detection，如果已知错误的 effect 最多为 $i$，就必须保证编码中两个有效编码之间的 Hamming Distance 要大于 $i$。
一个简单的例子如下。
Problem. 发送一个 $n$ 位的信息，但是传输过程中可能有一位被随机反转。想要传输之后还原出正确的信息，编码的长度至少是多少？
Solution.
首先用上面的性质得到长度必须满足的不等式。如果一个串长度为 $m$，那么有 $m$ 个串和它的 Hamming Distance 为 $1$，因此需要满足
$$
2^n \times m \leq 2^m
$$
在一般的范围内 $m / log m$ 是单调递增的。注意到一个显然的下界是
$$
m = n + \log_2 n + 1
$$
考虑构造一种方案到达这个下界。我们的编码由三部分组成。
第一部分为原来的长度为 $n$ 的字符串。
第二部分为 $\log_2 n$ 个 Parity Code。其中第 $i$ 个是原字符串中，下标二进制第 $i$ 位是 $1$ 的所有位的异或和。
第三部分为第二部分的 Parity Code，为第二部分所有位的异或和。
首先可以确认错误是否发生在第二、三部分。否则，通过第二部分出错的位置可以定位到第一部分出错的位置。
其实这个做法类似于 Hamming Code，只是 Hamming Code 的排列方式更高妙一点。这标志着我们能想到的东西的最近年代来到了 20 世纪（雾）。
Single Bits
为了 dectect 和 correct 一个位的错误我们采用的方法是反复发送。发送两次称为 double redundant，三次称为 triple redundant。
定义.(Code rate) 称一个编码的 code rate 为原始信息长度除以编码长度。
可以用 code rate 衡量一个编码的效率。
Multiple Bits
Parity
奇偶校验位。考虑将信息八位一组，后附八位的异或和。
Rectangular Code
将信息摆成 $2\times n$ 的矩形，然后对每行每列求 parity 并摆在对应的行列，再求 parity 的 parity 摆在右下角。
可以纠正一位错误和检验两位错误。
Hamming Code
第 $0$ 位是废位，$2^i$ 位是校验位，扣掉这些位置后，顺次在其他位置上填写有效信息。第 $i$ 个校验位存放所有二进制第 $i$ 位为 $1$ 的位置的异或和。
回忆我们在 Hamming Distance 中提出的编码的原理。这个编码的长度同样符合该节中的不等式给出的下界。纠错方法为将二进制第 $i$ 位为 $1$ 的所有位置的值异或起来，这就是错误位的二进制第 $i$ 位。
Block Code
称一个长度为 $n$，有效数据（除开 parity bit）的长度为 $k$，编码之间最小 Hamming Distance 为 $(n, k, d)$ Block Code。
Advanced Code
诸如 Bose-Chaudhuri-Hocquenhem (BCH) Codes 和 Reed-Solomon Codes 等。
这些编码都用了比前述朴素编码要高级一些的代数。一般会将信息看成 $\mathbb{F}_2[x]$ 中的多项式。
Probability
出现了很多术语，中英文对照一下。
Outcome. 结果。
Event. 事件，实验所有可能结果的一个子集。
Fundamental Event. 基本事件，即单个结果构成的事件。
Universal Event, Null Event 必然事件和不可能事件，对应全集和空集。
Mutal Exclusive, Exhaustive 互斥，完备。
将完备的事件分成若干个互斥的成分称为 Partition，如果每个成分都是 fundamental event 称为 Fundamental Partition。
定性地可以将 partition 分为 coarse-grained partition 和 fine-grained partition（粗/细粒度划分）两类。
接下来讲了一些东西诸如 Joint Event，Conditional Probability 等。其中 Bayes 公式比较有用，摘录如下
$$
P(A_i | M) = \frac{P(A_i)P(M|A_i)}{P(M)}
$$
Information
考虑如何衡量我们对一个事件的不确定度。下面是一个例子：
现有 $32$ 人，其中有 $2$ 女 $30$ 男，从中随机选出一个人，要表示这个人需要 $5$ 个 bit。
假设我们现在知道了这个人是女的，那么我们就只需要 $1$ bit 就能表示这个人，这里我们得到了 $4$ bit 的信息。类似地如果知道了这个人是男的，那么我们就只需要 $\log_2 30$ bit，得到了 $\log_2 \frac{32}{30}$ 的信息。
形式化地，给定了一个 partiton $A_1, A_2, …, A_n$，如果确定了结果属于 $A_i$，那么我们得到的信息量为
$$
\log_2(\sum |A_i|) - \log_2(|A_i|) = \log_2\left(\frac 1{P(A_i)}\right)
$$
若仅已知此划分而不知结果具体属于哪一个分事件，我们可以计算得到的信息量的期望为
$$
I = \sum_{i=1}^nP(A_i)\log_2\left(\frac{1}{P(A_i)}\right)
$$
假定划分中有两个事件，一个概率为 $p$，一个概率为 $1-p$，那么信息量为
$$
I = p\log(1/p) + (1-p)\log(1/(1-p))
$$
简单计算可以知道，当 $p$ 取 $0.5$ 时 $I$ 最大，达到了 $1$ bit。这告诉我们一个 01 串如果是等概率随机的，那么它的信息量最大（雾）
然而我们知道文本并不会是等概率在随机，所以说信息量可能不会很大，比如 $I < \log_2(n)$，这时候我们就有比定长编码更高效的编码，如 Huffman 编码（疑似可以做到平均长度 $I < E <I+1$，预计在下一章会有证明）