信號與編碼原理（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）之所在。