Error Detection and Correction

This Class

  • Calculation of BER and PER (FER)
  • Error detection and correction codes
  • Parity checks
  • CRC (code generation, error detection and correction capability)
  • Sources of bit errors: Interference, thermal noise, attenuation, fading, shadowing
  • Types of errors
    • Isolated errors: Bit errors that happen independently
    • Burst errors: A cluster of bits in which a number of errors occur
  • Burst errors increase with data rate
    • 1μs1\mu s of impulse noise or fading effect will affect
      • At most 2 bits when data rate is 1Mbps
      • At most 101 bits when data rate is 100Mbps

Bit Error and Packet Error

  • Bit corruption: one or multiple bits in a frame are corrupted (0 flipped to 1, or 1 flipped to 0) during transmission, results in packet corruption.
  • Bit error rate (BER) is the probability that a bit is corrupted during the transmission. It is very low on terrestrial links.
  • Derive relationship between BER and packet error rate PER (assuming a packet with n bits).
  • Packet error: loss of packet due to bit corruptions.
  • Probability that no bit in a frame is corrupted: (1−BER)N(1-BER)^N
  • Probability that a packet is not corrupted: 1−PER1-PER
  • Therefore: 1−PER=(1−BER)N1-PER = (1-BER)^N
  • PER=1−(1−BER)N≈N⋅BERPER = 1-(1-BER)^N \approx N \cdot BER if BER very small

How Often do Errors Occur?

  • Channel BER = 10−710^{-7}, and a packet is 10410^4 bit long, then the exact probability of a single error happens in the packet after its transmission is
    • (1041)(10−7)1(1−10−7)10000−1≈104×10−7=10−3{10^4 \choose 1} (10^{-7})^1 (1-10^{-7})^{10000-1} \approx 10^4 \times 10^{-7} = 10^{-3}
  • Probability of exactly two errors:
    • For two bits i, j the probability of error is: 10−7×10−7×(1−10−7)999810^{-7} \times 10^{-7} \times (1-10^{-7})^{9998}
    • Total # of 2-error patterns: (1042)=104×(104−1)2{10^4 \choose 2} = \frac{10^4 \times (10^4 - 1)}{2}
    • Probability of two errors: 5×107×10−14×(1−10−7)9998=5×10−75 \times 10^7 \times 10^{-14} \times (1-10^{-7})^{9998} = 5 \times 10^{-7}
  • Single-bit error happens with the highest probability (errors of more than one bit is sometimes ignorable)

Dealing with Errors

  • Receiver must be aware that an error occurred in a frame, needing an error detection mechanism.
  • Receiver must use the correct frame.
  • After error is detected, two possible strategies:
    • Correct errors (error correcting codes)
    • Ask sender to re-send frame (retransmission strategies)
  • In practice both are employed

Error Detection

  • Consider an alphabet of words {wi}\lbrace w_i \rbrace
  • Example of words: w0 = 000, w1 = 001, w2 = 010, w3 = 011, w4 = 100, w5 = 101, w6 = 110, w7 = 111
  • Illustrates that some corrupted words can result in other valid words.

Error Detection Code

  • Basic idea of Error Detection: To add redundant information to a frame that can be used to determine if errors have been introduced.
  • Extra bits (check bits) are redundant, adding no new information to the message itself.
  • Check bits are derived from the original message using some algorithm.
  • Both the sender and receiver know the algorithm.
  • Sender sends message m and redundant bits r.
  • Receiver computes r using m. If their correlation holds, no error.

Error Detection Code (General)

  • Consider an alphabet of words {wi}
  • Example of words: w0 = 000, w1 = 001, w2 = 010, w3 = 011, w4 = 100, w5 = 101, w6 = 110, w7 = 111
  • Example shows codeword with checkbits
  • Checkbits (c1=a2+a1 and c0=a1+a0)

Error Detection Schemes

  • Single parity checks: Append a single parity bit at end of frame so that the number of “1”’s is even.
  • Parity is 1 if # of ones is odd, and zero otherwise
  • Example: 0 1 1 0 1 0 1 0 1 1 0 0 ← parity
  • Single parity check can detect any odd # of errors
  • Cannot tell where the error took place or how many occurred
  • Mainly intended for independent errors

Two-dimensional Parity

  • Arrange bits of a frame into a two dimensional array
  • Can detect all 1-, 2-, and 3-bit errors, and most 4-bit errors but not all
  • Can also correct 1-bit errors, if it is known that a one-bit error occurred
  • Overhead is calculated as 13/35

Internet Checksum Algorithm

  • Add up all the words that are transmitted and then transmit the result of that sum
    • The result is called the checksum
  • The receiver performs the same calculation on the received data and compares the result with the received checksum
  • If any transmitted data, including the checksum itself, is corrupted, then the results will not match, so the receiver knows that an error occurred

Internet Checksum (2)

  • Sending:
    1. Arrange data in 16-bit words
    2. Put zero in checksum position, add
    3. Add any carryover back to get 16 bits
    4. Negate (complement) to get sum
  • Example demonstrates checksum calculation

Internet Checksum (3)

  • Sending (Continued):
    1. Arrange data in 16-bit words
    2. Put zero in checksum position, add
    3. Add any carryover back to get 16 bits
    4. Negate (complement) to get sum
  • Complement: invert each bit

Internet Checksum (4)

  • Receiving:
    1. Arrange data in 16-bit words
    2. Checksum will be non-zero, add
    3. Add any carryover back to get 16 bits
    4. Negate the result and check it is 0

Internet Checksum (5)

  • Receiving (Continued):
    1. Arrange data in 16-bit words
    2. Checksum will be non-zero, add
    3. Add any carryover back to get 16 bits
    4. Negate the result and check it is 0
  • Can detect 1 bit isolated error, and up to 16 bits burst errors

Error Detection Capacity

  • Consider an alphabet of words {wi}
  • Example of words: w0 = 000, w1 = 001, w2 = 010, w3 = 011, w4 = 100, w5 = 101, w6 = 110, w7 = 111
  • Example shows codeword with checkbits
  • Checkbits (c1=a2+a1 and c0=a1+a0)
  • Hamming Distance (wi,wj) is the the number of bits by which wi and wj differ.
  • Smallest Hamming distance for this encoding scheme is 2

Hamming Distance

  • Notation: (n, m)-code. n-bit code, among which m bits are information.
  • Weight of a word: The number of ones in the word. Ex.: W(100011101)= 5
  • Hamming distance between x, y: d(x,y)=W(x⊕y)d(x,y) = W(x \oplus y)
  • Ex. x = 10011101, y = 11100110, d = 6
  • Distance of codebook: the minimum Hamming distance out of all distances in a codebook

Error detection capacity explained:

  • If the minimum Hamming distance of a codebook is dmin then the coding scheme can detect up to dmin-1 bit errors.
  • Error Detection Capacity