1
LECTURE 4:
DATA LINK LAYER
NET 221D : COMPUTER NETWORKS
FUNDAMENTALS
3. Error control
How to make sure all frames are eventually delivered to
the network layer at the destination and in the proper
order.
Assume for the moment that the receiver can tell whether a
frame that it receives contains correct or faulty
information (using error detection and correction
techniques).
The usual way to ensure reliable delivery is to provide the
sender with some feedback about what is happening at the
other end of the line.
2
Typically, the protocol calls for the receiver to send
back special control frames bearing positive or
negative acknowledgements about the incoming
frames.
If the sender receives a positive acknowledgement
about a frame, it knows the frame has arrived
safely.
On the other hand, a negative acknowledgement
means that something has gone wrong and the
frame must be retransmitted again.
3
Redundancy
The central concept in detecting or correcting errors is
redundancy. To be able to detect or correct errors, we
need to send some extra bits with our data. These
redundant bits are added by the sender and removed
by the receiver. Their presence allows the receiver to
detect or correct corrupted bits.
10.4
Error detection and correction
• The correction of errors is more difficult than the detection. In
error detection, we are looking only to see if any error has
occurred. The answer is a simple yes or no.
• In error correction, we need to know the exact number of bits
that are corrupted and more importantly, their location in the
message.
Behrouz A. Forouzan” Data communications and Networking 5
Note
Data can be corrupted
during transmission.
Some applications require that
errors be detected and corrected.
10.6
Note
In a single-bit error, only 1 bit in the data
unit has changed.
10.7
Figure 10.1 Single-bit error
10.8
Note
A burst error means that 2 or more bits
in the data unit have changed.
10.9
Figure 10.2 Burst error of length 8
10.10
Note
To detect or correct errors, we need to
send extra (redundant) bits with data.
10.11
Figure 10.3 The structure of encoder and decoder
10.12
Figure 10.4 XORing of two single bits or two words
10.15
Example 10.4
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
10.
Example 10.5
Find the minimum Hamming distance of the coding
scheme in Table 10.1.
Solution
We first find all Hamming distances.
The dmin in this case is 2.
10.
Example 10.6
Find the minimum Hamming distance of the coding
scheme in Table 10.2.
Solution
We first find all the Hamming distances.
The dmin in this case is 3.
10.
PARITY CHECK
The parity check is only useful for detecting single-bit errors.
The sender counts the amount of 1s in the frame and adds the parity bit
in the following manner:
Even parity: If the number of 1s is even, the parity bit value will be 0.
The parity bit value will be 1 if the number of 1s is odd.
Odd parity: If the number of 1s is odd, the parity bit value will be 0. The
parity bit value will be 1 if the number of 1s is even.
When a frame is received, the receiver counts the number of 1s in it. In
the case of an even parity check, the frame is accepted if the number of
1s is even; otherwise, it is refused. A similar approach is used for odd
numbers.
Behrouz A. Forouzan” Data communications and Networking 20
When a frame is received, the receiver counts the number of 1s in it. In
the case of an even parity check, the frame is accepted if the number of
1s is even; otherwise, it is refused. A similar approach is used for odd
numbers.
Behrouz A. Forouzan” Data communications and Networking 21
Note
A simple parity-check code is a
single-bit error-detecting
code in which
n = k + 1 with dmin = 2.
Even parity (ensures that a codeword
has an even number of 1’s) and odd
parity (ensures that there are an odd
number of 1’s in the codeword)
10.
Table 10.3 Simple parity-check code C(5, 4)
10.
Figure 10.10 Encoder and decoder for simple parity-check code
10.
Example 10.12
Let us look at some transmission scenarios. Assume the
sender sends the dataword 1011. The codeword created
from this dataword is 10111, which is sent to the receiver.
We examine five cases:
1. No error occurs; the received codeword is 10111. The
syndrome is 0. The dataword 1011 is created.
2. One single-bit error changes a1 . The received
codeword is 10011. The syndrome is 1. No dataword
is created.
3. One single-bit error changes r0 . The received codeword
is 10110. The syndrome is 1. No dataword is created.
10.
Example 10.12 (continued)
4. An error changes r0 and a second error changes a3 .
The received codeword is 00110. The syndrome is 0.
The dataword 0011 is created at the receiver. Note that
here the dataword is wrongly created due to the
syndrome value. (not a single bit error)
5. Three bits—a3, a2, and a1—are changed by errors.
The received codeword is 01011. The syndrome is 1.
The dataword is not created. This shows that the simple
parity check, guaranteed to detect one single error, can
also find any odd number of errors.
10.
Simple parity check can detect all single-bit errors. It
can detect burst errors only if the total number of
errors in each data unit is odd.
A better approach is the two-dimensional parity check
which organizes the data units into table (rows and
columns). The parity bit for each column is Calculated
and added to the table as a new row (column parity)
Behrouz A. Forouzan” Data communications and Networking 27
Figure 10.11 Two-dimensional parity-check code
10.
TWO-DIMENSIONAL PARITY
CHECK
Behrouz A. Forouzan” Data communications and Networking 29
Figure 10.11 Two-dimensional parity-check code
10.
Figure 10.11 Two-dimensional parity-check code
10.
2. Cyclic Redundancy Check (CRC)
In a cyclic code, if a code-word is cyclically
shifted (rotated), the result is another code-
word.
Example:
if 0111001 is a code-word and we cyclically
left-shift, then 1110010 is also a code-word.
Figure 10.14: CRC encoder and decoder
A CRC code with C(7, 4)
10.33
The Process of CRC
Find the CRC of Data block 1001 with the divisor 1011
At the Sender:
Find The length of Divisor “L” 1011 (4 bits here) predefined and agreed
upon.
Append “L-1=3 bits” to the original Message 1001 (000)
1001 becomes 1001000
Perform Binary Operation
The Remainder of the division is= CRC
Table 10.4 Hamming code C(7, 4) - n=7, k = 4
10.
The Process of CRC
At the Receiver:
1. The decoder does the same division process as
the encoder.
2. The remainder of the division is the syndrome.
If the syndrome is all 0s, there is no error, the
dataword separated from the received codeword
and accepted.
Otherwise, everything is discarded.
Figure 10.15: Division in CRC encoder
Behrouz A. Forouzan” Data communications and Networking
Figure 10.16: Division in the CRC decoder for two cases
