Cyclic Redundancy Check (CRC)

Cyclic Redundancy Check (CRC) is an error detection technique used in the data link layer of computer networks to detect errors in data transmission. It involves adding a short sequence of bits, called the CRC or checksum, to the data at the transmitter end. The receiver then calculates the checksum and compares it to the one sent by the transmitter. If the two checksums match, the receiver knows that the data was transmitted without errors. Otherwise, an error is detected, and the receiver requests the retransmission of the data.

CRC Generator and Checker-

To generate a CRC, you can use the following steps:

1. Choose a generator polynomial, which is a binary number that will be used to compute the CRC. The degree of the polynomial determines the number of bits in the CRC.
2. Append n bits (where n is the degree of the generator polynomial) of 0s to the end of the message to be transmitted.
3. Divide the message (including the appended 0s) by the generator polynomial, using binary division. Discard the quotient and keep the remainder, which is the CRC.
4. Append the CRC to the original message and transmit the resulting codeword.

To check the received message for errors:

• Append n bits of 0s to the received message.
• Divide the received message (including the appended 0s) by the generator polynomial, using binary division. If the remainder is 0, then the message is error-free; otherwise, there is an error.
• If there is an error, the receiver can request the sender to retransmit the message.

Here is an example of generating a 4-bit CRC for the message “10110011“:

• Choose a generator polynomial: G(x) = x⁴ + x + 1 (represented in binary as 10011).
• Append 4 bits of 0s to the message: 10110011000.
• Divide the message by the generator polynomial:

• The remainder is 0100, so the CRC is 0100.
• Append the CRC to the original message to form the codeword:101100110100.

To check the received codeword for errors:

1. • Append 4 bits of 0s to the received message: 101100110100
   • Divide the received message by the generator polynomial:

• The remainder we get from this division is 0, which means that there is no error in the data block
• If the remainder is not 0, so there is an error. The receiver can request the sender to retransmit the message.