パリティチェック行列

符号理論において、線形ブロック符号Cのパリティ検査行列は、符号語の要素が満たさなければならない線形関係を記述する行列です。特定のベクトルが符号語であるかどうかを判断するために使用でき、復号化アルゴリズムでも使用されます。

正式には、線形コードCのパリティ検査行列Hは、双対コードC ^⊥の生成行列です。つまり、コードワードcがCに含まれるのは、行列ベクトル積H c ^⊤ = 0の場合のみです(一部の著者^[1]はこれを同等の形式c H ^⊤ = 0で記述します)。

パリティ検査行列の行はパリティ検査方程式の係数である。^[2]つまり、各コードワードの特定の桁（成分）の線形結合がゼロになることを示しています。たとえば、パリティ検査行列

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

パリティ検査方程式を簡潔に表すと、

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

ベクトルがCのコードワードになるためには、この条件を満たす必要があります。 ${\displaystyle (c_{1},c_{2},c_{3},c_{4})}$

パリティ チェック マトリックスの定義から、コードの最小距離は、パリティ チェック マトリックスHのすべてのd - 1列 が線形独立であり、Hのd列が線形従属であるような最小の数d であることが直接わかります。

与えられた符号のパリティ検査行列は、その生成行列から導出することができる（逆もまた同様）。^{[3] [} n , k ]符号の生成行列が標準形式である 場合、

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

パリティ検査行列は次のように表される。

${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{nk}\end{bmatrix}}}$、

なぜなら

${\displaystyle GH^{\top }=PP=0}$。

否定は有限体F _qで実行されます。2進コードの場合のように、基礎体の特性が 2 (つまり、その体では 1 + 1 = 0) の場合は - 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]}$。

G は行列であり、H も行列であることが確認できます。 ${\displaystyle k\times n}$${\displaystyle (nk)\times n}$

アンビエントベクトル空間の任意の（行）ベクトルxに対して、 s = H x ^{⊤ は}xのシンドロームと呼ばれる。ベクトルx がコードワードとなるのは、s = 0の場合のみである。シンドロームの計算は、シンドローム復号アルゴリズムの基礎となる。^[4]

• ハミングコード

• ヒル、レイモンド (1986)。符号理論入門。オックスフォード応用数学および計算科学シリーズ。オックスフォード大学出版局。69 ページ。ISBN 0-19-853803-0。
• Pless, Vera (1998)、誤り訂正符号理論入門（第3版）、Wiley Interscience、ISBN 0-471-19047-0
• ローマン、スティーブン（1992）、コーディングと情報理論、GTM、第134巻、Springer-Verlag、ISBN 0-387-97812-7
• JH van Lint (1992)。コーディング理論入門。GTM。第86巻（第2版）。Springer-Verlag。pp. 34。ISBN 3-540-54894-7。