线性码

编码理论中，线性码是一种纠错码，满足其任何码字的线性组合也是其码字。传统上，线性码分为分组码和卷积码两大类，尽管涡轮码可以看作是这两种类型的混合。线性码的编码和解码可以有比其他码更有效的算法（参见伴随式解码）。

线性码用于前馈纠错，用于在通信信道上传输符号（例如，比特），以使在通信中出现错误时，消息块的接收者可以纠正或检测到一些错误。线性分组码的码字是一种符号块，这种符号块使用比要发送的原始值更多的符号进行编码。

$N - K$

$K$

长度为n的线性码传输包含n个符号的块。例如，7,4,3汉明码是一种线性二进制码，使用7位码字表示4位消息。两个不同的码字至少有三位不同。因此，每个码字最多可以检测到两个错误，同时可以纠正一个错误。此代码包含 24=16个码字。

## 定义和参数

长度为n且维度为k的线性码是向量空间$\mathbb{F}_q^n$中维度为k的线性子空间C，其中$\mathbb{F}_q$是具有q个元素的有限域。这样的线性码称为q-ary码。如果q=2或q=3，则分别称其为二进制码、三进制码。C中的向量称为码字。线性码的大小是指码字的数量，即qk。

码字的权重（weight）是码字中非零元素的个数，两个码字之间的距离（distance）是指它们之间的汉明距离，即它们之间不同的元素个数。线性码的距离d是其非零码字的最小权重，其等效于不同码字之间的最小距离。长度为n、维度为k、距离为d的线性码称为n, k, d码（或更准确地说，$[n,k,d]_q$码）。

我们希望赋予$\mathbb{F}_q^n$标准基，因为每个向量坐标代表一个“比特”，该“比特”通过“噪声信道”传输，并且以小概率存在一些传输错误（二进制对称信道）。如果使用其他基，则无法使用该模型，并且汉明度量不能像我们所希望的那样测量传输中的错误数量。

## 生成矩阵和校验矩阵

作为$\mathbb{F}_q^n$的线性子空间，整个线性码组C （可能非常大）可以表示为一组长度为$k$的码字（在线性代数中称为基）的线性组合。这些基码字通常被整理成矩阵G的行，该矩阵称为码C的生成矩阵。当G具有分块矩阵形式$\boldsymbol{G} = [I_k \mid P]$（其中$I_k$表示$k \times k$单位矩阵，P是$k \times (n-k)$矩阵）时，我们称G具有标准形式。

表示线性函数$\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}$，核为C的矩阵H称为C的校验矩阵（有时也称奇偶校验矩阵）。上述表述等价于H是一个零空间为C的矩阵。设C是一个码组，其生成矩阵G为标准形式，则$\boldsymbol{G} = [I_k \mid P]$，则$\boldsymbol{H} = [-P^T \mid I_{n-k} ]$是C的校验矩阵。由H生成的码称为C的对偶码。可以验证G是$k \times n$矩阵，而H是$(n-k) \times n$矩阵。

线性保证码字c0与任何其他码字c≠c0之间的最小汉明距离d与c0无关。这从以下性质可以看出：C中两个码字的差c−c0也是一个码字（即子空间C的一个元素），且d ( c ,c 0 ) = d ( c−c0 ,0)。由上述性质可得

$$\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C,\ c \neq c_0}d(c-c_0, 0)=\min_{c \in C,\ c \neq 0}d(c, 0)=d.$$

换而言之，为了找出线性码的码字之间的最小距离，只需要查看非零码字。具有最小权重的非零码字与零码字的距离最小，从而决定了代码的最小距离。

线性码C的距离d也等于校验矩阵H的线性相关列的最小数量（列向量最小线性无关组的秩）。

证明:因为 $\boldsymbol{H} \cdot \boldsymbol{c}^T = \boldsymbol{0}$, 等价于$\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \boldsymbol{0}$，其中 $\boldsymbol{H_i}$ 是$\boldsymbol{H}$的第$i$列。除去使$c_i=0$的项，使$c_i \neq 0$的$\boldsymbol{H_i}$线性相关。是故，$d$不小于线性相关的列的最小个数。又，考虑线性相关列的最小集 $\{ \boldsymbol{H_j} \mid j \in S \}$，其中$S$是列指标的集合。$\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \sum_{j \in S} (c_j \cdot \boldsymbol{H_j}) + \sum_{j \notin S} (c_j \cdot \boldsymbol{H_j}) = \boldsymbol{0}$。考虑满足$j \notin S$时候$c_j'=0$的向量$\boldsymbol{c'}$。注意到由于$\boldsymbol{H} \cdot \boldsymbol{c'}^T = \boldsymbol{0}$，$\boldsymbol{c'} \in C$，是故，有$d \le wt(\boldsymbol{c'})$，后者是 $\boldsymbol{H}$之中线性相关的行的最小数目。上述性质得证。

## 示例：汉明码

汉明码在数字通信系统中得到了广泛的应用。对于任何正整数$r \ge 2$，存在一个$[2^r-1, 2^r-r-1,3]_2$汉明码。由于$d=3$，此类汉明码可以纠正1位错误。

例：具有以下生成矩阵和奇偶校验矩阵的线性分组码是$[7,4,3]_2$汉明码。

$\boldsymbol{G}=\begin{pmatrix} 1& 0& 0& 0& 1& 1& 0 \\ 0& 1& 0& 0& 0& 1& 1 \\ 0& 0& 1& 0& 1& 1& 1 \\ 0& 0& 0& 1& 1& 0& 1 \end{pmatrix} ,$ $\boldsymbol{H}=\begin{pmatrix} 1& 0& 1& 1& 1& 0& 0 \\ 1& 1&\ 1& 0& 0& 1& 0 \\ 0& 1& 1& 1& 0& 0& 1 \end{pmatrix}$

## 示例：阿达马码

阿达马码是$[2^r, r, 2^{r-1}]_2$线性码，能够纠正诸多误码。阿达马码可以逐列构建：第$i$列是整数$i$的二进制表示，如下例所示。阿达马码的最小距离为$2^{r-1}$，因此可以纠正$2^{r-2}-1$错误。

例：具有以下生成矩阵的线性分组码是$[8,3,4]_2$阿达玛码： $\boldsymbol{G}_\mathrm{Had}=\begin{pmatrix} 0& 0& 0& 0& 1&\ 1&1& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 1& 0& 1& 0& 1& 0& 1\end{pmatrix}$。

阿达马码是里德-穆勒码的一个特例。如果我们从$\boldsymbol{G}_\mathrm{Had}$中抽出第一列（全零列），我们可以得到$[7,3,4]_2$单纯形码，是汉明码的对偶码。

## 最近邻算法

参数d与码的纠错能力密切相关。以下构造/算法说明了这一点（称为最近邻解码算法）：

输入：接收到的$\mathbb{F}_q^n$中的向量v

输出：在$C$中最接近$v$的一个码字$w$（如果有）。

- 从$t=0$开始，重复以下两个步骤。
- 枚举（汉明）半径为$t$，以待编码$v$为中心的球的包含的元素，表示为$B_t(v)$。
- 对于每个$B_t(v)$中的$w$，检查$w$是否在$C$中。如果是，则返回$w$作为解决方案。
- 增加$t$。仅当$t > (d - 1)/2$时因失败终止。枚举已完成，但尚未找到解决方案。

如果对于每个$\mathbb{F}_q^n$中的$v$最多有一个码字在$B_t(v)$中，称线性码$C$是$t$-纠错的。

## 常用记号

码通常用字母C表示，长度为n且秩为k的码（即，其基中有n个码字，其生成矩阵中有k行）通常称为 (n, k) 码。线性分组码通常表示为 n, k, d 码，其中d表示码中任意两个码字之间的最小汉明距离。

（n, k, d 符号不应与 (n, M, d)符号混淆，后者用于表示长度为n、大小为M（即具有M 个码字）且最小汉明距离为d 的非线性码。）

## 辛格尔顿界

引理（辛格尔顿界）：每个线性 n,k,d 码C满足$k+d \leq n+1$。

参数满足k+d=n+1的代码C称为最大距离可分（Maximum Distance Separable）的或MDS。如果这样的代码存在，那么从某种意义上来说，它们就是最好的。

设C1和C2是两个长度为n的代码，且对称群Sn中存在置换p，当且仅当(cp (1) ,... , cp (n) ) 在C2中时，( c1 ,..., cn ) 在C1中，则称C1与C2是置换等价的。更一般地，如果存在$n\times n$广义置换矩阵$M\colon \mathbb{F}_q^n \to \mathbb{F}_q^n$使得C1同构于C2，那么称C1和C2是等价的。

引理：任何线性码都等价于标准形式的码的置换。

## 博尼索利定理

对于一个码字，当且仅当存在某个常数d，使得该码中任意两个不同码字之间的距离等于d时，其可以称为等距码。1984 年，阿里戈·博尼索利 (Arrigo Bonisoli) 确定了有限域上线性单重码的结构，并证明了每个等距线性码都是与汉明码对偶的序列。

## 示例

线性码的一些示例包括：

- 重复码
- 奇偶校验码
- 循环码
- 汉明码
- 戈莱码 (消歧义)，包括二元戈莱码的和三元戈莱码的
- 多项式码（典型代表：BCH码）
- 里德-所罗门码
- 里德-穆勒码
- 代数几何码
- 二元戈帕码
- 低密度奇偶校验码
- 扩展码
- 多维奇偶校验码
- 环面码
- 涡轮码
- 局部可恢复码

## 推广

在非域字母表上的汉明空间同样受到关注，尤其是有限环上的情形，其中最显著的是Z4上的伽罗瓦环。由此导出的是模结构而非向量空间结构，对应的环线性码（由子模定义）取代了传统线性码。此类空间通常采用李氏距离作为度量。研究发现：配备汉明距离的$\mathbb{Z}_2^{2m}$ （即 GF(22m )）与配备李距离的 $\mathbb{Z}_4^m$（亦记作 GR(4,m)）之间存在格雷等距映射。该映射的核心价值在于：它能将$\mathbb{Z}_4^m$上某些环线性码的像，对应于$\mathbb{Z}_2^{2m}$上具有优良性质却非线性的编码。

有些作者也将环上的此类码简称为线性码。

## 参考文献

### 参考书目

- Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

## 外部链接

- q-ary code generator program
- Code Tables: Bounds on the parameters of various types of codes, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH). Online, up to date table of the optimal binary codes, includes non-binary codes.
- The database of Z4 codes Online, up to date database of optimal Z4 codes.