ハミング(7,4)

符号理論において、Hamming(7,4)は、3 つのパリティ ビットを追加することで4ビットのデータを 7 ビットに符号化する線形誤り訂正符号です。これは、より大きなハミング符号ファミリーの一員です が、ハミング符号という用語は、 1950 年にリチャード W. ハミングが導入したこの特定の符号を指すことが多いです。当時、ハミングはベル電話研究所に勤務しており、エラーが発生しやすいパンチ カードリーダーに不満を抱いていたため、誤り訂正符号の研究を始めました。^{[ 1 ]}

ハミング符号は、メッセージの4ビットのデータごとに3ビットのチェックビットを追加します。ハミングの(7,4)アルゴリズムは、1ビットエラーを訂正したり、1ビットエラーと2ビットエラーを検出したりできます。つまり、任意の2つの正しい符号語間の最小ハミング距離は3であり、受信した符号語が送信者によって送信された符号語から最大1の距離にある場合、正しく復号できます。これは、バーストエラーが発生しない伝送媒体の状況では、ハミングの(7,4)符号が有効であることを意味します（7ビットのうち2ビットが反転するには、媒体が極めてノイズが多い必要があるため）。

量子情報では、ハミング符号（7,4）が量子誤り訂正に使用されるCSS符号の一種であるスティーン符号の基底として使用されます。

ハミング符号の目的は、データビットまたはパリティビットの単一ビットエラーを検出および訂正できるように、重複するパリティビットのセットを作成することです。複数の重複を作成することもできますが、一般的な方法はハミング符号で説明されています。

この表は、エンコードされたワード内のどの送信ビットがどのパリティビットによってカバーされるかを示しています。たとえば、p _{2 は}ビット 2、3、6、7 に対して偶数パリティを提供します。また、列を読み取ることで、どの送信ビットがどのパリティビットによってカバーされるかを詳細に示しています。たとえば、d _1はp ₁とp ₂によってカバーされますが、p ₃によってカバーされません。この表は、次のセクションのパリティチェック行列 ( H ) と非常によく似ています。

さらに、上記の表のパリティ列を削除した場合

すると、以下のコード生成行列（ G ）の1行目、2行目、4行目との類似性も明らかになります。

つまり、パリティビットのカバー範囲を正しく選択することで、ハミング距離が1のすべてのエラーを検出および訂正することができ、これがハミング符号を使用する目的です。

ハミング符号は線形符号であるため、行列を用いて線形代数的に計算できます。ハミング符号の目的のために、2つのハミング行列を定義できます。それは、符号生成行列Gとパリティ検査行列Hです。

$\displaystyle \mathbf {G^{T}}$ :={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}},\qquad \mathbf {H}  :={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}.}

前述のとおり、Gの1行目、2行目、4行目は、データビットをパリティビットにマッピングしているため、見覚えがあるはずです。

• p _{1 は}d ₁、d ₂、d ₄をカバーします
• p _{2 は}d ₁、d ₃、d ₄をカバーしています
• p _{3 は}d ₂、d ₃、d ₄をカバーしています

残りの行（3、5、6、7）は、データをエンコードされた形式でそれぞれの位置にマッピングしており、その行には1つしかないため、同一のコピーとなります。実際、これら4つの行は線形独立であり、単位行列を形成します（これは偶然ではなく、意図的なものです）。

また、前述のとおり、Hの3つの行はよく知られているはずです。これらの行は受信側でシンドロームベクトルを計算するために使用され、シンドロームベクトルがヌルベクトル（すべてゼロ）であれば、受信ワードはエラーフリーです。ゼロでない場合は、どのビットが反転したかを示します。

4 つのデータビットはベクトルpとして組み立てられ、Gで事前に乗算されます(つまり、${\displaystyle G^{T}p}$) を法2 で割って、送信されるエンコードされた値を生成します。元の 4 つのデータ ビットは、7 ビットに変換され (そのため「Hamming(7,4)」という名前が付けられます)、上記のデータ ビットのカバー範囲を使用して偶数パリティを保証するために 3 つのパリティ ビットが追加されます。上の最初の表は、各データ ビットとパリティ ビットの最終的なビット位置 (1 ～ 7) へのマッピングを示していますが、これはベン図でも表すことができます。この記事の最初の図は、3 つの円 (各パリティ ビットに 1 つずつ) を示し、各パリティ ビットがカバーするデータ ビットを囲んでいます。2 番目の図 (右側に表示) は同一ですが、代わりにビット位置がマークされています。

このセクションの残りの部分では、以下の4ビット（列ベクトルとして表示）を例として使用します。

${\displaystyle \mathbf {p} ={\begin{pmatrix}d_{1}\\d_{2}\\d_{3}\\d_{4}\\\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}}$

1011このデータ（ ）をノイズのある通信チャネルで送信するとします。具体的には、バイナリ対称チャネル、つまりエラーによる破損がゼロまたはイチのどちらか一方に偏らない（エラー発生に関して対称的である）チャネルです。さらに、すべてのソースベクトルは等確率であると仮定します。Gとpの積を、2を法とする要素を用いて計算し、送信符号語xを決定します。

${\displaystyle \mathbf {x} =\mathbf {G^{T}} \mathbf {p} ={\begin{pmatrix}1&1&0&1\\1&0&1&1\\1&0&0&0\\0&1&1&1\\0&1&0&0\\0&0&1&0\\0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\3\\1\\2\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}$

これは、0110011を送信する代わりに が送信されることを意味します1011。

行列乗算はmod 2で行われます。言い換えれば、結果の各行は、行と列をビットごとのAND演算した結果得られるセットビットの人口カウントの最下位ビットです。

隣の図では、符号化された単語の7ビットがそれぞれの位置に挿入されています。赤、緑、青の円のパリティが偶数であることは、図から明らかです。

• 赤い丸には1が2つあります
• 緑色の円には1が2つあります
• 青い円には1が4つあります

これから説明するように、送信中にビットが反転した場合、2つまたは3つすべての円のパリティが不正になり、3つの円すべてのパリティが偶数であるべきであることを知っていれば、（パリティビットの1つであっても）エラーが発生したビットを特定できます。

送信中にエラーが発生しない場合、受信した符号語rは送信した符号語xと同一になります。

${\displaystyle \mathbf {r} =\mathbf {x} }$

受信機はHとrを乗算してシンドロームベクトルzを取得します。これはエラーが発生したかどうか、発生した場合はどのコードワードビットで発生したかを示します。この乗算を実行すると（ここでも、エントリは2を法として計算されます）：

${\displaystyle \mathbf {z} =\mathbf {H} \mathbf {r} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}2\\4\\2\end{pmatrix}}={\begin{pmatrix}0\\0\\0\end{pmatrix}}}$

シンドロームzはヌルベクトルであるため、受信側はエラーが発生していないと結論付けることができます。この結論は、データベクトルにGを乗算すると、Hの核となるベクトル部分空間への基底変換が発生するという観察に基づいています。送信中に何も起こらなければ、r はHの核内に留まり、乗算の結果はヌルベクトルになります。

そうでなければ、次のように書けるとしよう

${\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{i}}$

mod 2、ここでe _iは${\displaystyle i_{th}}$単位ベクトル、つまり、1 が 1 であるゼロベクトル${\displaystyle i^{th}}$1から数えて。

${\displaystyle \mathbf {e} _{2}={\begin{pmatrix}0\\1\\0\\0\\0\\0\\0\end{pmatrix}}}$

したがって、上記の式は、${\displaystyle i^{th}}$場所。

さて、このベクトルにHを掛けると：

$\displaystyle \mathbf {Hr} =\mathbf {H} \left(\mathbf {x} +\mathbf {e} _{i}\right)=\mathbf {Hx} +\mathbf {He} _{i}}$

xは送信データであるため、エラーはなく、結果としてHとxの積はゼロになります。したがって

${\displaystyle \mathbf {Hx} +\mathbf {He} _{i}=\mathbf {0} +\mathbf {He} _{i}=\mathbf {He} _{i}}$

さて、Hと${\displaystyle i^{th}}$標準基底ベクトルはHのその列を選び出すので、エラーはこのHの列が存在する場所で発生することがわかります 。

例えば、ビット番号5にビットエラーが発生したとします。

${\displaystyle \mathbf {r} =\mathbf {x} +\mathbf {e} _{5}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}+{\begin{pmatrix}0\\0\\0\\0\\1\\0\\0\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\\1\end{pmatrix}}}$

右の図は、赤と緑の円で囲まれた部分に発生したビットエラー（青色の文字）と不良パリティ（赤色の文字）を示しています。ビットエラーは、赤、緑、青の円のパリティを計算することで検出できます。不良パリティが検出された場合、不良パリティの円のみと重なるデータビットがエラーのあるビットです。上記の例では、赤と緑の円に不良パリティが発生しているため、赤と緑の交点に対応するビット（青の交点には対応しないビット）がエラーのあるビットを示します。

今、

${\displaystyle \mathbf {z} =\mathbf {Hr} ={\begin{pmatrix}1&0&1&0&1&0&1\\0&1&1&0&0&1&1\\0&0&0&1&1&1&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\1\\1\\1\\1\end{pmatrix}}={\begin{pmatrix}3\\4\\3\end{pmatrix}}={\begin{pmatrix}1\\0\\1\end{pmatrix}}}$

これはHの5列目に対応します。さらに、使用されている一般的なアルゴリズム（ハミング符号#一般的なアルゴリズムを参照）は、101のシンドロームがバイナリ値の5に対応するように意図的に構築されており、これは5ビット目が破損していることを示しています。したがって、ビット5でエラーが検出され、修正できます（単にその値を反転または否定します）。

${\displaystyle \mathbf {r} _{\text{corrected}}={\begin{pmatrix}0\\1\\1\\0\\{\overline {1}}\\1\\1\end{pmatrix}}={\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}}$

この修正された受信値は、確かに上記の送信値xと一致します。

受信したベクトルにエラーがないと判断された場合、またはエラーが発生した場合は訂正された場合（エラーは0ビットまたは1ビットのみ発生すると仮定）、受信データを元の4ビットに復号する必要があります。

まず、行列Rを定義します。

${\displaystyle \mathbf {R} ={\begin{pmatrix}0&0&1&0&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}}$

すると、受信値p _rはRrと等しくなります。上記の実行例を使用すると、

${\displaystyle \mathbf {p_{r}} ={\begin{pmatrix}0&0&1&0&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{pmatrix}}{\begin{pmatrix}0\\1\\1\\0\\0\\1\\1\end{pmatrix}}={\begin{pmatrix}1\\0\\1\\1\end{pmatrix}}}$

この方式では、単一ビットエラーのみが訂正可能であることを示すのは難しくありません。あるいは、ハミング符号を使用すれば、エラーが発生したときにHの積がゼロでないことを観察するだけで、単一ビットエラーと二重ビットエラーの両方を検出できます。隣の図では、ビット4と5が反転されています。これにより、パリティが無効な円（緑色）が1つだけ生成されますが、エラーは回復できません。

しかし、ハミング符号（7,4）や類似のハミング符号では、1ビットエラーと2ビットエラーを区別することができません。つまり、2ビットエラーは1ビットエラーと同じように表示されます。2ビットエラーに対して誤り訂正を行うと、誤った結果になります。

同様に、ハミング符号は任意の 3 ビットのエラーを検出したり、そこから回復したりすることはできません。図を考えてみてください。緑色の円の中のビット (赤色で表示) が 1 の場合、パリティ チェックはヌル ベクトルを返し、符号語にエラーがないことを示します。

ソースが4ビットしかないため、送信可能なワードは16個のみです。追加のパリティビットを使用する場合は、8ビットの値も含まれます（追加のパリティビットを使用したハミング(7,4)符号を参照）。（データビットは青色、パリティビットは赤色、追加のパリティビットは緑色で示されています。）

ハミング(7,4)符号はE7格子と密接に関連しており、実際にはE7格子、より正確にはその双対格子E7∗を構築するために使用できます_{（ E7}^の_同様の構築には双対符号[7,3,4] ₂を使用します）。特に、Z7内のすべてのベクトルxのうち^、 xがハミング(7,4)の符号語と（法2で）合同であるものを選び、1/ √2でスケーリングすると、格子E7∗が得られ_ます^。

${\displaystyle E_{7}^{*}={\tfrac {1}{\sqrt {2}}}\left\{x\in \mathbb {Z} ^{7}:x{\bmod {2}}\in [7,4,3]_{2}\right\}.}$

これは、格子と符号の間のより一般的な関係の具体的な例です。たとえば、パリティビットの追加によって生じる拡張(8,4)ハミング符号も、E ₈格子と関連しています。^{[ 2 ]}

• ハミング符号(7,4)に関するプログラミング問題