Hamming(7,4)
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>
前述のように、 'G' の1,2および4行は、データビットをパリティビットにマップするときによく分かるはずです。
- p<sub>1</sub> covers d<sub>1</sub>, d<sub>2</sub>, d<sub>4</sub>
- p<sub>2</sub> covers d<sub>1</sub>, d<sub>3</sub>, d<sub>4</sub>
- p<sub>3</sub> covers d<sub>2</sub>, d<sub>3</sub>, d<sub>4</sub>
残りの行(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>
チャネルコーディング[編集]
このデータ([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<sub>i</sub> 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>
右側の図は、ビットエラー(青色のテキストで示されています)と、赤色と緑色の円で作成された不良パリティ(赤いテキストで表示)を示しています。ビットエラーは、赤、緑、青の円のパリティを計算することで検出できます。不良パリティが検出された場合、不良パリティサークルと重複するデータビットはエラーのあるビットです。上記の例では、赤と緑の円はパリティが悪いので、赤と緑の交点に対応するビットは青ではなく、エラーのあるビットを示します。
今、
- <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 '」に一致します。
デコード[編集]
エラーが発生した場合(ゼロまたは1ビットエラーのみが可能であると仮定して)、受信されたベクトルがエラーなしであると判定されると、受信したデータを元の4ビットに復号化する必要があります。
まず、行列 '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>
次に、受信された値 'p r </ sub>' は、 'R' に等しい。上記の実行例を使用する
- <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>
複数のビットエラー[編集]
このスキームを使用して単一ビットエラーのみを訂正できることを示すことは困難ではない。あるいは、エラーが発生するたびに の積が非ゼロであることに留意するだけで、ハミングコードを使用してシングルビットエラーおよびダブルビットエラーを検出することができます。隣接する図では、ビット4と5が反転されています。これにより、無効なパリティを持つ円(緑色)が1つしか生成されませんが、エラーは回復できません。
しかしながら、ハミング(Hamming)(7,4)及び類似のハミング符号は、単一ビット誤りと2ビット誤りとを区別することができない。つまり、2ビットのエラーは1ビットのエラーと同じに見えます。エラー訂正が2ビットエラーで実行された場合、結果は正しくありません。
同様に、ハミング符号は、任意の3ビット誤りを検出または回復することができない。ダイアグラムを考えてみましょう。緑色の丸(赤色)のビットが1の場合、パリティチェックはヌルベクトルを返し、コードワードにエラーがないことを示します。
すべてのコードワード[編集]
ソースはわずか4ビットであるので、16の可能な送信語しか存在しない。余分なパリティビットが使用されている場合、8ビットの値が含まれます(追加のパリティビットを持つハミングコード| .5B7.2C4.5Dハミングコード|追加のパリティビット付きのハミング(7,4)コード) ] )。 (データビットは青で表示され、パリティビットは赤で表示され、余分なパリティビットは緑で表示されます)。
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 |