The Hamming codes are an important class of single error correcting codes that can easily encode and decode. They were originally used in controlling errors in long-distance telephone calls. Binary Hamming codes have the following parameters:
Code length:
Dimension:
Minimum distance:
The easiest way to describe a Hamming code is through its parity check matrix. For a binary Hamming code of length , first construct an matrix whose columns are all nonzero binary -tuples. For example, for a binary Hamming code we take , so and , and start with
In order to obtain a parity check matrix for a code in systematic form, we move the appropriate columns to the end so that the matrix ends with the identity matrix. The order of the other columns is irrelevant. The result is the parity check matrix for a Hamming code. In our example, we move the 4th, 2nd, and 1st columns to the end to obtain
which is the matrix from Exercise 3.
We can easily calculate a generator matrix from the parity check matrix . Since Hamming codes are single error correcting codes, the syndrome method for decoding can be simplified. In particular, the error vector is allowed to have weight at most 1, and therefore will be zero or will have all zeros except for a single in the th position.
The Hamming decoding algorithm, which corrects up to one bit error, is as follows:
Compute the syndrome for the received vector . If , then there are no errors. Return the received vector and exit.
Otherwise, determine the position of the column of that is the transpose of the syndrome.
Change the th bit in the received word, and output the resulting code.
As long as there is at most one bit error in the received vector, the result will be the codeword that was sent.
The binary Hamming code has parity check matrix
Assume the received vector is
The syndrome is calculated to be . Notice that is the transpose of the 11th column of , so we change the 11th bit of to get the decoded word as
Since the first 11 bits give the information, the original message was
Therefore, we have detected and corrected the error.
3.129.26.108