Fundamentals of Computer Networks
ECE 578
Module 2.3: Error Detection & Correction
Prepared by: Loukas Lazos
Module Overview
Error occurrence in physical media
Error detection
Error correction
2
Bit Errors in a Link
Types of errors
Isolated errors: Bit errors occurring independently
Burst errors: A cluster of bits in error
1011001010101010101010101000100010111001010010
Isolated Burst
Burst errors increase with data rate
Assume 1μs of impulse noise and 1 symbol = 1 bit
Worst-case # of bits affected at 1Mbps?
Worst-case number of bits affected at 100Mbps?
3
How Often do Errors Occur?
BER = 10-7 (i.e., 1 bit every 10,000,000 bits)
Assume a file of 100Mbits (used bits for ease of calculation)
Let X be an RV denoting the number of bits in error – independent
errors
Average number of bits in error?
Probability of exactly two errors?
4
Dealing with Errors
Receiver must be aware that an error occurred in a frame
Need to have an error detection mechanism
Receiver must receive the correct frame
Two possible strategies
Add information redundancy to correct errors (error correcting codes)
Ask sender to re-send frame (retransmission strategies)
In practice both are employed
5
Error Detection
Single parity checks
Append a single parity bit at the end of a frame. 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
Not useful for burst errors
6
Two-dimensional Parity
Arrange bits of a frame into a two dimensional array
1 0 0 1 0 1 0 1
0 1 1 1 0 1 0 0
1 1 1 0 0 0 1 0
1 0 0 0 1 1 1 0
0 0 1 1 0 0 1 1
1 0 1 1 1 1 1 0
Can it detect single errors?
Can it detect double and triple errors?
What about 4-bit errors?
How many errors can be corrected?
7
(IP) Checksum
Treat data as 16-bit words
Add 16-bit words two at a time
Add carry to LSB
Once done, compute one’s complement (i.e., invert result)
E.g. Assume the following header
1000 0110 0101 1110
1010 1100 0110 0000
0111 0001 0010 1010
1000 0001 1011 0101
What type of errors can remain undetected?
8
Cyclic Redundancy Check (CRC)
Add k redundant bits on a n-bit message
Design goal k<<n so that overhead is low
Example: 32-bit CRC adequate for 12,000 bits (1,500) bytes
Represent (n+1)-bit messages as n -egree polynomials
Example: 10011010 maps to x7 + x4 + x3 + x1
The bits of the message to be transmitted become the
coefficients of the polynomial
9
Polynomial Arithmetic
Any polynomial B(x) is divisible by a polynomial C(x) if deg(B) ≥ deg(C)
C(x) is called the divisor
If C(x) and B(x) are of the same degree, the remainder is obtained by
subtracting C(x) from B(x)
Modulo 2 arithmetic, subtraction is an XOR operation between
coefficients
Example B(x) = x3 + 1, C(x) = x3 + x2 + 1
Remainder: R(x) = x2
B(x) = 1001, C(x) =1101, R(x) = 0100 (XOR of B(x), C(x))
10
CRC Calculation
Goal: For message M(x), and divisor C(x), construct polynomial P(x) that
is divisible by C(x)
C(x) known to both sender and receiver
Process:
Step 1: multiply M(x) by xk (add k zeros at the end of message) and obtain T(x) . k is
the degree of C(x).
Step 2: Divide T(x) by C(x)
Step 3: Subtract the remainder R(x) from T(x)
Step 4: Obtain P(x) = M(x)|R(x) divisible by C(x)
11
Example: CRC Calculation
M = 10011010,
C(x) = x3 + x2 +1
T(x) = ?
R(x) = ?
P(x) = ?
12
Example: CRC Calculation
M = 10011010, C(x) = x3 + x2 +1
T(x) = 10011010 | 000
R(x) = 101
P(x) = 10011010 | 101
13
Selection of C(x)
Bit errors can be seen as a polynomial E(x) added to P(x)
Error remains undetected if E(x) is divisible by C(x)
Single-bit errors: E(x) = xi, xk, x0 coefficients are nonzero, all single-bit
errors detected
Double-bit errors: C(x) has a factor with at least 3 terms
Odd number errors: C(x) contains the factor (x+1)
Any burst error of less than k bits and most burst errors of larger than k
bits
14
Commonly Used CRCs
CRC C(x)
CRC-8 x8 + x2 + x + 1
CRC-10 x10 + x9 + x5 + x4 + x + 1
CRC-12 x12 + x11 + x3 + x2 + 1
CRC-16 x16 + x15 + x2 + 1
CRC-CCITT x16 + x12 + x5 + 1
CRC-32 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x +1
15
Basics of Channel Coding
Map an k-bit word to an n-bit word.
Notation: This code is usually referred to as (n,k)-code
1011001010101010101010101000100010111001010010
1011001 0010100 Code Rate: k/n
k k
n n
Weight of a word: The number of ones in the word.
Ex.: W(1011001)= 4
Hamming distance between x, y: d(x, y) = W(x y)
Ex. x = 1011001, y = 0010100, d = 4
Minimum distance: the minimum Hamming distance out of all distances
in a code
16
Detecting and Correcting Errors
An (n, k)-code can detect up to n-k-1 errors and correct up to n-k/2
errors
Example
Hamming (7,4)-code, can detect any single or two bit errors, and
correct any single bit error
Decoding Strategy
Maximum Likelihood Decoding – pick codeword with smallest
distance to the received word
17
Example – Repetition Code
Decode a (1,3) repetition code
Received word Decoded bit
000
001
010
011
100
101
110
111
What is the code rate?
18
Dealing with Burst Errors - Interleaving
Idea: spread burst errors in multiple codewords
1011001010101010101010101000100010111001010010
Organize data into an MxN matrix E.g. 9 x 7 matrix
read
1 8 15 22 …
2 9 16 23
3 10 17 24
write
4 11 18 25
5 12 19 26
6 13 20 27
7 14 21 28
19
