2.2 線性分組碼

差錯控制編碼理論與實踐中最常用的信道編碼是定義在有限域上的碼。假設信源的輸出是有限域GF(2)上連續的二元符號序列，稱為信息序列。通常把信息序列中的二元符號稱為信息比特。在分組碼中，信息序列被劃分為固定長度的消息分組，每一個消息分組含有k個信息比特，所以一共有2k個不同的消息。在信道編碼器中，每個輸入消息u=(u0, u1, · · ·, uk-1)，其含有k個信息比特，按照一定的編碼規則被編碼成長為n的二進制序列c=(c1, c2, · · ·, cn-1)，其中n＞k。序列c稱為消息序列u的碼字。碼字中的二進制數字被稱為碼比特。因為有2k個不同的消息，對應有2k個碼字，所有碼字的集合構成一個(n, k)分組碼。其中，參數n稱為碼長，k稱為碼的維數或消息長度，由編碼器產生的n-k個添加到每個輸入消息中的比特稱為冗余比特。比率R=k/n稱為碼率，可以解釋為每一個碼比特所攜帶的平均信息比特數。

在分組碼中，最重要的一類是線性分組碼。如果一個碼C的碼字形成GF(q)上的一個向量空間，我們就說這個碼是線性碼。如果q＞2，那么稱碼C為多元或q元碼。

2.2.1 線性分組碼的定義與最小漢明距離

定義2.2 一個二元(n, k)線性分組碼C是GF(2)上所有n維向量組成的向量空間V的一個k維子空間，它包含有2k個碼字。

在任何線性碼中，都包含一個作為向量空間原點的全零碼字。

令c=(c0, c1, · · ·, cn-1)是GF(2)上的n維向量。c的漢明重量（Hamming weight）（簡稱重量），記為w(c)，它表示c中非零元素的個數。現在考慮一個碼字符號在GF(2)上的(n, k)線性分組碼C。對0≤i≤n，讓Ai表示C中漢明重量為i的碼字數。數A0, A1, · · ·, An稱為C的重量分布。顯然，A0+A1+· · ·+An=2k。由于線性分組碼里有且僅有一個全零碼字，因此A0=1。碼C的最小漢明重量，記為wmin(C)，是C中非零碼字的最小重量，即

令v和w是GF(2)上的兩個n維向量。v和w之間的漢明距離，記為d(v, w)，表示v和w相應位置元素不相同的元素個數。對于線性碼，dH(v, w)=d(0, w-v)=d(0, c)=w(c)。

(n, k)線性分組碼C的最小距離dmin(C)定義為C中兩個不同碼字之間的最小漢明距離，即

可以很容易證明，C的最小距離dmin(C)等于C的最小重量wmin(w)：

因此，對于線性分組碼，確定其最小距離就等價于確定其最小重量。一般來說，采用硬判決譯碼的糾錯性能由其最小距離決定，而采用軟判決最大似然譯碼的糾錯性能則由碼重量分布決定。

2.2.2 生成矩陣和校驗矩陣

因為一個二元(n, k)線性分組碼C是GF(2)上所有n維向量組成的向量空間的一個k維子空間，所以C中存在k 個線性獨立的碼字g0, g1, · · ·, gk-1，使得C中每個碼字c是這k個線性獨立碼字的線性組合，即

其中ui∈GF(2)。

可以把C中k個線性獨立的碼字g0, g1, · · ·, gk-1作為一個GF(2)上的k×n矩陣的行向量，表示如下：

令u=(u0, u1, · · ·, uk-1)是待編碼的消息。這個消息的對應碼字c=(c0, c1, · · ·, cn-1)可用u和G的矩陣乘積表示為

因此，消息u的碼字c是矩陣G的行向量的線性組合。矩陣G稱為(n, k)線性分組碼C的生成矩陣。

二元(n, k)線性分組碼C是GF(2)上所有n維向量組成的向量空間V的一個k維子空間。它的零空間（或對偶空間）記為Cd，是V的一個n-k維子空間：

Cd是一個二元(n, n-k)線性分組碼，稱為C的對偶碼。

通常，生成矩陣G可以經過線性變換轉化成如下的系統形式：

其中，Ik為一個k×k的單位矩陣，P為一個k ×(n-k)的矩陣，pi, j∈GF(2)。由系統矩陣G編出的碼被稱為系統碼，其中的碼字具有圖2.2所示的結構，碼字的第一部分包含k個原來的信息符號，第二部分為包含n-k個校驗符號的冗余校驗部分。如果一個線性分組碼有上述結構，那么稱它為線性系統碼（linear systematic code）。

令u=(u0, u1, · · ·, uk-1)是一個待編碼的消息。根據式(2.11)和式(2.13)，可得到對應的系統碼字：

其中n個碼比特為

及

式(2.15)表示碼字c最左邊的k個碼比特與k個待編碼的信息比特u0, u1, · · ·, uk-1是完全一致的。式(2.16)表示c最右邊的n-k個碼比特是信息比特的線性組合。這n-k個由信息比特線性求和得到的碼比特稱為一致校驗比特（簡稱校驗比特）。由式(2.16)給出的n-k個等式稱為碼的校驗方程。式(2.13)的生成矩陣形式稱為系統形式。

除上述的定義方法之外，一個(n, k)線性分組碼C還可以由其校驗矩陣H完全定義。假定H的維數是m，其中m≥n-k。矩陣G和H的關系為

當且僅當c · HT=0（n-k維全零向量）時，二進制n維向量c∈V是C中的碼字，即

H稱為C的校驗矩陣，C稱為H的零空間（null space）。因此，一個線性分組碼可以由兩個矩陣唯一確定，即生成矩陣和校驗矩陣。后面介紹的LDPC碼通常是基于校驗矩陣定義的，而Polar碼是基于生成矩陣定義的。如果線性分組碼的校驗矩陣H的秩和它的行數相等，那么就說其是滿秩的。但是在很多情況下，(n, k)線性分組碼的校驗矩陣并不是滿秩的，即它的行數大于其行秩n-k。在這種情況下，校驗矩陣H的一些行是n-k個線性獨立的行的線性組合。這些額外的行稱為冗余行。我們將在第3章介紹LDPC碼，它的校驗矩陣不一定是滿秩的。

如果(n, k)線性分組碼C的生成矩陣是形如式(2.13)的系統形式，那么對應的系統形式的校驗矩陣如下。

很容易證明G·HT=0。有些文獻中，將系統形式的生成矩陣表示為G=[P Ik]，則對應的校驗矩陣為H=[In-kP T]。一般二元線性分組碼的H矩陣是GF(2)上的(n-k)×n矩陣：

例2.1 令n=7, k=4，考慮系統形式的(7,4)線性分組碼。消息向量u=(u0, u1, u2, u3)，碼字c=(c0, c1, c2, c3, c4, c5, c6)=(u0, u1, u2, u3, c4, c5, c6)。系統形式的生成矩陣和校驗矩陣為

這樣，分組碼。

2.2.3 對一個線性碼簡單修改而構造新碼

假定C是一個已有的(n, k)線性分組碼，可以對其進行簡單修改而得到一個新碼。這些方法很簡單，但很實用，在編碼系統設計中經常用到。

（1）擴展碼（extending a code）：通過對C中的碼字增加校驗符號而增加碼長（或者說獲得碼長更長的新碼），這對應于增加生成矩陣的列。例如，對Hamming碼增加一個全校驗位就得到擴展Hamming碼。

（2）刪余碼（puncturing a code）：通過將C中碼字的一些校驗符號刪去（或者說進行打孔）而減少碼長，從而得到碼率更高的碼。這對應于刪掉生成矩陣的列。

（3）縮短碼（shortening a code）：通過扔掉一些數據符號而減少碼長，這對應于刪去校驗矩陣的列或者說減少生成矩陣的維數。新碼的碼率為。扔掉的數據符號一般是固定取值的，從而收發雙方已知。

（4）增余刪信碼（expurgating a code）：它是在原碼基礎上，刪去一些數據符號而同時增加校驗符號，從而碼長不改變，但顯然碼率會降低，這對應于刪去生成矩陣的行。一個增余刪信碼是原碼的子碼。