查看“︁奇偶檢驗矩陣”︁的源代码

{{NoteTA |G1=Math|G2=IT}}在[[编码理论]]裡，[[分組碼|線性區塊碼]] ''C'' 的'''奇偶檢驗矩陣'''（{{lang-en|'''parity-check matrix'''}}）是描述{{le|码字|codeword}}的成分间必须满足的线性关系的一个矩阵。它可以用来决定一个特定向量是否为码字，也用在译码算法中。

==定义==
形式上，线性码 ''C'' 的奇偶檢驗矩陣 ''H'' 是[[对偶码]] ''C''<sup>⊥</sup> 的[[生成矩阵]]。这就意味着[[当且仅当]]矩阵-向量乘积 {{nowrap|1=''H'''''c'''<sup>⊤</sup>  = '''0'''}}（一些作者<ref>比如{{harvnb|Roman|1992|loc=p. 200}}</ref>会写成其等价形式'''c'''''H''<sup>⊤</sup> = '''0'''）时，码字 '''c''' 才会在 ''C '' 中。

奇偶檢驗矩陣的行是奇偶检验方程的系数。<ref>{{harvnb|Roman|1992|loc=p. 201}}</ref> 也就是說，它們表示每个碼字中的某些數字（成分）如何線性組合可以等於零。例如，奇偶檢驗矩陣

:<math>H =

\left[
\begin{array}{cccc}
  0&0&1&1\\
  1&1&0&0
\end{array}
\right]
</math>,

紧凑表示了向量 <math>(c_1, c_2, c_3, c_4)</math> 要成为 ''C'' 的码字必须满足的奇偶检验方程，
:<math>\begin{align} c_3 + c_4 &= 0 \\ c_1 + c_2 &= 0 \end{align}</math>.

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

==建立奇偶檢驗矩陣==

某一给定碼的奇偶校驗矩陣可以从其[[生成矩阵]]导出（反之亦然）。<ref>{{harvnb|Pless|1998|loc=p. 9}}</ref> 若一 [''n'',''k''] 码的生成矩陣是標準形式 
: <math>G = \begin{bmatrix} I_k | P \end{bmatrix}</math>,
则奇偶檢驗矩陣为
: <math>H = \begin{bmatrix} -P^{\top} | I_{n-k} \end{bmatrix}</math>,
因為
: <math>G H^{\top} = P-P = 0</math>.
取反是在有限域 '''F'''<sub>''q''</sub> 内进行的。注意如果所处的域的[[特征 (代数)|特征]]为 2（即在这个域中 1 + 1 = 0），如在{{le|二元码|binary code}}中一样，因此 -''P'' = ''P''，所以取反是不需要的。

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

: <math>G = 
\left[
\begin{array}{cc|ccc}
1&0&1&0&1 \\
0&1&1&1&0 \\
\end{array}
\right]</math>,

则其奇偶檢驗矩陣就是

: <math>H =
\left[
\begin{array}{cc|ccc}
1&1&1&0&0 \\
0&1&0&1&0 \\
1&0&0&0&1 \\
\end{array}
\right]</math>.

==伴随式==

对向量空间环境中的任意（行）向量 '''x'''，'''s''' = ''H'''''x'''<sup>⊤</sup> 称为 '''x''' 的{{le|伴随式译码|Syndrome decoding|伴随式}}。当且仅当 '''s''' = '''0''' 时向量 '''x''' 为码字。计算伴随式是{{le|伴随式译码|syndrome decoding}}算法的基础。<ref>{{harvnb|Pless|1998|loc=p. 20}}</ref>

==参见==
*[[汉明码]]

==注释==
{{reflist|3}}

==參考文獻==
* {{cite book | last=Hill | first=Raymond | title=A first course in coding theory | url=https://archive.org/details/firstcourseincod0000hill | publisher=[[牛津大學出版社|Oxford University Press]] | series=Oxford Applied Mathematics and Computing Science Series | date=1986 | isbn=0-19-853803-0 | pages=[https://archive.org/details/firstcourseincod0000hill/page/69 69] }}
* {{citation|first=Vera|last=Pless|author-link=Vera Pless|title=Introduction to the Theory of Error-Correcting Codes|edition=3rd|publisher=Wiley Interscience|year=1998|isbn=0-471-19047-0}}
* {{citation|first=Steven|last=Roman|title=Coding and Information Theory|series=[[數學研究生教材|GTM]]|volume=134|publisher=Springer-Verlag|year=1992|isbn=0-387-97812-7}}
* {{cite book | author=J.H. van Lint | title=Introduction to Coding Theory | edition=2nd | publisher=Springer-Verlag | series=[[數學研究生教材|GTM]] | volume=86 | date=1992 | isbn=3-540-54894-7 | pages=34}}

[[Category:编码理论]]