Question

Suppose we want to transmit the message 11001001 and protect it from errors using the CRC polynomial \(x^{3}+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 the transmission link. What is the result of the receiver's CRC calculation? How does the receiver know that an error has occurred?

Short answer

Transmit 11001001100. An inverted bit results in a non-zero remainder, indicating an error.

Step-by-step solution

Convert Binary Message to Polynomial

Convert the message 11001001 into its corresponding polynomial. Each binary digit represents a coefficient of the polynomial.The message 11001001 corresponds to the polynomial:\[ x^7 + x^6 + x^3 + 1 \]

Determine the CRC Divisor Polynomial

The CRC polynomial given is \( x^3 + 1 \).

Append Zeroes to the Original Message

Append three zeroes (since the highest degree of the divisor polynomial is 3) to the original message to prepare for division. The new message is 11001001000.

Perform Polynomial Long Division

Divide the polynomial corresponding to 11001001000 by \( x^3 + 1 \) using polynomial long division. This determines the remainder.1. Divide highest degree terms: \( x^7 / x^3 = x^4 \)2. Subtract \((x^4 \times (x^3 + 1))\) from the polynomial.3. Repeat the process with the next highest degree result.After completing the division, we find the remainder.

Find the Remainder

The remainder after the polynomial long division is 100. This remainder is the CRC checksum.

Form the Transmitted Message

Combine the original message with the remainder. The data to be transmitted is 11001001100.

Simulate an Error

Invert the leftmost bit of the transmitted message due to noise. The corrupted message is now 01001001100.

Receiver's CRC Calculation

The receiver performs the same polynomial division (01001001100 divided by \( x^3 + 1 \)). If the message is error-free, the remainder should be zero.After division, the receiver finds a non-zero remainder, indicating an error.

Error Detection

The receiver knows an error has occurred because the remainder is non-zero after performing polynomial division on the received corrupted message.

Key concepts

Cyclic Redundancy Check

Cyclic Redundancy Check (CRC) is a popular method for detecting errors in digital data. It’s widely used in networking and storage devices. The primary idea is to treat the digital message as a polynomial. To detect errors, we append a CRC checksum to the original message. This checksum is derived using a predefined CRC polynomial.
By dividing the message polynomial by the CRC polynomial, we obtain a remainder. This remainder becomes the CRC checksum. When the message is transmitted, the receiver performs the same division. If the remainder matches the transmitted CRC checksum, then no errors are detected. If there is a mismatch, it indicates some data corruption during transmission.

Polynomial Long Division

Polynomial Long Division is a mathematical technique used to perform the division of polynomials. In the context of CRC, we use polynomial long division to divide the appended message by the CRC polynomial to find the checksum.
To divide a polynomial, we follow these steps:

• Identify the highest degree terms of both the message and the CRC polynomials.
• Divide the leading term of the message by the leading term of the CRC polynomial and multiply the result by the entire CRC polynomial.
• Subtract this product from the original message, resulting in a new polynomial.
• Repeat this process with the new polynomial until the degree of the remainder is less than the degree of the CRC polynomial.

The final remainder after this division is the CRC checksum.

Error Detection in Networks

Error Detection in Networks is crucial to ensure data integrity during transmission. CRC is a commonly used error detection method due to its effectiveness in identifying burst errors and its lightweight computational requirements.
When a message is transmitted, it can get corrupted due to noise or other interference. To detect errors, the sender appends a CRC checksum to the message. Upon receiving the message, the receiver performs the same polynomial division. If the calculated CRC remainder does not match the received checksum, the receiver concludes that an error has occurred.
This mechanism significantly improves the reliability of data transmission in various network protocols and storage systems.

Data Transmission Integrity

Data Transmission Integrity ensures that data sent from a sender arrives at the receiver without errors. CRC plays a vital role in maintaining this integrity. By appending a CRC checksum to the data, we can detect and sometimes even correct data errors.
The process involves several steps:

• The sender generates a CRC checksum from the original data.
• This checksum is appended to the data before transmission.
• During transmission, any noise or interference can introduce errors into the data.
• The receiver recalculates the CRC checksum from the received data.
• If the checksum matches the one sent with the data, the transmission is validated. If not, the receiver knows an error occurred.

This error detection method is efficient and helps ensure robust communication, especially in digital networks and storage systems.