In this article, we are going to explore about error detection in computer networks. We will be seeing some standard error detecting codes which help in detecting errors. So let's get started.
Table of contents:
- Introduction to Error
- TYPES OF ERROR
- ERROR DETECTING CODES
- Simple parity check
- Two dimensional parity check
- Cyclic redundancy check
Introduction to Error
Error as we all know is a situation when message received is not identical as compared to error sent. It is very important to detect the error for proper and perfect transfer of information and message. There are basically two types of errors in computer network which needs to be detected and corrected.
TYPES OF ERROR
SINGLE BIT ERROR:
As the name suggests, in this type of error only one or single bit is changed from 0 to 1 or from 1 to 0. Let's take an example:
Suppose the message that is to be sent is 000100 and the message received is 001100. So the bit(bolder part) is changed from 0 to 1 as we can see that there is only single bit error.
In this type of error, more than one bits are changed from 0 to 1 or from 1 to 0. Simply we can say that when there is error in multiple bits then it is known as a burst error. Let's take an example:
Suppose the message that is to be sent is 0100010001000011 and the message received is 0101110101100011. The important thing in this type of error is that we take the length of burst error from first corrupted bit to last corrupted bit. So for this message length of burst error will be 8(bits in bold).
In networking, error detection refers to the techniques used to detect noise or other impairments introduced into data while it is transmitted from sender to receiver. Error detection ensures reliable delivery of data across vulnerable networks. It minimizes the probability or possibility of passing incorrect data frames to the receiver, known as undetected error probability. So if we define error detection in very simple words then it would be like, error detection is nothing but to identify errors in networks. When a message is sent, it may be jumbled by noise or the data may be damaged. To avoid this, we employ error-detecting codes, which are bits of extra data appended to a digital message to assist us detect whether an error occurred during transmission. So there are various error detecting codes or techniques that detect the errors in computer networks. We will explore each of them in brief and see how they detect errors, how they work etc.
ERROR DETECTING CODES
Generally there are four basic error detecting codes in computer networks. They are:
- Simple parity check
- Two dimensional parity check
- Cyclic redundancy check
SIMPLE PARITY CHECK
Simple parity check code is the most basic and easiest error detecting code. In this code, a k-bit data word is changed to an n-bit code word where n = k + 1. There is an extra bit which is known as parity bit which is use to make the number of 1's(ones) in a code word to be even. Although some implementations specify an odd number of 1s. The minimum Hamming distance for this category is 2, which means that the code is a single-bit error-detecting code and that's why it is also known as single parity check. It does not correct errors.
In this technique there is an encoder at sender side and a decoder at receiver side. The encoder encodes the message or code word and at first it will check total number of 1's or number of 0's in the original message. If there are even number of 1's in the message then we will add 0 at the end of original message, otherwise we will add 1 at the end to make total number of 1's as even. This process of making number of 1's even is known as even parity. The bit to be added at the end is known as parity bit. Now that appended message is sent to receiver.
At the receiver side, decoder decodes the received message and if the transmission was correct there will be no error and the message will be identical at the receiver side as sent by the sender. But if the transmission is incorrect it will detect the error by checking the parity bit.
- It is very easy to use and implement.
- It can detect single bit errors which help in smaller networks.
- It takes less amount of time in detecting errors as compared to other error detecting codes.
- The major issue with this technique is that it can detect only single bit errors.
- If there is error in two bits then it is unable to work properly.
- It does not provide the facility of error correction.
Two dimensional parity check
As we have seen above single parity check is easy but not very beneficial. So two dimensional parity check is an upgraded version of single parity check. Performance can be improved by using this technique, which organizes the block of bits in the form of a table. It can detect as well as correct one or more bit errors.
In this, we will maintain a matrix by putting message in different rows. Then as we have done in single parity check technique, here also we will add a parity bit according to number of 1's and 0's. If there are even number of 1's in the message then we will add 0 at the end of original message, otherwise we will add 1 at the end to make total number of 1's as even. This process is done for every rows and columns of the matrix. Now in this way, we will generate a new bit(from columns) so now we will sent appended bits and new bit to the receiver. Receiver detects error by checking the parity bit and if there is no problem while transmission then there will be no error otherwise it will detect the error.
- It will detect and correct one or more bit errors.
- It is more efficient as compared to single parity check.
- The performance of this technique is very good as it is an upgraded version of simple parity check.
- In some cases, an only odd number of bit errors can be detected and corrected but even number of errors can only be detected but not corrected.
- This method is unable to detect even no bit error.
A checksum is a sequence of numbers and letters used to check data for errors. It is a technique which is used to detect errors in computer networks. The checksum is used in the internet by several protocols although not at the data link layer.
We will see the working and approach of checksum error detection.
CHECKSUM GENERATOR -
Starting with sender side, checksum generator divides code word into smaller units of equal length of p bits. After that they are added to get a new code word using one's complement method. This result is also of p bits and this is again complemented. The complemented result is called as checksum. The checksum is added at the end of original code word and then that code word generated is transferred to the receiver.
CHECKSUM CHECKER -
Now at receiver side, the data received along with checksum is transmitted to checksum checker. Then these data which is received is divided into equal smaller units and then the final result is complemented. If this answer is zero which means that there is no error, otherwise error can be detected.
Checksum error detection code or technique helps in detecting errors which have even number of bits or odd number of bits.
This code does not detect errors which is present in subunits so it becomes problematic when we transmit information further as it is unable to detect these errors.
CYCLIC REDUNDANCY CHECK
This code is also known as CRC. The cyclic redundancy check (CRC) is a technique used to detect errors in digital data. CRC produces a fixed-length data set based on the build of a file or larger data set. CRC is used in storage devices like hard disks etc. CRC is based on binary division and is also called polynomial code checksum.
In this technique, at sender side (k-1) zeros are appended at the end of original code word. Now this newly generated code word is divided by key that is formed by generator polynomial. Generator polynomial is something like a normal equation like x3+x+1 or x2+1. For x3+x+1 key will be 1011 and for
x2+1 key will 101. Now according to generator polynomial key will be there and we divide appended code word with the key. The division operation used here will be the standard arithmetic division. The remainder obtained after this division is known as CRC remainder. Finding this remainder we will append this remainder in the appended code word which was obtained at the starting.
At receiver side, the newly data generated was transmitted at receiver side and again we will perform the same division as we have done above. If the remainder comes out be zero then there will be no errors otherwise it will detect errors.
- This is just a simple code and can be produced and implemented in any form of applications.
- It can easily view single bit errors and multiple burst errors.
- CRC is very simple to implement in binary hardware and it is good in detecting errors caused by noise in transmission.
- It is not suitable for protecting data.
- In this there is a high possibility of data overflow.
So now we have explored and discussed every aspect of error detection in computer networks. We have seen all the error detection codes their working, advantages and disadvantages. Now i would like to conclude this article with a hope that you all who are reading this article will definitely study this topic.