Error Detection and Correction Study Notes

  • Data can be corrupted during transmission. Some applications require that errors be detected and corrected.
  • In a single-bit error, only one bit in the data unit has changed. A burst error means that two or more bits in the data unit have changed.
  • To detect or correct errors, we need to send extra (redundant) bits with data.
  • There are two main methods of error correction: forward error correction and correction by retransmission.
  • We can divide coding schemes into two broad categories: block coding and convolution coding.
  • In coding, we need to use modulo-2 arithmetic. Operations in this arithmetic are very simple; addition and subtraction give the same results. we use the XOR (exclusive OR) operation for both addition and subtraction.
  • In block coding, we divide our message into blocks, each of k bits, called datawords. We add r redundant bits to each block to make the length n ::: k + r. The resulting n-bit blocks are called codewords.
  • In block coding, errors be detected by using the following two conditions:
  •    a. The receiver has (or can find) a list of valid codewords.
    b. The original codeword has changed to an invalid one.
  • The Hamming distance between two words is the number of differences between corresponding bits. The minimum Hamming distance is the smallest Hamming distance between all possible pairs in a set of words.
  • To guarantee the detection of up to s errors in all cases, the minimum Hamming distance in a block code must be d
    min ::: s + 1. To guarantee correction of up to t errors in all cases, the minimum Hamming distance in a block code must be dmin ::: 2t + 1.
  • In a linear block code, the exclusive OR (XOR) of any two valid codewords creates another valid codeword.
  • A simple parity-check code is a single-bit error-detecting code in which n ::: k + 1 with d
    min ::: 2. A simple parity-check code can detect an odd number of errors.
  • All Hamming codes discussed in this book have dmin ::: 3. The relationship between
    m and n in these codes is n::: 2m – 1.
  • Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword.
  • A category of cyclic codes called the cyclic redundancy check (CRC) is used in networks such as LANs and WANs.
  • A pattern of Os and Is can be represented as a polynomial with coefficients of 0 and 1.
  • Traditionally, the Internet has been using a I6-bit checksum, which uses one’s complement arithmetic. In this arithmetic, we can represent unsigned numbers between o and 2^n -1 using only n bits.


Try Now – Data Communication and Networking MCQs
Practice Now – Data Communication and Networking Online Tests
Practice Now – Fundamentals of Networking Online Test