CEN 4500C Fundamentals of Computer Communication Networks

R. E. Newman-Wolfe , University of Florida

Last modified 1/30/95.

Error-detection and error-correction

Here we consider how to determine whether a logical unit of data has been received correctly (after either data transmission or storage), and if it is determined to be incorrect, how to attempt to correct it. First we develop some terminology and mathematics needed to describe errors and then we give several methods of error detection and correction. We will assume that the receiver has achieved block synchronization, which is the topic of the previous page .

1. Preliminaries

2. Methods of Error Detection

  • c. CRC - Cyclic Redundancy Check
  • Given a m-bit message M, and a predetermined (r+1)-bit number P, generate an r-bit frame check sequence (FCS) that, appended to M, will produce an (m+r)-bit number T divisible by P (modulo 2). This can also be viewed as polynomials with binary coefficients, with operations again modulo 2, so When the received transmission T', is divided by P, it is assumed to be error-free if and only if it has no remainder.
  • Errors that won't be caught by CRC:
  • Check out Ross N. Williams' A PAINLESS GUIDE TO CRC ERROR DETECTION ALGORITHMS for a longer and nicer explanation, along with code and some practical tips.

    3. Methods of Error Correction

    4. Burst errors

    Most of the techniques described do not handle burst errors well. LRC/VRC does reasonably well, since a burst no longer than word length will be detected by the LRC, and CRC does very well with most bursts (as noted in that section). In order to improve the performance of parity or Hamming codes in the presence of burst errors, we can buffer a frame of words, each with its own redundant bits, and then send out the bits of the frame column by column rather than by rows. If a burst is shorter than the number of rows in the frame, then each row will have one or fewer errors, and they will all be detected (or corrected). This is interleaving , and may be done on the bit, byte, word, or block level. Burst errors are distributed over the interleaved (time-division multiplexed) channels, so that if K channels are interleaved (i.e., an interleaving depth of K is used), then each channel suffers an error of length roughly 1/K of the original burst error. In this way, the LRC/VRC can detect bursts that are no longer than the number of rows in a column. LRC/VRC is a form of concatenated coding, another effective way to increase the power of error correction methods and resistance to burst errors.

    5. Tape Storage - Error Correction

    Nine-track tapes (as well as other storage media) use forward error correction methods. One common method is to use the ninth track as a parity track, and include a powerful error detection check sequence at the end of each block stored on the medium. Since a common error is to have one bad track, this bad track is likely to be detected by the check sequence at the end of the block, and as long as only one track is bad, the parity track can be used to correct the errorful track.

    6. Concatenated Codes

    When a data channel is coded at more than one level, then it is said to be encoded using concatenated coding. Essentially the inner code (the one closest to the transmitter)...(to be continued.... ran out of time just now :( ) In addition to the receiver being able to detect errors and perhaps to correct them, the sender and the receiver need to agree upon some common control information and frame formats, along with protocols to use in order to effect the successful transfer of a sequence of frames. Datalink control and sliding window protocols are the topic of the next page .
    This document is copyright 1995 by Richard E. Newman-Wolfe.
    Send comments to nemo@cis.ufl.edu