Error Detection and Correction

Data Link Layer

• Receives services from physical layer and
provides services to network layer
 Data Link Layer
• Node-to-node delivery
• Local responsibility
• Ensures reliable delivery
• Defines frames
• Physical addressing
• Error control
• Flow control
• Medium access control
 Error Detection and Correction
• Errors are inevitable
– Interference
– Corruption as a result of transmission
• Reliable communication is dependent on
being able to detect and correct errors
• How will we know an error occurred?
• Do we retransmit or correct?
 Types of Errors
• Single-bit error
• Burst error
 Single-bit Errors
• Only one bit is changed: 0 changed to 1, or a 1
to a 0
• Least likely type of error since noise usually lasts
longer than the time to send one bit
• More likely in parallel transmission
 Burst Errors
• Two or more bits in data unit are in error, not
necessarily consecutive in order
• Most likely in serial transmission
• Number of bits affected depend on data rate and
noise duration
 Detection
• Need to detect before message is
processed
• Redundancy may be used to add
additional bits to a message for error
control
• Process must be handled by destination
Redundancy
 Detection Methods
• Parity Check
• Cyclical Redundancy Check (CRC)
• Checksum

• Parity and CRC are performed by data link

layer; checksum performed by higher-layer
protocols
 Parity Check
• Most common and least expensive
• In even-parity, a redundant bit (parity bit)
is appended to every data unit so total
number of 1 bits is even; odd-parity – total
should be odd
Even-parity Check
Example 1
Suppose the sender wants to send the word world. In
ASCII the five characters are coded as
1110111 1101111 1110010 1101100 1100100
The following shows the actual bits sent
11101110 11011110 11100100 11011000 11001001
Example 2
Now suppose the word world in Example 1 is received by
the receiver without being corrupted in transmission.
11101110 11011110 11100100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even numbers (6, 6, 4, 4, 4). The data are accepted.
Example 3
Now suppose the word world in Example 1 is corrupted
during transmission.
11111110 11011110 11101100 11011000 11001001
The receiver counts the 1s in each character and comes up
with even and odd numbers (7, 6, 5, 4, 4). The receiver
knows that the data are corrupted, discards them, and asks
for retransmission.
 Simple Parity Performance
• Can detect all single-bit errors
• May detect all burst errors as long as total
number of bits changed is odd
• Cannot detect errors when total number of
bits changed is even since parity check
will pass even though errors had occurred
Two-Dimensional Parity Check
• Data unit is divided into rows and
columns; parity checks are performed
on corresponding bits of each column
Two-Dimensional Parity
 Two-Dimensional Parity
Performance
• Increases likelihood of detecting burst
errors
• LRC of n bits can easily detect a burst
error of n bits
• May also detect many burst errors of more
than in n bits
• Cannot detect errors when two bits in one
data unit are damaged and two bits in
exactly the same positions in another data
unit are damaged
 Cyclic Redundancy Check
(CRC)
• Parity checks based on addition; CRC
based on binary division
• A sequence of redundant bits (a CRC or
CRC remainder) is appended to the end of
the data unit
• These bits are later used in calculations to
detect whether or not an error had
occurred
 CRC Steps
• On sender’s end, data unit is divided by a
predetermined divisor; remainder is the
CRC
• When appended to the data unit, it should
be exactly divisible by a second
predetermined binary number
• At receiver’s end, data stream is divided
by same number
• If no remainder, data unit is assumed to be
error-free
 Deriving the CRC
• A string of 0s is appended to the data unit;
n is one less than number of bits in
predetermined divisor
• New data unit is divided by the divisor
using binary division; remainder is CRC
• CRC of n bits replaces appended 0s at
end of data unit
CRC Generator and Checker
 CRC Generator
• Uses modulo-2
division
• Resulting remainder
is the CRC
 CRC Checker
• Performed by receiver
• Data is appended
with CRC
• Same modulo-2
division
• If remainder is 0, data
are accepted
• Otherwise, an error
has occurred
 Polynomials
• Used to represent CRC generator
• Cost effective method for performing
calculations quickly
 Standard Polynomials

Name Polynomial Application

CRC-8 x8 + x2 + x + 1 ATM header

CRC-10 x10 + x9 + x5 + x4 + x 2 + 1 ATM AAL

ITU-16 x16 + x12 + x5 + 1 HDLC

x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 +

ITU-32 LANs
x7 + x5 + x4 + x2 + x + 1
 CRC Performance
• Can detect all burst errors affecting an odd
number of bits
• Can detect all burst errors of length less
than or equal to degree of polynomial
• Can detect with high probability burst
errors of length greater than degree of the
polynomial
 Checksum
• Performed by higher-layer protocols
• Also based on concept of redundancy
 Checksum Generator
• At sender, checksum generator subdivides
data unit into k equal segments of n bits
• Segments are added together using one’s
complement arithmetic to get the sum
• Sum is complemented and becomes the
checksum, appended to the end of the
data
Checksum
 Checksum Checker
• Receiver subdivides data unit in k sections
of n bits
• Sections are added together using one’s
complement to get the sum
• Sum is complemented
• If result is zero, data are accepted;
otherwise, rejected
 Performance
• Detects all errors involving odd number of
bits, most errors involving even number of
bits
• Since checksum retains all carries, errors
affecting an even number of bits would still
change the value of the next higher
column and the error would be detected
• If a bit inversion is balanced by an
opposite bit inversion, the error is invisible
 Error Correction
• Requires more redundancy bits; must
know not only that an error had occurred,
but where the error occurred in order to
correct it
• Correction simply involves flipping the bit
• Hamming code may be applied to identify
location where error occurred by
strategically placed redundancy bits
Redundancy Bits
 Example Hamming Code
• For a seven-bit data sequence

r1: bits 1, 3, 5, 7, 9, 11
r2: bits 2, 3, 6, 7, 10, 11
r3: bits 4, 5, 6, 7
r4: bits 8, 9, 10, 11
Example Hamming Code
Error Detection using Hamming
Code
 Burst Error Correction
• By rearranging the order of bit
transmission of the data units, the
Hamming code can correct burst errors
• Organize N units in a column and send
first bit of each, followed by second bit of
each, and so on
• Hamming scheme then allows us to
correct corrupted bit in each unit
Burst Error Correction Example