Gyanrush
Start freeOpen Gyanrush
Start freeOpen Gyanrush
  1. LPU MCA Semester 1
  2. CAP7001
  3. Unit 3

CAP7001 · Unit 3: Data link layer

Types of errors, error detection and correction

20 practice questions · in the MTE and ETE syllabus

Practise this topicPractise this topic

Key points

  • Even parity detects odd numbers of bit errors only
  • CRC: append n-1 zeros, modulo-2 divide, append remainder
  • Detect s errors: dmin = s + 1; correct t: dmin = 2t + 1
  • Hamming: 2^r >= m + r + 1

A single-bit error changes one bit; a burst error of length L spans from the first to the last corrupted bit (inner bits may be intact). Detection uses redundancy.

  • Parity (even): add a bit so the number of 1s is even; detects any odd number of flipped bits only.
  • Checksum: 1's complement sum of words, wrap the carry, then complement.
  • CRC: append n-1 zeros (n-bit generator), divide modulo-2, append the remainder.
  • Hamming distance d(x,y) = number of differing bits. Detect s errors needs dmin = s + 1; correct t errors needs dmin = 2t + 1.
  • Hamming code: smallest r with 2^r >= m + r + 1; parity bits sit at positions 1, 2, 4...

Worked example: data 100100, generator 1101: divide 100100000 by 1101, remainder 001, codeword 100100001. Checksum of 10110011 and 01011010: sum 269, wrap to 14, complement 11110001.

Exam pitfall: a CRC detects bursts up to the degree of the generator, but an error pattern that is itself a multiple of the generator (for example 0001011 with generator 1011) goes undetected.

Try two questions

Question 1 · Tier 3, Apply

To correct 2 errors, the minimum Hamming distance must be:

  1. 2
  2. 3
  3. 5
  4. 4
Show the answer

C. dmin = 2t + 1 = 5. Here t = 2, so dmin = 2(2) + 1 = 5; 4 would only correct 1 error.

Question 2 · Tier 3, Apply

Using even parity, the parity bit appended to 1011001 is:

  1. Not defined
  2. Either 0 or 1
  3. 0
  4. 1
Show the answer

C. 1011001 has four 1s (an even count), so the parity bit is 0.