Error detection - parity check, cyclic redundancy check, check sum

During transmission of data, data can be corrupted. Error detection and corrections are techniques that enable reliable communication. If the output information does not match the input information, then it is called error. During transmission of digital signal, some noise may be introduced in digital signal.

Error may be in single bit or may be in multiple bits.

TYPES OF ERROR

1. Single bit : Error may in single bit. For example, a 0 bit may changed into 1 bit.
2. Multiple bit: Error may be in multiple non-consecutive bits.
3. Burst bit: Error may be in multiple consecutive bits.

Error detection

Error detection is achieved by transmitting some extra bits with digital signal. These bits allows receiver to deduce that an error occurred in output digital signal.

Error detection methods

1. Parity check
2. Cyclic redundancy check
3. Checksum

After going to parity check, i cleared some terms

Even parity : In even parity we consider the even numbers of  1s in digital data. If digital data has odd numbers of 1s, then we add extra 1 at the end of digital data. 

For example, a digital data 11001000 has odd numbers of 1s, then we add an extra 1 at the end of this digital data, then the digital data becomes 110010001.

Odd parity : Odd parity refers to parity checking modes, where each set of transmitted bits has an odd number of bits. If the total number of ones in the data plus the parity bit is an odd number of ones, it is called odd parity. If the data already has an odd number of ones, the value of the added parity bit is 0, otherwise it is 1. 

Parity check

A parity bit is added to each digital data so that the even number of 1s including parity bit becomes even for even parity or odd for odd parity.

If the receiver gets same number of 1s as in the input digital data, then the digital data is accepted, otherwise data is rejected or corrected.

For example, that two devices are communicating with even parity. As the transmitting device sends data, it counts the number of set bits in each group of seven bits. If the number of set bits is even, it sets the parity bit to 0; if the number of set bits is odd, it sets the parity bit to 1. In this way, every byte has an even number of set bits. On the receiving side, the device checks each byte to make sure that it has an even number of set bits. If it finds an odd number of set bits, the receiver knows there was an error during transmission.

Cyclic redundancy check

It is a method of detecting errors during data transmission. The CRC was invented by W. Wesley Peterson in 1961. CRC is based on binary division. In this method, some redundant bits are appended to the end of digital data, that has to be sent.

The message to be transmitted are divided into predetermined lengths that are divided by a fixed divisor. According to the calculation, the remainder number is appended at the end of message and sent with the message. When the message is received, the computer recalculates the remainder and compares it to the transmitted remainder. If the numbers do not match, an error is detected.

Checksum

Checksum is a error detection method based on the concept of redundancy. In checksum error detection method, checksum is transmitted along with every block of data bytes.
To obtain checksum we have to do following steps:

Sender:

1. Divide the data into k parts each of n bits.
2. Add all the k parts.
3. Final result is complemented to make checksum.

Then the checksum is appended at the end of data to be sent.

Receiver:

1. After data is received, the receiver will divide data into k parts each of n bits.
2. Add all the k parts.
3. Final result is complemented.

After complementing the final result, if receiver gets all 0s then data is accepted, otherwise data is rejected.