茶年 · 中文维基百科

线性码

Wikipedia · 2026-05-29 维基百科 👁 1 阅读

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

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

外部链接

#编码理论 #有限域

评论 (0)

  • 还没有评论，来抢沙发吧。