Binary codes that use multiple check digits, called parity bits, to detect and correct s...

Binary codes that use multiple check digits, called parity bits, to detect and correct single digit transmission errors are called Hamming codes. Suppose we want to encode four bits: b₁ b₂ b₃ b₄. Three parity bits will be added at the end of the code, each calculated by using a different set of bits so the new code will contain the original four-bit code and three parity bits. It will now look like b₁ b₂ b₃ b₄ P₁ P₂ P₃. We will use congruence modulo 2 to define the three parity bits as follows:

For example, to the four bit code 1100, we would add the following three parity bits:

The transmission would look like 1100011. However, if there is interference in the transmission, and the receiver picks up the code as 0100011, how will the error be detected and corrected?

Because each of the original four bits shows up in at least two parity bit calculations, a single-bit error will show up in at least two parity bits, as the following table shows.

There was an error detected in parity bit 1, which involved b₁, b₂, and b₃. An error was also detected in parity bit 3 which involved b₁, b₃, and b₄. Notice that the parity bits that detected errors involved b₁ and b₃. Because no error was detected in parity bit 2, which also involved b₃, we conclude that b₃ must not be the source of the error. The error must be in b₁, and the code can be corrected by replacing the 0 with a 1 for the first bit in the four-bit code.

The transmission 1111111 was received as 1001111 with two single-digit errors. Will this type of error be detected? Can it be corrected? Explain.