Computer

Communications and
Networks
Izna Hussain
Lecturer
Computer Science Department
Islamabad Model College for Girls
St # 25 F-6/2 Islamabad
Data Link Layer –
Error Detection and Correction
Table of contents
01 02 03

Types of Errors Redundancy Coding

04 05 05

Error Detection Hamming code Cyclic Redundancy Check

Introduction
• Networks must be able to transfer data from one device to another with acceptable
accuracy.
• Any time data are transmitted from one node to the next, they can become corrupted in
passage.
Data can be corrupted during transmission. Some applications
require that errors be detected and corrected.
Single Bit Errors
• The term single-bit error means that only 1 bit of a given data unit (such as a byte,
character, or packet) is changed from 1 to 0 or from 0 to 1.
• Single-bit errors are the least likely type of error in serial data transmission.
Burst Error
• The term burst error means that 2 or more bits in the data unit have changed from 1 to 0
or from 0 to 1.
• A burst error does not necessarily mean that the errors occur in consecutive bits.
• The length of the burst is measured from the first corrupted bit to the last corrupted bit.
• Some bits in between may not have been corrupted.
Burst Error
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.
To detect or correct errors, we need to send extra
(redundant) bits with data.
Detection Versus 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.
• The number of the errors and the size of the message are important factors.
Forward Error Correction Versus Retransmission
There are two main methods of error correction.
• Forward error correction is the process in which the receiver tries to guess the
message by using redundant bits.
• This is possible if the number of errors is small.

• Correction by retransmission is a technique in which the receiver detects the

occurrence of an error and asks the sender to resend the message.
• Resending is repeated until a message arrives that the receiver believes is error-free.
Coding
• Redundancy is achieved through various coding schemes.
• The sender adds redundant bits through a process that creates a relationship between
the redundant bits and the actual data bits.
• The receiver checks the relationships between the two sets of bits to detect or correct
the errors.
• The ratio of redundant bits to the data bits and the robustness of the process are
important factors in any coding scheme.
Coding
Modular Arithmetic
Block Coding
• The message is divided into blocks, each of k bits, called datawords.
• Redundant bits are added to each block to make the length n=k+r
• Resulting n-bit blocks are called codewords.
Datawords and codewords in block coding
Error Detection
• If the following two conditions are met, the receiver can detect a change in the original
code word.
• The receiver has (or can find) a list of valid code words.
• The original code word has changed to an invalid one.
Process of error detection in block coding
Example
• Let us assume that k = 2 and n = 3. Table 10.1 shows the list of datawords and
codewords. Later, we will see how to derive a codeword from a dataword.
Example
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 (the leftmost bit is
corrupted). This is not a valid codeword and is discarded.
3. The codeword is corrupted during transmission, and 000 is received (the right two bits
are corrupted). This is a valid codeword. The receiver incorrectly extracts the dataword
00. 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.
Error Correction
• Error correction is much more difficult than error detection.
• In the receiver needs to find (or guess) the original codeword sent.
• we need more redundant bits for error correction than for error detection.
Error Correction
Example
Let us add more redundant bits to Example 10.2 to see if the receiver can correct an error
without knowing what was actually sent. We add 3 redundant bits to the 2-bit dataword to
make 5-bit codewords. Table 10.2 shows the datawords and codewords. Assume the
dataword is 01. The sender creates the codeword 01011. The codeword is corrupted during
transmission, and 01001 is received. First, the receiver finds that the received codeword is
not in the table. This means an error has occurred. The receiver, assuming that there is only
1 bit corrupted, uses the following strategy to guess the correct dataword.
Example
Example
• 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.
• By the same reasoning, the original codeword cannot be the third or fourth one in the
table.
• 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.
Hamming Distance
• One of the central concepts in coding for error control is the idea of the Hamming
distance.
• The Hamming distance between two words (of the same size) is the number of
differences between the corresponding bits.
• Hamming distance between two words x and y as d(x, y).
• The Hamming distance can easily be found if we apply the XOR operation (ffi) on the two
words and count the number of Is in the result.
The Hamming distance between two words is the number of
differences between corresponding bits.
Hamming Distance
• Let us find the Hamming distance between two pairs of words.
• The Hamming distance d(000, 011) is 2 because

• The Hamming distance d(10101, 11110) is 3 because

Minimum Hamming Distance
• In a set of words, the minimum Hamming distance is the smallest Hamming distance
between all possible pairs.
• We use dmin to define the minimum Hamming distance in a coding scheme.
Example
• Find the minimum Hamming distance of the coding scheme in Table 10.1.

• The dmin in this case is 2.

Example
• Find the minimum Hamming distance of the coding scheme in Table

• The dmin in this case is 3.

To guarantee correction of up to t errors in all cases, the minimum
Hamming distance in a block code
must be dmin = 2t + 1.
Example
A code scheme has a Hamming distance dmin = 4. What is the error detection and correction
capability of this scheme?

This code guarantees the detection of up to three errors

(s = 3), but it can correct up to one error. In other words,
if this code is used for error correction, part of its capability is wasted. Error correction
codes need to have an odd minimum distance (3, 5, 7, . . . ).
Linear Block Codes
• Almost all block codes used today belong to a subset called linear block codes.
• A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid
codewords creates another valid codeword.
A simple parity-check code is a
single-bit error-detecting
code in which
n = k + 1 with dmin = 2.
Simple parity-check code C(5, 4)
Encoder and decoder for simple parity-check code
Example
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.
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.
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.
A simple parity-check code can detect an odd number of errors.
Two-dimensional Parity check code
Two-dimensional Parity check code
Two-dimensional Parity check code
Hamming Code
• Hamming code is an error-correcting code used to ensure data accuracy during
transmission or storage.
• Hamming code detects and corrects the errors that can occur when the data is moved or
stored from the sender to the receiver.
• How to calculate redundant bits in hamming code?
𝟐𝒓 ≥ 𝒎 + 𝒓 + 𝟏
Here,
m is the number of bits in input data
r is the number of redundant bits
Example
• Suppose we have to send 1011 using hamming code
• Here,
m=4
• We will put different values of r in the inequality to find the number of redundant bits
r=3
𝟐𝟑 ≥ 𝟒 + 𝟑 + 𝟏
𝟖≥𝟖
So the number of redundant bits will be 3.
Example
1 001
 2^n where n = {0,1,2….}
 So, in 7-bit hamming code parity bits will be at position 1,2, and 4
2 010
 P1 => d3 d5 d7 3 011
 P2 => d3 d6 d7
4 100
 P4 => d5 d6 d7
5 101

6 110
d7 d6 d5 p4 d3 p2 p1
7 111

8 1000
Example
1 001
 Data to be transmitted: 1011
 Even Parity 2 010

3 011

4 100

5 101
d7 d6 d5 p4 d3 p2 p1
6 110
1 0 1 1

7 111
Example
1 001
 Data to be transmitted: 1011
 Even Parity 2 010

3 011

4 100

5 101
d7 d6 d5 p4 d3 p2 p1
6 110
1 0 1 1 1

7 111
Example
1 001
 Data to be transmitted: 1011
 Even Parity 2 010

3 011

4 100

5 101
d7 d6 d5 p4 d3 p2 p1
6 110
1 0 1 1 1

7 111
Example
1 001
 Data to be transmitted: 1011
 Even Parity 2 010

3 011

4 100

5 101
d7 d6 d5 p4 d3 p2 p1
6 110
1 0 1 1 0 1

7 111
Example
1 001
 Data to be transmitted: 1011
 Even Parity 2 010

3 011

4 100

5 101
d7 d6 d5 p4 d3 p2 p1
6 110
1 0 1 1 0 1

7 111
Example
1 001
 Data to be transmitted: 1011
 Even Parity 2 010

3 011
 Codeword will be: 1010101

4 100

5 101
d7 d6 d5 p4 d3 p2 p1
6 110
1 0 1 0 1 0 1

7 111
Example
 Received data is: 1110101

d7 d6 d5 p4 d3 p2 p1
1 1 1 0 1 0 1
Example
 Received data is: 1110101

d7 d6 d5 p4 d3 p2 p1
1 1 1 0 1 0 1

 Check parity for P1 and corresponding data values

 p1 d3 d5 d7 => 1111
 Even parity fulfilled
 Set p1 = 0
Example
 Received data is: 1110101

d7 d6 d5 p4 d3 p2 p1
1 1 1 0 1 0 1

 Check parity for P1 and corresponding data values

 p2 d3 d6 d7 => 0111
 Even parity not fulfilled
 Set p2 = 1
Example
 Received data is: 1110101

d7 d6 d5 p4 d3 p2 p1
1 1 1 0 1 0 1

 Check parity for P1 and corresponding data values

 p4 d5 d6 d7 => 0111
 Even parity not fulfilled
 Set p4 = 1
Example
 Received data is: 1110101

d7 d6 d5 p4 d3 p2 p1
1 1 1 0 1 0 1

 Now to correct the corrupted bit, it’s location will be found using the parity values that were set while
checking
 p4p2p1 => 110
 Convert it to decimal alternative => 6 => The bit at 6th location is changed during transmission.
 We will simply invert it to get the correct value of bit.
 After correction: 1010101
Cyclic Redundancy Check
• Transmitter
• For a k-bit block, transmitter generates an (n-k)-bit frame check sequence (FCS)
• Resulting frame of n bits is exactly divisible by predetermined number
• Receiver
• Divides incoming frame by predetermined number
• If no remainder, assumes no error
Cyclic Redundancy Check
• Based on binary division
• CRC generator is an algebraic polynomial represented as a bit pattern.
• Bit pattern is obtained from the CRC generator using the following rule “The power of
each term gives the position of the bit and the coefficient gives the value of the bit.”
• Consider the CRC generator is x7 + x6 + x4 + x3 + x + 1.
Cyclic Redundancy Check
• The data to be sent is: 1101011011
• Generator polynomial: x4 + x + 1
• Converting into bits: 10011
• As generator polynomial is of 5 bits, four zeroes will be appended at the end of the
message which makes it: 11010110110000
Cyclic Redundancy
Check
Step 2 – Appending CRC to Data Unit
• From here, CRC = 1110.

Now,
• The code word to be transmitted is obtained by replacing the last 4 zeroes of
11010110110000 with the CRC.
• Thus, the code word transmitted to the receiver = 11010110111110
Step 3 – Transmission to Receiver

The newly formed code word (Original data + CRC) is transmitted to the receiver.
Step 4 – Checking at Receiver Side
• At receiver side, the transmitted code word is received.
• The received code word is divided with the same CRC generator.
• On division, the remainder so obtained is checked.
• The following two cases are possible-
• Case-01: Remainder = 0
• If the remainder is zero,
• Receiver assumes that no error occurred in the data during the transmission.
• Receiver accepts the data.
• Case-02: Remainder ≠ 0
• If the remainder is non-zero,
• Receiver assumes that some error occurred in the data during the transmission.
• Receiver rejects the data and asks the sender for retransmission.
Example – Mini Activity
• A bit stream 10011101 is transmitted using the standard CRC method. The generator
polynomial is x3+1.

• What is the actual bit string transmitted?

• Suppose the third bit from the left is inverted during transmission. How will receiver
detect this error?
Checksum
• Suppose our data is a list of five 4-bit numbers that we want to send to a destination. In
addition to sending these numbers, we send the sum of the numbers.
• For example, if the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12, 0, 6, 36), where
36 is the sum of the original numbers.
• The receiver adds the five numbers and compares the result with the sum. If the two are
the same, the receiver assumes no error, accepts the five numbers, and discards the
sum.
• Otherwise, there is an error somewhere and the data are not accepted.
Checksum
• We can make the job of the receiver easier if we send the negative (complement) of the
sum, called the checksum.
• In this case, we send (7, 11, 12, 0, 6, −36).
• The receiver can add all the numbers received (including the checksum). If the result is
0, it assumes no error; otherwise, there is an error.
Checksum
How can we represent the number 21 in one’s complement arithmetic using only four bits?

The number 21 in binary is 10101 (it needs five bits). We can wrap the leftmost bit and add it to the four
rightmost bits. We have (0101 + 1) = 0110 or 6.
Checksum
How can we represent the number −6 in one’s complement arithmetic using only four bits?

In one’s complement arithmetic, the negative or complement of a number is found by inverting all bits.
Positive 6 is 0110; negative 6 is 1001. If we consider only unsigned numbers, this is 9. In other words,
the complement of 6 is 9.
Checksum
Checksum – Sender
1. The message is divided into 16-bit words
2. The value of checksum word is set to zero.
3. All words including the checksum are added using one’s complement addition.
4. The sum is complemented and becomes the checksum.
5. The checksum is sent with the data.
Checksum – Receiver Site
1. The message (including checksum) is divided into 16-bit words.
2. All words are added using one’s complement addition.
3. The sum is complemented and becomes the new checksum.
4. If the value of checksum is 0, the message is accepted; otherwise, it is rejected.
Example
Let us calculate the checksum for a text of 8 characters (“Forouzan”). The text needs to be
divided into 2-byte (16-bit) words. We use ASCII to change each byte to a 2-digit
hexadecimal number. For example, F is represented as 0x46 and o is represented as 0x6F.
Figure 10.25 shows how the checksum is calculated at the sender and receiver sites. In part
a of the figure, the value of partial sum for the first column is 0x36. We keep the rightmost
digit (6) and insert the leftmost digit (3) as the carry in the second column. The process is
repeated for each column. Note that if there is any corruption, the checksum recalculated
by the receiver is not all 0s. We leave this an exercise.
Example