Unit 3
Data link layer: Error detection And correction: Framing, flow and error control
Types of Errors
Whenever bits flow from one point to another, they are subject to unpredictable changes
because of interference. This interference can change the shape of the signal. In a single-bit
error, a 0 is changed to a 1 or a 1 to a O. In a burst error, multiple bits are changed. For eg,, a
11100 s burst of impulse noise on a transmission with a data rate of 1200 bps might change
all or some of the12 bits of information.
Single-Bit Error
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.
Figure 10.1 shows the effect of a single-bit error on a data unit. To understand the impact of the
change, imagine that each group of 8 bits is an ASCII character with a 0 bit added to the left. In
Figure 10.1,00000010 (ASCII STX) was sent, meaning start of text, but 00001010 (ASCII LF)
was received, meaning line feed.
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.
Figure 10.2 shows the effect of a burst error on a data unit. In this case, 0100010001000011 was
sent, but 0101110101100011 was received. Note that 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.
,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.
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. We are not even interested in the number of errors. A single-
bit error is the same for us as a burst error.
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. If we need to correct one single error in an 8-bit data unit, we need to
consider eight possible error locations; if we need to correct two errors in a data unit of the same
size, we need to consider 28 possibilities.
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 (usually, not all errors can be detected).
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. Figure 10.3 shows the general idea of coding.
We can divide coding schemes into two broad categories:
block coding and convolution coding.
,Modular Arithmetic
In modular arithmetic, we use only a limited range of integers. We define an upper limit,
called a modulus N. We then use only the integers 0 to N - I, inclusive. This is modulo-N
arithmetic. For example, if the modulus is 12, we use only the integers 0 to 11, inclusive.
An example of modulo arithmetic is our clock system. It is based on modulo-12 arithmetic,
substituting the number 12 for O. In a modulo-N system, if a number is greater than N, it is
divided by N and the remainder is the result. If it is negative, as many Ns as needed are added
to make it positive. Consider our clock system again. If we start a job at 11 A.M. and the job
takes 5 h, we can say that the job is to be finished at 16:00 if we are in the military, or we can
say that it will be finished at 4 P.M.
In modulo-N arithmetic, we use only the integers in the range 0 to N - 1, inclusive.
Modulo-2 Arithmetic
Of particular interest is modulo-2 arithmetic. In this arithmetic, the modulus N is 2. We can
use only 0 and 1. Operations in this arithmetic are very simple. The following shows how we
can add or subtract 2 bits.
Adding: 0+0=0 0+1=1 1+0=1 1+1=0
Subtracting: 0-0=0 0-1=1 1-0=1 1-1=0
In this arithmetic we use the XOR (exclusive OR) operation for both addition and
subtraction. The result of an XOR operation is 0 if two bits are the same; the result is I if two
bits are different. Figure 10.4 shows this operation.
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.We have a set of datawords, each of size k, and a set of codewords, each of
size of n. With k bits, we can create a combination of 2k datawords; with n bits, we can create
a combination of 2n codewords.
Since n > k, the number of possible codewords is larger than the number of possible
datawords.
, The block coding process is one-to-one; the same dataword is always encoded as the same
codeword. This means that we have 2n - 2k codewords that are not used. We call these
codewords invalid or illegal. Figure 10.5 shows the situation
Error Detection
How can errors be detected by using block coding? If the following two conditions are met, the
receiver can detect a change in the original codeword.
1. The receiver has (or can find) a list of valid codewords.
2. The original codeword has changed to an invalid one.
Figure 10.6 shows the role of block coding in error detection
The sender creates codewords out of datawords by using a generator that applies the rules and
procedures of encoding .Each codeword sent to the receiver may change during transmission.
If the received codeword is the same as one of the valid codewords, the word is accepted; the
corresponding dataword is extracted for use.
If the received codeword is not valid, it is discarded.
If the codeword is corrupted during transmission but the received word still matches a valid
codeword, the error remains undetected.
This type of coding can detect only single errors. Two or more errors may remain undetected.
Data link layer: Error detection And correction: Framing, flow and error control
Types of Errors
Whenever bits flow from one point to another, they are subject to unpredictable changes
because of interference. This interference can change the shape of the signal. In a single-bit
error, a 0 is changed to a 1 or a 1 to a O. In a burst error, multiple bits are changed. For eg,, a
11100 s burst of impulse noise on a transmission with a data rate of 1200 bps might change
all or some of the12 bits of information.
Single-Bit Error
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.
Figure 10.1 shows the effect of a single-bit error on a data unit. To understand the impact of the
change, imagine that each group of 8 bits is an ASCII character with a 0 bit added to the left. In
Figure 10.1,00000010 (ASCII STX) was sent, meaning start of text, but 00001010 (ASCII LF)
was received, meaning line feed.
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.
Figure 10.2 shows the effect of a burst error on a data unit. In this case, 0100010001000011 was
sent, but 0101110101100011 was received. Note that 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.
,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.
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. We are not even interested in the number of errors. A single-
bit error is the same for us as a burst error.
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. If we need to correct one single error in an 8-bit data unit, we need to
consider eight possible error locations; if we need to correct two errors in a data unit of the same
size, we need to consider 28 possibilities.
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 (usually, not all errors can be detected).
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. Figure 10.3 shows the general idea of coding.
We can divide coding schemes into two broad categories:
block coding and convolution coding.
,Modular Arithmetic
In modular arithmetic, we use only a limited range of integers. We define an upper limit,
called a modulus N. We then use only the integers 0 to N - I, inclusive. This is modulo-N
arithmetic. For example, if the modulus is 12, we use only the integers 0 to 11, inclusive.
An example of modulo arithmetic is our clock system. It is based on modulo-12 arithmetic,
substituting the number 12 for O. In a modulo-N system, if a number is greater than N, it is
divided by N and the remainder is the result. If it is negative, as many Ns as needed are added
to make it positive. Consider our clock system again. If we start a job at 11 A.M. and the job
takes 5 h, we can say that the job is to be finished at 16:00 if we are in the military, or we can
say that it will be finished at 4 P.M.
In modulo-N arithmetic, we use only the integers in the range 0 to N - 1, inclusive.
Modulo-2 Arithmetic
Of particular interest is modulo-2 arithmetic. In this arithmetic, the modulus N is 2. We can
use only 0 and 1. Operations in this arithmetic are very simple. The following shows how we
can add or subtract 2 bits.
Adding: 0+0=0 0+1=1 1+0=1 1+1=0
Subtracting: 0-0=0 0-1=1 1-0=1 1-1=0
In this arithmetic we use the XOR (exclusive OR) operation for both addition and
subtraction. The result of an XOR operation is 0 if two bits are the same; the result is I if two
bits are different. Figure 10.4 shows this operation.
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.We have a set of datawords, each of size k, and a set of codewords, each of
size of n. With k bits, we can create a combination of 2k datawords; with n bits, we can create
a combination of 2n codewords.
Since n > k, the number of possible codewords is larger than the number of possible
datawords.
, The block coding process is one-to-one; the same dataword is always encoded as the same
codeword. This means that we have 2n - 2k codewords that are not used. We call these
codewords invalid or illegal. Figure 10.5 shows the situation
Error Detection
How can errors be detected by using block coding? If the following two conditions are met, the
receiver can detect a change in the original codeword.
1. The receiver has (or can find) a list of valid codewords.
2. The original codeword has changed to an invalid one.
Figure 10.6 shows the role of block coding in error detection
The sender creates codewords out of datawords by using a generator that applies the rules and
procedures of encoding .Each codeword sent to the receiver may change during transmission.
If the received codeword is the same as one of the valid codewords, the word is accepted; the
corresponding dataword is extracted for use.
If the received codeword is not valid, it is discarded.
If the codeword is corrupted during transmission but the received word still matches a valid
codeword, the error remains undetected.
This type of coding can detect only single errors. Two or more errors may remain undetected.
