Error detection and correction

ERROR DETECTION AND CORRECTION

The reliability of a memory unit may be improved by employing error-detecting and error-correcting codes. The most common error detection scheme is the parity bit. A parity bit is generated and stored along with the data word in memory. The parity of the word is checked after reading it from memory. The data word is accepted if the parity of the bits read out is correct. If the parity checked results in an inversion, an error is detected, but it cannot be corrected.

An error-correcting code generates multiple parity check bits that are stored with the data word in memory. Each check bit is parity over a group of bits in the data word. When the word is read back from memory, the associated parity bits are also read from memory and compared with a new set of check bits generated from the data that have been read. If the check bits are correct, no error has occurred. If the check bits do not match the stored parity, they generate a unique pattern called a syndrome, which can be used to identify the bit that is in error. A single error occurs when a bit changes in value from 1 to 0 or from 0 to 1 during the write or read operation. If the specific bit in error is identified, then the error can be corrected by complementing the erroneous bit.

ü    Hamming Code

One of the most common error-correcting codes used in RAMs was devised by R. W. Hamming. In the Hamming code, k. parity bits are added to an n-bit data word, forming a new word of n + k bits. The bit positions are numbered in sequence from 1 to n + k, these positions numbered as a power of 2 are reserved for the parity bits. The remaining bits are the data bits.

Consider, for example the 8-bil data word 11000100. We include 4 parity bits with the 8-bit word and arrange the 12 bits as follows:

The 4 parity bits P1, P2, P4 and P8 are in positions 1, 2, 4 and 8 respectively. The 8 bits of the data word are in the remaining positions. Each parity bit is calculated as follows:

The 8-bit data word is stored in memory together with the 4 parity bits as a 12-bit composite word. Substituting the 4 P bits in their proper positions, we obtain the 12-bit composite word stored in memory.

When the 12 bits are read from memory, they are checked again for errors. The parity is checked over the same combination of bits, including the parity bit. The 4 check bits are evaluated as follows:

ü    Single-Error Correction, Double-Error Detection

The Hamming code can detect and correct only a single error. By adding another parity bit to the coded word, the Hamming code can be used to correct a single error and detect double errors.