1
CS 656
1
Data Link Layer, Part 2
Error Detection and Correction
These slides are created by Dr. Yih Huang of George
Mason University. Students registered in Dr.
Huang's courses at GMU can make a single
machine-readable copy and print a single copy of
each slide for their own reference, so long as each
slide contains the copyright statement, and GMU
facilities are not used to produce paper copies.
Permission for any other use, either in machine-
readable or printed form, must be obtained from
the author in writing.
CS 656
2
Transmission Errors
Causes: noises, attenuation, distortion,
crosstalk, losing synchronization
Error detection
– Parity checks, cyclic redundancy codes, …
Error correction
– send redundant information with data
– when receiving data incorrectly, the
receiver makes “educated guess” about the
original data
– Ex. Hamming code
2
CS 656
3
Parity Checks
Add an extra bit to a string of bits in order to make
the total number of 1’s even (even parity) or odd
(odd parity)
Example (even parity): 0 1 1 0 1 1 0 1 1
Advantages
– detects any single bit error
– in fact, detects any error involving odd number
of bits
Disadvantages
– only 50% chance of detecting burst errors
– an n-bit burst error is a string of bits inverted
during transmission
CS 656
4
Cyclic Redundancy Codes (CRC)
Basic idea: treat string of bits as coefficients of a
polynomial that uses modulo 2 arithmetic
– Ex. 1 0 1 0 0 1 represents x5 + x3 + 1.
Additions and subtractions are equivalent to
Exclusive-OR:
1 0 0 1 1 0 1 1 1 1 1 1 0 0 0 0
+ 1 1 0 0 1 0 1 0 - 1 0 1 0 0 1 1 0
3
CS 656
5
Method
Sender:
– divide string (frame) by a generator
polynomial G(x)
– tag the remainder (called a checksum)
onto the frame when it is transmitted
Receiver:
– divide the entire frame by G(x)
– a non-zero remainder indicates errors
Example:
– data: 1010001101, G(x): 110101
CS 656
6
1 0 1 0 0 0 1 1 0 1 0 0 0 0 0
1 1 0 1 0 1
1 1 1 0 1 1
1 1 0 1 0 1
1 1 1 0 1 0
1 1 0 1 0 1
1 1 1 1 1 0
1 1 0 1 0 1
1 0 1 1 0 0
1 1 0