Error-Correcting Codes: Hamming Codes

For the (7,4) example, we have

error patterns that can be corrected. We start with single-bit error patterns, and multiply them by the parity check matrix. If we obtain unique answers, we are done; if two or more error patterns yield the same result, we can try double-bit error patterns. In our case, single-bit error patterns give a unique result.

eHe
1000000101
0100000111
0010000110
0001000011
0000100100
0000010010
0000001001

Parity Check Matrix

This corresponds to our decoding table: We associate the parity check matrix multiplication result with the error pattern and add this to the received word. If more than one error occurs (unlikely though it may be), this "error correction" strategy usually makes the error worse in the sense that more bits are changed from what was transmitted.

As with the repetition code, we must question whether our (7,4) code's error correction capability compensates for the increased error probability due to the necessitated reduction in bit energy. Figure shows that if the signal-to-noise ratio is large enough channel coding yields a smaller error probability. Because the bit stream emerging from the source decoder is segmented into four-bit blocks, the fair way of comparing coded and uncoded transmission is to compute the probability of block error: the probability that any bit in a block remains in error despite error correction and regardless of whether the error occurs in the data or in coding buts. Clearly, our (7,4) channel code does yield smaller error rates, and is worth the additional systems required to make it work.

Probability of error occurring

Note that our (7,4) code has the length and number of data bits that perfectly fits correcting single bit errors. This pleasant property arises because the number of error patterns that can be corrected,

, equals the codeword length

. Codes that have

are known as Hamming codes, and the following table provides the parameters of these codes. Hamming codes are the simplest single-bit error correction codes, and the generator/parity check matrix formalism for channel coding and decoding works for them.

NNKKEE (efficiency)
310.33
740.57
15110.73
31260.84
63570.90
1271200.94

Hamming Codes

Unfortunately, for such large blocks, the probability of multiple-bit errors can exceed the number of single-bit errors unless the channel single-bit error probability

is very small. Consequently, we need to enhance the code's error correcting capability by adding double as well as single-bit error correction.

Exercise

What must the relation between

and

be for a code to correct all single- and double-bit errors with a "perfect fit"?

In a length-

block,

single-bit and

double-bit errors can occur. The number of non-zero vectors resulting from

must equal or exceed the sum of these two numbers.

The first two solutions that attain equality are (5,1) and (90,78) codes. However, no perfect code exists other than the single-bit error correcting Hamming code. (Perfect codes satisfy relations like Equation with equality.)

 

This textbook is open source. Download for free at http://cnx.org/contents/778e36af-4c21-4ef7-9c02-dae860eb7d14@9.72.

 
Use left and right arrow keys to change pagesUse left and right arrow keys to change pages.
Swipe left and right to change pages.\Swipe left and right to change pages.
Make Bread with our CircuitBread Toaster!

Get the latest tools and tutorials, fresh from the toaster.

What are you looking for?