Error Detection and Correction
Data can be corrupted during transmission for reliable communication errors must be detected and corrected
Types of Error:
- Single Bit error
- Burst Error
Single Bit Error:-
Single bit error in it only 1 bit of given data unit such as a byte, character, data packet is changed from 1 to 0 or from 0 to 1. Single bit error least least likely type of error in serial data communication. Single bit error can happen if we are sending data using parallel transmission.
Example: If 8 wires are used to send all 8 bits of one byte at the same time and 1 wire is noisy then 1 bit can be corrupted in each byte. Duration of noise <= Duration of 1 bit.
Burst Error in it two or more bits in the data unit have changed from 1 to 0 or from 0 to 1. Note: Burst Error does not necessary means that error occur in consecutive bits, the length of burst is measured from the 1st corrupted bit to the last corrupted bit. Duration of noise >= duration of 1 bit.
Techniques for Error Detection:-
- Parity check
- Simple Parity Check
- Two Dimensional Parity Check
- Cyclic Redundancy Check
The concept of including extra information in the transmission for error detection is better than sending the same bit stream twice for comparison at is it doubles the transmission time and also it takes some extra time for comparison. Error Detection uses the concept of redundancy which means adding extra bit for detecting error at the destination.
- Data stream is generated
- Data analyzed and add it’s appropriate coded redundancy check
- The new data + extra Bits is transferred through the link to receiver
- Receiver puts the data + extra Bits through a checking function.
- If checking criteria is fulfilled the data portion is accepted and redundant bits are discarded.
Simple parity check:
In this technique redundant bit called parity bit is added to every data unit so that the total number of 1s in the unit’s including the parity bit became even or odd.
- Adding number of ones.
- If number of 1s in the data is odd then parity bit is appended with value 1.
- If number of 1s in the data is even then a parity bit is appended with value 0.
- resulting in an even number of ones in the bit stream.
- The entire expanded unit is now transmitted across the network link.
- At the destination the unit is put in the even parity checking function if the number of ones in the data unit is even the data is passed without the parity bit. If the number of ones in the data unit is odd then the data unit is rejected because the receiver knows an error has occurred.
- Simple parity check can detect all single bit errors.
- It can detect errors as long as total number of bits changed is odd.
Two dimensional parity check.
A block of bits is organized in a table, then we calculate parity bit for each data unit. Then we organize them into a table. We then calculate the parity bit for each column and create a new row of 8 bits they are the parity bits of the whole Block. We then attach the second parity to the original data.
Two dimensional parity bit increases the likelihood of detecting burst error.
- A redundancy of n bits can easily detect a burst error of n bits.
- A burst error of more than 1 bits is also detected by this method.
- Only one pattern of errors remains exclusive, if two bits in one data unit are damaged and two bits in exactly the same position in another data unit are also damage then, the checking function will not detect an error.
Cyclic Redundancy Check (CRC):
- It is based on binary division CRC.
- CRC Remainder is appended to the end of a data unit so that the resulting data becomes exactly divisible by a second predetermined binary number.
- At its destination the incoming data unit is divided by the same number if there is no remainder the data is assume to be intact and is therefore accepted.
- A Reminder indicates the data has been corrupted in transit.
Valid conditions for CRC:
- It must have exactly one less bit then the divisor.
- Appending it to the end of the data stream must make the resulting bit sequence exactly divisible by the divisor.
Steps for CRC:
- A string of and 0s is appended to the data unit. The number N is 1 less than the number of bits in the predetermined divisor which is N + 1 bit.
- The new elongated data unit is now divided by the divisor using binary division the resulting reminder is called CRC.
- The CRC of N bits replace the appended 0s at the end of the data unit.
- The data unit arrives at the receiver, Data first followed by the CRC , the receiver treats the whole as a unit and divide it by the same divisor to find the CRC reminder.
Divisor has 4 bit so 3 0s will be appended in the data bits and division will take place.
It works in the same way if the remainder is 0 then the CRC is dropped and the data unit is accepted.
- CRC can detect all burst error that affect an odd number of bits.
- CRC can detect all Burst errors of length less than or equal to degree of polynomial.
- CRC can detect with a very high probability burst error of length greater than the degree of the polynomial.
- The unit is divided into K sections of N bits each of N bits.
- All sections are added using 1’s Complement to get the sum.
- Sum is complemented and becomes the checksum.
- The checksum is sent with the data.
- The unit is divided into N bits of K sections.
- All sections are added using 1’s complement to get the sum.
- The sum is complemented if the result is 0, the data is accepted otherwise rejected.
- The checksum detects all errors involving an odd number of bits as well as most errors involving even number of bits.
- If one or more bits of a segment are damaged and corresponding bit or bits of the opposite value in the second segment are also damage, then sum of those column will not change and the receiver will not detect the problem.