线性码 📖 Wikipedia

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

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

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

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

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

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

${\displaystyle \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的线性相关列的最小数量（列向量最小线性无关组的秩）。

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

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

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

${\displaystyle {\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}},}$  ${\displaystyle {\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}}}$ 

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

例：具有以下生成矩阵的线性分组码是${\displaystyle [8,3,4]_{2}}$ 阿达玛码： ${\displaystyle {\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}}}$  。

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

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

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

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

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

如果对于每个${\displaystyle \mathbb {F} _{q}^{n}}$ 中的${\displaystyle v}$ 最多有一个码字在${\displaystyle B_{t}(v)}$ 中，称线性码${\displaystyle C}$ 是${\displaystyle 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满足${\displaystyle 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₂是置换等价的。更一般地，如果存在${\displaystyle n\times n}$ 单项式矩阵（英语：monomial matrix）${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$ 使得C₁同构于C₂ ，那么称C₁和C₂是等价的。

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

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

线性码的一些示例包括：

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

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

• 译码方法

1. ^ William E. Ryan and Shu Lin. Channel Codes: Classical and Modern . Cambridge University Press. 2009: 4. ISBN 978-0-521-84868-8. 
2. ^ Martínez, Consuelo; Molina, Fabián. The syndromes decoding algorithm in group codes. Finite Fields and Their Applications. 2023-08-01, 89 [2025-07-05]. ISSN 1071-5797. doi:10.1016/j.ffa.2023.102206. 
3. ^ MacKay, David, J.C. Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. 2003: 9 [2025-07-06]. Bibcode:2003itil.book.....M. ISBN 9780521642989. （原始内容存档 (PDF)于2012-09-15）. In a linear block code, the extra ${\displaystyle N-K}$  bits are linear functions of the original ${\displaystyle K}$  bits; these extra bits are called parity-check bits 
4. ^ Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc. 1991: 210–211. ISBN 978-0-471-06259-2. 
5. ^ Grossman, Jay. Coding theory: introduction to linear codes and applications. (PDF). Insight: River Academic Journal. 2008, 4 (2) [2025-07-05]. 
6. ^ Grossman, Jay. Coding theory: introduction to linear codes and applications. (PDF). Insight: River Academic Journal. 2008, 4 (2) [2025-07-05]. （原始内容存档 (PDF)于2024-04-15）. 
7. ^ ^{7.0 7.1} 樊昌信; 曹丽娜 (编). 通信原理. 北京: 国防工业出版社. 2024: 341-343. ISBN 978-7-118-08768-0. 
8. ^ 冯桂; 周林 (编). 信息论与编码. 北京: 清华大学出版社. 2016: 92-93. ISBN 978-7-302-42427-7. 
9. ^ Etzion, Tuvi; Raviv, Netanel. Equidistant codes in the Grassmannian. arXiv:1308.6231   [math.CO]. 
10. ^ Bonisoli, A. Every equidistant linear code is a sequence of dual Hamming codes. Ars Combinatoria. 1984, 18: 181–186. 
11. ^ Marcus Greferath. Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso , 编. An Introduction to Ring-Linear Coding Theory. Springer Science & Business Media. 2009. ISBN 978-3-540-93806-4. 
12. ^ Encyclopedia of Mathematics. www.encyclopediaofmath.org. [2025-07-06]. （原始内容存档于2016-12-25）. 
13. ^ J.H. van Lint. Introduction to Coding Theory  3rd. Springer. 1999. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.  含有內容需登入查看的頁面 (link)
14. ^ S.T. Dougherty; J.-L. Kim; P. Sole. Open Problems in Coding Theory. Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (编). Noncommutative Rings and Their Applications. American Mathematical Soc. 2015: 80. ISBN 978-1-4704-1032-2. 

• 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.