奇偶檢驗矩陣

在编码理论裡，線性區塊碼 C 的奇偶檢驗矩陣（英語：parity-check matrix）是描述码字（英语：codeword）的成分间必须满足的线性关系的一个矩阵。它可以用来决定一个特定向量是否为码字，也用在译码算法中。

定义

形式上，线性码 C 的奇偶檢驗矩陣 H 是对偶码 C^⊥ 的生成矩阵。这就意味着当且仅当矩阵-向量乘积 Hc^⊤ = 0（一些作者^[1]会写成其等价形式cH^⊤ = 0）时，码字 c 才会在 C 中。

奇偶檢驗矩陣的行是奇偶检验方程的系数。^[2] 也就是說，它們表示每个碼字中的某些數字（成分）如何線性組合可以等於零。例如，奇偶檢驗矩陣

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

紧凑表示了向量 ${\displaystyle (c_{1},c_{2},c_{3},c_{4})}$  要成为 C 的码字必须满足的奇偶检验方程，

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

根据定义，奇偶检验矩阵直接遵循该码的最小距离为，使得奇偶检验矩阵 H 的任意 d - 1 列都线性无关并且存在 d 列线性相关的最小数 d。

建立奇偶檢驗矩陣

某一给定碼的奇偶校驗矩陣可以从其生成矩阵导出（反之亦然）。^[3] 若一 [n,k] 码的生成矩陣是標準形式

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

则奇偶檢驗矩陣为

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

因為

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

取反是在有限域 F_q 内进行的。注意如果所处的域的特征为 2（即在这个域中 1 + 1 = 0），如在二元码（英语：binary code）中一样，因此 -P = P，所以取反是不需要的。

例如，如果一个二元码的生成矩阵

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

则其奇偶檢驗矩陣就是

${\displaystyle 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 的伴随式（英语：Syndrome decoding）。当且仅当 s = 0 时向量 x 为码字。计算伴随式是伴随式译码（英语：syndrome decoding）算法的基础。^[4]

参见

• 汉明码

注释

1. 比如Roman 1992，p. 200
2. Roman 1992，p. 201
3. Pless 1998，p. 9
4. Pless 1998，p. 20

參考文獻

• 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.