Question

Suppose we want to transmit the message 11001001 and protect it from errors using the CRC polynomial x³+ 1. (a) Use polynomial long division to determine the message that should be transmitted. (b) Suppose the leftmost bit of the message is inverted due to noise on thetransmission link. What is the result of the receiver’s CRC calculation? How does thereceiver know that an error has occurred?

Answer 1

To protect data using CRC, one appends a check value to the original message derived from polynomial long division. When an error like a bit inversion occurs, the remainder of the division at the receiver's end will not be zero, indicating an error.

Step-by-step explanation:

a) The process of ensuring the integrity of the transmitted data using Cyclic Redundancy Check (CRC) involves appending a check value to the message, which is derived from the remainder of polynomial division of the message by a given CRC polynomial. In this case, the CRC polynomial is x³+1; this corresponds to the binary 1001 (x³ is '1', x² and x are '0's because they are missing, and the constant term is '1'). We append three zeros to the original message (because our CRC polynomial is of order 3), making it 11001001000.

b) Next, we perform polynomial division, treating the binary numbers as polynomials, with 1 and 0 representing if a term of a specific degree is present or not. For the message 11001001000 and the polynomial 1001, the long division gives us a remainder which is the CRC check value that gets appended to the original message. As such, the transmitted message includes both the original message and the CRC check value.

c) If an error occurs during transmission, such as the leftmost bit being inverted, the receiver will perform the same division with the received message and the CRC polynomial. If there is no error, the remainder of this division should be zero. If the remainder is not zero, the receiver knows there has been an error. An inverted bit will result in a non-zero remainder, thus revealing the error.

Answer 2

The transmitted message, after applying the CRC polynomial x³ + 1, is 11001001011. If the leftmost bit is inverted during transmission, the receiver's CRC calculation will detect an error, and the receiver will know that an error has occurred.

Step-by-step explanation:

In the polynomial long division, the given message 11001001 is divided by the CRC polynomial x³ + 1. The division results in a quotient of 11001 and a remainder of 011, which is appended to the original message. Therefore, the transmitted message becomes 11001001011.

Now, if the leftmost bit is inverted due to noise, the receiver recalculates the CRC using the same polynomial division process. If there is no error, the remainder should be 000. However, with the inverted leftmost bit, the remainder will be 111, indicating an error in the received message.

CRC calculations are designed to detect errors efficiently. The receiver can compare the calculated CRC remainder with the expected value (000) and recognize any discrepancies as an indication of an error. In this case, the receiver would identify the non-zero remainder and conclude that the message has been corrupted during transmission. Error detection mechanisms like CRC are crucial in ensuring the integrity of transmitted data in communication systems.