How to Generate a CRC at the Sender Side

TL;DR

Generate a CRC by appending L minus one zeros to the original message, where L is the divisor length, then divide the extended message using exclusive OR operations. The remainder is the CRC, which replaces the appended zeros in the transmitted data. For message 100100 and divisor 1101, the CRC is 001, producing transmitted data 100100001.

Transcript

Hello everyone. Welcome back to the next lecture in the computer network series. And we are now in the last error detection technique, the cyclic redundancy check, CRC. In part one, we will be focusing on the sender side, that is the CRC generation. Let's start the session with the outcomes. What we are going to learn in today's session? In today... Read More

Key Insights

• CRC is the final error-detection method presented after VRC, LRC, and checksum. It generates redundant bits that are appended to the original message, enabling the receiver to determine whether an error occurred during transmission.
• The divisor is determined by protocols mutually agreed upon by the sender and receiver. Both sides therefore know the same divisor, allowing the sender to generate the CRC and the receiver to verify it.
• The first CRC generation step is finding the divisor length and naming it L. The divisor length determines how many temporary zeros must be appended and how many bits the final CRC remainder must contain.
• The number of temporary zeros appended to the message is L minus one. These zeros are required to perform the division operation, but they are not themselves the CRC and are later replaced by the calculated remainder.
• CRC binary division uses exclusive OR instead of ordinary subtraction. Exclusive OR produces zero when the two input bits are the same and one when the input bits are different.
• The remainder from the binary division is the CRC. Although the operation also produces a quotient, the sender uses the remainder, whose length must equal L minus one, as the redundant code appended to the message.
• The CRC for message 100100 with divisor 1101 is 001. Since the divisor contains four bits, three zeros are appended before division, and the resulting three-bit remainder becomes the CRC.
• A polynomial divisor can be converted into binary by recording one for every power that appears and zero for every missing power. A constant term corresponds to the coefficient for the zero power and is represented by one.

Questions & Answers

Q: How do you generate a CRC at the sender side?

To generate a CRC, first find the length of the divisor and call it L. Append L minus one zeros to the original message, then perform binary division using exclusive OR operations. The division produces a quotient and a remainder. The remainder is the CRC, and it is appended to the original message to form the data that the sender transmits.

Q: Why are L minus one zeros appended before CRC division?

L minus one zeros are appended to create the extended message needed for the binary division operation, where L is the number of bits in the divisor. These temporary zeros are not the CRC. After division, the L minus one-bit remainder becomes the actual CRC and is appended to the original message as the redundant portion of the transmitted data.

Q: How is exclusive OR used in CRC binary division?

CRC binary division applies exclusive OR when the divisor is aligned with the current message bits. For each aligned pair, equal inputs produce zero, so zero with zero and one with one both yield zero. Different inputs produce one. After each exclusive OR operation, the next message bit is brought down and the division process continues.

Q: What is the CRC for message 100100 and divisor 1101?

The CRC is 001. The divisor 1101 contains four bits, so L equals four and three zeros are appended to message 100100 before division. Performing binary division with exclusive OR produces the three-bit remainder 001. This remainder is appended to the original message, making the complete transmitted data sequence 100100001.

Q: What data is transmitted after a CRC is calculated?

The sender transmits the original message followed by the calculated CRC remainder. In the worked example, the original data block is 100100 and the remainder obtained with divisor 1101 is 001. Appending that CRC to the data block produces 100100001, consisting of the original data part followed by the three-bit CRC part.

Q: How is the divisor chosen for CRC generation?

The divisor is decided by the protocols mutually agreed upon by the sender and receiver. As a result, both sides know the divisor. The sender uses it to calculate and append the CRC, while the receiver uses the same divisor to verify the received data and determine whether an error is present.

Q: How do you convert a polynomial divisor into binary?

Write one for each power of x that appears in the polynomial and zero for each missing power, starting from the highest listed power and continuing through the zero power. For example, the transcript maps x power seven plus x power five plus x square plus x plus one by marking present and absent powers in order. A constant term contributes one at the zero-power position.

Q: What are the four error-detection methods discussed?

The four error-detection methods identified are VRC, LRC, checksum, and cyclic redundancy check. VRC, LRC, and checksum were discussed in previous lectures, while CRC is presented as the final method. Each technique appends redundant bits to a message, and those bits enable the receiver to determine whether the received transmission contains an error.

Summary & Key Takeaways

• CRC is one of four error-detection methods discussed alongside VRC, LRC, and checksum. Like the other methods, it adds redundant bits to a message so the receiver can determine whether an error occurred. In CRC, these redundant bits are specifically called the CRC and are generated by the sender.

• Sender-side CRC generation follows four main steps. Determine the divisor length L, append L minus one zeros to the original message, perform binary division using exclusive OR, and take the resulting remainder as the CRC. The CRC must contain L minus one bits before being appended to the original message.

• For data block 100100 and divisor 1101, the divisor length is four, so three zeros are initially appended. Binary division of the extended message produces the remainder 001. This remainder becomes the CRC, and appending it to the original message creates the transmitted data sequence 100100001.