パリティチェック行列

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

意味

正式には、線形符号Cのパリティ検査行列Hは、双対符号C ^⊥の生成行列である。これは、符号語cがCに属する場合、かつ行列ベクトル積H c ^⊤ = 0となる場合に限ることを意味する（一部の著者^[1]はこれを等価な形式c H ^⊤ = 0と表記する）。

パリティ検査行列の行は、パリティ検査方程式の係数である。^[2]つまり、各符号語の特定の桁（成分）の線形結合が0になる様子を示している。例えば、パリティ検査行列は

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

、

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

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

、

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

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

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

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

、

パリティ検査行列は次のように与えられる。

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

、

なぜなら

GH^{\top }=PP=0

。

否定は有限体F _q上で行われます。なお、基底体の標数が2（つまり、その体では1 + 1 = 0）の場合（ 2進コードの場合）、 - 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]

。

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

周囲ベクトル空間の任意のベクトルxに対して、 s = H xはxのシンドロームと呼ばれる。ベクトルx が符号語となるのは、 s = 0のときのみである。シンドロームの計算は、シンドローム復号アルゴリズムの基礎となる。^[4]

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