纠错码理论

纠错码一开始应用于数字通信系统，目的是使消息可以在信道中可靠的传输而不产生错误，其通过在消息中增加冗余的方法，排除噪声信道下带来的干扰，从而使接收方能够正确的检测或纠正错误

定义1（线性分组码）：

二进制(n, k)线性分组码 C 是 GF(2)上的 n 维线性空间的一个 k 维子空间。n 表示码字的长度，k 表示消息位的长度。

对于(n, k)线性分组码 C，对于(n, k)线性分组码 C，若矩阵 $G \in F_2^{k \times n}$ 满足

C = \{mG|m \in F_2^k\}

称矩阵G为码C的生成矩阵。

可见，码字空间是矩阵G的行的线性组合张成的子空间，对G做初等变换有 $G=[I_kP]$ , $I_k$ 是k阶的单位阵，P是大小为 $k\times (n-k)$ 的矩阵，由该G生成的码称为系统码，且系统码的前k位是信息位，后 $(n-k)$ 位是校验位。

若矩阵 $H \in F_2^{(n-k)\times n}$ 满足

C= \{c\in F_2^n|Hc^T=0\}

称矩阵H为码C的校验矩阵

设向量 $c\in F_2^n$ ,校验矩阵 $H\in F_2^{(n-k)\times n}$ 。若向量 $s\in F_2^{n-k}$ 有

s^T = Hc^T\in F_2^{n-k}

称s为向量c的校验子。当码字正确是，校验子为0向量。

设向量 $c\in F_2^{n}$ ,汉明重量指向量中非0元素的个数，记作 $w(c)$

设向量 $a,b \in F_2^n$ ,汉明距离指对应位置不同元素的个数，记作 $d(a,b)=w(a-b)$

设线性分段码C， $\forall c_1,c_2\in C$ 且 $c_1 \neq c_2$ ，最小距离记作 $d_{min}= min\ d(c_1,c_2)$ 。其等价于线性分组码C中非零码字的最小汉明重量，即 $c\in C,c\neq0,d_{min} = min\ w(c)$ 。

若一个(n,k)线性分组码的最小距离为 $d_{min}$ ，则

下文将以(n,k,d)表示线性分组码，其中d表示 $d_{min}$

设(n,k,d)线性分组码 $C_1$ 和 $C_2$ ，置换 $C_1$ 中的n个码元位置并加一个不变的n维向量a后能够得到 $C_2$ ，称 $C_1$ 与 $C_2$ 属于一个等价类。即

C_2 \in \{ \pi(u)+a,u\in C_1\}

对 $C_1$ 和 $C_2$ 而言，判断二者是否为同一等价类等价于寻找k阶满秩方阵S和n阶置换矩阵P，使得 $C_1$ 的生成矩阵 $G_1$ 和 $C_2$ 的生成矩阵 $G_2$ 满足

G_1 = SG_2P

若满足上式，则代表 $C_1$ 与 $C_2$ 等价。