信号与编码原理（2）

对于一段给定的信号，比如数字化后的一段文字，我们先把它划分为等长的k维向量，（x1, x2, …, xk）；其中，每个xi的值来自于一个有限域GF(q) (或称Galois域，q为某个质数的幂；通常取q = 2)，也可以是一个矩阵，SL（2，C）中的一个元素（或称为一个量子）。这样，可以表出q^k 或 16^k 个码字。

码字在传输过程中可能会受到各种干扰（比如噪声）。在二元对称通道中，它可能把0变为1，或者1变为0（传送错误，概率为p < ½）。人们想到了增加校验元y1, y2, …, yr，组成一个长度为k + r = n的向量：（x1, x2, …, xk, y1, y2, …, yr）=：（c1，c2，…, cn）= C, 要求它满足r个方程式：Ej(c1, c2, …, cn) = 0, j = 1, 2, …, r。当收到一个码字（e1, e2, …, en）时，可以逐个检查这r个方程，只要有一个不满足，那么，所收到的码字就出错了。

假设发送的码字是（c1，c2，…, cn）, 差错模式就是 (e1 – c1, e2 – c2, …, en – cn) = R：非零的位置即是出错之处。出现m个错误的概率是p^m (1 – p)^(n – m)；由于p < ½, 此数列对于m是单调减少的；出现m个错误的概率大于出现m + 1个错误的概率，所以我们自然是去找概率最大的那个可能，也就是最小的m值。因此，在所有可能的q^k个码字中，找出与（e1, e2, …, en）最接近的那一个。如果有多个最接近的话，那就要控制译码错误的概率。

纠错编码理论的一个主要目的就是要找到一种比逐个对照更快的译码方法，而这主要取决于校验位的设计。如果每个yj都是 (x1, x2, …, xk) 的线性函数，我们就得到了一个线性码；所有码字的集合是（GF(q)）^n 的一个k维子空间，含有q^k个向量。每一个码字都可以表示为 (c1, c2, …，cn）=（x1, x2,…，xk）G，ｘi∈F_q, 其中G= （I，A）是一个k * n矩阵，称为生成矩阵。以方程组GX = 0的r = n - k个线性无关的解向量为行，构造一个r×n矩阵H，则有GH^T= 0，Ｈ称为码的校验矩阵：C =（c1, c2, …，cn）的充要条件是 CH^T = 0.

设H的任意t列均线性无关，但某t + 1列线性相关；则此码可以纠正不超过t/2 个错误。事实上，假设在某次传送过程中，发送的字为 C =（c1, c2,…，cn），但由于干扰而出现差错，收到的字是 B =（b₁, b₂, …，b_n），向量 R= B－C 就是差错模式；Ｒ中非零分量的个数称为Ｒ的重量，记为ω(R), 这实际上就是出现差错的个数。如果差错的个数≤t/2，则在所有重量≤t/2的差错模式Ｒ中，存在唯一的R0_，使B－R0为码字：若还有R1满足ω(R1) ≤ t/2，使B－R0和 B－R1都属于Ｃ，则由（B－R0）H^T＝０和（B－R1）H^T＝０可得（R1－R0）H^T＝０。又因为 ω（R1－R0）≤ω(R1) + ω(R0) ≤ t，而H的任意t列均线性无关，故有R1－R0＝０。

在线性码中，一个码字的（Hamming）w(C)重量定义为其非零分量的个数（在二进制码中，就是1的个数）。两个不同码字X，Y之间的距离定义为其差的重量w(X – Y)。码集中所有码对距离的最小值，就称为码间距d。因为码集是子空间，d就是所有非零码字的最小重量。当d为奇数时，此码可以纠正(d – 1)/2个错误；当d为偶数时，它可以纠正1/2 d – 1 个错误，检测d/2个错误。

事实上，如果d = 2h + 1, 码空间中以任一码字为中心、h为半径的球都没有交集，所以，当差错个数不超过h时，总可以找出唯一的那个码字。如果d = 2h + 2, 半径为h的球都互不相交；如果所收到的码字中出现了h + 1个错，它可能位于两个球的正中央：我们知道出错了，但不能确定是哪一个球心。

纠错编码理论的另一个目的是，给定码间距d的值，要获取尽可能多的码字；这就需要非线性码。能纠正2个错、长度为11的线性码最多有16个码字；而同样的非线性码可达24个码字。第二种构造校验元的方法是用布尔函数（只对二元码），即每个yj都是x1, x2, …, xk的次数不超过m的多项式：x1^a1 … xk^ak，ai = 0 或1, a1 + … + ak ≤ m. 当m=1时，还是线性码；当m>1时，如果选取所有的、次数不超过m的k元单项式（1次除外）作为校验元，就得了Reed-Muller码。

为了计算码字的个数，先要给码集分类。一个码长为n、码间距为d、含有最多M个码字的二元码集，记为一个 (n, M, d) 码; 也可以说，给定n和M，d达到最大。两个码集称为是等价的，如果一个集中的每一个码字都可以通过另一集中的某个码字通过分量下标的一个置换、再加一个向量平移而得到。

为了估计M的最大值，我们引入生成函数、重量分布与距离分布。一个码集?的生成函数是级数?{t^w(C): C 遍历码集中的所有码字，w(C)为码字C的重量，t为形式变量} ；它也等于? {Ai*t^i: Ai 是重量为i的码字的个数} 。显然，M就是此式当t = 1的值。用两种不同方法计算dist(C, D) 之和，C，D遍历所有码字，可以得出M的Plotkin上界。为了求出生成函数，公式w (C + D) = w(C) + w(D) – 2W(C*D) 是有用的，其中，C*D 是把两个码字的对应位元相乘而得到的一个新码字。然而，对于非线性码，一般的生成函数难于求出。

一个特别情形是等重码，即所有非零码字的重量都相同。如果含有全1码字，可以将其排除，称之为弱等重码。可以证明，任何线性等重码都弱等价于Walsh-Hadamard码。非线性等重码可以通过并元群、区组设计等方法去构造。一个码长为n、码间距为d、每个码字重量为w的码集，就记为（n, d, w）。在所有这些码集中，容量（码字个数）的最大值记为A（n, d, w)。我们没有A(n, d, w)的准确表达式，只有其上、下界的估计值。

这些构造码集的方法，充分体现了人类的聪明才智：在给定码长的前提下，码间距要尽可能大、码字个数又要尽可能多，这是相当困难的。如何构造新的表达式，是永无止境的。正如各种数学分析学科中一样，要探明某种性质，必须要构造出一个实体才行。这正是人的机智与独创性（Ingenuity）之所在。