线性分组码

线性分组码是指码字空间构成一个线性空间的分组码。设码字长度为n，信息位长度为k，则线性分组码记为(n,k)码。

生成矩阵

• 定义：生成矩阵G是一个 $(k\times n)$ 的矩阵，则编码规则为：

$$\mathbf{c}=\mathbf{m}\cdot G$$

• 解码规则为:

$$\mathbf{m}=\mathbf{c}\cdot G^{-1}$$

• 其中，$\mathbf{m}$ 是一个 $1\times k$ 的信息向量，$\mathbf{c}$ 是一个 $1\times n$ 的码字向量。
• 可以把 $(k,n)$ 线性分组码视作 ${\mathbb{F}}_2^n$ 上的一个线性映射，映射到 $k$ 维上的一个子空间。
• 更形象化的说，想象一下有 $n$ 个向量张成了一个 $n$ 维空间，然后在这个空间里选取 $k$ 个向量，每个向量有 $n$ 个点，组成一个 $k\times n$ 的矩阵，这个矩阵就是生成矩阵，行张成了一个 $k$ 维子空间。而编码就是把信息规约到这个 $k$ 维子空间上。

校验矩阵

• 定义：校验矩阵H是一个 $(n-k)\times n$ 的矩阵，满足：

$$G\cdot H^T=0(1)$$

• 对于每一个合法码字$\mathbf{c}$，都有：

$$H\cdot {\mathbf{c}}^T=0(2)$$

• 显然，式(1)表示的是H的行空间与G的行空间正交，式(2)表示的是所有合法码字$\mathbf{c}$也和H正交。
• 为什么H是 $n-k$ 维：想象一下，在一个三维空间中，和一个二维平面正交的显然只有一个维度，和一个一维直线正交的显然有两个维度（一整个平面），故而，和一个 $k$ 维子空间正交的显然是 $n-k$ 维子空间。

系统码

• 定义：如果生成矩阵G可以写成如下形式：
• $G=[I_k|P]$
• 则称该线性分组码为系统码，其中$I_k$是一个 $k\times k$ 的单位矩阵，$P$是一个 $k\times (n-k)$ 的矩阵。
• 对应的校验矩阵H可以写成如下形式：
• $H=[-P^T|I_{n-k}]$
• 此时信息位直接出现在码字的前k位。

纠错与译码

• 接收到向量 $r=c+e$ 后，计算伴随式$S(1\times r)$ :

$$S=r{H}^T=(c+e)H^T=c{H}^T+e{H}^T=0+e{H}^T=e{H}^T$$

• 若 $S=0$（全零向量），则认为无错。
• 若 $S\ne 0$，则 $S$ 对应于校验矩阵 $H$ 中的某一列向量。
• 找到该列向量在 $H$ 中的索引位置 $i$（即满足 $H$ 的第 $i$ 列等于 $S^T$），则 $i$ 即为错误发生的位位置。
• 翻转对应位置 $i$ 的比特即可完成纠错。