Coding Theory 编码理论

基础

考虑一个binary symmetric channel，其中每一位传输错误的概率为$p$。记$q := 1-p$。

假设$C$是一个长度为$n$,包含$M$个词（$x_1,…,x_M$）的code。设$P_i$为$x_i$被错误解码的概率，

$P_C := \frac{1}{M}\sum^M_{i=1}P_i$

以及

$P^*(M,n,p) := \underset{\text{all possible codes }C}{\text{min}} P_C$

Definition:

The channel capacity $C(p)$ of a binary symmetric channel is defined as:

$\begin{align*}C(p) &:= 1 + p \, \text{log}_2(p)+ q \,\text{log}_2(p) \\&=1 + p \, \text{log}_2(p)+ (1-p) \, \text{log}_2(1-p)\end{align*}$

Theorem (Shannon’s Theorem 香农定理):

Let$C(p)$ be the channel capacity. If $0 < R < C(p)$ and $M_n := 2^{\lfloor Rn \rfloor}$, then

$\underset{n \to \infty}{\text{lim}}P^*(M_n,n,p) = 0.$

首先R其实表示的是目前编码的传输效率，因为当传输n位的信息时，其中只有$\text{log}_2(M)$位是真的有效信息。

所以可以这样理解Shannon’s Theorem 香农定理：

对于每个频道（Channel）来说，$C(p)$是其传输效率（R）的上限。

注意到，当$p=0.5$时，$C(p) = 1 + \text{log}_2(0.5) = 1-1 = 0$ 。也就是说，当传输时每一位的准确率都是纯随机的时候，不存在任何编码使得我们可以正确地传输数据。