ハミング符号

ハミング符号以前には、いくつかの単純な誤り検出符号が使用されていたが、同じ容量オーバーヘッドでハミング符号ほど効果的なものはなかった。

以下の一般的なアルゴリズムは、任意のビット数に対して単一誤り訂正（SEC）コードを生成します。基本的な考え方は、インデックスXOR（ 1を含むすべてのビット位置のXOR）が0になるように誤り訂正ビットを選択することです。ここでは、位置1、10、100など（バイナリ）を誤り訂正ビットとして使用します。これにより、メッセージ全体のインデックスXORが0になるように誤り訂正ビットを設定できることが保証されます。受信側がインデックスXORが0の文字列を受信すれば、破損はなかったと判断できます。そうでない場合は、インデックスXORが破損したビットのインデックスを示します。

以下の記述からアルゴリズムを導き出すことができる。

1. ビットを1から番号付けします：ビット1、2、3、4、5、6、7、…
2. ビット数をバイナリで書きます: 1、10、11、100、101、110、111、など。
3. 2のべき乗であるすべてのビット位置（その位置の2進数表現で1ビットが1であるビット）はパリティビットです。1、2、4、8など（1、10、100、1000）。
4. バイナリ形式で2つ以上の1ビットを持つその他のすべてのビット位置は、データビットです。
5. 各データビットは、そのビット位置のバイナリ形式によって決定される、2つ以上のパリティビットからなる固有のセットに含まれる。
   1. パリティビット1は、最下位ビットがセットされているすべてのビット位置（ビット1（パリティビット自体）、3、5、7、9など）を対象とします。
   2. パリティビット2は、2番目に下位のビットがセットされているすべてのビット位置（ビット2～3、6～7、10～11など）を対象とします。
   3. パリティビット4は、下位3番目のビットがセットされているすべてのビット位置（ビット4～7、12～15、20～23など）を対象とします。
   4. パリティビット8は、下位4番目のビットがセットされているすべてのビット位置（ビット8～15、24～31、40～47など）をカバーします。
   5. 一般に、各パリティビットは、パリティ位置とビット位置のビットごとのAND演算がゼロでないすべてのビットをカバーします。

エンコードするデータバイトが10011010の場合、データワード（パリティビットを表すためにアンダースコアを使用）は__1_001_1010となり、コードワードは011100101010となります。

パリティが偶数か奇数かは重要ではないが、エンコードとデコードの両方で同じ選択をしなければならない。

この一般的なルールは、視覚的に示すことができる。

図には符号化されたビットのうち20ビット（パリティビット5ビット、データビット15ビット）のみが表示されていますが、このパターンは無限に続きます。ハミング符号の重要な点は、視覚的に確認すると、任意のビットが固有のパリティビットのセットに含まれているということです。エラーをチェックするには、すべてのパリティビットをチェックします。エラーパターンはエラーシンドロームと呼ばれ、エラーのあるビットを特定します。すべてのパリティビットが正しければ、エラーはありません。そうでない場合は、エラーのあるパリティビットの位置の合計によって、エラーのあるビットが特定されます。たとえば、位置1、2、8のパリティビットがエラーを示している場合、ビット1+2+8=11がエラーです。1つのパリティビットのみがエラーを示している場合は、そのパリティビット自体がエラーです。

mビットのパリティでは、1 から$2m-1$カバーできます。パリティビットを割り引いた後、${\displaystyle 2^{m}-m-1}$ビットはデータとして使用するために残ります。mが変化するにつれて、考えられるすべてのハミング符号が得られます。

マトリックス ${\displaystyle \mathbf {G}$ :={\begin{pmatrix}{\begin{array}{c|c}I_{k}&-A^{\text{T}}\\\end{array}}\end{pmatrix}}} は、 線形 ( n , k ) コードの (正準) 生成行列と呼ばれます。

そして${\displaystyle \mathbf {H}$ :={\begin{pmatrix}{\begin{array}{c|c}A&I_{nk}\\\end{array}}\end{pmatrix}}} は パリティチェック行列と呼ばれます。

これは、標準形式（または系統形式）でのGとHの構成です。形式に関係なく、線形ブロック符号のGとH は以下を満たす必要があります。

${\displaystyle \mathbf {H} \,\mathbf {G} ^{\text{T}}=\mathbf {0} }$、すべてゼロの行列。^{[ 6 ]}

[7,  4,  3] =  [ n , k , d ] = [2 ^m − 1, 2 ^m − 1 − m , 3]であるため、ハミング符号のパリティ検査行列Hは、ペアごとに独立な長さmのすべての列をリストすることによって構築されます。          

したがって、Hは、左辺がすべての非ゼロのn組であり、行列の列におけるn組の順序は関係ない行列です。右辺は ( n  − k )単位行列です。 

したがって、G は、Hの左辺の転置行列と、 Gの左辺のk次元単位行列とを組み合わせることによってHから得ることができます。 

コードジェネレーターマトリックス${\displaystyle \mathbf {G} }$パリティチェックマトリックス${\displaystyle \mathbf {H} }$は：

${\displaystyle \mathbf {G}$ :={\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix}}_{4,7}}

そして

${\displaystyle \mathbf {H}$ :={\begin{pmatrix}1&1&0&1&1&0&0\\1&0&1&1&0&1&0\\0&1&1&1&0&0&1\end{pmatrix}}_{3,7}.}

最後に、これらの行列は、次の操作によって同等の非系統的コードに変換できます。^{[ 6 ]}

• 列の順列（列の入れ替え）
• 基本的な行操作（行を複数の行の線形結合で置き換える操作）

例

上記の行列から、2 ^k = 2 ⁴ = 16 個の符号語が得られます。${\displaystyle {\vec {a}}}$バイナリデータビットの行ベクトルである。${\displaystyle {\vec {a}}=[a_{1},a_{2},a_{3},a_{4}],\quad a_{i}\in \{0,1\}}$合言葉${\displaystyle {\vec {x}}}$16個のデータベクトルのいずれに対しても${\displaystyle {\vec {a}}}$標準行列積によって与えられる${\displaystyle {\vec {x}}={\vec {a}}G}$ここで、加算演算は法2で行われます。

例えば、${\displaystyle {\vec {a}}=[1,0,1,1]}$生成行列を使用する${\displaystyle G}$上記より、(合計にモジュロ2を適用した後)、

${\displaystyle {\vec {x}}={\vec {a}}G={\begin{pmatrix}1&0&1&1\end{pmatrix}}{\begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}={\begin{pmatrix}1&0&1&1&2&3&2\end{pmatrix}}={\begin{pmatrix}1&0&1&1&0&1&0\end{pmatrix}}}$

[7,4] ハミング符号は、(7,4) 符号化ワードの上にパリティビットを追加することで、[8,4] 符号に容易に拡張できます ( Hamming(7,4)を参照)。これは、改訂された行列で要約できます。

${\displaystyle \mathbf {G}$ :={\begin{pmatrix}1&1&1&0&0&0&0&1\\1&0&0&1&1&0&0&1\\0&1&0&1&0&1&0&1\\1&1&0&1&0&0&1&0\end{pmatrix}}_{4,8}}

そして

${\displaystyle \mathbf {H}$ :={\begin{pmatrix}1&0&1&0&1&0&1&0\\0&1&1&0&0&1&1&0\\0&0&0&1&1&1&1&0\\1&1&1&1&1&1&1&1\end{pmatrix}}_{4,8}.}

Hは標準形式ではないことに注意してください。Gを得るには、基本行操作を使用して、Hと同等の系統形式の行列を得ることができます。

${\displaystyle \mathbf {H} =\left({\begin{array}{cccc|cccc}0&1&1&1&1&0&0&0\\1&0&1&1&0&1&0&0\\1&1&0&1&0&0&1&0\\1&1&1&0&0&0&0&1\end{array}}\right)_{4,8}.}$

例えば、この行列の最初の行は、非系統形式のHの2行目と3行目の合計です。上記のハミング符号の系統的な構成を使用すると、行列Aは明らかであり、Gの系統形式は次のように記述されます。

${\displaystyle \mathbf {G} =\left({\begin{array}{cccc|cccc}1&0&0&0&0&1&1&1\\0&1&0&0&1&0&1&1\\0&0&1&0&1&1&0&1\\0&0&0&1&1&1&1&0\end{array}}\right)_{4,8}.}$

Gの非体系的な形式は、（基本行操作を用いて）行簡約化することで、この行列に一致させることができる。

4行目を追加することで、実質的にすべてのコードワードビット（データとパリティ）の合計が4番目のパリティビットとして計算されます。

例えば、1011は (このセクションの冒頭で説明した G の非系統形式を使用して) 01 1 0 011 0にエンコードされます。ここで、青色の数字はデータ、赤色の数字は [7,4] ハミング符号のパリティ ビット、緑色の数字は [8,4] 符号によって追加されたパリティ ビットです。緑色の数字によって [7,4] 符号語のパリティが偶数になります。

最後に、最小距離が[7,4]符号の3から[8,4]符号の4に増加したことが示せる。したがって、この符号は[8,4]ハミング符号と定義できる。

[8,4] ハミング符号を復号するには、まずパリティビットを確認します。パリティビットがエラーを示している場合、単一誤り訂正（[7,4] ハミング符号）によってエラー位置が示され、「エラーなし」の場合はパリティビットが示されます。パリティビットが正しい場合、単一誤り訂正によって2つのエラー位置の（ビットごとの）排他的論理和が示されます。位置が等しい場合（「エラーなし」）、2ビットエラーは発生していないか、または相殺されています。それ以外の場合は、2ビットエラーが発生しています。