The (7,4) Hamming Code

 

Hamming codes are (n,m) linear block codes with the number of check bits equal to:



Single error correction or double error detection.


Let

To formulate the P submatrix, use Hammings rule:

Let the m rows of P have all k(=3) bit words with 2 or more 1's in any order.

A generator matrix, G, is defined such that when multiplied by the message vector, M, the code word X results.

where

=[4x4] identity matrix (for a (7,4) hamming code)

=[4x3] thus:


G = nxm generator matrix for the (n,m) hamming code.
Let
M = a block of m message bits (4 bits for a (7,4) code).
Let
C= a block of k check bits (k=3 bits = 7-4, for a (7,4) code)

Let X = code vector of n bits, such that:

A code vector is obtained by the formula:

The check vector is obtained via:

Let W(x) be the scalar weight of a code word, so, for the first 8 of the 16 code words, we can compute a table:

Let X= transmitted code word and Y= code word received.
if

a transmission error was made, but the converse is not always true.
Let

So that

Please verify, for yourself, that

provided that X is a code vector.
Let
E be an error vector which shows where a single bit error has occured in an n bit code word.

So s depends only on the error vector, E and is computed, simply, as:

,S

At the rcvr, we compute

and find out where the error happened.