How does error correction work

The constructed sets of data and error bits are known as Hamming codes. Let's see how to construct the 7, 4 Hamming codes that is, the code is seven bits long, of which four bits are data bits. Number the bits starting from one: 1, 2, 3, 4, 5, 6, 7.

Write them in binary: 1, 10, 11, , , , All of the bits with an index that has only a single one bit are parity bits, the others are data bits. Hence, the parity bits are found at indexes that are powers of two: 1, 2, 4; and the data bits are at 3, 5, 6, 7. Each data bit is included in the calculation for two or more parity bits. In particular, parity bit one P1 is calculated from those bits whose index has the least significant bit set: 1, 11, , , or 1, 3, 5, 7.

Parity bit two at index two, or 10 in binary , P2, is calculated from those bits whose index has the second least significant bit set: 10, 11, , , or 2, 3, 6, 7. Parity bit three at index four or binary is calculated from those bits whose index has the third least significant bit set: , , , , or 4, 5, 6, 7. We'll apply this to some example data: Write it out as x, x, 1, x, 0, 1, 0, where each x defines one of the even parity bits we need to calculate.

Parity bit one is calculated from bits 3, 5, 7 which are 1, 0, 0 and hence is one. Parity bit two is calculated from bits 3, 6, 7 and is therefore zero.

Parity bit four is calculated from 5, 6, 7 and is one. The complete Hamming code for is Figure 2 shows this construction and calculation. Let's transmit this and assume that the receiver gets , with a single bit flipped. We can do the Hamming code calculation on the data bits, get , and therefore detect that the received code is invalid.

But there's something more we can deduce. If we look at the parity bits, we can see that bits one and four are incorrect, whereas two is right. The common data bit used for the calculation of parity bits one and four is bit five. Since the Hamming code ensures that each parity bit is calculated from a distinct set of data bits, we can conclude that it is data bit five that is incorrect: it should be zero, not one.

Hence Hamming codes are not only error detection, but error correction codes. In fact, through some pretty heavy duty mathematics we can show that Hamming codes are the most efficient way to add parity bits to detect and correct one-bit errors.

Hamming codes are less used now, as better detection and correction algorithms have been devised, like Reed-Solomon codes, which can cope with burst errors rather than the less noisy random errors detected and corrected by Hamming codes.

Whenever a message is transmitted, it may get scrambled by noise or data may get corrupted. To avoid this, we use error-detecting codes which are additional data added to a given digital message to help us detect if an error occurred during transmission of the message. A simple example of error-detecting code is parity check. Along with error-detecting code, we can also pass some data to figure out the original message from the corrupt message that we received.

This type of code is called an error-correcting code. Error-correcting codes also deploy the same strategy as error-detecting codes but additionally, such codes also detect the exact location of the corrupt bit. In error-correcting codes, parity check has a simple way to detect errors along with a sophisticated mechanism to determine the corrupt bit location. In this case, the receiver asks for retransmission only if the parity data bits are not enough for successful error detection and correction.

By: Justin Stoltzfus Contributor, Reviewer. By: Satish Balakrishnan. Dictionary Dictionary Term of the Day. Natural Language Processing. Techopedia Terms. Connect with us. Sign up. The overhead involved is usually far greater than that required for error-detection schemes, and for this reason error correction is generally only used for applications where re-transmission of the data is not practical.

In some schemes, a compromise hybrid solution is used in which minor errors are corrected using error correction codes, while major errors result in a request for retransmission. Signals from Voyager 1 now take more than fourteen hours to reach Earth.

An error-detecting code or backward error correction involves the addition of sufficient redundant data to the information being sent to enable the receiver to detect errors and request the receiver to retransmit the data. This approach is known as an automatic repeat request ARQ strategy. A number of commonly used error detection schemes exist, which vary considerably in their complexity. The amount of additional information sent is usually the same for a given amount of data, and the error detection information will have a relationship to the data that is determined by the application of an algorithm of some kind to the data itself.

The receiver applies the same algorithm to the data it receives to obtain its own version of the error correction code, and then compares that version with the error correction code it has received.