第七节、等长编码
约 484 个字 预计阅读时间 2 分钟
一、等长编码
设某种信息 ~~（可能是外星人的某种语言）~~ 的字符表是\(\mathcal{A}=\{a_1,a_2,\cdots,a_K\}\)， 其概率分布为\(\{p_1,p_2,\cdots,p_k\}\), 那么输出长度为\(L\)的消息序列\(\mathbf{u}^L={u_1,u_2,\cdots,u_K}\), 这样的序列一共有\(K^L\)个。
编码时：
编码字符表：\(\mathcal{B}=\{b_1,b_2,\dots,b_D\}\) 编码长度：\(N\) 无损编码：\(D^N \geq K^L \Rightarrow N \geq \frac{L \log K}{\log D}\) (两边取对数就有)
我们先考虑等长编码。进行整数编码：
- 若有\(\mathcal A=\{0,1,\dots,9\}, L=1\), 而编码字符表 \(\mathcal B=\{0,1\}\) （用二进制编码）, 则\(N\geq \log 10, N \geq 4\), 4bit
- 若\(\mathcal A = \{0,1,\dots,9\} , L=2\) , 或\(\mathcal A = \{0,1,\dots, 99\}, L=1\), 则\(N \geq \log 100, N=7\), 每个字符要 3.5 bit
- \(\mathcal A = \{0,1,\dots,9\} , L=\infty\), 则\(N_0=\frac{N}{L}\leq \log 10 = 3.322\)
因此，理论上，信源输出序列越长，编码效率越高，接近\(\log K\)。而实际上，\(L\ \text{无法} \rightarrow \infty\) , 因为编码序列越长，译码时延也越长。
二、香农编码定理
问题：
我们刚刚知道了，码字长度 \(N \geq \frac{L \log K}{\log D}\), 而又有 \(H(U) \leq \log K\)
那么是否有可能不等号能够取等，即\(N=\frac{LH(U)}{\log D}\)?
1. 定理
典型列：
考虑抛硬币，50次正面，50次反面。序列发生的概率是\(C_{100}^{50} (\frac{1}{2})^{50} (\frac{1}{2})^{50}\) 这样的序列的出现概率都是\((\frac{1}{2})^{50} (\frac{1}{2})^{50}\), 有\(C_{100}^{50}\)种。
当\(L \rightarrow \infty\), 输出非典型列的可能性趋于零。（抛硬币时，抛无穷多次的时候，只有\(\epsilon\)的概率出现例如 0.4 正面/ 0.6 反面的非典型列。）
以0.4正面，0.6反面的一个抛硬币事件为例。
理论的精髓： \(L \rightarrow \infty\)， 才出现典型列和无穷等分性质