编码理论中的校验码与纠错码是两种在通信中应用的编码,对于一定长度的编码,前者可以在通信出错之后检测出错误,而后者可以在通信过程出错之后检测并改正错误。编码理论和很多数学分支有关系,近年来的研究甚至已经用到了代数几何。这篇文章主要探讨纠错码的代数理论。

纠错码的问题中,我们主要是在原来的码字中做一个代数变换,把信息的长度增加,来获得对于一定程度错误的纠正能力。

奇偶校验码:举例说明一下,对于 \(F_2\) 中的长度为 \(3\) 的向量空间。如果把整数 \(0,1,2,3,4,5,6,7\) 用 \((000),(001),\ldots,(111)\) 传输,末尾加上一位奇偶校验码,使得新的四元向量的数字 \(1\) 的个数是偶数个,那么就是一个奇偶校验码。

虽然四维空间 \(F^4_2\) 中有 \(16\) 个向量,但是奇偶校验码中只有 \(8\) 个合法的码字。在正常的传输中,如果出了 \(1\) 个错误,那么是可以检测出错误的(然而两个就不行了)。

重复码:对于一个码字,我们把这个信号重复三次,就是一个简单的重复码。对于长度为 \(3\) 的二元码,我们重复三次得到一个长度为 \(9\) 的码,九维空间中向量有 \(2^9\) 个,但是有效的码字只有 \(8\) 个。这个时候可以对有一个或两个(不相同位置)错误的情况下纠正错误。


首先我们正式地定义一下编码,用 \(F^n_q\) 表示有限域上的 \(n\) 维向量空间。\(F^n_q\) 中的每个非空子集合 \(C\) 都可以叫做一个 \(q\) 元码,\(n\) 叫做码的码长,\(C\) 中的向量叫做码字。而在代数编码中,\(F_q^n\) 向量空间也是一个赋范空间。我们赋予向量 \(a\) 范数 \(w(a)\) 为它的非零分量的个数,并定义范数诱导的距离 \(d(a, b)\) 为 \(a, b\) 中对应分量不相等的个数。为了证明这个向量空间是度量空间,容易验证 \(d\) 函数是一个正的、对称的满足三角不等式的二元函数。

而且既然我们定理了度量,那么我们就可以使用 “闭球” 这个语言来描述度量空间中的分割。定义闭球为

叫做以 \(\mathbf{v}\) 为中心,以 \(r\) 为半径的闭球。

而 \(C\) 是这个赋范向量空间的一个子集,我们定义其元素之间的最小距离为 \(d(C) = \min{ d(a, b) a, b\in C }\),称为 \(C\) 的距离。一般的来说,纠错码的纠错能力与这个距离有关。

定理:如果我们使用最小 Hamming 距离校验和纠错,那么假设纠错码 \(C\) 的距离为 \(d\),它可以校验 \(d - 1\) 位的错误,或者纠正 \(\left[\frac{d-1}{2}\right]\) 位的错误。

证明:对于一个发出的向量 \(\mathbf{c}\),在信道中有错误 \(\mathbf{\epsilon}\),并且 \(\mathbf{\epsilon}\) 有 \(d-1\) 个非零分量,那么收到的向量应该是 \(\mathbf{v} = \mathbf{c} + \mathbf{\epsilon}\)。如果我们要求能够校验,那么就一定有 \(\mathbf{v}\notin C\) 总是成立的(其实相当于在一个码字处做一个最大闭球且不包含其他码字)。

如果我们需要检验错误,那么就需要最大闭球不相交,也就是闭球的最大半径是 \(\left[\frac{d-1}{2}\right]\)。


对于一个纠错码,有下面几个参数比较重要,

  1. 码长 n
  2. 码字的个数 \(|C|\),通常记为 \(K\)
  3. \(C\) 的距离 \(d\)

而对于满足这几个参数的码,我们可以表示为纠错码 \((n, K, d)_q\),来表示纠错码的特征(也可以令信息位数 $k = \log_qK$,称为 $[n, k, d]_q$ 的纠错码)。

在纠错码的构造问题中,我们需要寻找性能良好的纠错码,也就是纠错码信息效率高(\(\frac{\log_q{K}}{n}\) 大),而且 \(C\) 的距离 \(d\) 比较大的构造,以及速度更快的编码/解码算法。然而纠错码的参数是相互制约的:例如在极端条件下,\(K = q^n\),这个时候信息效率最高,然而 \(d = 1\) 没有纠错能力;如果 \(d = n\),那么 \(q\) 元码的码字最多只有 \(q\) 个,于是信息效率又很低(最多 \(\frac{1}{n}\)。

在研究中,有的 \(C\) 作为编码,可以看成是等价的。对于以下几个变换,如果 \(C\) 可以在有限次内变换成为 \( C^{\prime} \),那么就称它们为等价的。

  1. 分量置换:对于分量的顺序进行变换。对于一个 \([n]\) 上的置换 \(\sigma\),我们称 \(\sigma(\mathbf{c}) = (c_{\sigma(i)}), i\in{1,2,3\ldots,n}\) 为一个分量置换。
  2. 元素置换:对于一个 \(F_q\) 到 \(F_q\) 上的置换 \(f\),保证 \(f(0) = 0\) 的情况下,称 \(\sigma(\mathbf{c}) = (f(c_i)), i\in{1,2,3\ldots,n}\) 为一个元素置换。
  3. 码的平移:对于一个码,\(C\),我们把每个元素,加一个相同的向量 \(\mathbf{v}\),就称为一个平移。

二元码的 Plotkin 界:如果存在参数为 \((n, K, d)\) 的二元码,并且 \(2d>n\),那么

这个不等式后来没有用到,就不证明了。


线性码:为了更好地利用 \(C\),我们需要给 \(C\) 加上一些代数结构。这里我们假定 \(C\) 是一个线性子空间,也就是说码字在线性运算后,还是码字。

对于线性码,我们可以定义它的最小重量为 $\min \{ d(\mathbf{x},\mathbf{0})|\mathbf{x}\in C \} $。而且注意到,在线性码的条件下,最小重量和 \(C\) 的最小距离有一个相等的关系:

$\renewcommand{v}{\mathbf}$ 对于线性码,线性代数的知识,都可以运用到这里。比如可以取 \(C\) 的一组在 \(F_q^n\) 的基 \({\v{v_1}, \v{v_2}, \ldots, \v{v_k}}\),其中 \(\v{v_i} = (a_{i1}, a_{i2}, \ldots, a_{in})\),其中 \(a_{ij}\in F_q\)。这样每个码字都可以用这组基来唯一地表示。

如果把这组基写成矩阵的形式,

于是 \(\v{G}\) 称为线性码 \(C\) 的一个生成阵。于是 \(C\) 中的向量唯一表示为 \(\v{v} = b_1\v{v_1} + b_2\v{v_2} + \ldots + b_k\v{v_k}\),并且这种表示其实就是一个从 \({F_q^k}\) 到 \(F_q^n\) 的单射

从另外一个角度看,\(F_q^k\) 这个空间还有一个正交空间,其一组基可以记作 \( { \v{h_1},\v{h_2},\ldots,\v{h_n} }\),于是也可以组成一个矩阵 \(\v{H}\) 称为“校验阵”。

这个矩阵的意义是 \(\v{v} \in C \iff \v{vH}^T = \v{0}\),所以可以用来检验 \(C\) 中的码字。另外,这个 \(\v{H}\) 也可以用来决定线性码 \(C\) 的最小距离。如果我们把 \(\v{H}\) 换一种表示,表示成列向量的形式

定理:如果任意 \(d-1\) 个列向量都是在 \(F_q\) 下线性无关,并且任意 \(d\) 个列向量都是线性相关,那么 \(C\) 的最小距离就是 \(d\)。

证明:我们检验 \(C\) 的最小重量。对于一个 \(\v{c} = (c_1, c_2, \ldots, c_n)\) 是 \(F^n_q\) 中的一个 Hamming 距离是 \(l\) 的向量(这个向量有 \(l\) 个分量不是零),我们可以说明

这个时候,\(\v{c}\) 允许的最小权值就应该是 \(d\)。

对于一个纠错码,我们还要提出相关的线性码。线性码的纠错码算法主要利用的是校验矩阵 $\v{H}$。首先对发出的信号 $\v{c}$,加上一个可能的错误 $\v{\epsilon}$,收到的信号就是 $\v{y} = \v{v}+\v{\epsilon}$。我们验证 $\v{v}= \v{Hy}^T$,如果 $\v{v} = \v{0}$,那么我们可以声称这里是没有错误的。如果 $\v{v} = a_1\v{u_1}+\ldots+a_n\v{u_n}$,我们就让 $\v{\epsilon}= (a_1, a_2, \ldots, a_n)$。这个时候就可以计算出 $\v{c} = \v{y} - \v{\epsilon}$。

还可以注意到编码的对偶:也就是 $C$ 和 $C^\perp$ 相互对偶,后者叫做对偶码;如果 $C^\perp\subseteq C$,称这个编码为自正交码;如果 $C = C^\perp$ 我们称这个编码为自对偶码;并且注意到,有限维空间内 $(C^\perp)^\perp = C$。

注意到这样两个对偶的观察:

  1. 如果 $\v{G}$ 是线性码 $C$ 的生成阵,那么它是线性码 $C^\perp$ 的校验阵。
  2. 如果 $\v{H}$ 是线性码 $C$ 的校验阵,那么它是线性码 $C^\perp$ 的生成阵。

Hamming 界:对于纠错码 \((n, K, d)q\),

证明:这个是因为对于闭球 \(S_q(\mathbf{v}, r)\) 中的向量总数,有一个计数公式

由于每个球都是不交的,我们对纠错码为中心,\(\left[\frac{d-1}{2}\right]\) 为半径的 \(K\) 个球的所有向量的数的和不超过 \(q^n\) 就可以得到所需不等式。

完全码:如果 Hamming 界的等式成立,也就是说对于一个 \(C\) 为纠错码 \((n, K, 2l + 1)\),有

成立,那么就称这个码为完全码。这类码的所有球,正好可以填充整个空间。

我们先介绍两类平凡的完全线性码:

  1. $C = F_1^n$,这个显然是完全码(但是没有纠错作用)。
  2. $F_2^{2l +1}$ 空间中,$C$ 只有全零和全一两个向量,$d = 2l + 1$。这个时候所有向量都会被两个闭球完全覆盖。

下面我们来介绍完全线性码的概念:Hamming 码和 Golay 码。

我们称 $F_q^m$ 中两个向量 $\v{v_1}, \v{v_2}$ 是射影等价的,当且仅当存在一个 $\alpha\in F_q, \v{v_1} = \alpha\v{v_2}$。这个时候我们把射影等价的向量作为一个等价类,那么一个等价类里面应该有 $q-1$ 个向量($\alpha$ 的可取的值为 $1, 2, \ldots, q-1$)。所以一共有 $n = \frac{|F_q^m|}{q-1} = \frac{q^m-1}{q-1}$ 个等价类。从每个等价类取出一个向量 $\v{u_1},\v{u_2},\ldots,\v{u_n}$ 作为校验阵 $\v{H}_m = (\v{u_1},\v{u_2},\ldots,\v{u_n})$。

Hamming 码:校验阵为 $\v{H}_m$ 的矩阵对应的线性码 $C$ 为一个 Hamming 码。Hamming 码的参数为 $[\frac{q^m-1}{q-1}, \frac{q^m-1}{q-1} -m, 3]$,下面我们证明 Hamming 码是完全码。

证明:由于 $F_q^m$ 空间的一组基属于不同的等价类,所以这些等价类取出代表元,构成的 $\v{H}$ 矩阵的秩为 $m$。于是 $n = \frac{q^m - 1}{q - 1}, k = n-m$。并且 $\v{H_m}$ 中任意两个向量无关,但是任意两向量的和又属于某一个等价类,于是三个向量相关,所以 $d = 3$。

最后我们验证 Hamming 码是完全码,这里只需要验证 Hamming 界的等式是成立的。

所以 Hamming 码是完全码。

对于完全码,我们有一个分类定理,是 van Lint 和 Tietavainen 在 1973 年做出的:非平凡的完全码只有两类,Hamming 码和 Golay 码。 这个定理我们不证明,但是我们这里介绍以下 Golay 码的内容。

(Golay 码的内容等待补充)


接下来我们介绍另外一类线性码:MDS 线性码。

Singleton 界:对于 \(q\) 元码 \((n, K, d)\),\(1\leq d \leq n - 1\),有 [K \leq q^{n - d + 1}]

证明:设 \(C\) 是 \(q\) 元码,对于每个元素 \(a \in F_q\),令 \(C_a\) 是 \(C\) 中所有末位是 \(a\) 的码字中去掉 \(a\)组成的 \(F_q^{n-1}\) 的向量空间的子集。

容易得出,\(d(C_a)\geq d(C) = d\)。而从另一个角度,所有 \(C_a\) 对 \(C\) 进行了一个“划分”,也就是说 \(K = \sum_{a \in F_q}|C_a|\)。那么至少存在一个划分,可以让 \(|C_a|\geq \frac{K}{q}\),所以存在参数 \((n-1,\geq \frac{K}{q}, \geq d)\) 的 \(q\) 元码。

一直这样做下去,就可以得到参数为 \a((d,\geq \frac{K}{q^{n-d}},\geq d ) 的 \(q\) 元码 \(C^\prime\)。由于它的码长和距离的关系,我们可以得到这个纠错码中,最多有 \(q\) 个码字,于是 \(q\geq |C^\prime|\geq \frac{K}{q^{n-d}}\),从而得到结论 \(K\leq q^{n-d+1}\)。

对于以上的不等式,如果我们有等号成立,也就是 \(K = q^{n-d+1}\),也就是 $k = n-d+1$,我们就称这个纠错码为极大距离可分码(Maximal Distance Separable),也就是 MDS 码。首先我们给出 MDS 的一个刻画:

定理 设 $C$ 为参数 $[n, k , d]$ 的 $q$ 元线性码,$\v{G}$ 和 $\v{H}$ 是码 $C$ 的生成阵和校验阵,那么下面四个条件等价。

  1. $C$ 是 MDS 码,即 $n = k + d - 1$。
  2. $\v{G}$ 中任意 $k$ 个列向量是线性无关的。
  3. $\v{H}$ 中任意 $n-k$ 个列向量是线性无关的。
  4. $C^\perp$ 是 MDS 码。

证明:$(1)\iff(3)$:如果 $d = n -k+1$,我们知道 $\v{H}$ 中任意 $n-k$ 列都是线性无关的;如果 $\v{H}$ 中 $n-k$ 列是线性无关的,那么 $d \geq n - k +1$,但是又有 Singleton 界,$d\leq n- k+1$,那么 $d = n-k+1$ $(2)\iff(4)$:同上理。 $(1)\iff(2)$:记

其中 $\v{v_1}, \ldots, \v{v_k}$ 是一组基,而 $\v{u_1}, \v{u_2}, \ldots, \v{u_n}$ 是一组列向量。假设 $C$ 不是 MDS 码,那么 $d < n-k+1$,那么 $C$ 中就有一个非零的码字,使得 $\v{c} = \alpha_1\v{v}_1 + \ldots + \alpha_k\v{v}_k$,而且重量 $1\leq w(\v{c})\leq n -k$,这也就是说,$\v{G}$ 中有 $k$ 个是线性相关的。取逆否命题,就知道 $(2)\implies (1)$ 成立。另外一个方向显然。

推论:对于一个 MDS 码,参数为 $[n, k, d]$,我们知道 $C^\perp$ 的参数是 $[n, n - k, k + 1]$。


接下来我们介绍以下循环码,循环码的好处,是可以比代数码增加一些额外的数学结构。

循环码:$F_q$ 上长度为 $n$ 的线性码是循环码,如果 $\v{c} = (c_0, c_1, \ldots, c_{n-1})$ 循环移位之后 $\v{c^\prime} = (c_{n-1}, c_0, c_1, \ldots, c_{n-2})$ 还在 $C$ 内。

如果把循环码中的 $\v{c} = (c_0, c_1,\ldots,c_{n-1})$ 写成多项式形式,就是

而且

所以这个代数结构就是一个商环 $R = F_q[x]/(x^n-1)$。这个时候 $F_q^n$ 的一个线性子空间,也可以看作 $R$ 中的一个线性子空间,为了方便,仍然记为 $C$。对于循环码,我们知道 $c(x)\in C\implies xc(x)\in C$。所以也就是说,$C$ 为循环码,当且仅当 $C$ 为环 $R$ 的一个理想。于是在分析循环码的时候,我们就可以使用抽象代数的工具,特别是关于多项式环的工具。

我们知道 $R$ 中每个理想 $C$ 都是主理想,

并且可以取 $g(x)$ 是 $x^n-1$ 在 $F_q[x]$ 中的首 $1$ 多项式因子。循环码 $C$ 和 $g(x)$ 是一一对应的,称 $g(x)$ 为循环码的生成多项式。令

那么称 $h(x)$ 是循环码 $C$ 的校验多项式

对于循环码 $C$ 中的每个码字 $c(x) = a(x)g(x)\in R$,用 $h(x)$ 取除 $a(x)$,就可以得到

这就说明了 $g(x), xg(x),\ldots,x^{k-1}g(x)$ 是线性码 $C$ 的一组 $F_q$ 基。所以 $C$ 的维数就是 $k = \deg h(x)$。

并且,$C$ 的生成阵就是

同样的道理,我们也可以考虑这个循环码的校验式,道理是一样的,

对于代数码的对偶的定理,到这里也可以使用,于是我们就有一个关于循环码的对偶的定理: 定理:$q$ 元循环码 $C$ 的对偶码 $C^\perp$ 也是循环码。并且如果 $C$ 的生成式和校验式分别是 $g(x)= g_0+g_1+\ldots+g_{k-1}x^{k-1}, h(x) = h_0+h_1x+\ldots+h_{k-1}x^{k-1}$,那么我们就有一个关于 $C^\perp$ 的两个反向多项式,

它们给出的首一多项式 $h^\perp(x) = g_0^{-1}g^* (x)$ 和 $g^\perp(x) = h_0^{-1}h^* (x)$ 分别是循环码 $C^\perp$ 的校验式和生成式。

为了让纠错码有一定的好的性质,我们可以假设 $n$ 与 $q$ 互素。这个时候 $x^n-1$ 在 $F_q$ 的扩域里面没有重根,所以 $g(x)$ 可以分解成为不同的首一多项式的乘积。


循环码的根:定义 $C$ 是油 $g(x)$ 生成的一个 $q$ 元循环码,那么 $g(x)$ 的根也叫做循环码 $C$ 的根。

在我们假设 $n, q$ 互素的情况下,$x^n-1$ 在 $F_1$ 的扩域里面没有重根,又 $g(x)|x^n-1$,于是 $g(x)$ 也是没有重根的。记 $R$ 为 $g(x)$ 的根的集合,那么 $|R| = \deg g(x)$,对每个多项式,$c(x)\in F_q[x]$,我们可以得到 $c(x)$ 为 $C$ 中的码字 $\iff g(x)|c(x) \iff c(\gamma) = 0, \forall \gamma\in R$。

所以对循环码有这样的一个刻画:

现在我们让 $g(x) = p_1(x)\ldots p_g(x)$,为一个首1不可约多项式的分解,让 $\deg p_i(x) = d_i$。设 $\gamma_i$ 是 $p_i(x)$ 在扩域中的一个根,那么 $F_q(\gamma_i) = F_{q^{d_i}}$,而且全部的根为 $\gamma_i^{q^\lambda}, 0\leq\lambda\leq d_i-1$。

而且由于 $p_i(x)$ 的不可约性质,它的根都是 $c(x)$ 的根。于是可以利用 $C$ 的一部分根来进行一个刻画:

这种刻画可以给出一个校验阵,设 $c(x) = c_0 + c_1x+ \ldots + c_{n-1}x^{n-1}$,那么可以看出来

所以定义一个新的校验阵,

这个时候 $c(x)\in C \iff \v{H}\cdot\v{c} = \v{0}$。

循环码的这种根的刻画的方式,可以用来构造一族最小距离很大的循环码,我们称为 BCH 码。(BCH 码是 Bose, Chaudhuri, Hocquenghen 三个人的名字)

BCH 码:设 $n, q$ 互质,$\beta$ 是 $F_q$ 的某个扩域中的 $n$ 阶元素。$l, \delta$ 是正整数,$2\leq\delta\leq n-1$,以 $\beta^l, \beta^{l+1}, \ldots, \beta^{l+\delta-2}$ 为根的码长为 $n$ 的 $q$ 元循环码

叫做设计距离为 $\delta$ 的 BCH 码。这个定义的意思是说,循环码 $C$ 的生成式,就是 $\beta^{l}, \beta^{l+1}, \ldots, \beta^{l+\delta-2}$ 在 $F_q[x]$ 中的最小多项式的公倍式 $g(x)$,这里 $C$ 的参数是 $[n, k]$,并且 $k = n-\deg g(x)$。

简要说明一下 BCH 码的最小距离一定不能小于设计距离。这是因为对于其校验阵,我们证明其任意 $\delta - 1$ 列都是线性无关的,也就是任取 $\delta-1$ 阶的方阵都是可逆的,然而它的行列式一定是 Vandermode 行列式的倍数,所以 $d\geq \delta$ 是可证明的。

关于 BCH 码的译码,我们有这样一个算法,

待补充)


Reed-Solomon 码:我们之前介绍的纠错码,都是纠正独立差错的码,但是有的时候,码字在传送时候,会出现连续几个位的码都发生错误的情况,我们需要构造连续差错的纠错码。假设我们所遇到的差错是一个连续的序列,我们首先声明,$q$ 元 $(n, k)$ 循环码,可以校验出任意一个长度为 $b\leq n-k$ 的区间的差错。

证明:设 $\v{c} = (c_0, c_1, \ldots, c_{n-1})$ 是一个发送的码字,$\v{e} = (e_0, e_1, \ldots, e_{n-1})$是差错,但是只有在连续的 $b$ 位中不为零。

然而 $e(x) = e_{i+1}x^{i+1}+\ldots+e_{i+b}x^{i+b} = x^ia(x)$,其中 $a(x) = e_{i+1} + e_{i+2}x+\ldots+e_{i+b}x^{i+b}$。这个时候 $g(x)|a(x)$ 不成立,但是 $g(x)|c(x)$。于是 $\v{c}+\v{e}$ 不是码字,于是可以校验出来。

一般的 Reed-Solomon 码定义为:

设 $\alpha$ 是 $F_q$ 的一个本原元素,$n=q-1, 2\leq d\leq n$,以 $\alpha, \alpha^2,\ldots, \alpha^{d-1}$ 为根的 BCH 码就是 Reed-Solomon 码

一般的, RS 码是一个参数为 $[q-1, n-d+1, d]$ 的码,也是 MDS 码,同时 $C$ 也是多项式码

说一个好玩的事情,我们平时见到的二维码(QR code),就是一种 Reed-Solomon 码,而且工程实现还挺复杂,要涉及到二维码的分块和分层的错误率。这里给大家看一下 Wikipedia 上的介绍,


这里简单介绍了一些关于纠错码的代数理论的知识,其实还是运用到线性代数的知识多一些,而运用到抽象代数的知识相对比较少。对于代数编码这一块的知识,主要是清华大学的冯克勤老师的《纠错码的代数理论》的内容的一些摘录,甚至省略了很多的例子,有的地方看起来还是不够自然。而且,还是省略了一些内容,比如 Reed-Muller 码,MacWilliams 恒等式,以及 Goppa 码的内容,都没有介绍。

除了代数编码这一块知识,其实还有 Coding Theory: Algorithms, Architectures and Applications 中提及的一些卷积码、Turbo 码,以及冯贵良、吴新文编写的《代数几何码》中提到的代数几何码(A-G 码),属于比较难的内容了。

代数编码这里的知识其实比较琐碎,精力所限,也就只能总结这么多了。立一个小小的 flag,以后要学习学习代数几何,再来啃代数几何码。