线性码

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

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

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

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

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

 生成矩阵和校验矩阵 
作为的线性子空间，整个线性码组C （可能非常大）可以表示为一组长度为的码字（在线性代数中称为基）的线性组合。这些基码字通常被整理成矩阵G的行，该矩阵称为码C的生成矩阵。当G具有分块矩阵形式（其中表示单位矩阵，P是矩阵）时，我们称G具有标准形式。

表示线性函数，核为C的矩阵H称为C的校验矩阵（有时也称奇偶校验矩阵）。上述表述等价于H是一个零空间为C的矩阵。设C是一个码组，其生成矩阵G为标准形式，则 ， 则是C的校验矩阵。由H生成的码称为C的对偶码。可以验证G是矩阵，而H是矩阵。

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



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

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

证明:因为 , 等价于，其中  是的第列。除去使的项，使的线性相关。是故，不小于线性相关的列的最小个数。又，考虑线性相关列的最小集 ，其中是列指标的集合。。考虑满足时候的向量。注意到由于，，是故，有，后者是 之中线性相关的行的最小数目。 上述性质得证。

 示例：汉明码 

汉明码在数字通信系统中得到了广泛的应用。对于任何正整数 ，存在一个汉明码。由于 ，此类汉明码可以纠正1位错误。

例：具有以下生成矩阵和奇偶校验矩阵的线性分组码是汉明码。



 示例：阿达马码 

是线性码，能够纠正诸多误码。 阿达马码可以逐列构建： 第列是整数的二进制表示 ，如下例所示。 阿达马码的最小距离为，因此可以纠正错误。

例：具有以下生成矩阵的线性分组码是阿达玛码：  。

是的一个特例。如果我们从中抽出第一列（全零列），我们可以得到单纯形码，是汉明码的对偶码。

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

输入：接收到的中的向量v 

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

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

如果对于每个中的最多有一个码字在中，称线性码是-纠错的。

 常用记号 
码通常用字母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=n+1的代码C称为最大距离可分（Maximum Distance Separable）的或MDS 。如果这样的代码存在，那么从某种意义上来说，它们就是最好的。

设C1和C2是两个长度为n的代码，且对称群Sn中存在置换p ，当且仅当(cp (1) ,... , cp (n) ) 在C2中时，( c1 ,..., cn ) 在C1中，则称C1与C2是置换等价的。更一般地，如果存在使得C1同构于C2 ，那么称C1和C2是等价的。

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

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

 示例 
线性码的一些示例包括：


 奇偶校验码
 循环码
 汉明码
 ，包括的和的
 多项式码（典型代表：BCH码）
 里德-所罗门码







 涡轮码


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

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

 参见 

 译码方法

 参考文献 

 参考书目 

  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.
Category:有限域
Category:编码理论