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ビットがフリップされるために媒体が非常に騒がしくなければならないため） 。

Goal

The goal of the Hamming codes is to create a set of parity bits that overlap such that a single-bit error (the bit is logically flipped in value) in a data bit or a parity bit can be detected and corrected. While multiple overlaps can be created, the general method is presented in Hamming codes.

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>

This table describes which parity bits cover which transmitted bits in the encoded word. For example, p₂ provides an even parity for bits 2, 3, 6, and 7. It also details which transmitted bit is covered by which parity bit by reading the column. For example, d₁ is covered by p₁ and p₂ but not p₃ This table will have a striking resemblance to the parity-check matrix (H) in the next section.

Furthermore, if the parity columns in the above table were removed

	<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>

then resemblance to rows 1, 2, and 4 of the code generator matrix (G) below will also be evident.

So, by picking the parity bit coverage correctly, all errors with a Hamming distance of 1 can be detected and corrected, which is the point of using a Hamming code.

Hamming matrices

Hamming codes can be computed in linear algebra terms through matrices because Hamming codes are linear codes. For the purposes of Hamming codes, two Hamming matrices can be defined: the code generator matrix G and the parity-check matrix 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

As mentioned above, rows 1, 2, and 4 of G should look familiar as they map the data bits to their parity bits:

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

The remaining rows (3, 5, 6, 7) map the data to their position in encoded form and there is only 1 in that row so it is an identical copy. In fact, these four rows are linearly independent and form the identity matrix (by design, not coincidence).

Also as mentioned above, the three rows of H should be familiar. These rows are used to compute the syndrome vector at the receiving end and if the syndrome vector is the null vector (all zeros) then the received word is error-free; if non-zero then the value indicates which bit has been flipped.

The four data bits — assembled as a vector p — is pre-multiplied by G (i.e., Gp) and taken modulo 2 to yield the encoded value that is transmitted. The original 4 data bits are converted to seven bits (hence the name "Hamming(7,4)") with three parity bits added to ensure even parity using the above data bit coverages. The first table above shows the mapping between each data and parity bit into its final bit position (1 through 7) but this can also be presented in a Venn diagram. The first diagram in this article shows three circles (one for each parity bit) and encloses data bits that each parity bit covers. The second diagram (shown to the right) is identical but, instead, the bit positions are marked.

For the remainder of this section, the following 4 bits (shown as a column vector) will be used as a running example:

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

Channel coding

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

Mapping in the example x. The parity of the red, green, and blue circles are even.

Suppose we want to transmit this data (<code>1011</code>) over a noisy communications channel. Specifically, a binary symmetric channel meaning that error corruption does not favor either zero or one (it is symmetric in causing errors). Furthermore, all source vectors are assumed to be equiprobable. We take the product of G and p, with entries modulo 2, to determine the transmitted codeword x:

<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>

This means that <code>0110011</code> would be transmitted instead of transmitting <code>1011</code>.

Programmers concerned about multiplication should observe that each row of the result is the least significant bit of the Population Count of set bits resulting from the row and column being Bitwise ANDed together rather than multiplied.

In the adjacent diagram, the seven bits of the encoded word are inserted into their respective locations; from inspection it is clear that the parity of the red, green, and blue circles are even:

• red circle has two 1's
• green circle has two 1's
• blue circle has four 1's

What will be shown shortly is that if, during transmission, a bit is flipped then the parity of two or all three circles will be incorrect and the errored bit can be determined (even if one of the parity bits) by knowing that the parity of all three of these circles should be even.

Parity check

If no error occurs during transmission, then the received codeword r is identical to the transmitted codeword x:

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

The receiver multiplies H and r to obtain the syndrome vector z, which indicates whether an error has occurred, and if so, for which codeword bit. Performing this multiplication (again, entries modulo 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>

Since the syndrome z is the null vector, the receiver can conclude that no error has occurred. This conclusion is based on the observation that when the data vector is multiplied by G, a change of basis occurs into a vector subspace that is the kernel of H. As long as nothing happens during transmission, r will remain in the kernel of H and the multiplication will yield the null vector.

Error correction

Otherwise, suppose a single bit error has occurred. Mathematically, we can write

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

modulo 2, where e_i is the <math>i_{th}</math> unit vector, that is, a zero vector with a 1 in the <math>i^{th}</math>, counting from 1.

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

Thus the above expression signifies a single bit error in the <math>i^{th}</math> place.

Now, if we multiply this vector by H:

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

Since x is the transmitted data, it is without error, and as a result, the product of H and x is zero. Thus

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

Now, the product of H with the <math>i^{th}</math> standard basis vector picks out that column of H, we know the error occurs in the place where this column of H occurs.

For example, suppose we have introduced a bit error on bit #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

A bit error on bit 5 causes bad parity in the red and green circles

The diagram to the right shows the bit error (shown in blue text) and the bad parity created (shown in red text) in the red and green circles. The bit error can be detected by computing the parity of the red, green, and blue circles. If a bad parity is detected then the data bit that overlaps only the bad parity circles is the bit with the error. In the above example, the red and green circles have bad parity so the bit corresponding to the intersection of red and green but not blue indicates the errored bit.

Now,

<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>

which corresponds to the fifth column of H. Furthermore, the general algorithm used (see Hamming code#General algorithm) was intentional in its construction so that the syndrome of 101 corresponds to the binary value of 5, which indicates the fifth bit was corrupted. Thus, an error has been detected in bit 5, and can be corrected (simply flip or negate its value):

<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>

This corrected received value indeed, now, matches the transmitted value x from above.

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/