Error-Correcting Codes: Hamming Codes

Module by: Don Johnson

Summary: A description of some strategies for minimizing there errors in a transmitted bit-stream.

Note: You are viewing an old version of this document. The latest version is available here.

For the (7,4) example, we have 2N-K-1=7 2 N K 1 7 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.

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 increases error probability due to the necessitated reduced bit energy. Figure 2 shows that if the signal-to-noise ratio is large enough channel coding yeilds a smaller error probability. Because the bit stream emerging from the source coder 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 yeild smaller error rates, and is worth the additional systems required to make it work.

Figure 1: The probability of an error occuring in transmitted K=4 K 4 data bits equals 1-1- p e 4 1 1 p e 4 as 1- p e 4 1 p e 4 equals the probability that the four bits are received without error. The upper curve displays how this probability of an error anywhere in the four-bit block varies with the signal-to-noise ratio. When a (7,4) single-bit error correcting code is used, the transmitter reduced the energy it expends during a single-bit transmission by 4/7, appending three extra bits for error correction. Now the probability of any bit in the seven-bit block being in error after error correction equals 1-1- p e 7-7 p e ′ 1- p e ′ 6 1 1 p e 7 7 p e ′ 1 p e ′ 6 , where p e ′ p e ′ is the probability of a bit error occuring in the channel when channel coding occurs. Here 7 p e ′ 1- p e ′ 6 7 p e ′ 1 p e ′ 6 equals the probability of exactly on in seven bits emerging from the channel in error; The channel decoder corrects this type of error, and all data bits in the block are received correctly.

Probability of error occuring

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, 2N-K-1 2 N K 1 , equals the codeword length NN. Codes that have 2N-K-1=N 2 N K 1 N 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.

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 p e p e is very small. Consequently, we need to enhance the code's error correcting capability by adding double as well as single-bit error correction.

Comments, questions, feedback, criticisms?

Send feedback

• E-mail the author of the module, Error-Correcting Codes: Hamming Codes

Footer

More about this content: Metadata | Version History

• How to reuse and attribute this content
• How to Cite and attribute this content

This work is licensed by Don Johnson under a Creative Commons Attribution License (CC-BY 1.0).

Last edited by (Unknown) on Nov 20, 2002 12:00 am US/Central.