Error Detection with Parity Check and Checksum

Errors in data transmission in one or multiple bits are unavoidable. To detect or correct errors, we need to send extra (redundant) bits with data.

Let us consider following probabilities -

Pb : Probability that a bit is received in error; also known as the bit error rate (BER)

P1 : Probability that a frame arrives with no bit errors

P2 : Probability that, with an error-detecting algorithm in use, a frame arrives with one or more undetected errors

P3 : Probability that, with an error-detecting algorithm in use, a frame arrives with one or more detected bit errors but no undetected bit errors

When there is no detection algorithm then P3 = 0 And

         P1 = (1 - Pb)f
         P2 = (1 - P1)

f is the number of bits per frame

Error Detection with Parity Check

Parity Check

A simple parity-check code is a single-bit error-detecting code in which n = k + 1 with dmn = 2.

 Encoder & decoder for simple parity-check code -

A simple parity-check code can detect an odd number of errors.

Two - dimensional parity-check code -

Deriving row and column parities

Single and double bits errors in two-dimensional parity check code -

Checksum

The checksum is used in the Internet by several protocols althrough not at the data link layer.

Let us consider that we have a list of five 4-bit numbers that we want to send to a destination. Along with these numbers i.e. (7, 11, 12, 0,6), we shall send also their sum i.e. (7, 11, 12, 0, 6, 36). At the receiving end the sum will be checked.

To make the process simpler, we can send the negative (complement) of the sum, called the checksum. In this case, we send (7, 11, 12, 0, 6, -36). The receiver can add all the numbers received (including the checksum). If the result is 0, it assumes no error; otherwise, there is an error.

Internet Checksum

At the sender's site : 

• The message is divided into 16-bit words.

• The value of the checksum word is set to 0

• All words including the checksum are added using one's complement addition

• The sum is complemented and becomes the checksum.

• The checksum is sent with the data

At the receiver's site :

• The message (including checksum) is divided into 16-bit words.
• All words are added using one's complement addition
• The sum is complemented and becomes the new checksum.
• If the value of checksum is 0, the message is accepted; otherwise, it is rejected.