線性碼

編碼理論中，線性碼是一種糾錯碼，滿足其任何碼字的線性組合也是其碼字。傳統上，線性碼分為分組碼和卷積碼兩大類，儘管渦輪碼可以看作是這兩種類型的混合。線性碼的編碼和解碼可以有比其他碼更有效的演算法（參見伴隨式解碼）。

線性碼用於前饋糾錯，用於在通信信道上傳輸符號（例如，比特），以使在通信中出現錯誤時，消息塊的接收者可以糾正或檢測到一些錯誤。線性分組碼的碼字是一種符號塊，這種符號塊使用比要發送的原始值更多的符號進行編碼。

$N - K$

$K$

長度為n的線性碼傳輸包含n個符號的塊。例如，7,4,3漢明碼是一種線性二進位碼，使用7位碼字表示4位消息。兩個不同的碼字至少有三位不同。因此，每個碼字最多可以檢測到兩個錯誤，同時可以糾正一個錯誤。此代碼包含 24=16個碼字。

## 定義和參數

長度為n且維度為k的線性碼是向量空間$\mathbb{F}_q^n$中維度為k的線性子空間C，其中$\mathbb{F}_q$是具有q個元素的有限域。這樣的線性碼稱為q-ary碼。如果q=2或q=3，則分別稱其為二進位碼、三進位碼。C中的向量稱為碼字。線性碼的大小是指碼字的數量，即qk。

碼字的權重（weight）是碼字中非零元素的個數，兩個碼字之間的距離（distance）是指它們之間的漢明距離，即它們之間不同的元素個數。線性碼的距離d是其非零碼字的最小權重，其等效於不同碼字之間的最小距離。長度為n、維度為k、距離為d的線性碼稱為n, k, d碼（或更準確地說，$[n,k,d]_q$碼）。

我們希望賦予$\mathbb{F}_q^n$標準基，因為每個向量坐標代表一個「比特」，該「比特」通過「噪聲信道」傳輸，並且以小機率存在一些傳輸錯誤（二進位對稱信道）。如果使用其他基，則無法使用該模型，並且漢明度量不能像我們所希望的那樣測量傳輸中的錯誤數量。

## 生成矩陣和校驗矩陣

作為$\mathbb{F}_q^n$的線性子空間，整個線性碼組C （可能非常大）可以表示為一組長度為$k$的碼字（在線性代數中稱為基）的線性組合。這些基碼字通常被整理成矩陣G的行，該矩陣稱為碼C的生成矩陣。當G具有分塊矩陣形式$\boldsymbol{G} = [I_k \mid P]$（其中$I_k$表示$k \times k$單位矩陣，P是$k \times (n-k)$矩陣）時，我們稱G具有標準形式。

表示線性函數$\phi : \mathbb{F}_q^n\to \mathbb{F}_q^{n-k}$，核為C的矩陣H稱為C的校驗矩陣（有時也稱奇偶校驗矩陣）。上述表述等價於H是一個零空間為C的矩陣。設C是一個碼組，其生成矩陣G為標準形式，則$\boldsymbol{G} = [I_k \mid P]$，則$\boldsymbol{H} = [-P^T \mid I_{n-k} ]$是C的校驗矩陣。由H生成的碼稱為C的對偶碼。可以驗證G是$k \times n$矩陣，而H是$(n-k) \times n$矩陣。

線性保證碼字c0與任何其他碼字c≠c0之間的最小漢明距離d與c0無關。這從以下性質可以看出：C中兩個碼字的差c−c0也是一個碼字（即子空間C的一個元素），且d ( c ,c 0 ) = d ( c−c0 ,0)。由上述性質可得

$$\min_{c \in C,\ c \neq c_0}d(c,c_0)=\min_{c \in C,\ c \neq c_0}d(c-c_0, 0)=\min_{c \in C,\ c \neq 0}d(c, 0)=d.$$

換而言之，為了找出線性碼的碼字之間的最小距離，只需要查看非零碼字。具有最小權重的非零碼字與零碼字的距離最小，從而決定了代碼的最小距離。

線性碼C的距離d也等於校驗矩陣H的線性相關列的最小數量（列向量最小線性無關組的秩）。

證明:因為 $\boldsymbol{H} \cdot \boldsymbol{c}^T = \boldsymbol{0}$, 等價於$\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \boldsymbol{0}$，其中 $\boldsymbol{H_i}$ 是$\boldsymbol{H}$的第$i$列。除去使$c_i=0$的項，使$c_i \neq 0$的$\boldsymbol{H_i}$線性相關。是故，$d$不小於線性相關的列的最小個數。又，考慮線性相關列的最小集 $\{ \boldsymbol{H_j} \mid j \in S \}$，其中$S$是列指標的集合。$\sum_{i=1}^n (c_i \cdot \boldsymbol{H_i}) = \sum_{j \in S} (c_j \cdot \boldsymbol{H_j}) + \sum_{j \notin S} (c_j \cdot \boldsymbol{H_j}) = \boldsymbol{0}$。考慮滿足$j \notin S$時候$c_j'=0$的向量$\boldsymbol{c'}$。注意到由於$\boldsymbol{H} \cdot \boldsymbol{c'}^T = \boldsymbol{0}$，$\boldsymbol{c'} \in C$，是故，有$d \le wt(\boldsymbol{c'})$，後者是 $\boldsymbol{H}$之中線性相關的行的最小數目。上述性質得證。

## 示例：漢明碼

漢明碼在數字通信系統中得到了廣泛的應用。對於任何正整數$r \ge 2$，存在一個$[2^r-1, 2^r-r-1,3]_2$漢明碼。由於$d=3$，此類漢明碼可以糾正1位錯誤。

例：具有以下生成矩陣和奇偶校驗矩陣的線性分組碼是$[7,4,3]_2$漢明碼。

$\boldsymbol{G}=\begin{pmatrix} 1& 0& 0& 0& 1& 1& 0 \\ 0& 1& 0& 0& 0& 1& 1 \\ 0& 0& 1& 0& 1& 1& 1 \\ 0& 0& 0& 1& 1& 0& 1 \end{pmatrix} ,$ $\boldsymbol{H}=\begin{pmatrix} 1& 0& 1& 1& 1& 0& 0 \\ 1& 1&\ 1& 0& 0& 1& 0 \\ 0& 1& 1& 1& 0& 0& 1 \end{pmatrix}$

## 示例：阿達馬碼

阿達馬碼是$[2^r, r, 2^{r-1}]_2$線性碼，能夠糾正諸多誤碼。阿達馬碼可以逐列構建：第$i$列是整數$i$的二進位表示，如下例所示。阿達馬碼的最小距離為$2^{r-1}$，因此可以糾正$2^{r-2}-1$錯誤。

例：具有以下生成矩陣的線性分組碼是$[8,3,4]_2$阿達瑪碼： $\boldsymbol{G}_\mathrm{Had}=\begin{pmatrix} 0& 0& 0& 0& 1&\ 1&1& 1\\ 0& 0& 1& 1& 0& 0& 1& 1\\ 0& 1& 0& 1& 0& 1& 0& 1\end{pmatrix}$。

阿達馬碼是里德-穆勒碼的一個特例。如果我們從$\boldsymbol{G}_\mathrm{Had}$中抽出第一列（全零列），我們可以得到$[7,3,4]_2$單純形碼，是漢明碼的對偶碼。

## 最近鄰演算法

參數d與碼的糾錯能力密切相關。以下構造/演算法說明了這一點（稱為最近鄰解碼演算法）：

輸入：接收到的$\mathbb{F}_q^n$中的向量v

輸出：在$C$中最接近$v$的一個碼字$w$（如果有）。

- 從$t=0$開始，重複以下兩個步驟。
- 枚舉（漢明）半徑為$t$，以待編碼$v$為中心的球的包含的元素，表示為$B_t(v)$。
- 對於每個$B_t(v)$中的$w$，檢查$w$是否在$C$中。如果是，則返回$w$作為解決方案。
- 增加$t$。僅當$t > (d - 1)/2$時因失敗終止。枚舉已完成，但尚未找到解決方案。

如果對於每個$\mathbb{F}_q^n$中的$v$最多有一個碼字在$B_t(v)$中，稱線性碼$C$是$t$-糾錯的。

## 常用記號

碼通常用字母C表示，長度為n且秩為k的碼（即，其基中有n個碼字，其生成矩陣中有k行）通常稱為 (n, k) 碼。線性分組碼通常表示為 n, k, d 碼，其中d表示碼中任意兩個碼字之間的最小漢明距離。

（n, k, d 符號不應與 (n, M, d)符號混淆，後者用於表示長度為n、大小為M（即具有M 個碼字）且最小漢明距離為d 的非線性碼。）

## 辛格爾頓界

引理（辛格爾頓界）：每個線性 n,k,d 碼C滿足$k+d \leq n+1$。

參數滿足k+d=n+1的代碼C稱為最大距離可分（Maximum Distance Separable）的或MDS。如果這樣的代碼存在，那麼從某種意義上來說，它們就是最好的。

設C1和C2是兩個長度為n的代碼，且對稱群Sn中存在置換p，若且唯若(cp (1) ,... , cp (n) ) 在C2中時，( c1 ,..., cn ) 在C1中，則稱C1與C2是置換等價的。更一般地，如果存在$n\times n$廣義置換矩陣$M\colon \mathbb{F}_q^n \to \mathbb{F}_q^n$使得C1同構於C2，那麼稱C1和C2是等價的。

引理：任何線性碼都等價於標準形式的碼的置換。

## 博尼索利定理

對於一個碼字，若且唯若存在某個常數d，使得該碼中任意兩個不同碼字之間的距離等於d時，其可以稱為等距碼。1984 年，阿里戈·博尼索利 (Arrigo Bonisoli) 確定了有限域上線性單重碼的結構，並證明了每個等距線性碼都是與漢明碼對偶的序列。

## 示例

線性碼的一些示例包括：

- 重複碼
- 奇偶校驗碼
- 循環碼
- 漢明碼
- 戈萊碼 (消歧義)，包括二元戈萊碼的和三元戈萊碼的
- 多項式碼（典型代表：BCH碼）
- 里德-所羅門碼
- 里德-穆勒碼
- 代數幾何碼
- 二元戈帕碼
- 低密度奇偶校驗碼
- 擴展碼
- 多維奇偶校驗碼
- 環面碼
- 渦輪碼
- 局部可恢復碼

## 推廣

在非域字母表上的漢明空間同樣受到關注，尤其是有限環上的情形，其中最顯著的是Z4上的伽羅瓦環。由此導出的是模結構而非向量空間結構，對應的環線性碼（由子模定義）取代了傳統線性碼。此類空間通常採用李氏距離作為度量。研究發現：配備漢明距離的$\mathbb{Z}_2^{2m}$ （即 GF(22m )）與配備李距離的 $\mathbb{Z}_4^m$（亦記作 GR(4,m)）之間存在格雷等距映射。該映射的核心價值在於：它能將$\mathbb{Z}_4^m$上某些環線性碼的像，對應於$\mathbb{Z}_2^{2m}$上具有優良性質卻非線性的編碼。

有些作者也將環上的此類碼簡稱為線性碼。

## 參考文獻

### 參考書目

- Chapter 5 contains a more gentle introduction (than this article) to the subject of linear codes.

## 外部連結

- q-ary code generator program
- Code Tables: Bounds on the parameters of various types of codes, IAKS, Fakultät für Informatik, Universität Karlsruhe (TH). Online, up to date table of the optimal binary codes, includes non-binary codes.
- The database of Z4 codes Online, up to date database of optimal Z4 codes.