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

1. Internet checksum of the words 0x0001 and 0xFFFE?
   Stuck? Peek at 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.

   Read lesson 2.2.3

2. d_min needed to correct 2 errors?
   Stuck? Peek at 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.

   Read lesson 2.2.2

3. Remainder length when dividing by a 5-bit divisor (modulo 2)?
   Stuck? Peek at 0.2.3 XOR, 1's complement addition and modulo-2 division

   • AND (mask), OR, NOT (flip), XOR (1 where bits differ).
   • a ⊕ a = 0, a ⊕ 0 = a, (a ⊕ k) ⊕ k = a.
   • 1's complement = flip all bits; 1's-complement addition wraps the end carry back in.
   • Modulo-2: + = − = XOR, no carries; bits ↔ polynomial.
   • Mod-2 division: leading 1 → XOR divisor; leading 0 → XOR zeros; remainder = (divisor length − 1) bits.

   Read lesson 0.2.3

Every frame your laptop sends on a cable or over Wi-Fi ends with a short check value made by long division — not ordinary division, but the carry-free modulo-2 division you practised in Lesson 0.2.3. It is called the CRC (cyclic redundancy check), and it catches every burst of errors shorter than the check value. That is why the link layer uses it rather than parity or a checksum.

The sender appends r bits so that the whole frame divides exactly (modulo 2) by an agreed (r + 1)-bit generator. The receiver divides again. What remainder should it get if nothing was damaged?

Zero. The appended bits are exactly the remainder that makes the whole string a multiple of the generator. Any nonzero remainder means some bits changed.

Generator polynomial

Sender: append zeros, divide, attach remainder

1. Append r zeros to the data (r = degree of G).
2. Divide by G using modulo-2 division.
3. Replace the r zeros with the r-bit remainder. Transmit data + remainder.

          111101   ← quotient
1101 ) 100100000
       1101   ← leading 1: XOR with divisor
       ----
        1000
        1101   ← leading 1: XOR with divisor
        ----
         1010
         1101   ← leading 1: XOR with divisor
         ----
          1110
          1101   ← leading 1: XOR with divisor
          ----
           0110
           0000   ← leading 0: XOR with zeros
           ----
            1100
            1101   ← leading 1: XOR with divisor
            ----
             001   ← remainder (3 bits)

Receiver check

Divide the whole received string by G. Remainder 0 → accept; otherwise → error detected. Mathematically, if the transmitted codeword is T and the error pattern is E (1s where bits flipped), the receiver sees T ⊕ E; since T divides exactly, the remainder is that of E alone. An error goes undetected exactly when E is a multiple of G.

What CRC catches

• All single-bit errors if G has at least two terms.
• All odd numbers of errors if G has (x + 1) as a factor.
• All bursts of length ≤ r (G of degree r with a constant term 1).
• Bursts of length r + 1 are missed with probability 2⁻⁽ʳ⁻¹⁾; longer bursts with probability 2⁻ʳ.
• All double-bit errors as long as G does not divide xᵏ + 1 for any k up to the frame length.

Putting it together

• CRC appends the r-bit remainder of (data · xʳ) ÷ G.
• The receiver accepts only a zero remainder.
• CRC catches all single-bit errors and all bursts up to r bits; it misses only multiples of G.

• Append r zeros, where r is the degree (generator length − 1), not the generator length.
• The transmitted frame is data followed by the remainder — not the quotient.
• Keep leading zeros in the remainder: 0010 has 4 bits.
• "Detects all bursts ≤ r" — a burst of exactly r + 1 is not guaranteed.

"Pad with r zeros, divide, keep the remainder — the receiver wants zero."

Chapter 2.2 is complete: parity, Hamming distance, checksum and CRC. Our frames now arrive checked. Next (Ch 2.3): on a shared link, many nodes want to send — if two send at once, both frames are destroyed. Who should speak, and when?

1. MCQ

   Data 1010001101, G = 110101. The CRC is:

   1. 01110
   2. 1110
   3. 00111
   4. 10111
2. NAT

   G(x) = x⁸ + x² + x + 1. How many CRC bits are appended?

   Write your answer before opening the key.

3. MSQ

   For a generator of degree r with constant term 1, which are always detected?

   1. All single-bit errors
   2. All bursts of length ≤ r
   3. All bursts of length r + 1
   4. Error patterns equal to G
4. MCQ

   Received 100100001 with G = 1101. The receiver:

   1. accepts (remainder 0)
   2. rejects (remainder ≠ 0)
   3. needs the quotient
   4. cannot check without the data length
5. NAT

   With G = 1101 and data 101110, how many bits are transmitted in total?

   Write your answer before opening the key.

• 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⁻ʳ.

• CRC (cyclic redundancy check), FCS
• generator polynomial, degree r
• append r zeros
• receiver remainder test
• error pattern E; undetected iff G divides E
• burst detection guarantees

1. How many zeros to append for CRC?
   Reveal answer

   r = degree of the generator.
2. When is an error missed by CRC?
   Reveal answer

   When the error pattern is a multiple of G.
3. Bursts always detected?
   Reveal answer

   Length ≤ r.
4. G = 10011: CRC bits?
   Reveal answer

   4.

• CRC length = degree of G = (number of generator bits) − 1; append that many zeros. — always.
• Undetected ⇔ E is a multiple of G; bursts ≤ r are always caught. — G has a nonzero constant term (ends in 1).