Error Detecting Codes A simple way to detect errors when a bit string is transmi

Question

Error Detecting Codes

A simple way to detect errors when a bit string is transmitted is to add a parity check bit at the end of the string. If the bit string contains an even number of 1s we put a 0 at the end of the string. If the bit string contains an odd number of 1s we put a 1 at the end of the string. In other words, we encode the message x1x2 . . . xn as x1x2 . . . xnxn+1, where the parity check bit xn+1 is given by

xn+1 = (x1 + x2 + . . . + xn) mod 2.

Adding the parity check bit guarantees that the number of 1s in the extended string must be even. It is easy to see that the codewords in this code are bit strings with an even number of 1s.

Note that when a parity check bit is added to a bit string, if a single error is made in the transmission of a codeword, the total number of 1s will be odd. Consequently, this error can be detected. However, if two errors are made, these errors cannot be detected, since the total number of 1s in the extended string with two errors will still be even. In general, any odd number of errors can be detected, while an even number of errors cannot be detected.

Could the following bit strings have been received correctly if the last bit is a parity bit? a) 1000011 b) 111111000 c) 10101010101 d) 110111011100

Explanation / Answer

Since the string 1000011, contains an odd number of 1s, it cannot be a valid codeword (and must, therefore, contain an odd number of errors). On the other hand, the string 10111101, 111111000, 10101010101 and 110111011100 contains an even number of 1s. Hence it is either a valid codeword or contains an even number of errors.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.