9 Channel Coding
章节目录
- 章节目录
- 9-1 误差控制系统 Error Control Systems
- 9-2 信道编码定理 Channel Coding Theorem
- 9-3 线性分组码 Linear Block Codes
- 9-4 检错纠错能力 Error Detection and Correction
9-1 误差控制系统 Error Control Systems
9-1-1 ARQ、FEC 与 HEC
信道编码的目标是在有噪信道中提高传输可靠性。它通过加入冗余，使接收端能检测或纠正传输错误。
三类误差控制方式如下：
| 方式 Method | 机制 | 特点 |
|---|---|---|
| ARQ Automatic Repeat reQuest | 接收端检测错误，发现错误后请求重传 | 译码简单，需要反馈链路，实时性较弱 |
| FEC Forward Error Correction | 接收端直接利用冗余纠错 | 不需要反馈链路，译码复杂度较高 |
| HEC Hybrid Error Control | 可纠正则纠正，不可纠正则请求重传 | 兼顾连续性和复杂度 |
FEC 的抽象链路为：
其中
9-1-2 随机错误与突发错误 Random and Burst Errors
随机错误 Random Error 指错误在传输序列中近似独立、均匀出现。BSC 是随机错误模型的基本例子。
突发错误 Burst Error 指一段时间内连续或密集出现错误。无线衰落、强干扰和同步失效都可能导致突发错误。
在 BSC 中，长度为
少于
不少于
平均错误个数为：
因此 BSC 的平均误码率仍为
9-1-3 最小错误概率译码 Minimum Error Probability Decoding
接收端收到
则条件错误概率为：
为了最小化条件错误概率，应选择后验概率最大的输入符号：
由 Bayes 公式：
由于
若输入符号等概率，则先验概率相同，准则退化为最大似然译码：
9-2 信道编码定理 Channel Coding Theorem
9-2-1 重复码直觉 Repetition Code Intuition
在 BSC 中，若直接传输一个二元符号，最大似然译码的错误概率就是交叉概率
把一个符号重复
接收端按多数判决译码。若发送
当
错误概率下降，但编码率也下降为：
若
当
9-2-2 ML 与 MAP 译码 ML and MAP Decoding
设发送码字为
最大似然 Maximum Likelihood, ML 译码为：
ML 默认各码字等概率发送。
最大后验 Maximum A Posteriori, MAP 译码为：
由 Bayes 公式可得：
MAP 把先验概率
9-2-3 有噪信道编码定理 Noisy Channel Coding Theorem
有噪信道编码定理 Noisy Channel Coding Theorem
该定理又称香农第二定理 Shannon's Second Theorem。
设离散无记忆信道容量为
其中
若
若发送端每秒发送
实际信息传输率为：
单位时间信道容量为
即：
信道编码定理给出存在性结论。具体构造哪一种码、复杂度是否可接受，需要在线性分组码、卷积码、Turbo 码、LDPC 码等具体方案中处理。
9-3 线性分组码 Linear Block Codes
9-3-1 基本定义 Basic Definitions
线性分组码 Linear Block Code 把
消息向量为：
码字为：
接收向量为：
编码率为：
线性分组码的“线性”指所有运算在有限域中进行。二元线性分组码在
9-3-2 生成矩阵 Generator Matrix
其中：
矩阵大小为
- 全零向量
是合法码字； - 任意两个码字异或后仍是合法码字；
- 任意码字都是
的行向量线性组合。
例如
因此：
9-3-3 校验矩阵与伴随式 Parity Check Matrix and Syndrome
对生成矩阵
则
任意合法码字都满足：
设传输错误图样为：
其中
定义伴随式 Syndrome：
代入接收向量：
伴随式只与错误图样有关，与发送的具体码字无关。这是线性分组码译码的基本依据。
9-3-4 系统码 Systematic Code
若生成矩阵可写为：
则对应码称为系统码 Systematic Code。消息位直接出现在码字前
对二元系统码，可取校验矩阵：
此时：
系统码便于从译码后的码字中直接读出消息位。
9-4 检错纠错能力 Error Detection and Correction
9-4-1 最小 Hamming 距离 Minimum Hamming Distance
Hamming 重量 Hamming Weight 是向量中非零元素个数：
Hamming 距离 Hamming Distance 是两个等长向量对应位置不同的个数：
对二元向量：
码的最小 Hamming 距离为：
线性分组码中，任意两个码字之差仍是码字，因此：
9-4-2 伴随式译码 Syndrome Decoding
若码的最小距离为
以及：
若要求同时纠正
伴随式译码的流程为：
- 选取最可能出现的错误图样
； - 计算每个错误图样对应的伴随式
- 建立
表； - 对接收向量计算
- 查表得到估计错误图样
； - 修正码字：
在 BSC 且
9-4-3 重复码性能 Repetition Code Performance
最小距离为：
因此最多可纠正：
个错误。
若 BSC 交叉概率为
当
但编码率为：
重复码适合说明可靠性与速率的权衡，不适合作为高效率编码方案。
9-4-4 Hamming 码 Hamming Code
Hamming 码 Hamming Code 是一类线性分组码，满足：
因此伴随式个数正好等于“无错误”加上所有单比特错误图样的个数。Hamming 码是单比特纠错的完美码。
二元
对应校验矩阵可取：
它满足：
因此它可以纠正
若 BSC 的比特错误概率为
一般
其编码率为：
当
但单错纠正能力不随码长同比例增长，因此固定交叉概率下：
这说明高码率本身不等于高可靠性。码的距离结构和译码能力必须同时考虑。