Let us know what is an error before going into the topic, there may be a circumstance where a sender sends the data to the receiver, then the data may get lost. So an error is a circumstance in which the data which is sent by the sender does not “match” the data that is at the receiver’s side. To read more about Error Correction And Detection In Computer Networks, keep reading this article till the end.
So when an error is encountered, then we should send back the data. So there are many different techniques to control the errors in computer networks. And there are different types of errors:
1.Single bit error: If there exists a change in the data that sender sends, that is in only one bit of the data, then it is knows as single bit error.
Example: if the data is sent by the sender is 110(6) and if the receiver receives it as 111(7) then it is known as single bit.
bits which are sent(110) à bits which are received(111)
2.Burst error: if there exists a change in the data that sender sends, that is in only two or more bits of the data, then it is known as burst error.
Example: if the data sent by the sender is 1100(12) and if the receiver receives it as 1001(9) then it is known as burst error.
(bits which are sent)1100 à bits which are received(1001)
Error Correction And Detection In Computer Networks
Error control
The data link layer has an error control mechanism, it consists of a process of detection and data retransmission that was lost during sending the data. Detecting and correcting mechanisms must be presented in any system which is reliable. So the transport layer has both error detection and correction.
Error control mechanism has phases:
- Error detection
- Acknowledgement
- Retransmission
In error detection, we should detect the error at the end of receiver to see if the data has received or not.
Acknowledgement means when detection of error happens, the receiver will send a NACK(negative acknowledgement) to the sender.
Retransmission means the sender will retransmit the data again when he does not get the negative acknowledgement or any acknowledgement from the receiver.
Error detection
There are 4 techniques in this:
- Vertical Redundancy Check
- Longitudinal Redundancy Check
- Circular Redundancy Check
- Checksum
Vertical Redundancy check
There is a redundant called parity bit, and this bit is added to the data. So if the number of bits(1’s) in the data is even then the parity bit is added. This is known as even parity checking.
we will add the bit 0, when the “number of 1’s” is even, if the number of 1’s is odd we will add 1.
The odd number of 1’s will also be checked by the systems. This is known as odd parity checking.
Let us consider that we have a data 1001001, this data is received by even parity generator and that will add a redundant bit it will check how many number of 1’s are there. This even parity generator adds a bit 1 if it has odd number of 1’s.
Longitudinal Redundancy check:
In VRC the parity bit is given to all blocks of data, but in LRC ,the bit blocks are arranged in columns and rows. We also called LRC as Two Dimensional Parity. This calculation of parity bit will be done for each and every column and that is sent along with the data. The parity block will be acted as the redundant bits because these bits should be set along with the data so that the receiver can receive all the data blocks and also redundant bits, these redundant bits are useful for the receiver to detect whether there are errors during transmission of data or not.
Cyclic Redundancy check:
Cyclic redundancy check will detect the changes or errors that are accidental which is in the channel of communication.
This will use “Generator Polynomial”, and this is present in sender side as well as receiver side.
At sender side: (the encoded data generation from data and generator polynomial)or so called key:
This binary data is added by using k-1 zeroes at the data end.
We have to use modulo-2 binary division which is used to divide binary data by using the key and save the division’s remainder.
The remainder is appended at the data end which will form the encoded data and same thing is sent.
At Receiver side:
We have to perform modulo-2 division and if we the remainder as 0, it is error-free.
What is modulo-2 division?
The process consists of usage of decimal numbers, instead of subtraction, we will use XOR operation.
In each and every step, divisor copy is XORed with the dividend k-bits.
The XOR operation result which is remainder that is n-1 bits, after 1 extra bit that is used for the next step which pulls down that will make it n bits.
So if no bits are not left for pulling down, result is found. The remainder of n-1 bits that is given to the side of sender.
Checksum: Error Correction And Detection In Computer Networks
It is also a block code method in which creation of checksum happens which is dependent on the values of data in the data blocks to be sent that uses an algorithm and appends to the data. When the data is received by receiver, calculation of new checksum happens and it is compared with the already present checksum. When there is no match, it will indicate the error.
In this method, division of data happens into fixed size frames or segments:
Sender’s end: The sender will add the frames by using 1’s complement that will give the result of sum. The sum is complemented to get the checksum and it is sent along with the frames of data.
Receiver’s end: the receiver will add segments which are incoming that is along with the checksum by using 1’s complement to get the sum and complements it.
[I hope you are liking our article on Error Correction And Detection In Computer Networks]
When the result is 0, the frames that are received are accepted, if not they are removed.
Error correction code:
It is useful for deriving a sequence of numbers so that if any errors that are entered that will be detected and also corrected depending on the remaining numbers.
Error detection is very easier than error correction.
Hamming code:
With the help of this hamming code, we can detect the errors and we can correct the errors. Hamming code can be applied to any data bits of any length,it is used to detect and correct single bit errors.
Hamming code structure looks like all bit positions which are a power of 2 are given as parity bits. The other bits are for data to be encoded.
Handling of error correction are done in two ways:
Backward error correction: when the error is detected, the receiver will request the sender to send back the whole data again.
Forward error correction: The user will be using “error-correcting” codes and that will automatically corrects the errors.
Hamming code algorithm:
The bits of “d”s information is added to the redundant bits “r” which will be formed as d+r.
(d+r) digits location is given a decimal value.
In the positions of 1,2…2^k-1, these “r” bits are present.
The parity bits are calculated once again at the end of the receiver. The parity bits of decimal value will determine the error’s position.
One extra single bit will only perform the detection of error but it can’t correct the error.
User should know the position of the error which is exact, for example: when you want to calculate a single-bit error, this “error correction code” will identify if there’s an error in 7 bits. To get this done successful, user should few extra redundant bits.
Let us consider r as the redundant bits and d means total number of bits of data. Then the formula is
2^r=d+r+1
For example if we give the value of d as four, the small possible value which will be satisfied in the given formula is three.
Error correcting codes are of two types:
Block codes: The data is divided into the sized blocks that are fixed and addition of redundant bits will be done to detect the errors and correct the errors.
Convolutional codes: the data consists of streams which are of length arbitrary and generation of parity bits will be done by using the Boolean function to the stream of data.
Error correcting codes are:
Hamming codes
Binary convolution code
Reed-Solomon code.
Low density parity check code.
I hope you have read and understood the article on Error Correction And Detection In Computer Networks.
Leave a comment