Editing Hamming code (section)

==[7,4] Hamming code==
{{main|Hamming(7,4)}}
[[File:Hamming(7,4).svg|thumb|300px|Graphical depiction of the four data bits and three parity bits and which parity bits apply to which data bits]]

In 1950, Hamming introduced the [7,4] Hamming code. It encodes four data bits into seven bits by adding three parity bits. As explained earlier, it can either detect and correct single-bit errors or it can detect (but not correct) both single and double-bit errors.

With the addition of an overall parity bit, it becomes the [8,4] extended Hamming code and can both detect and correct single-bit errors and detect (but not correct) double-bit errors.

===Construction of G and H===
The matrix 
<math>\mathbf{G} := \begin{pmatrix} \begin{array}{c|c}
I_k & -A^\text{T} \\
\end{array} \end{pmatrix}</math> is called a (canonical) generator matrix of a linear (''n'',''k'') code,

and <math>\mathbf{H} := \begin{pmatrix} \begin{array}{c|c}
A & I_{n-k} \\
\end{array} \end{pmatrix}</math> is called a [[parity-check matrix]].

This is the construction of '''G''' and '''H''' in standard (or systematic) form. Regardless of form, '''G''' and '''H''' for linear block codes must satisfy

<math>\mathbf{H}\,\mathbf{G}^\text{T} = \mathbf{0}</math>, an all-zeros matrix.<ref name=Moon>Moon T. Error correction coding: Mathematical Methods and
Algorithms. John Wiley and Sons, 2005.(Cap. 3) {{ISBN|978-0-471-64800-0}}</ref>

Since [7,&nbsp;4,&nbsp;3] =&nbsp;[''n'',&nbsp;''k'',&nbsp;''d''] =&nbsp;[2<sup>''m''</sup>&nbsp;−&nbsp;1, 2<sup>''m''</sup>&nbsp;−&nbsp;1&nbsp;−&nbsp;''m'',&nbsp;3]. The [[parity-check matrix]] '''H''' of a Hamming code is constructed by listing all columns of length ''m'' that are pair-wise independent.

Thus '''H''' is a matrix whose left side is all of the nonzero ''n''-tuples where order of the ''n''-tuples in the columns of matrix does not matter. The right hand side is just the (''n''&nbsp;−&nbsp;''k'')-[[identity matrix]].

So '''G''' can be obtained from '''H''' by taking the transpose of the left hand side of '''H''' with the identity ''k''-[[identity matrix]] on the left hand side of&nbsp;'''G'''.

The code [[generator matrix]] <math>\mathbf{G}</math> and the [[parity-check matrix]] <math>\mathbf{H}</math> are:

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

and

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

Finally, these matrices can be mutated into equivalent non-systematic codes by the following operations:<ref name=Moon/>

* Column permutations (swapping columns)
* Elementary row operations (replacing a row with a linear combination of rows)

===Encoding===
;Example

From the above matrix we have 2<sup>k</sup> = 2<sup>4</sup> = 16 codewords.
Let <math>\vec{a}</math> be a row vector of binary data bits, <math> \vec{a}=[a_1,a_2,a_3,a_4],\quad a_i\in \{0,1\} </math>. The codeword <math>\vec{x}</math> for any of the 16 possible data vectors <math> \vec{a} </math> is given by the standard matrix product <math>\vec{x}=\vec{a}G </math> where the summing operation is done modulo-2.

For example, let <math>\vec{a}=[1,0,1,1]</math>. Using the generator matrix <math>G</math> from above, we have (after applying modulo 2, to the sum),

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

===[8,4] Hamming code with an additional parity bit===
[[File:Hamming(8,4).svg|thumb|300px|The same [7,4] example from above with an extra parity bit. This diagram is not meant to correspond to the matrix H for this example.]]

The [7,4] Hamming code can easily be extended to an [8,4] code by adding an extra parity bit on top of the (7,4) encoded word (see [[Hamming(7,4)]]).
This can be summed up with the revised matrices:

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

and

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

<!-- the equations here before had two (2) errors--these satisfy G*H^T=0 -->

<!-- I don't have the time to fix it myself right now, but in the format G is in after row-reduction, it changes the order -->
<!-- of the bits in the message being delivered... i.e., any of the columns of G with one hi bit will pass the data directly -->
<!-- Ex. [d1 d2 d3 d4] * G = [d1 d2 d3 d4 p1 p2 p3 p4], this is not the same as the format described immediately below it -->
<!-- where the message should be in the format [p1 p2 d1 p3 d2 d3 d4 p4] -->

Note that H is not in standard form. To obtain G, elementary row operations can be used to obtain an equivalent matrix to H in systematic form:

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

For example, the first row in this matrix is the sum of the second and third rows of H in non-systematic form. Using the systematic construction for Hamming codes from above, the matrix A is apparent and the systematic form of G is written as

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

The non-systematic form of G can be row reduced (using elementary row operations) to match this matrix.

The addition of the fourth row effectively computes the sum of all the codeword bits (data and parity) as the fourth parity bit.

For example, <span style="color:blue;">1011</span> is encoded (using the non-systematic form of G at the start of this section) into <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> where blue digits are data; red digits are parity bits from the [7,4] Hamming code; and the green digit is the parity bit added by the [8,4] code.
The green digit makes the parity of the [7,4] codewords even.

Finally, it can be shown that the minimum distance has increased from 3, in the [7,4] code, to 4 in the [8,4] code. Therefore, the code can be defined as [8,4] Hamming code. <!-- if we need more proof, or a citation, let me know -->

To decode the [8,4] Hamming code, first check the parity bit. If the parity bit indicates an error, single error correction (the [7,4] Hamming code) will indicate the error location, with "no error" indicating the parity bit. If the parity bit is correct, then single error correction will indicate the (bitwise) exclusive-or of two error locations. If the locations are equal ("no error") then a double bit error either has not occurred, or has cancelled itself out. Otherwise, a double bit error has occurred.