Describe strategies for error detection
The basic approach used for error detection is the use of redundancy, where additional bits are added to facilitate detection and correction of errors. Popular techniques are:
- simple parity check
- two-dimensional parity check
- checksum
- cyclic redundancy check
Simple Parity Check
- A redundant bit called a parity bit, is appended to every data unit so that the number of 1's in the unit including the parity becomes even.
- Blocks of data from the source are subjected to a check bit generator form, where a parity of 1 is added to the block if it contains an odd number of 1's and 0 is added if it contains an even number of 1's. At the receiving end the parity bit is computed from the received data and compared with the received parity bit.
- This scheme makes the total number of 1's even.
Two-Dimensional Parity Check
- Organises the block of bits in the form of a table. Parity check bits are calculated for each row, which is equivalent to a simple parity check bit.
- Parity check bits are also calculated for all columns then both are sent along with the data. At the receiving end these are compared with the parity bits calculated on the received data.
Checksum
- The data is divided into k segments each of m bits. At the sender's end the segments are added using 1's complement arithmetic to get the sum. The sum is completed to get checksum.
- The checksum segment is sent along with the data segments.
- At the receiver's end, all received segments are added using 1's complement arithmetic to get the sum. This sum is complemented. If the result is zero, the received data is accepted; otherwise discarded.
Cyclic Redundancy Checks
- Most powerful and easy to implement
- Based on binary division
- A sequence of redundant bits, called cyclic redundancy check bits, are appended to the end of the data unit so that the resulting data unit becomes exactly divisible by a second, predetermined binary number.
- At the destination, the incoming data unit is assumed to be correct and is therefore accepted. A remainder indicated that the data unit has been damaged in transit and therefore must be rejected.