English
Menu

Information Theory and Coding Basics

Which of the following correctly describes a CRC whose generator polynomial has degree r (r check bits) and a constant term of 1?

  1. AFor a 1-bit error, its main use is to identify which bit is wrong and correct it
  2. BIt detects every burst error (an error confined to a contiguous range) of length r bits or less
  3. CWith a well-chosen generator polynomial, it detects every possible error pattern
Show answer and explanation

Answer: B. It detects every burst error (an error confined to a contiguous range) of length r bits or less

Representing the error pattern as a polynomial E(x), a CRC fails to detect an error only when E(x) is divisible by the generator polynomial G(x). A burst error of length r or less can be written as x^i × B(x) (B(x) of degree r − 1 or less with a constant term of 1), which is not divisible by a degree-r G(x) with a constant term of 1, so it is always detected. On the other hand, patterns that are divisible, such as an error with the same form as G(x) itself, are not detected. CRCs are used mainly to detect errors, and when one is found the data are sent again.

  • A. A CRC is used mainly to detect errors, and when one is found the data are sent again. Correction uses error-correcting codes such as Hamming codes.
  • B. Correct. A burst error of length r or less is not divisible by the generator polynomial, so it is always detected.
  • C. If the error pattern is divisible by the generator polynomial, the remainder does not change, so the error is not detected. Every generator polynomial has such patterns.
Practice this topic Back to topic

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

More Information Theory and Coding Basics questions

  1. Which of the following is the Hamming distance between the two 7-bit codewords 1011010 and 0110011?
  2. The minimum Hamming distance of a code (the smallest Hamming distance between any two codewords) is 5. Consider using it only for error detection, or only for error correction. Which of the following correctly pairs the number of bit errors that can always be detected with the number that can always be corrected?
  3. Which of the following correctly pairs the minimum Hamming distance of the code consisting of the four codewords 00000, 01011, 10101 and 11110 with the number of bit errors it can always correct?
  4. Which of the following is closest to the code rate of the Hamming (7, 4) code, which adds 3 check bits to 4 bits of data to form a 7-bit codeword?
  5. In a Hamming (7, 4) code, the seven bits are numbered 1 to 7 from the left, and bits 1, 2 and 4 are check bits. They are set so that the number of 1s is even in bits 1, 3, 5 and 7 (check 1), in bits 2, 3, 6 and 7 (check 2) and in bits 4, 5, 6 and 7 (check 4). If the received word 0110001 has a single-bit error, which of the following is the wrong bit?