線性碼

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

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

定義和參數

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

碼字的權重（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具有標準形式。^[6]

表示線性函數 $\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$ 矩陣。

線性保證碼字c₀與任何其他碼字c≠c₀之間的最小漢明距離d與c₀無關。這從以下性質可以看出：C中兩個碼字的差c−c₀也是一個碼字（即子空間C的一個元素），且d ( c ,c ₀ ) = d ( c−c₀ ,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\leq wt({\boldsymbol {c'}})$ ，後者是 ${\boldsymbol {H}}$ 之中線性相關的行的最小數目。上述性質得證。

示例：漢明碼

漢明碼作為首類為糾錯目的而開發的線性碼，在數字通信系統中得到了廣泛的應用。對於任何正整數 $r\geq 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}$ 單純形碼，是漢明碼的對偶碼。

常用記號

碼通常用字母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 。如果這樣的代碼存在，那麼從某種意義上來說，它們就是最好的。

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

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

博尼索利定理

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

示例

線性碼的一些示例包括：

推廣

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

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

參見

譯碼方法

參考文獻

^ William E. Ryan and Shu Lin. Channel Codes: Classical and Modern. Cambridge University Press. 2009: 4. ISBN 978-0-521-84868-8.
^ Martínez, Consuelo; Molina, Fabián. The syndromes decoding algorithm in group codes. Finite Fields and Their Applications. 2023-08-01, 89 [2025-07-05]. ISSN 1071-5797. doi:10.1016/j.ffa.2023.102206.
^ MacKay, David, J.C. Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. 2003: 9. Bibcode:2003itil.book.....M. ISBN 9780521642989. In a linear block code, the extra $N-K$ bits are linear functions of the original $K$ bits; these extra bits are called parity-check bits
^ Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc. 1991: 210–211. ISBN 978-0-471-06259-2.
^ Grossman, Jay. Coding theory: introduction to linear codes and applications. (PDF). Insight: River Academic Journal. 2008, 4 (2) [2025-07-05].
^ Grossman, Jay. Coding theory: introduction to linear codes and applications. (PDF). Insight: River Academic Journal. 2008, 4 (2) [2025-07-05].
^ Etzion, Tuvi; Raviv, Netanel. Equidistant codes in the Grassmannian. arXiv:1308.6231  [math.CO].
^ Bonisoli, A. Every equidistant linear code is a sequence of dual Hamming codes. Ars Combinatoria. 1984, 18: 181–186.
^ Marcus Greferath. Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso , 編. An Introduction to Ring-Linear Coding Theory. Springer Science & Business Media. 2009. ISBN 978-3-540-93806-4.
^ Encyclopedia of Mathematics. www.encyclopediaofmath.org.
^ J.H. van Lint. Introduction to Coding Theory 3rd. Springer. 1999. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.
^ S.T. Dougherty; J.-L. Kim; P. Sole. https://books.google.com/books?id=psrXBgAAQBAJ&pg=PA80 |chapterurl=缺少標題 (幫助). Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (編). Open Problems in Coding Theory. American Mathematical Soc. 2015: 80. ISBN 978-1-4704-1032-2.

參考書目

J. F. Humphreys; M. Y. Prest. Numbers, Groups and Codes 2nd. Cambridge University Press. 2004. ISBN 978-0-511-19420-7. 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.

[1] William E. Ryan and Shu Lin. Channel Codes: Classical and Modern. Cambridge University Press. 2009: 4. ISBN 978-0-521-84868-8.

[2] Martínez, Consuelo; Molina, Fabián. The syndromes decoding algorithm in group codes. Finite Fields and Their Applications. 2023-08-01, 89 [2025-07-05]. ISSN 1071-5797. doi:10.1016/j.ffa.2023.102206.

[DrMacKayECC-3] MacKay, David, J.C. Information Theory, Inference, and Learning Algorithms (PDF). Cambridge University Press. 2003: 9. Bibcode:2003itil.book.....M. ISBN 9780521642989. In a linear block code, the extra $N-K$ bits are linear functions of the original $K$ bits; these extra bits are called parity-check bits

[Cover_and_Thomas-4] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory. John Wiley & Sons, Inc. 1991: 210–211. ISBN 978-0-471-06259-2.

[5] Grossman, Jay. Coding theory: introduction to linear codes and applications. (PDF). Insight: River Academic Journal. 2008, 4 (2) [2025-07-05].

[6] Grossman, Jay. Coding theory: introduction to linear codes and applications. (PDF). Insight: River Academic Journal. 2008, 4 (2) [2025-07-05].

[7] Etzion, Tuvi; Raviv, Netanel. Equidistant codes in the Grassmannian. arXiv:1308.6231  [math.CO].

[8] Bonisoli, A. Every equidistant linear code is a sequence of dual Hamming codes. Ars Combinatoria. 1984, 18: 181–186.

[Greferath2009-9] Marcus Greferath. Massimiliano Sala; Teo Mora; Ludovic Perret; Shojiro Sakata; Carlo Traverso , 編. An Introduction to Ring-Linear Coding Theory. Springer Science & Business Media. 2009. ISBN 978-3-540-93806-4.

[10] Encyclopedia of Mathematics. www.encyclopediaofmath.org.

[Lint1999-11] J.H. van Lint. Introduction to Coding Theory 3rd. Springer. 1999. Chapter 8: Codes over ℤ₄. ISBN 978-3-540-64133-9.

[DoughertyFacchini2015-12] S.T. Dougherty; J.-L. Kim; P. Sole. https://books.google.com/books?id=psrXBgAAQBAJ&pg=PA80 |chapterurl=缺少標題 (幫助). Steven Dougherty; Alberto Facchini; Andre Gerard Leroy; Edmund Puczylowski; Patrick Sole (編). Open Problems in Coding Theory. American Mathematical Soc. 2015: 80. ISBN 978-1-4704-1032-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]