The Internet checksum: compute and verify

1. d_min = 5: errors detected? corrected?
   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

2. 2-D parity check bits for a 3 × 5 block?
   Stuck? Peek at 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.

   Read lesson 2.2.1

3. How does 1's-complement addition treat the final carry?
   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

A shopkeeper adds up a bill, writes the total on the slip, and the customer re-adds the items to compare. The Internet checksum works the same way, with one twist: the sender writes the complement of the total, so that the receiver's sum of everything (data + checksum) comes out as all 1s. It is cheap enough to compute in software for every unit, which is why it is used in network- and transport-layer headers you will meet in Phases 3 and 4.

A sender adds the data words, takes the 1's complement, and sends it along. The receiver adds the data words and the checksum. If nothing was damaged, what will the receiver's sum be?

All 1s (0xFFFF for 16-bit words). A number plus its 1's complement is all 1s. Complementing that gives 0, so the receiver accepts when its complemented sum is 0.

Sender algorithm

1. Split the data into 16-bit words (pad with a zero byte if the length is odd).
2. Add all words using 1's-complement addition (wrap every carry back in).
3. The checksum = 1's complement of that sum (flip every bit). Put it in the checksum field, which was set to 0 while summing.

Receiver check

The receiver adds every word including the checksum with 1's-complement addition. Result all 1s (complement 0) → accept; anything else → error detected, discard.

What it catches and misses

• Detects all single-bit errors and most bursts.
• Misses errors that leave the 1's-complement sum unchanged: for example, swapping two 16-bit words (addition is order-independent), or a +x in one word cancelled by −x in another.
• Weaker than the polynomial code of the next lesson, but very cheap in software.

Putting it together

• Sum the words with wrap-around, send the complement.
• The receiver's total including the checksum must be all 1s.
• Cheap and catches single-bit errors, but blind to reordering.

• Set the checksum field to 0 before the sender sums.
• Do not drop the carry — wrap it back in. Ordinary binary addition gives a different (wrong) checksum.
• The checksum is the complement of the sum, not the sum itself.

"Sum, wrap, flip — and the receiver must see all ones."

The checksum is cheap but blind to reordering. Next (2.2.4): the stronger link-layer check — treat the bits as a polynomial and send the remainder of a modulo-2 division (Lesson 0.2.3) — catches every burst up to a known length.

1. MCQ

   The 16-bit Internet checksum of the words 0x4500, 0x0073, 0x4000, 0x4011 is:

   1. 0x3A7B
   2. 0xC584
   3. 0x3A7A
   4. 0xC585
2. MCQ

   At the receiver, data words plus checksum add (1's complement) to 0xFFFF. The receiver:

   1. detects an error
   2. accepts the data
   3. requests the checksum again
   4. cannot decide
3. MSQ

   Which errors can the Internet checksum miss?

   1. Two 16-bit words swapped
   2. A single flipped bit
   3. One word +1 and another word −1
   4. A word 0x0000 changed into 0xFFFF
4. NAT

   16-bit 1's-complement sum of 0xFFF0 and 0x0020, in decimal?

   Write your answer before opening the key.

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

• Internet checksum
• 16-bit word sum with wrap-around
• checksum = complement of the sum
• receiver verification (all 1s)

1. Internet checksum steps?
   Reveal answer

   Sum 16-bit words in 1's complement (wrap carries), then flip all bits.
2. Receiver accepts when?
   Reveal answer

   Sum of all words including checksum = 0xFFFF.
3. One error the checksum cannot see?
   Reveal answer

   Two words swapped.

• Hex shortcut: add in hex; whenever the result exceeds 0xFFFF, drop the leading 1 and add 1; checksum = 0xFFFF − sum (each digit from F). — 16-bit words.
• Receiver test: sum(all words incl. checksum) = 0xFFFF ⇔ no error detected. — the same 1's-complement addition as the sender.