線性分組編碼

在通信中，由於信息碼元序列是一種隨機序列，接收端無法預知碼元的取值，也無法識別其中有無錯碼。所以在發送端需要在信息碼元序列中增加一些差錯控制碼元，它們稱為監督碼元（校驗元）。這些監督碼元和信息碼元之間有確定的關係。

在信息碼元序列中加監督碼元就稱為差錯控制編碼，差錯控制編碼屬於信道編碼。

信息碼元和監督碼元之間有一種關係，關係不同，形成的碼類型也不同。可分為兩大類：分組碼和卷積碼。其中，分組碼是把信息碼元序列以每k個碼元分組，編碼器將每個信息組按照一定規律產生r個多餘的碼元（稱為校驗元），形成一個長為n=k+r的碼字。

當分組碼的信息碼元與監督碼元之間的關係為線性關係時（用線性方程組聯繫），這種分組碼就稱為線性分組碼。包括漢明碼和循環碼。

對於長度為n的二進制線性分組碼，它有種可能的碼字，從中可以選擇M=個碼字（k<n）組成一種編碼，其中碼字稱為許用碼字，其餘碼字稱為禁用碼字。這樣，一個k比特信息可以映射到一個長度為n的碼組中，該碼字是從M個碼字構成的碼字集合中選出來的，剩下的碼字即可以對這個分組碼進行檢錯或糾錯。

在線性分組碼中，兩個碼字對應位上數字不同的位數稱為碼字距離，簡稱距離，又稱漢明距離。

編碼中各個碼字間距離的最小值稱為最小碼距d，最小碼距是衡量碼組檢錯和糾錯能力的依據，其關係如下：

（1）為了檢測e個錯碼，則要求最小碼距d>e+1;

（2）為了糾正t個錯碼，則要求最小碼距d>2t+1;

（3）為了糾正t個錯碼，同時檢測e個錯碼，則要求最小碼距d>e+t+1,e>t。

線性分組碼是建立在代數羣論基礎上的，各許用碼字的集合構成了代數學中的羣，它們的主要性質如下：

（1）任意兩許用碼字之和（對於二進制碼這個和的含義是模二和）仍為一個需要碼字，也就是説，線性分組碼具有封閉性；

（2）碼字間的最小碼距等於非零碼的最小碼重。

由於碼字空間C是n維數二元線性空間中的一個k維子空間，由線性代數理論可知，

是由“1”或“0”元素組成的矩陣，它的k個行就是線性獨立矢量，，，。

矩陣G稱為線性碼C的生成矩陣。公式（1.1）建立了信息空間到碼字空間的線性映射。

經過行變換和列變換的矩陣生成的線性空間與原來的矩陣生成的線性空間是等價的，也就是説生成矩陣經過初等變換之後，所生成的碼與原來的碼是等價的。由此可以將生成矩陣經過變換之後，形成系統生成矩陣（即產生的碼中，信息碼元在碼字的高位部分，而校驗碼元在碼字的低位部分）。即

這也表示由G的行矢量所擴張成的k維子空間與H矩陣行矢量所擴張成的r維子空間是正交的。

G與H中只要有一個確定，另一個就是可以確定的。只要校驗矩陣給訂=定，校驗碼元和信息碼元之間的關係就完全確定了。

下面是一個（7,3）線性分組碼，有信息組(m₂m₁m₀),信息組在碼字的前部，即：

生成矩陣為

信息組和對應的碼字由表3.1給出。

則其校驗矩陣為

設(n,k)線性分組碼，生成矩陣為G，校驗矩陣H，發送端送出的碼字為：

C=(cn－1 cn－2 …c1c0)

接收端收到的碼字為：

R=(rn－1 rn－2…r1 r0)

由於信道噪聲的干擾為：

R=E+C

E為傳輸過程中由於干擾而疊加在C上的錯誤圖樣。

E=(en－1 en－2…e1 e0)

其中

接收端可以用H矩陣來進行檢驗，檢驗運算的結果為伴隨式S。

可見，由於CHT=0，因此伴隨式(或稱校驗因子)S只和E有關。

本節所舉的(7,3)碼，最小碼距為4，可糾正一位錯同時檢二位錯。

（1）糾一位錯

設E=(0100000)，即C5的位置出錯，則有：

S正好為H中對應C5位置的一列，可見是C5出錯，即可糾正。

（2）檢兩位錯

設E=(0110000)，即C5C4出錯，則有：

S不等於0，表示有錯，但它又不等於H中的任一列，所以能檢二位錯，但不能糾正。

（3）三位錯

設E=(0111000)，即C5C4C3同時出錯，則有：

S不等於0，表示有錯，但S卻是H中對應於C0的一列，於是判斷C0出錯，造成錯糾。因此該(7,3)線性碼只能糾一位錯，檢兩位。在有三位出錯時，就會產生錯糾。但如果只用於檢錯，則可檢三位錯。

所以，當S0時，即可判斷R不是碼字，即有錯。當S=0時，按收方就認為R是對方發送的碼字C。但是需要指出的是如果E恰好等於碼字集中7個非零碼字中的一個，即：

R=C+E

E為另一碼字，二個碼字之和，必然為一碼字，從而有：

RHT=0

這種類型的錯誤圖樣稱為不可檢錯誤圖樣。由於有2k－1個非零碼字，所以有2k－1個不可檢錯誤圖樣。