线性码

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

线性码用于前馈纠错，用于在通信信道上传输符号（例如，比特），以使在通信中出现错误时，消息块的接收者可以纠正或检测到一些错误。线性分组码的码字是一种符号块，这种符号块使用比要发送的原始值更多的符号进行编码。长度为n的线性码传输包含n个符号的块。例如，[7,4,3]汉明码是一种线性二进制码，使用7位码字表示4位消息。两个不同的码字至少有三位不同。因此，每个码字最多可以检测到两个错误，同时可以纠正一个错误。此代码包含 2⁴=16个码字。

定义和参数

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

码字的权重（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$矩阵。

线性保证码字c₀与任何其他码字c≠c₀之间的最小汉明距离d与c₀无关。这从以下性质可以看出：C中两个码字的差c−c₀也是一个码字（即子空间C的一个元素），且d ( c ,c ₀ ) = d ( c−c₀ ,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\leq wt({\boldsymbol {c'}})$，后者是 ${\boldsymbol {H}}$之中线性相关的行的最小数目。 上述性质得证。

示例：汉明码

汉明码作为首类为纠错目的而开发的线性码，在数字通信系统中得到了广泛的应用。对于任何正整数$r\geq 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 。如果这样的代码存在，那么从某种意义上来说，它们就是最好的。

设C₁和C₂是两个长度为n的代码，且对称群S_n中存在置换p _，当且仅当(c_{p (1)} ,... , c_{p (n)} ) 在C₂中时，( c₁ ,..., c_n ) 在C₁中，则称C₁与C₂是置换等价的。更一般地，如果存在$n\times n$单项式矩阵$M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}$使得C₁同构于C₂ ，那么称C₁和C₂是等价的。

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

博尼索利定理

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

示例

线性码的一些示例包括：

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

推广

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

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

参见

• 译码方法

参考文献

参考书目

• J. F. Humphreys; M. Y. Prest. Numbers, Groups and Codes 2nd. Cambridge University Press. 2004. ISBN 978-0-511-19420-7.  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.