線性碼

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

線性碼用於前饋糾錯，用於在通信信道上傳輸符號（例如，比特），以使在通信中出現錯誤時，消息塊的接收者可以糾正或檢測到一些錯誤。線性分組碼的碼字是一種符號塊，這種符號塊使用比要發送的原始值更多的符號進行編碼。^[3]長度為n的線性碼傳輸包含n個符號的塊。例如，[7,4,3]漢明碼是一種線性二進制碼，使用7位碼字表示4位消息。兩個不同的碼字至少有三位不同。因此，每個碼字最多可以檢測到兩個錯誤，同時可以糾正一個錯誤。^[4]此代碼包含 2⁴=16個碼字。

定義和參數

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

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

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

生成矩陣和校驗矩陣

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

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

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

${\displaystyle \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的線性相關列的最小數量（列向量最小線性無關組的秩）。

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

示例：漢明碼

主條目：漢明碼

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

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

${\displaystyle {\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}},}$ ${\displaystyle {\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}}}$

示例：阿達馬碼

主條目：阿達馬碼（英語：Hadamard code）

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

例：具有以下生成矩陣的線性分組碼是${\displaystyle [8,3,4]_{2}}$阿達瑪碼： ${\displaystyle {\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}}}$ 。

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

最近鄰算法

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

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

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

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

如果對於每個${\displaystyle \mathbb {F} _{q}^{n}}$中的${\displaystyle v}$最多有一個碼字在${\displaystyle B_{t}(v)}$中，稱線性碼${\displaystyle C}$是${\displaystyle 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滿足${\displaystyle k+d\leq n+1}$ 。

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

設C₁和C₂是兩個長度為n的代碼，且對稱群S_n中存在置換p _，若且唯若(c_{p (1)} ,... , c_{p (n)} ) 在C₂中時，( c₁ ,..., c_n ) 在C₁中，則稱C₁與C₂是置換等價的。更一般地，如果存在${\displaystyle n\times n}$單項式矩陣（英語：monomial matrix）${\displaystyle M\colon \mathbb {F} _{q}^{n}\to \mathbb {F} _{q}^{n}}$使得C₁同構於C₂ ，那麼稱C₁和C₂是等價的。

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

博尼索利定理

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

示例

線性碼的一些示例包括：

• 重複碼（英語：Repetition code）
• 奇偶校驗碼
• 循環碼
• 漢明碼
• 戈萊碼（英語：Golay code (disambiguation)），包括二元（英語：Binary Golay code）的和三元（英語：Ternary Golay code）的
• 多項式碼（典型代表：BCH碼）
• 里德-所羅門碼
• 里德-穆勒碼（英語：Reed-Muller Code）
• 代數幾何碼（英語：Algebraic geometry code）
• 二元戈帕碼（英語：Binary Goppa code）
• 低密度奇偶校驗碼（英語：Low-density parity-check codes）
• 擴展碼（英語：Expander code）
• 多維奇偶校驗碼（英語：Multidimensional parity-check code）
• 環面碼（英語：Toric code）
• 渦輪碼
• 局部可恢復碼（英語：Locally recoverable code）

推廣

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

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

參見

• 解碼方法