奇偶檢驗矩陣

在編碼理論裡，線性區塊碼 C 的奇偶檢驗矩陣（英語：parity-check matrix）是描述碼字的成分間必須滿足的線性關係的一個矩陣。它可以用來決定一個特定向量是否為碼字，也用在譯碼算法中。

定義

形式上，線性碼 C 的奇偶檢驗矩陣 H 是對偶碼 C^⊥ 的生成矩陣。這就意味着當且僅當矩陣-向量乘積 Hc^⊤ = 0（一些作者會寫成其等價形式cH^⊤ = 0）時，碼字 c 才會在 C 中。

奇偶檢驗矩陣的行是奇偶檢驗方程的係數。 也就是說，它們表示每個碼字中的某些數字（成分）如何線性組合可以等於零。例如，奇偶檢驗矩陣

$H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]$,

緊湊表示了向量 $(c_{1},c_{2},c_{3},c_{4})$ 要成為 C 的碼字必須滿足的奇偶檢驗方程，

${\begin{aligned}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{aligned}}$.

根據定義，奇偶檢驗矩陣直接遵循該碼的最小距離為，使得奇偶檢驗矩陣 H 的任意 d - 1 列都線性無關並且存在 d 列線性相關的最小數 d。

建立奇偶檢驗矩陣

某一給定碼的奇偶校驗矩陣可以從其生成矩陣導出（反之亦然）。 若一 [n,k] 碼的生成矩陣是標準形式

$G={\begin{bmatrix}I_{k}|P\end{bmatrix}}$,

則奇偶檢驗矩陣為

$H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}$,

因為

$GH^{\top }=P-P=0$.

取反是在有限域 F_q 內進行的。注意如果所處的域的特徵為 2（即在這個域中 1 + 1 = 0），如在二元碼中一樣，因此 -P = P，所以取反是不需要的。

例如，如果一個二元碼的生成矩陣

$G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]$,

則其奇偶檢驗矩陣就是

$H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]$.

伴隨式

對向量空間環境中的任意（行）向量 x，s = Hx^⊤ 稱為 x 的伴隨式。當且僅當 s = 0 時向量 x 為碼字。計算伴隨式是伴隨式譯碼算法的基礎。

參見

• 漢明碼

參考文獻

• Hill, Raymond. A first course in coding theory. Oxford Applied Mathematics and Computing Science Series. Oxford University Press. 1986: 69. ISBN 0-19-853803-0. 
• Pless, Vera, Introduction to the Theory of Error-Correcting Codes 3rd, Wiley Interscience, 1998, ISBN 0-471-19047-0 
• Roman, Steven, Coding and Information Theory, GTM 134, Springer-Verlag, 1992, ISBN 0-387-97812-7 
• J.H. van Lint. Introduction to Coding Theory. GTM 86 2nd. Springer-Verlag. 1992: 34. ISBN 3-540-54894-7.