5.4.6 码

5.4.6.1 控制数字

在信息论方法中提供了数据组合误差的识别和纠正方法. 一些最简单的方法可以表示为下列控制数字的形式.

1. 国际标准书号 ISBN-10

数的同余的一个简单应用是将控制数字用于国际标准书号 ISBN. 对一本书设定一个形式为

$$\begin{array}{}\text{(5.263a)}& \text{ISBN a-bcd-efghi-p}\end{array}$$

的 10 个数字的组合. 这些数字有下列意义: $a$ 是组号 (例如, $a=3$ 告诉我们出版物国家为奥地利、德国或瑞士), bcd 是出版社号, 而 efghi 是这家出版社确定的书名号. 添加控制数字 $p$ 用来检测错误的书号从而有助于减少开支. 控制数字 $p$ 是满足下列同余式的最小的非负数字:

$$\begin{array}{}\text{(5.263b)}& 10a+9b+8c+7d+6e+5f+4g+3h+2i+p\equiv 0\left(11\right).\end{array}$$

若控制数字 $p$ 是 10,则应用一元符号例如 $\mathrm{X}$ (还可参见第 513 页 5.4.6.1,3.). 现在提供的 ISBN 可以检验含在 ISBN 中的控制数字和由所有其他数字确定的控制数字的匹配. 在不匹配的情形一定有错误. ISBN 控制数字方法可以发现下列差错:

(1) 单个数字错误;

(2) 两个数字互换.

统计研究表明用这个方法可以检测出 $90\mathrm{\%}$ 以上的真实错误. 所有其他观察到的错误类型的相对频率小于 $1\mathrm{\%}$ . 在多数情形中上述方法可以发现两个数字或两个完整的数字段的互换.

2. 药品和医学中的中心码

在医药学中, 一个类似的控制数字数值系统被用来验证药物. 在德国, 每个药品都设定一个 7 数字控制码:

$$\begin{array}{}\text{(5.264a)}& \text{abcdefp.}\end{array}$$

最后一个数字是控制数字 $p$ . 它是满足同余式

$$\begin{array}{}\text{(5.264b)}& 2a+3b+4c+5d+6e+7f\equiv p\left(11\right)\end{array}$$

的最小的非负数字. 在这里可发现单个数字差错或两个数字互换.

3. 账号

银行和储蓄所应用为至多 10 位数字 (这取决于营业额) 的统一的账号. 第一个 (至多 4 个) 数字用于账号的分类. 其余 6 个数字表示实际的账号, 其中包括最末位的控制数字. 个别银行和储蓄所倾向于应用不同的控制数字方法, 例如:

a) 从最右边的数字开始交错地用 2 或 1 乘各个数字. 然后取控制数字 $p$ ,使得它与这些积相加得到的新和是一个 (与原和) 最接近的能被 10 整除的数. 若给出含控制数字 $p$ 的账号 abcde fghip,则同余式

$$\begin{array}{}\text{(5.265)}& 2i+h+2g+f+2e+d+2c+b+2a+p\equiv 0\left(\mathrm{mod}10\right)\end{array}$$

成立.

b) 同方法 a), 但首先将两位数的积换成这两个数字的和, 然后计算总和.

在情形 a), 所有由相邻数字的互换以及几乎所有单个数字所引起的差错都可被发现.

但在情形 b), 所有由一个数字的改变以及几乎所有由于两个相邻数字的互换所引起的差错都可被发现. 这是由于两个非相邻数字的互换以及两个数字的改变所引起的差错常常不能被发现.

不应用能力更强的模 11 控制数字方法是出于非数学性的原因. 非数值符号 X(用来代替控制数字 10(参见第 512 页 5.4.6.1, 1.)要求扩充数值键盘. 但放弃控制数字为 10 的那些账号将在相当多的情形防碍原账号的平稳扩充.

4. 欧洲论文编号 EAN

EAN 用于欧洲论文编号. 在多数论文中可以发现它是一个含 13 或 8 个数字的条码或字符. 条码可以借助计算器上的扫描仪读出. 在 13 个数字符的情形, 前两个数字表示来源国, 例如, 40, 41, 42 以及 43 用于德国. 接着的 5 个数字表示作者, 再下面 5 个数字表示特别的成果. 最后的数字是控制数字 $p$ .

这个控制数字是这样得到的: 首先将字符的所有 12 个数字从最左一个开始交错地乘以 1 和 3,然后将所有的积相加,最后加上 $p$ ,得到最接近的能被 10 整除的数. 若给出含控制数字 $p$ 的论文号 abcde $f$ ghikmn $p$ ,则同余式

$$\begin{array}{}\text{(5.266)}& a+3b+c+3d+e+3f+g+3h+i+3k+m+3n+p\equiv 0\left(\mathrm{mod}10\right)\end{array}$$

成立. 这个控制数字方法总可以发现 EAN 中的单个数字差错, 并且常常能发现两个相邻数字的交换. 通常不能发现两个非相邻数字的交换以及两个数字的改变.

5.4.6.2 纠错码

1. 数据传输和差错纠正模型

在通过噪声信道传输信息时差错纠正常常是可能的. 首先将信息进行编码, 然后将传输后通常的有偏倚的码纠正为正确的码, 于是将它们译出就可重新得到原来的信息. 我们现在考虑这种情形: 信息的字长是 $k$ ,码字长为 $n$ ,并且它们都仅由 0 和 1 组成. 那么 $k$ 是信息位置的个数,而 $n-k$ 是冗余位置的个数. 每个信息字是 $\mathrm{GF}{\left(2\right)}^k$ 的元素 (参见第 486 页 5.3.7.4),而每个码字是 $\mathrm{GF}{\left(2\right)}^n$ 的元素. 为简化记号,信息字写作 $a_1,a_2,\cdots ,a_k$ 形式,码字写成 $c_1,c_2,\cdots ,c_n$ 形式. 信息字不被传送, 只有码字被传输.

通常使用的纠错思想是首先将要传输的字 $d_1,d_2,\cdots ,d_n$ 转换为有效的码字 $c_1,c_2,\cdots ,c_n$ ,它与要传输的字相差的数字个数最小 (译码 MLD). 这种方法能发现和纠正多少差错取决于编码及传输信道的性质.

在数字重复的码中信息字 0 用码字 0000 表示. 如果传输后接受者得到字 0010 , 那么他假设原来的码字是 0000 , 并且将他译为信息字 0 . 但如果接受到的字是 1010 , 那么类似的假设可以不被采用, 因为信息字 1 被译作 1111, 从而差别是类似的. 至少可以辨认在收到的字中存在某个差错.

2. $t$ 纠错码

所有码字的集合称为码 $\mathcal{C}$ . 两个码字的距离是指这种数字位置的个数,在其上两个码字有不同的数字. $\mathcal{C}$ 的码字间距离中的最小值称为码的最小距离 $d_{min}\left(\mathcal{C}\right)$ .

对于 ${\mathcal{C}}_1=\{0000,1111\},d_{min}\left({\mathcal{C}}_1\right)=4$ . 对于 ${\mathcal{C}}_2=\{000,011,101,110\},d_{min}\left({\mathcal{C}}_2\right)=$ 2,因为存在距离是 2 的两个码字. 对于 ${\mathcal{C}}_3=\{00000,01101,10111,11010\}$ , $d_{min}\left({\mathcal{C}}_3\right)=3$ ,因为 ${\mathcal{C}}_3$ 中存在距离是 3 的两个码字.

如果已知码 $\mathcal{C}$ 的最小距离 $d_{min}\left(\mathcal{C}\right)$ ,那么容易判断有多少个传输差错可被纠正. 可纠正 $t$ 个差错的码称为 $t$ 纠错码. 如果 $d_{min}\left(\mathcal{C}\right)\ge 2t+1$ ,那么 $\mathcal{C}$ 是 $t$ 纠错码. (续) ${\mathcal{C}}_1$ 是 1 纠错码, ${\mathcal{C}}_2$ 是 0 纠错码 (这意味着不能纠错), ${\mathcal{C}}_3$ 是 1 纠错码.

对于每个 $t$ 纠错码 $\mathcal{C}\subseteq \mathrm{GF}{\left(2\right)}^n$ 有 $\sum _{i=0}^t\left(\begin{array}{c}n\\ i\end{array}\right)\cdot \left|\mathcal{C}\right|\le 2^n$ . 如果等式成立,那么 $\mathcal{C}$ 称为 $t$ -完全码.

数字重复码 $\mathcal{C}=\{00\cdots 0,11\cdots 1\}\subseteq \mathrm{GF}{\left(2\right)}^{2t+1}$ 是 $t$ -完全码.

3. 线性码

如果非空子集 $\mathcal{C}\subseteq \mathrm{GF}{\left(2\right)}^n$ 是 $\mathrm{GF}{\left(2\right)}^n$ 的子向量,那么 $\mathcal{C}$ 称为(二元) 线性码. 如果线性码 $\mathcal{C}\subseteq \mathrm{GF}{\left(2\right)}^n$ 有维数 $k$ ,那么它称作(n, k)线性码.

(续) ${\mathcal{C}}_1$ 是(4,1)线性码, ${\mathcal{C}}_2$ 是(3,2)线性码, ${\mathcal{C}}_3$ 是(5,2)线性码. 在线性码的情形, 极小距离 (以及作为推论, 可纠差错的个数) 容易确定: 这样一个码的极小距离是向量空间中的零向量与非零向量间的最小距离. 如果给出各码字 (除全为零的码字) 中 1 的最小个数, 就可求得极小距离.

对于每个(n, k)线性码存在生成矩阵 $\mathbf{G}$ 使得 $\mathcal{C}=\left\{a\mathbf{G}\mid a\in \mathrm{GF}{\left(2\right)}^k\right\}$ :

$$\begin{array}{}\text{(5.267)}& \mathbf{G}={\left(\begin{array}{ccc}{g}_{11}& \cdots & g_{1n}\\ ⋮& & ⋮\\ g_{k1}& \cdots & g_{kn}\end{array}\right)}_{k\times n}=\left(\begin{array}{c}{g}_1\\ ⋮\\ g_k\end{array}\right).\end{array}$$

码由生成矩阵唯一确定; 信息字 $a_1{a}_2\cdots a_k$ 的码字用下列方式确定:

$$\begin{array}{}\text{(5.268)}& a_1{a}_2\cdots a_k\mapsto \underset{a\mathbf{G}}{\underbrace{a_1{g}_1+a_2{g}_2+\cdots +a_k{g}_k}}.\end{array}$$

在(n, k)线性码 $\mathcal{C}$ 的情形,为了译码需要校验矩阵:

$$\begin{array}{}\text{(5.269)}& \mathbf{H}={\left(\begin{array}{ccc}{h}_{11}& \cdots & h_{1n}\\ ⋮& & ⋮\\ h_{n-k,1}& \cdots & h_{n-k,n}\end{array}\right)}_{\left(n-k\right)\times n}.\end{array}$$

如果 $\mathbf{H}$ 的行是两两不同的非零向量,那么 (二元) 线性码 $\mathcal{C}$ 是 1 纠错码. 如果传输的结果是字 $d=d_1{d}_2\cdots d_n$ ,那么算出 $\mathbf{H}{d}^{\mathrm{T}}$ . 如果结果是零向量,那么 $d$ 是一个码字. 不然,如果 $\mathbf{H}{d}^{\mathrm{T}}$ 是校验矩阵 $\mathbf{H}$ 的第 $i$ 行,那么对应的码字是 $d+e_i$ ,其中 $e_i=\left(0,\cdots ,0,1,0,\cdots ,0\right)$ ,并且 1 在第 $i$ 个位置.

4. 循环码

循环码是研究得最多的线性码. 它们提供有效的编码和译码. 一个 $\left(\text{二元})(n,k\right)$ 线性码称作循环码,如果对于每个码字 $c_0{c}_1\cdots c_{n-1}$ 通过将分量右向循环移位也得到一个码字,即 $c_0{c}_1\cdots c_{n-1}\in \mathcal{C}\Rightarrow c_{n-1}{c}_0{c}_1\cdots c_{n-2}\in \mathcal{C}$ .

$\mathcal{C}=\{000,110,101,011\}$ 是一个循环(3,2)线性码.

为了有效地使用循环码,码字是通过次数 $\le n-1$ 的系数属于 $\mathrm{GF}\left(2\right)$ 的多项式表示的.

$\left(\mathrm{二}\text{元}\right)\left(n,k\right)$ 线性码 $\mathcal{C}$ 是循环的,当且仅当对于每个 $c\left(x\right)$ :

$$\begin{array}{}\text{(5.270)}& c\left(x\right)\in \mathcal{C}\Rightarrow c\left(x\right)\cdot x\left(\mathrm{mod}{x}^n-1\right)\in \mathcal{C}.\end{array}$$

循环(n, k)线性码可以用生成多项式和控制多项式刻画如下: $n-k(k\in \{1$ , $2,\cdots ,n-1\})$ 次生成多项式 $g\left(x\right)$ 是 $x^n-1$ 的一个因子. 满足 $g\left(x\right)h\left(x\right)=x^n-1$ 的 $k$ 次多项式 $h\left(x\right)$ 称为控制多项式. 在多项式表示 $a\left(x\right)$ 下 $a_1{a}_2\cdots a_k$ 的编码由

$$\begin{array}{}\text{(5.271)}& a\left(x\right)\mapsto a\left(x\right)\cdot g\left(x\right)\end{array}$$

给出. 如果生成多项式 $g\left(x\right)$ 是 $d\left(x\right)$ 的因子,或者控制多项式 $h\left(x\right)$ 满足关系式 $d\left(x\right)h\left(x\right)\equiv 0\left(\mathrm{mod}{x}^n-1\right)$ ,那么多项式 $d\left(x\right)$ 是码中的一个元素.

一类重要的循环码是 $\mathrm{BCH}$ 码. 在此可以对极小距离的下界 $\delta$ 以及码能够用它来纠正的差错的个数的下界提出要求. 其中 $\delta$ 称作码的设计距离.

一个 $\left(-\text{元}\right)\left(n,k\right)$ 线性码 $\mathcal{C}$ 是 $\mathrm{BCH}$ 码,如果对于生成多项式 $g\left(x\right)$ 有

$$\begin{array}{}\text{(5.272)}& g\left(x\right)=\mathrm{lcm}\left(m_{{\alpha }^b}\left(x\right),m_{{\alpha }^{b+1}}\left(x\right),\cdots ,m_{{\alpha }^{b+\delta -2}}\left(x\right)\right),\end{array}$$

其中 $\alpha$ 是本原 $n$ 次单位根, $b$ 是一个整数. 多项式 $m_{{\alpha }^j}\left(x\right)$ 是 ${\alpha }^j$ 的极小多项式.

对于极小距离为 $\delta$ 的 $\mathrm{BCH}$ 码 $\mathcal{C}$ 关系式 $d_{min}\left(\mathcal{C}\right)\ge \delta$ 必定成立.