Reliability

• What can introduce bit errors in physical links?

  Noise and interference
• What does the bit error rate (BER) measure?

  Frequency of bit errors over time
• What does a bit error rate of $10^{-3}$ indicate?


  1 error in every 1,000 bits
• How common are bit errors on wired links?

  Rare, around $10^{-12}$ for optical transmission
• How do bit errors in wireless links compare to wired links?

  More common, around $10^{-2}$ in 3G/4G
• What are parity bits used for?

  • Detecting errors in data transmission
  • Sent with each fixed amount of data
  • Calculated by counting the number of 1 bits
• What is even parity?

  Parity bit produces an even number of 1 bits
• What is odd parity?

  Parity bit produces an odd number of 1 bits
• What limitation do parity bits have?

  Cannot detect even number of bit errors
• What does the Internet checksum algorithm do?

  Sums together the data being sent
• What is a limitation of the Internet checksum?

  Poor at detecting multiple errors
• What are the strengths of Cyclic Redundancy Check (CRC)?

  • Detects single-bit errors
  • Detects double-bit errors
  • Detects bursts of errors
• How can binary data be represented in CRC?

  As a polynomial with binary coefficients
• What is the degree of a polynomial representing a bitstring?

  One less than the number of bits
• How is a bitstring represented as a polynomial?

  Using each bit as a coefficient
• What is the purpose of a generator polynomial in CRC?

  To ensure error detection capabilities
• What happens if the transmitted polynomial is not divisible by the generator polynomial?

  A bit error has occurred
• What is the significance of the remainder in CRC?

  Indicates if bit errors occurred
• What is the condition for polynomial division in CRC?

  Dividend must have a higher degree than divisor
• How is the remainder calculated in polynomial division?

  Using exclusive OR (XOR) on coefficients
• What are the steps to produce a CRC check sequence?

  1. Pad the original message with zeros
  2. Divide by the generator polynomial
  3. Subtract the remainder from the padded message
• What is the generator polynomial used in the example?

  CRC-4, which is $x^4 +$$x +$$1$
• What does a remainder of 0 indicate at the receiver?

  No bit errors have occurred
• What is the goal when selecting a generator polynomial?

  To minimize undetected errors
• How can single bit errors be detected?

  By selecting a generator polynomial with non-zero ends
• How can odd number of bit errors be detected?

  By using a generator polynomial with an even number of terms
• What are some common CRCs and their properties?

  • CRC-16: Detects all 1 and 2 bit errors
  • CRC-4: Used for smaller data frames
• What is a common error in data transmission?

  Single bit error
• How is a single bit error represented mathematically?

  As 𝐸(��) = 𝑥ⁱ
• What condition must the generator polynomial 𝐺(𝑥) meet to detect single bit errors?

  First and last terms must be non-zero
• What does it mean if 𝐸(𝑥) does not divide exactly into 𝐺(𝑥)?

  Single bit errors can always be detected
• How can we ensure that 𝐸(𝑥) does not divide equally into 𝐺(𝑥) for odd bit errors?

  𝐺(𝑥) must have an even number of terms
• What factor guarantees that 𝐺(𝑥) has an even number of terms?

  (1 + ��)
• What types of errors does CRC-16 detect?

  • All 1 and 2 bit errors
  • All error bursts up to 16 bits
  • All bursts affecting an odd number of bits
  • 99.997% of 17 bit error bursts
  • 99.998% of error bursts longer than 17 bits
• What is the polynomial for CRC-32?

  • ��³² + 𝑥²⁶ + 𝑥²³ + 𝑥²² + 𝑥¹⁶ + ��¹² + 𝑥¹¹ + ��¹⁰ + 𝑥⁸ + 𝑥⁷ + 𝑥⁴ + 𝑥² + 𝑥 + 1
• In which applications is CRC-32 used?

  Ethernet, SATA, PNG, gzip
• What is Forward Error Correction (FEC)?

  Original transmission includes redundant information
• What does Automatic Repeat Request (ARQ) do?

  Resends the frame after an error indication
• How does the Hamming code work for error correction?

  • Positions that are powers of 2 are parity bits
  • Each parity bit covers specific bit positions
  • Receiver checks parity bits to locate errors
• How many parity bits cover each data bit in Hamming code?

  Two or more parity bits