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

1. Which errors does a single parity bit detect?
   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

2. How many frames carry a packet over 3 links?
   Stuck? Peek at 2.1 Role of the data link layer: hop-to-hop delivery and MAC addresses

   • Data link layer = hop-to-hop delivery of frames to the next directly connected node.
   • Jobs: framing, link addressing, error detection, medium access (+ error/flow control).
   • MAC address: 48 bits, 6 bytes, 12 hex digits; 24-bit vendor prefix; flat.
   • A new frame (new MAC addresses) is built on every link; the packet inside is unchanged.
   • Foundation: bit stuffing inserts a 0 after five consecutive 1s.

   Read lesson 2.1

3. How do you count positions where two bit strings differ?
   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

Imagine valid words placed on a map so that any two are at least three steps apart. If one letter gets smudged, the damaged word is still closer to the original than to any other valid word, so you can even guess back the original. The distance between valid codewords is what decides how many errors a code can catch or fix.

A code has only two codewords: 000 and 111. How many flipped bits can it always detect? How many can it correct?

Distance 3. It detects up to 2 flips (no 1- or 2-flip pattern turns 000 into 111) and corrects 1 (one flip leaves the word closer to its original — majority vote).

Hamming distance

Detection and correction rules

• To detect up to s errors: d_min ≥ s + 1 → a code detects d_min − 1 errors.
• To correct up to t errors: d_min ≥ 2t + 1 → a code corrects ⌊(d_min − 1)/2⌋ errors.

Why: s flips must not reach another codeword; for correction, the spheres of radius t around codewords must not overlap.

Hamming code size (how many check bits)

A single-error-correcting Hamming code for m data bits needs the smallest r with 2ʳ ≥ m + r + 1: the r check bits must name every one of the m + r positions, plus "no error".

Putting it together

• Hamming distance counts differing bits; d_min is the code's weakest pair.
• Detect d − 1 errors, correct ⌊(d − 1)/2⌋.
• Hamming codes need r with 2ʳ ≥ m + r + 1.

• d_min is the minimum over all pairs, not the average or maximum.
• Correction count uses the floor: d = 4 corrects only 1.
• A code cannot simultaneously correct t and detect s unless d ≥ t + s + 1; questions usually ask one or the other.

"Detect = one less than the gap; correct = less than half the gap."

Distance tells us the strength of any code. Next (2.2.3): a very cheap detection code used inside headers on the Internet — adding the data in 1's complement (Lesson 0.2.3) and sending the complement of the sum.

1. NAT

   Hamming distance between 1100110 and 1010101?

   Write your answer before opening the key.

2. NAT

   A code has d_min = 6. How many errors can it correct?

   Write your answer before opening the key.

3. MCQ

   To detect up to 3 errors, the minimum distance must be at least:

   1. 3
   2. 4
   3. 6
   4. 7
4. NAT

   Check bits in a single-error-correcting Hamming code for 11 data bits?

   Write your answer before opening the key.

5. MSQ

   For the code {000000, 010111, 101011, 111100}:

   1. d_min = 4
   2. it detects 3 errors
   3. it corrects 2 errors
   4. it corrects 1 error

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

• Hamming distance
• minimum distance d_min
• detect d − 1, correct ⌊(d − 1)/2⌋
• Hamming code check bits 2ʳ ≥ m + r + 1

1. Errors detected with d_min?
   Reveal answer

   d_min − 1.
2. Errors corrected with d_min?
   Reveal answer

   ⌊(d_min − 1)/2⌋.
3. Hamming check bits for m data bits?
   Reveal answer

   Smallest r with 2ʳ ≥ m + r + 1.

• Detect s ⇔ d ≥ s + 1; correct t ⇔ d ≥ 2t + 1. — any block code; detect and correct counts are separate guarantees, not simultaneous.
• Hamming check bits: smallest r with 2ʳ ≥ m + r + 1. — single-error-correcting Hamming codes.