线性分组码

基本思路：增加冗余位。

码距

最小码距

分组码：将信息序列以 k 为长度进行等长划分，然后按规则添加一定数目冗余位的编码方法

线性分组码：信息位和校验位之间满足线性关系的分组码

线性分组码的参数：$(n,k)$ n 为码字的长度，也就是编码后的总长度；k 是信息比特的长度，也就是原始消息的比特数

c 是 n 维码矢量（这里写成行向量），m 是 k 维信息矢量，G 是生成矩阵

$$c=mG$$

码率：

$$R=\frac{k}{n}$$

当 G 给定的时候，线性分组码有以下性质：

1. 零向量一定是一个码字，称为零码字
2. 任意两个码字的和或者差一定仍是一个码字
3. 任意码字 c 是 G 的行向量的线性组合
4. 线性分组码的最小距离等于最小非零码字重量

$$d(c_i,c_j)=w(c_i\oplus c_j)\to d_{min}=\underset{c\ne 0}{\min }w(c)$$

译码部分

对于一个 $GF(2)$ 上的 $k\times n$ 生成矩阵 $G$，必然存在一个 $(n-k)\times n$ 的矩阵 $H$

$$G{H}^T=[0{]}_{k\times (n-k)}$$

这意味着任何一个合法的码字 c 与 $H^T$ 相乘的时候结果必然是全零向量

系统码

为了更加好看，我们对 G 进行约束，得到：系统码

检错能力

若最小码距为 $d_{min}$，那么线性分组码可以

• 可以检测出任意小于等于 $d_{min}-1$ 个 bit 的差错：任何小于等于 $d_{min}-1$ 个的变化都不会成为一个新的合法码字（最小码距决定了）
• 可以纠正任意小于等于 $\lfloor \frac{d_{min}-1}{2}\rfloor$ 个 bit 的差错：对每一个合法码字为中心画一个以码字为中心，半径为 $\lfloor \frac{d_{min}-1}{2}\rfloor$ 的“球”，这个时候它们彼此不重叠，任何一个在球中出现的差错都能被纠正到球心
• 检错和纠错能力之和有上限 $d_{min}-1$：一个码字不能够在作为 a 作为检验出差错的同时，落在另一个 b 的确定纠错范围内。如果这个发生的话，那就会产生纠错和检错的不一致，也就是误纠

$(n,k)$ 线性分组码的最小码距为 $d_{min}$ 为 $H$ 中最小的、列线性相关的列数：一定能够找到一个合法码字乘以 H 得到 0。

同时，既然我们一定能够找到 $d_{min}-1$ 个线性无关的列向量在 $H$ 中，则一定有 $d_{min}-1\le n-k$ （线性相关数不能超过空间维数），这个最小码距称之为汉明界。

若 $d_{\min }=n-k+1$ ，相应的码为 极大最小距离码

常用线性分组码

• 汉明码
• 循环码
• 系统循环码