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.
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
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