Computer Networking Lecture Notes

2014 October 22 💡 Data Link Error Detection and Correction

---

Outline

• Data-link framing.
• Error detecting codes.
  • Parity, checksum, cyclic redundancy checks.
• Error correcting codes.

Channel Characteristics

• Physical-layer services can be noisy, which could induce errors.
  • Value in error detection and perhaps correction.
• Shared channels may need addressing.
• Abstract from the media access control sublayer.
• These issues can be dealt with by framing (encapsulation).

Framing

• Framing adds information to support data transmission.

• Packet: Network PDU, most likely.
• First question: how are frames framed?
  • What delimits a frame on the wire?

Byte Counts

• First try: the header is a byte count.

  

• Problems:

  

  • Hard to recover from errors.
  • No information to request retransmission.

Byte Flags

• Second try: explicitly mark frame ends.

  

• The mark is called the flag byte, a frame-unique value.
• Successive flag bytes mark the start of a frame.

  

Byte Stuffing

• A flag byte is just a byte value.
• What happens when the flag byte occurs in the payload?
  • Confusion may reign.
• Use an escape byte to neutralize payload flag-byte values.
  • An escape byte is an other frame-unique byte value.
• Preceding a payload flag-byte value with an escape byte escapes (neutralizes) the value.

Byte-Stuffing Example

• But isn’t the escape byte a byte value too?

  

Bit Stuffing

• Byte stuffing might double the frame size.
  • And what happens when the payload isn’t byte oriented?
• Bit stuffing is an alternative to byte stuffing.
• The frame flag is still a frame-unique byte value as a bit pattern.
  • High-Level Data Link Control (HDLC) uses 7E₁₆ = 01111110₂.

Stuffing Bits

• Using the HDLC flag every sequence of 5 1 bits is followed by (stuffed with) a 0 bit.

  

• Bit stuffing adds at most 20% to the frame length.
• Stuffing (bits or bytes) is invisible outside the data-link layer.

Errors

• An error occurs when a bit “spontaneously” changes value: 0 → 1 or 1 → 0.
• A bit string undergoes an error burst of length n at bit i when
  • bits i and i + n - 1 change value, and
  • bits i + j, 0 < j < n - 1, change value with probability p.
  • 010000 → 000101, i = 1, n = 5, p = 0.3.
• Frequently i is ignored and p = 0.5.

Error Detection

• Error detection is most useful when
  • Error rates are low (≥ 10⁹ bits/error).
  • Errors can be ignored.
  • Retransmission is cheap.

Parity

• Parity deals with even or odd 1-bit counts.
• A bit string has an even or odd 1-bit count.

  01000010		2 1-bits		even parity
  01011000		3 1-bits		odd parity

• A bit string’s parity bit is the value giving the bit string even parity.

  01000010		parity bit = 0
  01011000		parity bit = 1

Parity Error Detection

• Append a parity bit to a bit string; the result always has even parity.
  • A string + parity with odd parity indicates an error.
• Parity can detect single-bit errors.
  • Or an odd number of single-bit errors

  010000100 010100100 010000000 010000101

  010000100 000010000 100010010 101010011

More Parity

Parity doesn’t detect an even number of errors.

010000100 000000000 100000010 100100011

Add more structure by using smaller groups and more parity bits.

0100001011 0000000011 1010000011 1010100001

• Even numbers of errors in a group still go undetected.

Interleaving

Add even more structure by interleaving, not grouping, bits.

0000000011 1010000011 1010100001

• K-bit interleaved parity - k parity bits, one for each kth bit.
  • Any one of the parity bits is enough to signal an error.

Checksums

• Use arithmetic for even more structure.
  • Group the bit string into k-bit values.
  • Sum the values to get a k-bit checksum.
  • Append the checksum to the bit string.
• “Checksum” often refers to any error-detection value.
• Checksums differ in handling the carry-out bit.

Internet Checksums

• The Internet checksum (rfc 1071) is
  • the one’s-compliment of
  • the sum of 16-bit one’s compliment values.
• The checksum IP header field is part of the checksum.
  • The sender zeros it out.
  • The receiver includes it in the checksum.
• A successful checksum produces -0.

More Structure

• Moving from parity bits to arithmetic adds structure.
• Adding more arithmetic adds more structure.
• Alice and Bob what to communicate decimal numbers to each other.
  • 101, 31415, 20141022, and so on.
• They're worried about decimal digit errors.
  • Send 07742, receive 07840.
• What can they do?

Fun Division Facts

• Suppose a/b = q remainder r, 0 ≤ r < b.
  • Then a = q*b + r, and
  • (a - r)/b = q remainder 0.
• For example

  25/4 = 6 remainder 1
  25 = 4*6 + 1
  (25 - 1)/4 = 24/4 = 6

• Division represents a complicated interrelation among parts.

Division-Based Error Detection

• How can Alice and Bob use division for error detection?
• They agree on a divisor d.
• Alice divides message m by d to get r (and q, which is ignored).
• Bob knows only d, not m or r.
  • So what's the point?
• Don't forget our fun fact: (m - r)/d has remainder 0.

Zero-Remainder Messages

• Alice and Bob agree to send only messages divisible by d.
  • That is, m/d has remainder 0.
• Alice knows how to generate those messages.
  • Given m send m\('\) = m - rem(m/d).
• Bob knows how to divide by d and recognize 0.
  • Non-zero remainder means corrupted message.
• Wow! Problem solved?

The Problem

• Bob knows m\('\) isn't (or is) corrupted.
• But Bob doesn't know r, and so can't compute m\('\) - r = m.
• Oh no! Was this just a complete waste of time?
• When Alice computed m\('\) = m - rem(m/d), she destroyed m for Bob.
• Is there some way to preserve m yet still have zero-remainder error checking?

Scaled Messages

• Let s be the smallest power of 10 at least d.
  • If d = 19, then s = 100.
  • Alice and Bob know s.
• Given m, Alice uses the scaled message sm.
  • This shifts 0s into m from the right.
• Alice computes m\('\) = sm - rem(sm/d).
  • The subtraction disturbs the shifted 0s, not the message (mostly).

Example

• Alice and Bob agree on d = 19; s = 100.
• Alice wants to send m = 20141022:

  sm = 20141022·100 = 2014102200
  rem(sm/d) = rem(2014102200/19) = 18
  m\('\) = 2014102200 - 18 = 2014102182

• Bob receives 2014102182.

  rem(2014102182, 19) = 0
  m/s = 2014102182/100 = 20141021 + 1

• Bob receives 2014112182.

  rem(2014112182, 19) = 6
  

So What?

• An n-bit message can be represented as an n-1 degree binary coefficient polynomial.
  • Given M = b_n-1\(\cdots\)b₁b₀,
  • get M(x) = Σ_{0 ≤ i < n} b_ixⁱ.
• The sender and receiver exchange binary coefficient polynomials.
• The division fun facts apply to polynomials too.

Example

• Let M be 10011010,
• then

  M(x) =	b7x7 + b6x6 + b5x5 + b4x4 +
  	b3x3 + b2x2 + b1x1 + b0x0
  =	1x7 + 0x6 + 0x5 + 1x4 +
  	1x3 + 0x2 + 1x1 + 0x0
  =	x7 + x4 + x3 + x

Polynomial Error Detection

• Sender and receiver agree
  • on a check polynomial C(x) of degree k.
    • K is the number of error checking (redundant) bits.
  • to only send messages (polynomials) evenly divisible by C(x).
• If C(x) doesn't even divide the received message (polynomial), errors occurred during transmission.

Evenly Divisible Polynomials

• A message polynomial M(x) may not be evenly divisible by C(x).
• Not to worry:
  • Add k extra bits to M(x): M'(x) = M(x)x^k.
  • Subtract the remainder of M'(x)/C(x) from M'(x) to get M''(x).
    • C(x) evenly divides M''(x).
  • Send M''(x).

Cyclic Redundancy Check

• Polynomial-based error detection is known as cyclic redundancy checking (CRC).
• CRC is a powerful error detection technique.
  • Few check bits protects many message bits.
    • k = 32 and n = 12,000 (1,500 bytes).

Selecting C(x)

• Check polynomial properties determine CRC error-detection capabilities:
  • All single-bit errors when the x^k and x⁰ terms have coefficient 1.
  • All double-bit errors when C(x) contains a factor with at least three terms.
  • Any odd number of errors when C(x) contains the factor x + 1.
  • Any error burst of length less than k bits.

Error Correction

• If
  • error rates aren't low (≤ 10⁶ bits/error), or
  • errors can't be ignored, or
  • retransmission is expensive, then
• error detection doesn't do a good enough job.
• Or fix the errors when detected.
  • This is known as forward error detection.

Redundancy

• Undoing errors requires extra information, meaning extra bits.
• An m-bit message uses r bits of redundancy.
  • This is an (n, m) code, n = m + r.
• The n-bit result is a codeword.
• The code rate = m/n measures redundancy.
  • High error rates, code rate ∼ 0.5.
  • Low error rates, code rate ∼ 1.

Distance

Two codewords differ in some number of bits.

⊕ 01000010 01011010 00011000

• Count the 1 bits in the exclusive or of the codewords.
• The Hamming distance between two codewords is the number of different bits.
  • 01000010 and 01011010 have Hamming distance 2.

Errors and Distances

• Two codewords with Hamming distance d require d single-bit errors to change one into another.

  01000010 → 01010010 → 01011010 01000010 ← 01010010 ← 01011010

• A code's Hamming distance is the smallest Hamming distance between any two codewords in the code.

  for all i, j : min Hamming(c_i, c_j)

Sparseness

• An (n, m) code contains codewords in inverse proportion to its Hamming distance.
  • The larger the Hamming distance, the fewer the codewords.

  

Error Detection and Correction

• A code with Hamming distance d can
  • detect up to d - 1 errors in a codeword.
  • correct up to ⌊(d - 1)/2⌋ errors in a codeword.

  

Summary

• Errors in transit may be detected and possibly corrected.
  • Depending on costs (extra bits, missed errors) and benefits (faster cheaper recovery).
• Error detection and correction relies on redundancy and interrelatedness.

References

• Performance of Checksums and CRCs over Real Data by Jonathan Stone, Michael Greenwald, Craig Partridge, Jim Hughes in IEEE/ACM Transactions on Networking, October, 1998.
• Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks by P. Koopman and T. Charkravarty, International Conference on Dependable Systems and Networks, June 2004.

---

This page last modified on 2014 October 20.