Editing Hamming code (section)

===[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.