Question

Assume that CRC is used for error detection and the generator polynomial is x^5+x^3+x+1. The following message needs to be transmitted: 1101001100100111.

(a) What is the bit stream that is actually transmitted?

(b)Now assume that there is an error and the 5th bit from the left is converted due to the error. How does the receiver know that it received an erroneous message?

Answer 1

The CRC (Cyclic Redundancy Check) error detection, helps to detect whether their is any error in the transmitted message or not, if there is any error in the message then the remainder will not be zero on the receiver side otherwise it will be zero, it will only give the answer in yes or no (that is whether error is present or not).

(a.) In CRC first we convert the CRC polynomial into binary bits

=> x⁵ + x³ + x + 1 can be written as 1.x⁵ + 0.x⁴ + 1.x³ + 0.x² + 1.x¹ + 1

=> Binary format of CRC = 101011

Now next we append (n-1) 0's in the message where n is the number of CRC bits, since number of CRC bits is 6 therefore we will add 5 0's at the end of the message

=> The message will become 110100110010011100000

Now we take the XOR of CRC with the message as follows:-

Since we get the remainder as 11100, therefore we will update the last append 5 0's with 11100, and send it to the receiver along with the CRC bits.

Therefore the transmitted bit stream will be 110100110010011111100

(b.) According to the question the 5th bit from the left side has the error that is let it has been changed from 0 to 1 during transmission, therefore the message that the receiver received is 110110110010011111100

Now receiver will again take the XOR of CRC bits with the received bit stream, and if remainder is non zero then there is error in the message.

Clearly we can see that we get the remainder 10 which is non zero, which means that there is an error in the transmitted message.