# 通信路通信路不断地传输信息 0 , 1 0,1 0 , 1
假设一个通信路中，
顺利接受信号 0 0 0 p 0 p_0 p 0
顺利接受信号 1 1 1 p 1 p_1 p 1
我们可以考虑这样一个简单的方法：将一个信号重复发送三次，并定义
对方收到两个或者三个 0 0 0 0 0 0
对方收到两个或者三个 1 1 1 1 1 1
这样一来，考虑发送 0 0 0
三个都是 0 0 0 p 0 3 p_0^3 p 0 3
两个是 0 0 0 1 1 1 3 p 0 2 ( 1 − p 0 ) 3p_0^2 (1-p_0) 3 p 0 2 ( 1 − p 0 )
那么，整体来说成功的概率为 p 0 3 + 3 p 0 2 ( 1 − p 0 ) p_0^3 + 3p_0^2 (1-p_0) p 0 3 + 3 p 0 2 ( 1 − p 0 ) 1 1 1 p 1 3 + 3 p 1 2 ( 1 − p 1 ) p_1^3 + 3p_1^2 (1-p_1) p 1 3 + 3 p 1 2 ( 1 − p 1 ) 0 0 0 p 0 p_0 p 0 0.9 0.9 0 . 9 0 0 0 0.972 0.972 0 . 9 7 2
然而，重复太多次会导致信息的无用部分过多，一个很长的信息串中包含较少真正信息n n n
除了上述的重复，我们还可以想一些别的方法来提升通信效率编码 ，而对方收到信息进行处理的过程称为解码
001 ↦ 001001 , 101 ↦ 101101 , ⋯ 001 \mapsto 001001,\quad
101 \mapsto 101101,\quad
\cdots 0 0 1 ↦ 0 0 1 0 0 1 , 1 0 1 ↦ 1 0 1 1 0 1 , ⋯
这样一来传输 0 0 0
p 0 ′ = p 0 4 + 4 p 0 5 − 4 p 0 6 p_0' = p_0^4 + 4p_0^5 - 4p_0^6
p 0 ′ = p 0 4 + 4 p 0 5 − 4 p 0 6
一般地，给定文字全体的集合 Q Q Q q q q V : = Q n V := Q^n V : = Q n V V V Q Q Q n n n C ⊆ V C \subseteq V C ⊆ V n n n
e f f ( C ) : = log q ∣ C ∣ n \mathrm{eff}(C) := \frac{\log_q |C|}{n}
e f f ( C ) : = n log q ∣ C ∣
我们想要考察，当接收到某个信息时（V V V C C C f : C → V f: C \to V f : C → V
令 Hamming 距离 d H d_H d H
d H ( a , f ( a ) ) = min b ∈ C d H ( a , b ) d_H(\boldsymbol a, f(\boldsymbol a)) = \min_{\boldsymbol b \in C} d_H(\boldsymbol a, \boldsymbol b)
d H ( a , f ( a ) ) = b ∈ C min d H ( a , b )
称
d ( C ) : = min a , b ∈ C , a ≠ b d H ( a , b ) d(C) := \min_{\boldsymbol a, \boldsymbol b \in C, \boldsymbol a \neq \boldsymbol b} d_H(\boldsymbol a, \boldsymbol b)
d ( C ) : = a , b ∈ C , a = b min d H ( a , b )
为编码 C C C
若一个 n n n t t t 2 t + 1 2t + 1 2 t + 1 2 t + 1 2t + 1 2 t + 1 t t t
# Shannon 定理给出 t t t e 1 , e 2 , ⋯ , e t e_1, e_2, \cdots, e_t e 1 , e 2 , ⋯ , e t p i p_i p i 熵 (Entropy)「不確実度」
H ( p 1 , p 2 , ⋯ , p t ) : = − ∑ i = 1 t p i log 2 p i H(p_1, p_2, \cdots, p_t) := -\sum_{i=1}^t p_i \log_2 p_i
H ( p 1 , p 2 , ⋯ , p t ) : = − i = 1 ∑ t p i log 2 p i
熵（实际上此处也可以说是信息熵）反映了事件发生的平均不确定度，或者说平均信息量e 1 e_1 e 1 e 2 e_2 e 2 0.5 0.5 0 . 5 H ( 0.5 , 0.5 ) = 1 H(0.5, 0.5) = 1 H ( 0 . 5 , 0 . 5 ) = 1 1 1 1 e 1 e_1 e 1 e 2 e_2 e 2 0.9 0.9 0 . 9 0.1 0.1 0 . 1 H ( 0.9 , 0.1 ) ≈ 0.469 H(0.9, 0.1) \approx 0.469 H ( 0 . 9 , 0 . 1 ) ≈ 0 . 4 6 9 0.469 0.469 0 . 4 6 9
现在假设这样一个信道：我们有 r r r a 1 , a 2 , ⋯ , a r a_1, a_2, \cdots, a_r a 1 , a 2 , ⋯ , a r s s s b 1 , b 2 , ⋯ , b s b_1, b_2, \cdots, b_s b 1 , b 2 , ⋯ , b s a i a_i a i x i x_i x i a i a_i a i b j b_j b j
如果接收端知道 x i x_i x i
E = − ∑ i = 1 r x i log 2 x i E = -\sum_{i=1}^r x_i \log_2 x_i
E = − i = 1 ∑ r x i log 2 x i
根据 Bayes 定理，当接收端收到信号 b j b_j b j a i a_i a i
P ( a i ∣ b j ) = x i p i j ∑ k = 1 r x k p k j P(a_i \mid b_j) = \frac{x_i p_{ij}}{\sum_{k=1}^r x_k p_{kj}}
P ( a i ∣ b j ) = ∑ k = 1 r x k p k j x i p i j
因此，在接收到信号 b j b_j b j x i = P ( a i ∣ b j ) x_i = P(a_i \mid b_j) x i = P ( a i ∣ b j )
E After = − ∑ i = 1 r x i p i j ∑ k = 1 r x k p k j log 2 x i p i j ∑ k = 1 r x k p k j E_{\text{After}} = -\sum_{i=1}^r \frac{x_i p_{ij}}{\sum_{k=1}^r x_k p_{kj}} \log_2 \frac{x_i p_{ij}}{\sum_{k=1}^r x_k p_{kj}}
E After = − i = 1 ∑ r ∑ k = 1 r x k p k j x i p i j log 2 ∑ k = 1 r x k p k j x i p i j
这样一来，接收到一个信号时，熵的期望值为
E After = ∑ j = 1 s ( ( − ∑ i = 1 r x i p i j ∑ k = 1 r x k p k j log 2 x i p i j ∑ k = 1 r x k p k j ) ⏟ Conditional entropy given b j ⋅ ∑ k = 1 r x k p k j ⏟ Probability of receiving b j ) = − ∑ j = 1 s ∑ i = 1 r x i p i j ( log 2 x i + log 2 p i j − log 2 ( ∑ i = 1 r x i p i j ) ) = ∑ j = 1 s ( ∑ i = 1 r x i p i j ) log 2 ( ∑ i = 1 r x i p i j ) − ∑ i = 1 r x i log 2 x i − ∑ j = 1 s ∑ i = 1 r x i p i j log 2 p i j \begin{aligned}
E_{\text{After}} &= \sum_{j=1}^s \left(
\underbrace{(-\sum_{i=1}^r \frac{x_i p_{ij}}{\sum_{k=1}^r x_k p_{kj}} \log_2 \frac{x_i p_{ij}}{\sum_{k=1}^r x_k p_{kj}})}_{\text{Conditional entropy given } b_j} \cdot \underbrace{\sum_{k=1}^r x_k p_{kj}}_{\text{Probability of receiving } b_j}
\right) \\
&= -\sum_{j=1}^s \sum_{i=1}^r x_i p_{ij}
\left(\log_2 x_i + \log_2 p_{ij} - \log_2
\left(
\sum_{i=1}^r x_i p_{ij}
\right)\right) \\
&= \sum_{j=1}^s
\left(
\sum_{i=1}^r x_i p_{ij}
\right) \log_2
\left(
\sum_{i=1}^r x_i p_{ij}
\right) - \sum_{i=1}^r x_i \log_2 x_i - \sum_{j=1}^s \sum_{i=1}^r x_i p_{ij} \log_2 p_{ij}
\end{aligned} E After = j = 1 ∑ s ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ Conditional entropy given b j ( − i = 1 ∑ r ∑ k = 1 r x k p k j x i p i j log 2 ∑ k = 1 r x k p k j x i p i j ) ⋅ Probability of receiving b j k = 1 ∑ r x k p k j ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ = − j = 1 ∑ s i = 1 ∑ r x i p i j ( log 2 x i + log 2 p i j − log 2 ( i = 1 ∑ r x i p i j ) ) = j = 1 ∑ s ( i = 1 ∑ r x i p i j ) log 2 ( i = 1 ∑ r x i p i j ) − i = 1 ∑ r x i log 2 x i − j = 1 ∑ s i = 1 ∑ r x i p i j log 2 p i j
定义信息量 为收到信息时，基于熵的减少量，那么在这个背景下，每个信号所包含的信息量期望值为
E Before − E After = − ∑ j = 1 s ( ∑ i = 1 r x i p i j ) log 2 ( ∑ i = 1 r x i p i j ) + ∑ j = 1 s ∑ i = 1 r x i p i j log 2 p i j E_{\text{Before}} - E_{\text{After}} = -\sum_{j=1}^s
\left(
\sum_{i=1}^r x_i p_{ij}
\right) \log_2
\left(
\sum_{i=1}^r x_i p_{ij}
\right) + \sum_{j=1}^s \sum_{i=1}^r x_i p_{ij} \log_2 p_{ij} E Before − E After = − j = 1 ∑ s ( i = 1 ∑ r x i p i j ) log 2 ( i = 1 ∑ r x i p i j ) + j = 1 ∑ s i = 1 ∑ r x i p i j log 2 p i j
对于一个通信路来说，通过修改 x i x_i x i 容量
