Question

Suppose we want to transmit the message 1011001001001011 and protect it from errors using the CRC-8 polynomial \(x^{8}+x^{2}+x^{1}+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

The transmitted message should include the original message followed by the CRC remainder. If the leftmost bit is inverted, the receiver's CRC calculation will be non-zero, indicating an error.

Step-by-step solution

- Convert the Polynomial to Binary

Convert the given CRC-8 polynomial to binary. For the polynomial \(x^8 + x^2 + x^1 + 1\), this can be represented as 100000111 in binary.

- Append Zeros to the Message

Append 8 zeros to the end of the original message to make room for the CRC. The message 1011001001001011 becomes 101100100100101100000000 after appending 8 zeros.

- Polynomial Long Division

Perform polynomial long division of the augmented message (101100100100101100000000) by the binary polynomial 100000111. This will yield the remainder which should be added to the original message to form the transmitted message. Steps for division:1. XOR the first 9 bits of the message with the polynomial (100000111).2. Shift to the left and bring down the next bit of the augmented message.3. Repeat the process until all bits are brought down.4. The remaining bits will be the remainder.

- Form the Transmitted Message

Add the remainder obtained from the polynomial division to the original message (without the appended zeros). This final message is what should be transmitted.

- Check for Errors on Received Message

When the receiver receives the message, it performs the same polynomial long division on the received message. If there are no errors, the result should be zero. If the leftmost bit of the message is inverted, the division result will not be zero, indicating an error.

- Determine Error Detection

Explain that if the receiver's calculated CRC value is non-zero, it indicates an error in the transmission. The receiver knows an error has occurred if the result of the division is not zero.

Key concepts

CRC polynomial

A CRC polynomial is used in error detection to produce a checksum that's attached to the data being transmitted. In this exercise, we use the CRC-8 polynomial, which is expressed as \(x^{8} + x^{2} + x^{1} + 1\). This polynomial is turned into a binary representation before use. Each term corresponds to a power of 2, which can easily be converted into binary. For instance, the term \(x^8\) converts to 1 followed by 8 zeros (100000000). When combined, the polynomial \(x^{8} + x^{2} + x^{1} + 1\) is represented as 100000111.

Polynomial long division

Polynomial long division in CRC is similar to standard long division but done with binary numbers. Here’s how it works:

• Append zeros to the data equal to the degree of the polynomial (in this case, 8 zeros).
• Perform a binary division using XOR operations.
• Slide the divisor (polynomial) to align with the highest bit in the dividend.
• Subtract by XORing the divisor with the aligned digits of the dividend.
• Bring down the next bit of the dividend and repeat until the entire dividend has been processed.

The remainder of this division is the checksum, which is appended to the original data before transmission.

Binary representation

Binary representation is crucial in understanding CRC operations. Each polynomial term is represented by a binary number whose length is determined by the highest degree. To convert \(x^8 + x^2 + x^1 + 1\) to binary:

• Identify powers of x that appear in the polynomial: \(x^8, x^2, x^1, x^0\)
• Set respective positions in a 9-bit binary number to 1 for each term.
• The final binary form is 100000111.

Data is also treated as a binary string. The initial message 1011001001001011 becomes an extended binary sequence when zeros are appended for CRC computation.

Error detection

CRC uses its polynomial properties to detect errors in transmitted messages. Here’s the process:

• The sender processes the original data using the CRC polynomial to generate a checksum.
• The sender appends this checksum to the data before transmission.
• Upon receiving the data, the recipient re-runs the CRC process.
• If the remainder is zero, the data is error-free. If not, an error is detected.

For example, if noise inverts the leftmost bit during transmission:

• The recipient's CRC calculation will yield a non-zero remainder.
• This discrepancy signals an error in the transmission.

Thus, CRC is a powerful tool to check data integrity efficiently.