Error Correction and Error Detection
Error correction and error detection techniques are work on the data-link layer. The data link layer ensures the frames are sent from the sender to the receiver with accuracy. Error correction is more difficult than error detection.
An error is a situation when the data send by the sender and receive by the receiver, but that data doesn't match the sender data.
For example, the sender sends the 0101010 data, and the receiver receives the 1101010.
Types of Error
- Single bit error
- Burst error
Single-bit error: In the single-bit error, only one bit is changed in the frame. For example, the sender sends the data (01010100) in the frame, and the receiver receives the data (11010100) in the frame.
Burst error: In the burst error, one or more than one bits is changed in the frame. For example, the sender sends the data (01010100) in the frame, and the receiver receives the data (11010100) in the frame.
The main concept of error detection and error correction is redundancy. To the error detection and error correction, redundancy adds some extra redundant bits in the bits. The sender adds these redundant bits, and the receiver eliminates these redundant bits.
Redundancy is achieved by way of various coding schemes. The sender introduces redundant bits by establishing a connection between the redundant bits and the actual data bits. The receiver checks the relationship between the redundant bits and the actual data bits to detect the error. Coding schemes can be divided into two categories: block coding and convolution coding. Block coding is less complex than the convolution coding.
Error detection is the method of identifying errors. To identify these errors, it uses some redundancy codes. Redundancy codes added in actual data, and it has transmitted by the sender. These codes are known as error detection codes.
Types of error detection techniques:
- Parity Checking
- Cyclic Redundancy Check (CRC)
Parity Checking is also known as the Vertical redundancy check (VRC). Parity checking is a very simple technique. There are two cases in the parity checking techniques:
Even parity: If the number of 1's is even in the frame, 0 is added in the frame. The even-parity example shown in the figure below.
Odd parity: If the number of 1's is odd in the frame, 1 is added in the frame. The odd-parity example shown in the figure below.
Cyclic Redundancy Check
The cyclic redundancy check was developed by W-Wesley Peterson in 1961. It is a technique that is used to find errors in digital-data. The cyclic redundancy check is very easy to implement in hardware. It can be analyzed mathematically. The cyclic redundancy check is more effective than VRC and LRC techniques in detecting errors. VRC and LRC are based at the binary-addition, whereas the CRC is based at the binary-division.
The important points of CRC are following in the below.
- If the remainder is non-zero arrives after doing the Binary Division, that data is not error-free.
- If the remainder zero arrives after doing binary division, that data is error-free.
For better understand, let take an example.
Example 1 Data word = 110101
Divisor = 1010
Step 1: We can see that the divisor is of 4 bits, so we have to add (4-1) 0 to the data word.
Data word = 110101000
|1010) 110101000 (111011 1010 1110 1010 1001 1010 0110 0000 1100 1010 1100 1010 110|
The remainder is non-zero, so that will be again the binary division.
|1010) 110101110 (111011 1010 1110 1010 1001 1010 0111 0000 1111 1010 1010 1010 0000|
Now, the remainder is all zero. Hence, the data has error-free.
The checksum is an error detection technique. It can be applied to any information. The checksum is mostly used at the network layer and transport layer rather than the data-link layer.
At the sender side, each m bit of the data is divided into k segments. The segments are added with the 1's complement arithmetic at the sender end to get the sum. At the end of the receiver, all segments obtained are added using the arithmetic 1's complement to get the sum.
- If the value is 0, the obtained data is accepted.
- If the value is non-zero, the obtained data is discarded.
For better understand, let take an example, Suppose the sender wants to transmit 4-frames each of 8-bits. The frames are 11010100, 10101001, 00101100, and 01011100.
At the sender side, add first two frames
|11010100 10101001 101111101 Now, 1 is the shift 01111101 1 01111110 Now, add the third frame of this addition of first two frames 01111110 00101100 10101010 Now, add the fourth frame 10101010 01011100 100000110 Now, 1 is the shift 00000110 1 Sum = 00000111 Checksum is 1’s complement of sum = 11111000|
At the receiver side, add first two frames
|11010100 10101001 101111101 Now, 1 is the shift 01111101 1 01111110 Now, add the third frame of this addition of first two frames 01111110 00101100 10101010 Now, add the fourth frame 10101010 01011100 100000110 Now, 1 is the shift 00000110 1 00000111 Now, add checksum 00000111 11111000 11111111 Complement: 00000000 The complement value is zero. Hence, all frames have been accepted.|
Error correction is more difficult than error detection. Error correction codes are used to detect and correct errors when transmitting data from the sender to the receiver. It can be done in two ways:
- Backward Error Correction
- Forward Error Correction
Backward Error Correction: If the receiver receives an error in the received data, it tells the sender to retransmit the data again.
Forward Error Correction: If the receiver finds an error in the received data, the error correction codes correct these errors automatically.