パリティチェックマトリックス

符号理論において、線形ブロック符号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}}}$、

ベクトルに対して満たされなければならない条件${\displaystyle (c_{1},c_{2},c_{3},c_{4})}$Cのコードワードである。

パリティチェック行列の定義から、コードの最小距離は、パリティチェック行列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}}}$、

なぜなら

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

否定は有限体F _qで行われます。基となる体の標数が 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 は${\displaystyle k\times n}$行列である一方、Hは${\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巻 、シュプリンガー・フェルラーク、ISBN 0-387-97812-7
• JH van Lint ( 1992).符号理論入門. GTM . Vol.  86 (第2 版). Springer-Verlag. pp. 34. ISBN  3-540-54894-7。