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

1. Size of a MAC address?
   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

2. T_t of a 1500-byte frame at 100 Mbps?
   Stuck? Peek at 1.3.1 Bandwidth, data rate, throughput and transmission delay

   • Bandwidth / data rate B = link capacity in bps (decimal prefixes).
   • T_t = L / B (L in bits) — independent of distance.
   • Throughput = bits delivered / time ≤ min link rate on the path (bottleneck).

   Read lesson 1.3.1

3. a ⊕ a = ?
   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

When you read back a phone number, you might add "and the digits add up to 32" so the listener can catch a mistake. Networks do the same: the sender adds a few extra check bits computed from the data; the receiver recomputes them. If they disagree, something was damaged. The cheapest check is a single bit.

The sender adds one bit so that every frame contains an even number of 1s. Two bits flip on the way. Will the receiver notice?

No. Two flips keep the count of 1s even, so the check still passes. A single parity bit detects every odd number of flipped bits and misses every even number.

Kinds of errors

• Single-bit error: exactly one bit flipped.
• Burst error: several bits damaged in a row. The burst length is counted from the first damaged bit to the last damaged bit, inclusive — the bits in between may or may not be flipped.

On fast links, noise lasts longer than one bit time, so bursts are the common case.

Redundancy: dataword and codeword

1-D (simple) parity

Detects all errors that flip an odd number of bits; misses all even-numbered flips. Cost: 1 bit per dataword.

2-D parity

Arrange the data in rows; add a parity bit to every row and every column (plus one corner bit). A single flipped bit breaks exactly one row check and one column check, so the receiver can locate and correct it.

• Detects all 1-, 2- and 3-bit errors.
• Corrects any single-bit error.
• Misses some 4-bit errors: four flips on the corners of a rectangle leave every row and column even.

Putting it together

• Errors are single bits or bursts; detection needs redundant bits.
• One parity bit catches odd numbers of flips only.
• 2-D parity catches up to 3 flips and corrects 1.

• Burst length counts from the first to the last damaged bit, including undamaged bits in between.
• Simple parity misses every even number of flips, including 2.
• 2-D parity can correct only a single-bit error; it can detect but not locate two errors.

"Parity counts heads: an odd number of coin flips always shows; an even number hides."

Parity uses very few check bits, but its power is limited. Next (2.2.2): how do we measure how many errors any code can detect or correct? By counting how far apart its codewords are.

1. MCQ

   Even parity bit for 1101011?

   1. 1
   2. 0
   3. cannot be determined
   4. 2
2. MSQ

   A single even-parity bit detects which of these?

   1. 1 flipped bit
   2. 2 flipped bits
   3. 3 flipped bits
   4. 4 flipped bits
3. NAT

   Bits 2 and 9 of a frame are flipped (and nothing else). Burst length?

   Write your answer before opening the key.

4. NAT

   Check bits added by 2-D parity on a 6 × 8 block?

   Write your answer before opening the key.

5. MCQ

   Which error pattern can 2-D parity fail to detect?

   1. One flipped bit
   2. Two flipped bits in the same row
   3. Three flipped bits
   4. Four flipped bits at the corners of a rectangle

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

• single-bit error
• burst error, burst length
• redundancy, dataword, codeword
• even / odd parity
• 1-D parity
• 2-D parity

1. What does 1-D parity detect?
   Reveal answer

   Any odd number of flipped bits.
2. 2-D parity check bits for R × C?
   Reveal answer

   R + C + 1.
3. Burst length definition?
   Reveal answer

   From the first damaged bit to the last damaged bit, inclusive.

• 1-D parity detects error ⇔ the number of flipped bits is odd. — one parity bit over the whole dataword, even or odd convention.
• 2-D parity check bits for an R × C block = R + C + 1. — one parity bit per row and per column plus the corner bit.