第4章 信道编码 (Channel Coding)

1. 基本概念与目的

• 目的：通过增加信源符号的冗余度（Redundancy），提高信息传输的可靠性（Reliability）。
• 模型：$x_i \to [C] \to y_j$
  • 发送端发送信号 $x_i$。
  • 接收端收到 $y_j$，需要推测发送的是哪一个 $x_i$。
  • 通过译码函数 $f(y_j)$ 来实现映射：
    • 若 $f(y_j) = x_i$，则译码正确 ($\checkmark$)；
    • 若 $f(y_j) \neq x_i$，则译码错误 ($\times$)。

2. 错误概率与译码准则

2.1 错误概率 $P_E$

• 平均错误概率：

  $P_E = \sum_{j} P(y_j) P(e|y_j)$

  其中 $P(e|y_j)$ 表示在收到 $y_j$ 的条件下译码错误的概率。对于特定的 $y_j$，译码错误的概率等于所有非正确译码选项的概率之和。

• 联合概率矩阵 $P_{XY}$：

  $P(x_i, y_j) = P(x_i) \cdot P(y_j|x_i)$

  可以通过信道转移概率矩阵（$P_{Y|X}$）与信源分布相乘得到。

• 快速计算法： 在联合概率矩阵 $P_{XY}$ 中，每一列代表一个 $y_j$。如果我们为每个 $y_j$ 选定了一个正确的译码结果 $x_i$，那么这一列中除了该正确项以外的所有项之和，就是这一列产生的错误概率。将所有列的错误概率求和即可得到平均错误概率 $P_E$。

2.2 常见译码准则

1. 最小错误概率准则 (MAP, Maximum A Posteriori)
   • 核心思想：在已知收到 $y_j$ 的条件下，挑选使后验概率 $P(x_i|y_j)$ 最大的 $x_i$。
   • 操作方法：在联合概率矩阵 $P_{XY}$ 中，对每一列挑出最大元素对应的 $x_i$ 作为译码结果。
   • 适用场景：信源概率 $P(x_i)$ 已知时。
2. 极大似然译码准则 (ML, Maximum Likelihood)
   • 核心思想：挑选使似然概率 $P(y_j|x_i)$ 最大的 $x_i$。
   • 操作方法：在信道转移矩阵 $P_{Y|X}$ 中，对每一列挑出最大元素。
   • 注意：当信源等概率分布时，ML 准则等价于 MAP 准则。

3. 汉明距离与重复编码

3.1 汉明距离 (Hamming Distance)

• 定义：两个等长二元码字之间不同位的个数。
  • 例：$010101$ 与 $110100$ 的汉明距离 $d=2$。
• 汉明重量 (Hamming Weight)：码字中非 0 位的个数。
• 最小汉明距离 $d_{min}$：一组码字中任意两个码字之间距离的最小值。

3.2 重复编码 (Repetition Coding)

• 码字：$C = \{0, 1\} \to C' = \{000, 111\}$。
• 译码原则：少数服从多数。例如收到 $001$，译码为 $0$。

3.3 最小距离译码准则

• 在 BSC（二元对称信道）中，如果错误概率 $p < 0.5$（即正确传输概率更大），则极大似然准则（ML）等价于最小距离译码。即挑选与接收序列汉明距离最小的发送码字。

4. 信息传输率与定理

4.1 信息传输率 $R$

平均每个符号携带的信息量：

$R = \frac{\log_2 M}{n} \quad (\text{bit/符号})$

其中 $M$ 为输入符号数，$n$ 为码长。

4.2 Fano 不等式

描述信道疑义度 $H(X|Y)$ 与错误概率 $P_E$ 之间的关系：

$H(X|Y) \leq H(P_E) + P_E \log_2(|X|-1)$

• $H(P_E)$ 是关于错误概率的二元熵。
• $\log_2(|X|-1)$ 表示发生错误时，剩下的错误选项产生的信息量。

4.3 香农第二定理（有噪信道编码定理）

只要信息传输率 $R < C$（信道容量），就存在一种编码方式，当码长 $n \to \infty$ 时，可以实现译码错误概率 $P_E$ 任意小。

5. 综合例题推导

例题 1：MAP 与 ML 准则对比

已知条件： 信道转移矩阵 $P_{Y|X} = \begin{bmatrix} 1/2 & 1/3 & 1/6 \\ 1/6 & 1/2 & 1/3 \\ 1/3 & 1/6 & 1/2 \end{bmatrix}$ 信源分布 $P(x_1) = 1/2, P(x_2) = 1/4, P(x_3) = 1/4$。

解答过程：

1. 计算联合概率矩阵 $P_{XY}$（行乘 $P(x_i)$）：

   $P_{XY} = \begin{bmatrix} 1/4 & 1/6 & 1/12 \\ 1/24 & 1/8 & 1/12 \\ 1/12 & 1/24 & 1/8 \end{bmatrix}$

2. MAP 准则（看 $P_{XY}$ 每一列最大值）：

   • $y_1$ 列：最大值 $1/4$，对应 $f(y_1) = x_1$
   • $y_2$ 列：最大值 $1/6$，对应 $f(y_2) = x_1$
   • $y_3$ 列：最大值 $1/8$，对应 $f(y_3) = x_3$
   • $P_E(MAP)$ = 所有非圈选项之和 = $1/24 + 1/12 + 1/8 + 1/24 + 1/12 + 1/12 = 11/24$。

3. ML 准则（看 $P_{Y|X}$ 每一列最大值）：

   • $y_1 \to x_1, y_2 \to x_2, y_3 \to x_3$
   • $P_E(ML)$ = 在 $P_{XY}$ 中计算此规则的错误概率 = $1/6 + 1/12 + 1/24 + 1/12 + 1/12 + 1/24 = 1/2$。

结论：MAP 的错误概率（11/24）小于 ML 的错误概率（12/24），验证了 MAP 是最小错误概率准则。

例题 2：二元对称信道 (BSC) 的重复编码

https://www.bilibili.com/video/BV1b1421r7vn?t=21222.0

条件：码长 $n=4$，码字 $W_1=0000, W_2=0011, W_3=1100, W_4=1111$。 信源分布：$P(W_1)=1/2, P(W_2)=1/8, P(W_3)=1/8, P(W_4)=1/4$。 信道：BSC，单个比特错误概率 $p < 0.01$。

计算 SOP：

1. 写出汉明距离矩阵 $P_D$（接收序列与码字之间的距离）。
2. 根据准则在每一列挑选最匹配的码字。
3. 计算 $P_E$。由于 $p$ 很小，通常项的阶数越低（$p^k$ 中的 $k$ 越小）对结果影响越大。

平均错误概率公式：

$P_E = \sum_j P(y_j) P(e|y_j)$

在 $p$ 极小时，主要的错误项来自于距离为 1 的传输。例如，若正确码字为 $0000$，传输变成 $0001$，其概率权重为 $p(1-p)^3$。

6. 标准操作流程 (SOP) 总结

6.1 译码计算 SOP

1. 将信道转移矩阵 $P_{Y|X}$ 转化为联合概率矩阵 $P_{XY}$。
2. 根据准则（MAP 选 $P_{XY}$ 最大，ML 选 $P_{Y|X}$ 最大）确定每一列的译码结果。
3. 加总所有未被选中的概率值，得到 $P_E$。

6.2 汉明码译码 SOP

1. 计算接收序列与所有合法码字的汉明距离。
2. 选择距离最小的作为译码结果。
3. 若存在距离相等的情况，选择对应信源概率 $P(x_i)$ 较大的那一个（这实际上是 MAP 的思想）。