5.2 Error Correction

COS2621 - Computer Organisation · 5. Internal Memory

Error Correction

Introduction to Error Correction

Error correction is essential in computer memory systems. It helps identify and correct errors that occur during data storage or transmission. Errors can arise from various sources, such as electrical interference, hardware malfunctions, or cosmic rays. Without error correction, data integrity could be compromised, leading to system failures or incorrect data processing.

Types of Errors

There are two main types of errors:

  • Single-bit errors: These occur when only one bit of data is corrupted. For example, if the original data is 1101, it may change to 1001.
  • Multiple-bit errors: These involve two or more bits being corrupted. For instance, the data 1101 could change to 1110.

Error Detection and Correction Techniques

Common techniques for error detection and correction include:

Parity Bits

A parity bit is an additional bit added to a binary number to ensure that the total number of 1-bits is even (even parity) or odd (odd parity). For example, for the binary number 1101, the parity bit for even parity would be 1, making it 11101. If the received number is 11100, it indicates an error since it has an odd number of 1-bits.

Remember: The left-most bit is often used as the parity bit.

Checksums

A checksum is a value calculated from a data set and sent along with the data. The receiver recalculates the checksum and compares it with the received checksum. If they do not match, an error is detected. For example, if the data is 1010 and the checksum is calculated as 2 (in decimal), the receiver will check if the checksum matches.

Cyclic Redundancy Check (CRC)

CRC is a more advanced error detection method that uses polynomial division to generate a checksum. It is more reliable than simple checksums. If the calculated CRC at the receiver does not match the transmitted CRC, an error is detected.

Hamming Code

The Hamming code is an error correction technique that can detect and correct single-bit errors. It adds multiple parity bits to the data. For example, to encode the 4-bit data 1101, the Hamming code adds 3 parity bits, resulting in a 7-bit code. The positions of the parity bits are powers of 2 (1, 2, 4).

Consider the data 1101:

  • Data bits are placed in positions 3, 5, 6, and 7.
  • Parity bits are calculated as follows:
    • P1 checks bits 1, 3, 5, 7
    • P2 checks bits 2, 3, 6, 7
    • P4 checks bits 4, 5, 6, 7

After calculating the parity bits, the Hamming code for data 1101 becomes 1110110. If an error occurs, the parity bits will indicate the position of the error, allowing for correction. Hamming code can correct single-bit errors and detect two-bit errors.

Conclusion

Error correction is vital for maintaining data integrity in computer memory systems. Techniques such as parity bits, checksums, CRC, and Hamming codes are commonly used to detect and correct errors.

Check your understanding

  • What is the purpose of a parity bit?
  • How does a checksum work?
  • What is the advantage of using Hamming code over simple parity checks?
  • Can CRC detect multiple-bit errors? Explain.

Test yourself

5 quick questions on this lesson. Pick an answer to see if you're right.

  1. 1. Which one of the following binary codes have even parity (assume that the left-most bit is the parity bit)?

  2. 2. Which error detection technique uses polynomial division to generate a checksum?

  3. 3. What is the primary purpose of a parity bit in error correction?

  4. 4. What type of errors can Hamming code correct?

  5. 5. Which of the following statements is true regarding checksums?