Hamming(7,4)

ファイル:Hamming(7,4).svg

Graphical depiction of the 4 data bits d₁ to d₄ and 3 parity bits p₁ to p₃ and which parity bits apply to which data bits

Hamming（7,4）は、線形誤り訂正符号であり、データの4つの[[bit]を7ビットに符号化し、 3つのパリティビット s。それはHamming codeのより大きいファミリのメンバーですが、「Hamming code」という用語は、1950年に導入されたこの特定のコードを指すことがよくあります。その時点で、Hamming [ベル電話研究所]で働き、エラーが起こりやすい[穿孔されたカード]リーダーに不満を抱いていたので、エラー修正コードの作業を開始しました。

ハミングコードは、メッセージの4つのデータビットごとに3つの追加チェックビットを追加する。 Hamming（7,4）アルゴリズムは、単一ビットエラーを修正したり、すべてのシングルビットエラーと2ビットエラーを検出したりすることができます。換言すれば、任意の2つの正しいコードワード間の最小[ハミング距離]は3であり、受信者が送信者によって送信されたコードワードから最大で1つの距離にある場合、正しく復号されることができる。これは、バーストエラーが発生しない伝送媒体の状況では、ハミング（7,4）コードが効果的であることを意味する（7ビットのうち2ビットがフリップされるために媒体が非常に騒がしくなければならないため） 。

目標

ハミングコードの目的は、データビットまたはパリティビットで単一ビットエラー（ビットが論理的に値に反転される）が重なるように重なるパリティビットのセットを作成することです検出され、訂正されます。複数のオーバーラップを作成することができますが、一般的な方法はハミングコード|ハミングコードで表示されます。

Bit #	1	2	3	4	5	6	7
Transmitted bit	<math>p_1</math>	<math>p_2</math>	<math>d_1</math>	<math>p_3</math>	<math>d_2</math>	<math>d_3</math>	<math>d_4</math>
<math>p_1</math>
<math>p_2</math>
<math>p_3</math>

この表は、どのパリティビットが符号化ワード内のどの送信ビットをカバーするかを説明している。例えば、 p ＆lt; sub2＆lt; / sub＆gt;ビット2,3,6、および7の偶数パリティを提供します。また、どの送信ビットが列を読み取ることによってどのパリティビットによってカバーされるかについても詳しく説明します。例えば、 d ＆lt; sub 1＆lt; / sub＆gt; "p" _{1 </ sub>で覆われている。 「p」「＆lt; sub2＆gt;＆lt; sub＆gt; 'p' '＆lt; sub3＆lt; / sub＆gt;この表は、次のセクションのパリティ検査行列（ 'H' ）と非常に似ています。}

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

	<math>d_1</math>	<math>d_2</math>	<math>d_3</math>	<math>d_4</math>
<math>p_1</math>
<math>p_2</math>
<math>p_3</math>

下のコード生成行列（ 'G' ）の行1,2、および4との類似性も明白になります。

したがって、パリティビットカバレッジを正しく選択することにより、ハミング距離が1であるすべてのエラーを検出して修正することができます。これはハミングコードを使用する点です。

ハミング行列

ハミングコードは線形代数であるので、[[行列（数学）|行列]を通じて線形代数項でハミングコードを計算することができます。ハミングコードの目的のために、2つのハミング行列を定義することができます：コード生成行列 'G' と '['チェックマトリックス]] 'H' ：

<math>\mathbf{G} := \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}.</math>

ファイル:Hamming(7,4) as bits.svg

Bit position of the data and parity bits

前述のように、 'G' の1,2および4行は、データビットをパリティビットにマップするときによく分かるはずです。

• p₁ covers d₁, d₂, d₄
• p₂ covers d₁, d₃, d₄
• p₃ covers d₂, d₃, d₄

残りの行（3、5、6、7）は、符号化された形式でデータをその位置にマップし、その行には1だけしか存在しないため、同一のコピーです。実際、これらの4つの行は線形独立であり、[恒等行列]を形成する（設計上、偶然ではない）。

また、前述したように、 'H' の3つの行はよく知られているはずです。これらの行は、受信側でシンドロームベクトル 'を計算するために使用され、シンドロームベクトルが[ヌルベクトル（ベクトル空間）|ヌルベクトル]]（すべてゼロ）である場合、受信されたワードは、無料;非ゼロの場合、値は反転されたビットを示します。

4つのデータビット。ベクトル 'p' としてアセンブルされます。は、G '（すなわち、' Gp '）によって事前に乗算され、モジュロ 2とされて、送信される符号化値が得られる。元の4データビットは、上記のデータビットのカバレッジを使用して偶数パリティを保証するために3つのパリティビットが追加された7ビット（したがって、名前「Hamming（7,4）」に変換されます。上の最初の表は、各データとパリティビットの最終ビット位置（1〜7）へのマッピングを示していますが、これも[Venn図]で表示できます。この記事の最初の図は、3つの円（各パリティビットごとに1つ）を示し、各パリティビットがカバーするデータビットを囲みます。 2番目の図（右側に示す）は同じですが、代わりにビット位置がマークされています。

このセクションの残りの部分では、次の4ビット（列ベクトルとして示される）が実行例として使用されます。

<math>\mathbf{p} = \begin{pmatrix} d_1 \\ d_2 \\ d_3 \\ d_4 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}</math>

チャネルコーディング

ファイル:Hamming(7,4) example 1011.svg

例 'x' のマッピング。赤、緑、青の円のパリティは均一です。

このデータ（[signal noise | noisy] [[channel（communications）|通信チャネル]）を介してこのデータ（ 1011 </ code>）を送信したいとします。具体的には、バイナリ対称チャネルは、エラーの破損が0または1のいずれかを優先しないことを意味します（エラーを引き起こす点で対称的です）。さらに、全てのソースベクトルは等確率であると仮定される。送信されたコードワード x 'を求めるために、モジュロ2を使って' 'G' '

<math>\mathbf{x} = \mathbf{G} \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} </math>

これは、＆lt; code＆gt; 0110011＆lt; / code＆gt; ＆lt; code＆gt;＆gt;＆lt; code＆gt;の代わりに送信される。

乗算に関係するプログラマは、結果の各行が、乗算されるのではなく、行と列が一緒になることに起因するセットビットの Population Countの最下位ビットであることを観察する必要があります。

隣接する図では、符号化されたワードの7ビットがそれぞれの位置に挿入される。検査の結果、赤、緑、青の円のパリティは均一であることが明らかです。

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

まもなく表示されるのは、伝送中にビットがフリップされた場合、2つまたは3つの円のパリティが正しくなく、エラービットが（たとえパリティビットの1つであっても）これらのサークルの3つはすべて偶数でなければなりません。

パリティチェック

送信中にエラーが発生しない場合、受信されたコードワード 'r' は、送信されたコードワード 'x' と同一です。

<math>\mathbf{r} = \mathbf{x}</math>

受信機は、エラーが発生したかどうかを示す "シンドローム" "ベクトル" z 'を得るために' を乗算し、どの符号語ビット。この乗算を実行します（もう一度、2を法とするエントリ）。

<math>\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} </math>

シンドローム 'z' はヌルベクトルなので、受信者はエラーが発生していないと判断できます。この結論は、データベクトルに 'G' を乗算すると、基底の変化が 'H'の[カーネル（行列）|カーネル]であるベクトル部分空間に発生するという観測に基づいています '。送信中に何も起こらない限り、 'は' 'のカーネルに残り、乗算はヌルベクトルを生成します。

エラー訂正

さもなければ、「単一の」ビット誤りが起こったと仮定してください。数学的には、

<math>\mathbf{r} = \mathbf{x} +\mathbf{e}_i</math>

モジュロ2、ここで e_i is the <math>i_{th}</math> unit vector, すなわち、ゼロベクトルでは1で <math>i^{th}</math>,

<math>\mathbf{e}_2 = \begin{pmatrix} 0 \\ 1 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix}</math>

したがって、上記の式は、 <math>i^{th}</math> 場所となる。

今、このベクトルに H:

<math>\mathbf{Hr} = \mathbf{H} \left( \mathbf{x}+\mathbf{e}_i \right) = \mathbf{Hx} + \mathbf{He}_i</math>

'x' は送信されたデータであるため、エラーなしであり、結果として と 'x' の積はゼロです。従って

<math> \mathbf{Hx} + \mathbf{He}_i = \mathbf{0} + \mathbf{He}_i = \mathbf{He}_i</math>

ここで、 と＆lt; math＆gt; i ^ {th}＆lt; / math＆gt;標準基底ベクトルが 'H' の列を選択すると、この列が 'になる場所でエラーが発生することがわかります。

たとえば、ビット＃5にビットエラーを導入したとします。

<math>\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 \end{pmatrix}</math>

ファイル:Hamming(7,4) example 1011 bit 5 error.svg

ビット5でビットエラーが発生すると、赤と緑の円で不良パリティが発生する

]

右側の図は、ビットエラー（青色のテキストで示されています）と、赤色と緑色の円で作成された不良パリティ（赤いテキストで表示）を示しています。ビットエラーは、赤、緑、青の円のパリティを計算することで検出できます。不良パリティが検出された場合、不良パリティサークルと重複するデータビットはエラーのあるビットです。上記の例では、赤と緑の円はパリティが悪いので、赤と緑の交点に対応するビットは青ではなく、エラーのあるビットを示します。

今、

<math>\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 \end{pmatrix} = \begin{pmatrix} 3 \\ 4 \\ 3 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} </math>

'H' の第5列に対応しています。さらに、101のシンドロームが5の2進値に対応するように、使用される一般的なアルゴリズム（Hamming code＃General algorithm を参照）は意図的であり、これは第5ビットが壊れていることを示します。したがって、ビット5でエラーが検出され、修正することができます（単純にその値を反転または無効にします）。

<math> \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} </math>

実際には、この補正された受信値は、上から送信された値「 x '」に一致します。

Decoding

Once the received vector has been determined to be error-free or corrected if an error occurred (assuming only zero or one bit errors are possible) then the received data needs to be decoded back into the original four bits.

First, define a matrix R:

<math>\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} </math>

Then the received value, p_r, is equal to Rr. Using the running example from above

<math>\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} </math>

Multiple bit errors

ファイル:Hamming(7,4) example 1011 bits 4 & 5 error.svg

A bit error on bit 4 & 5 are introduced (shown in blue text) with a bad parity only in the green circle (shown in red text)

It is not difficult to show that only single bit errors can be corrected using this scheme. Alternatively, Hamming codes can be used to detect single and double bit errors, by merely noting that the product of H is nonzero whenever errors have occurred. In the adjacent diagram, bits 4 and 5 were flipped. This yields only one circle (green) with an invalid parity but the errors are not recoverable.

However, the Hamming (7,4) and similar Hamming codes cannot distinguish between single-bit errors and two-bit errors. That is, two-bit errors appear the same as one-bit errors. If error correction is performed on a two-bit error the result will be incorrect.

Similarly, Hamming codes cannot detect or recover from an arbitrary three-bit error; Consider the diagram: if the bit in the green circle (colored red) were 1, the parity checking would return the null vector, indicating that there is no error in the codeword.

All codewords

Since the source is only 4 bits then there are only 16 possible transmitted words. Included is the eight-bit value if an extra parity bit is used (see Hamming(7,4) code with an additional parity bit). (The data bits are shown in blue; the parity bits are shown in red; and the extra parity bit shown in green.)

Data<BR><math>({\color{blue}d_1}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})</math>	Hamming(7,4)		Hamming(7,4) with extra parity bit (Hamming(8,4))
	Transmitted<BR><math>({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4})</math>	Diagram	Transmitted<BR><math>({\color{red}p_1}, {\color{red}p_2}, {\color{blue}d_1}, {\color{red}p_3}, {\color{blue}d_2}, {\color{blue}d_3}, {\color{blue}d_4}, {\color{green}p_4})</math>	Diagram
<span style="color:blue;">0000</span>	<span style="color:red;">00</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">000</span>	Hamming code for 0000 becomes 0000000	<span style="color:red;">00</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">000</span><span style="color:green;">0</span>	Hamming code for 0000 becomes 0000000 with extra parity bit 0
<span style="color:blue;">1000</span>	<span style="color:red;">11</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">000</span>	Hamming code for 1000 becomes 1000011	<span style="color:red;">11</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">000</span><span style="color:green;">1</span>	Hamming code for 1000 becomes 1000011 with extra parity bit 1
<span style="color:blue;">0100</span>	<span style="color:red;">10</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">100</span>	Hamming code for 0100 becomes 0100101	<span style="color:red;">10</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">100</span><span style="color:green;">1</span>	Hamming code for 0100 becomes 0100101 with extra parity bit 1
<span style="color:blue;">1100</span>	<span style="color:red;">01</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">100</span>	Hamming code for 1100 becomes 1100110	<span style="color:red;">01</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">100</span><span style="color:green;">0</span>	Hamming code for 1100 becomes 1100110 with extra parity bit 0
<span style="color:blue;">0010</span>	<span style="color:red;">01</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">010</span>	Hamming code for 0010 becomes 0010110	<span style="color:red;">01</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">010</span><span style="color:green;">1</span>	Hamming code for 0010 becomes 0010110 with extra parity bit 1
<span style="color:blue;">1010</span>	<span style="color:red;">10</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">010</span>	Hamming code for 1010 becomes 1010101	<span style="color:red;">10</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">010</span><span style="color:green;">0</span>	Hamming code for 1010 becomes 1010101 with extra parity bit 0
<span style="color:blue;">0110</span>	<span style="color:red;">11</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">110</span>	Hamming code for 0110 becomes 0110011	<span style="color:red;">11</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">110</span><span style="color:green;">0</span>	Hamming code for 0110 becomes 0110011 with extra parity bit 0
<span style="color:blue;">1110</span>	<span style="color:red;">00</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">110</span>	Hamming code for 1110 becomes 1110000	<span style="color:red;">00</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">110</span><span style="color:green;">1</span>	Hamming code for 1110 becomes 1110000 with extra parity bit 1
<span style="color:blue;">0001</span>	<span style="color:red;">11</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">001</span>	Hamming code for 0001 becomes 0001111	<span style="color:red;">11</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">001</span><span style="color:green;">0</span>	Hamming code for 0001 becomes 0001111 with extra parity bit 0
<span style="color:blue;">1001</span>	<span style="color:red;">00</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">001</span>	Hamming code for 1001 becomes 1001100	<span style="color:red;">00</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">001</span><span style="color:green;">1</span>	Hamming code for 1001 becomes 1001100 with extra parity bit 1
<span style="color:blue;">0101</span>	<span style="color:red;">01</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">101</span>	Hamming code for 0101 becomes 0101010	<span style="color:red;">01</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">101</span><span style="color:green;">1</span>	Hamming code for 0101 becomes 0101010 with extra parity bit 1
<span style="color:blue;">1101</span>	<span style="color:red;">10</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">101</span>	Hamming code for 1101 becomes 1101001	<span style="color:red;">10</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">101</span><span style="color:green;">0</span>	Hamming code for 1101 becomes 1101001 with extra parity bit 0
<span style="color:blue;">0011</span>	<span style="color:red;">10</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">011</span>	Hamming code for 0011 becomes 0011001	<span style="color:red;">10</span><span style="color:blue;">0</span><span style="color:red;">0</span><span style="color:blue;">011</span><span style="color:green;">1</span>	Hamming code for 0011 becomes 0011001 with extra parity bit 1
<span style="color:blue;">1011</span>	<span style="color:red;">01</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">011</span>	Hamming code for 1011 becomes 1011010	<span style="color:red;">01</span><span style="color:blue;">1</span><span style="color:red;">0</span><span style="color:blue;">011</span><span style="color:green;">0</span>	Hamming code for 1011 becomes 1011010 with extra parity bit 0
<span style="color:blue;">0111</span>	<span style="color:red;">00</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">111</span>	Hamming code for 0111 becomes 0111100	<span style="color:red;">00</span><span style="color:blue;">0</span><span style="color:red;">1</span><span style="color:blue;">111</span><span style="color:green;">0</span>	Hamming code for 0111 becomes 0111100 with extra parity bit 0
<span style="color:blue;">1111</span>	<span style="color:red;">11</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">111</span>	Hamming code for 1111 becomes 1111111	<span style="color:red;">11</span><span style="color:blue;">1</span><span style="color:red;">1</span><span style="color:blue;">111</span><span style="color:green;">1</span>	Hamming code for 1111 becomes 1111111 with extra parity bit 1

Source

http://wikipedia.org/