Data Communication and
Computer Networks
Data Link Layer, Error Detection
Dr. Ehsan Munir
Department of Computer Science
COMSATS University Islamabad, Wah Campus
ehsanmunnir@gmail.com
The slides are adapted from the publisher’s material
Data Communications and Networking by Behrouz A. Forouzan, 5 th edition
Data and Computer Communications by William Stallings, 8 th Edition
Computer Networking: A Top-Down Approach by J F Kurose, K W Ross, 6 th Edition
Computer Networks, by L. Peterson, and B. Davie, 5 th edition
Outline
Why error detection and correction
Types of errors (Single or Burst)
Detection Vs Correction
What do we mean by redundancy and Coding
Hamming Distance
Error detection techniques
Simple Parity check
Two-dimensional Parity check
What Goes Wrong in the Network?
Reliability
Most important function that network
provide
How networks can fail?
Bit-level Vs Burst errors (electrical
interference)
Packet-level errors (congestion)
distinction between lost and late packet
Link and node failures
distinction between broken and flaky link
Why error detection and
correction
During data transmission bits are subject to
unpredictable changes because of interference
Attenuation, distortion and noise are the main
cause of random bit errors because it can
change the shape of a signal
This clearly emphasizes the need for error
detection and correction, and is one of the
service provided by data link layer
Single Bit Error
In a single-bit error, only 1 bit in the data
unit has changed.
Burst Error of Length 8
A burst error mean that 2 or more bits in
the data unit have changed.
If the bandwidth of a channel is 1Gbps then for how much duration the error should last?
Redundancy
To detect or correct errors, we need to send extra
(redundant) bits with data.
Detection versus Correction
In error detection, looking only to see if any error has
occurred. Simple yes or no answer.
In error correction, need to know the exact number of
bits that are corrupted and more importantly their
location in the message
Coding (block/convolution)
Redundancy is achieved through various coding
schemes. The sender adds redundant bits through a
process that receiver checks the relationships between
the two sets of bits to detect errors.
BLOCK CODING
In block coding, we divide our message into blocks,
each of k bits, called datawords. We add r redundant
bits to each block to make the length n = k + r. The
resulting n-bit blocks are called codewords.
Process of error detection in block coding
A code for error detection
Assume k=2, n=3
Assume the sender encodes
the dataword 01 as 011 and
sends it to the receiver.
Consider the following
cases:
1. The receiver receives 011. It is a valid codeword. The receiver
extracts the dataword 01 from it.
2. The codeword is corrupted during transmission, and 111 is
received. This is not a valid codeword and is discarded.
3. The codeword is corrupted during transmission, and 000 is
received. This is a valid codeword. The receiver incorrectly
extracts the dataword 00.
4. Two corrupted bits have made the error undetectable.
An error-detecting code can detect
only the types of errors for which it is
designed; other types of errors may
remain undetected.
A code for error correction
Assume k=2, n=5
The sender creates the
codeword 01011. The
codeword is corrupted
during transmission, and
01001 is received.
1. Comparing the received codeword with the first codeword in the table
(01001 versus 00000), the receiver decides that the first codeword is not the
one that was sent because there are two different bits.
2. By the same reasoning, the original codeword cannot be the third or fourth
one in the table.
3. The original codeword must be the second one in the table because this is
the only one that differs from the received codeword by 1 bit. The receiver
replaces 01001 with 01011 and consults the table to find the dataword 01.
Figure XORing of two single bits or two words
Hamming Distance
The Hamming distance between two words
(of the same size) is the number of
differences between the corresponding bits.
Represented as d (x, y) for two words x and y
Found by applying XOR operation on the two
words and counting number of 1s in the
result
Example
Let us find the Hamming distance between two pairs of
words.
1. The Hamming distance d(000, 011) is 2 because
2. The Hamming distance d(10101, 11110) is 3 because
The minimum Hamming distance is the
smallest Hamming distance between
all possible pairs in a set of words.
Example
Find the minimum Hamming distance of the coding
scheme for error detection.
Solution
We first find all Hamming distances.
The dmin in this case is 2.
Example
Find the minimum Hamming distance of the coding
scheme for error correction.
Solution
We first find all the Hamming distances.
The dmin in this case is 3.
Error detection techniques
Popular techniques
Simple Parity check
Two-dimensional Parity check
Checksum
Cyclic redundancy check
Simple Parity-Checking
Simple Parity Checking or One-dimension
Parity Check
The common, simple and least expensive
mechanism
In this technique, a redundant bit called
parity bit, is appended to every data unit so
that the number of 1s in the unit (including
the parity becomes even)
Even parity checking scheme
Possible 4-bit data words and corresponding code words
Decimal Value Data Block Parity bit Code word
0 0000 0 00000
1 0001 1 00011
2 0010
3 0011
4 0100
5 0101
6 0110
7 0111
8 1000
9 1001
10 1010
11 1011
12 1100
13 1101
14 1110
15 1111
performance
Can detect all single bit errors
Can detect burst errors if the number of bits
in error is odd
Cannot detect if even number of bits are
corrupted
Two-dimensional Parity check
Performance can be improved by using two-
dimensional parity check, which organizes the
block of bits in the form of a table
Parity check bits are calculated for each row,
which is equivalent to a simple parity check
bit
Parity check bits are also calculated for all
columns then both are sent along with the
data
At the receiving end these are compared
with the parity bits calculated on the received
data
Figure Two-dimensional parity-check code
Figure Two-dimensional parity-check code
performance
Extra overhead is traded for better error
detection capability
It can detect many burst errors but not all
