Error Detection
Error detection in a block becomes possible with one parity check bit. We simply choose the parity check bit so that there is an even number of 1 s in a block. For example, if the information bits are 1011, then the parity check bit would be 1. We write the corresponding block as 1011|1. Other examples of blocks are 0110|0, 1000|1, and 1001|0.
Notice what happens when a single bit error occurs in a block. If a 0 becomes a 1, then the total number of 1 s in the block increases by one. On the other hand, if a 1 becomes a 0, then the total number of 1 s decreases by one. Either way, the total number of 1 s is now odd. Thus, any single bit error can be detected. Note that the bit in error can be an information bit or the parity check bit.
A precise algorithm for the error detection can be described as follows. Examine whether the parity check bit creates even parity in the block. If it does, we declare that there is no error. Otherwise, we declare that there is an error.
2. Error Correction
Whereas the method for error detection works on any number of information bits, the following method for error correction is for blocks containing exactly 4 information bits together with 3 parity check bits.
Recall that we are concerned with single bit errors in a block. To locate the single bit error, we will check for its existence in selected subsets of the block using error detection and from there deduce its position. The bit in error can then of course be corrected.
For a block of 7 bits, we use 3 subsets as illustrated by the circles below. The 4 regions of intersections represent the informations bits, while the 3 remaining regions represent the parity check bits. By placing an ordering on the regions, we can write out the 7 bits as a block.
The parity check bits are chosen to create even parity in their respective circles. Note that each circle has the error detection described earlier. So whenever a parity check bit fails to create even parity in its circle, the single bit error must be located somewhere in that circle. Knowing which of the circles contain the single bit error and which do not allows us to pinpoint its exact location. Place the mouse over any region to select the location of the single bit error. The parity check bits that fail to create even parity in their circles will flash in red. We see a one-to-one correspondence between the location of the single bit error and the parity check bits failing to create even parity in their circles. Note that, as with the error detection, the bit in error can be an information bit or a parity check bit.