Error detection

Parity: 1-D detects odd numbers of flips; 2-D (R + C + 1 bits) detects up to 3 and corrects 1. Hamming distance: detect d − 1, correct ⌊(d − 1)/2⌋; Hamming code r with 2ʳ ≥ m + r + 1. Internet checksum: 16-bit 1's-complement sum, send the complement; receiver total = 0xFFFF. CRC: append r zeros, divide by G (degree r), send the remainder; misses only multiples of G; catches bursts ≤ r.

From 2.2.1 Single-bit vs burst errors; redundancy; 1-D and 2-D parity

• Single-bit vs burst; burst length = first to last damaged bit inclusive.
• Codeword = dataword (k) + r check bits.
• 1-D parity: detects odd numbers of flips only.
• 2-D parity: R + C + 1 check bits; detects all 1–3-bit errors, corrects 1, misses some 4-bit rectangles.

From 2.2.2 Hamming distance: detect d − 1, correct ⌊(d − 1)/2⌋

• d(x, y) = number of 1s in x ⊕ y; d_min = smallest over codeword pairs.
• Detect d_min − 1; correct ⌊(d_min − 1)/2⌋.
• Detect s needs d ≥ s + 1; correct t needs d ≥ 2t + 1.
• Hamming code: smallest r with 2ʳ ≥ m + r + 1.

From 2.2.3 The Internet checksum: compute and verify

• 16-bit words; checksum field = 0 while summing.
• Sum with 1's-complement addition (wrap carries); checksum = complement of the sum.
• Receiver: sum of all words + checksum = 0xFFFF → accept.
• Misses word reordering and compensating errors.

From 2.2.4 CRC: generator polynomial, modulo-2 division, what CRC catches

• G of degree r (r + 1 bits); append r zeros, divide modulo 2, send data + r-bit remainder.
• Receiver divides the whole frame: remainder 0 → accept.
• Undetected ⇔ error pattern E is a multiple of G.
• Catches: all single-bit errors (≥ 2 terms), all odd counts (x + 1 | G), all bursts ≤ r; (r+1)-bursts missed w.p. 2⁻⁽ʳ⁻¹⁾, longer 2⁻ʳ.

1. MCQ · 2 marks

   CRC of data 11100110 with G = 1001?

   1. 001
   2. 110
   3. 011
   4. 100
2. NAT · 2 marks

   Internet checksum (decimal) of the 16-bit words 0x8000 and 0x8001?

   Write your answer before opening the key.

3. NAT · 1 mark

   d_min of {0000, 0111, 1011, 1101}?

   Write your answer before opening the key.

4. MSQ · 1 mark

   Which detect every single-bit error?

   1. Even parity
   2. Internet checksum
   3. CRC with G = 10011
   4. A code with d_min = 1
5. NAT · 1 mark

   Check bits of a single-error-correcting Hamming code for 26 data bits?

   Write your answer before opening the key.

6. MCQ · 1 mark

   A CRC with degree-16 generator is guaranteed to detect all bursts of length up to:

   1. 15
   2. 16
   3. 17
   4. 32
7. NAT · 1 mark

   Parity bits in 2-D parity over a 5 × 5 block?

   Write your answer before opening the key.

8. MCQ · 1 mark

   Which error is the Internet checksum unable to detect?

   1. One bit flipped
   2. Two 16-bit words interchanged
   3. Last bit flipped
   4. First bit flipped
9. MCQ · 1 mark

   A code must correct 3 errors. Minimum d_min?

   1. 4
   2. 6
   3. 7
   4. 3
10. MSQ · 2 marks

    With G = 1101, which received strings are accepted?

    1. 100100001
    2. 000000000
    3. 110100000
    4. 100100000