Error Control Codes: Detection and Correction

Posted on Mar 19, 2025 in Electronics

Error Control Codes in Computer Communication

To enable communication between two different computers, a code is necessary. This code consists of a limited set of symbols combined by specific rules known to both the sender and receiver. When a recipient receives a message coded in natural binary, it contains only digits that can have two values: 0 and 1. Each digit is called a bit.

Error Detection Codes

Binary code is suitable for representing decimal numbers. However, it’s very sensitive to errors in data transmission. A single changed bit can cause the receiver to interpret the word as a different number or character. To minimize errors caused by the transmission channel, coding procedures are used to detect errors, though not their exact location within the word. These codes warn of an error but cannot pinpoint it.

Parity Code

The simplest error detection code is the parity check. It adds a digit to the code word, with the value depending on the digits forming the word. There are two methods of simple parity checks:

  • Even Parity: A ‘1’ is added if the original word contains an odd number of ones, and a ‘0’ is added if it contains an even number of ones.
  • Odd Parity: A ‘1’ is added if the original word contains an even number of ones, and a ‘0’ is added if it contains an odd number of ones.

A more efficient error detection method is two-dimensional parity checking. This involves dividing the information into fragments of the same number of bits, arranging them in a matrix, and applying parity checks to both rows and columns. This adds a bit for each row (horizontal parity) and an entire row for vertical parity.

Cyclic Redundancy Code (CRC)

For more complex errors (involving multiple digits), the Cyclic Redundancy Code (CRC) is used. Different versions of CRC are employed to detect errors during the transmission process.

Error Correction Methods

  • Backward Error Correction (at the sender): Errors are corrected by retransmission.
  • Forward Error Correction (at the receiver): The receiver receives enough control information to detect and correct the error itself, without requesting retransmission.

These are the more traditional methods. The steps used in transmitting information using CRC are:

  1. A natural binary word of N bits is given. R digits, all with a value of 0, are added to the end. The value R is called the degree of the code (message polynomial).
  2. The previous bit string is divided by another word, called the generator polynomial or divisor polynomial, which is R+1 bits in length. The division is performed in binary.
  3. The remainder (residue polynomial) obtained from the binary division in step 2 is subtracted from the bit string in step 1. This results in the encoded CRC word.

When the encoded CRC word is received, the following steps are taken:

  1. Divide the binary codeword polynomial by the CRC generator polynomial.
  2. If the remainder is all zeros, it means no error has occurred.
  3. If the remainder is not all zeros, it means an error has occurred during transmission.

Three widely used CRC codes are:

  • CRC-12: Its generator polynomial is 110000000011 and is used for 6-bit data words.
  • CRC-16: The generator polynomial is 11000000000000101 and is used for 8-bit data words.
  • CRC-CCITT: The generator polynomial is 10001000000100001 and is used for 8-bit data words.

Error Detection and Correction Codes

Error-correcting codes not only indicate the existence of an error but also provide information about which binary digit(s) are affected. This allows for correction by inverting their values. These codes are primarily used when retransmission is impossible or in systems with high error rates. They are less useful in low-error-rate systems where retransmission is feasible, as the number of redundant digits needed to correct multiple bit errors is large relative to the word length.