How to calculate the CRC

An integral part of transferring data over a network is ensuring data reliability and minimizing transmission errors. This is carried out using mechanisms such as the following:

• Cyclic Redundancy Check (CRC)

• Vertical Redundancy Check (VRC)

• Checksums

Among these, CRC is a powerful and easy-to-implement mechanism that ensures that data packets aren't corrupted and their integrity is maintained.

Methodology

Ensuring data reliability using a CRC involves the following:

1. Generating a CRC.

2. Appending the CRC to a data packet.

3. Forwarding the modified data packet.

4. Verifying the CRC at the destination.

The data packet can be deemed free from transmission errors if the CRC is successfully verified.

The generation and verification of the CRC function are based on a mathematical operation known as modulo-2 polynomial division. The modulo-2 polynomial division is similar to regular division that we perform with decimal numbers. However, we take the XOR of the two digits instead of subtracting it at every step.

An example of a modulo-2 polynomial division is illustrated below.

In the case of CRC, the divisorThe divisor is the number by which another number is to be divided. is a polynomial upon which the sender and the receiver of the data packet agree. It's calculated by treating the polynomial as having binary coefficients, like in the following:

Generating the CRC

Generating the CRC requires the following steps:

1. Find the length of the divisor $N$.

2. Append $N-1$ bits containing 0 to the end of the data packet.

3. Perform this modulo-2 polynomial division: $\frac{\text{modified data packet}}{\text{divisor}}$

4. The remainder of the division is the CRC.

5. Send the original data packet after appending it with the CRC.

Verifying the CRC

Verifying the CRC once a data packet is received requires the following steps:

1. Perform this modulo-2 polynomial division: $\frac{\text{received data packet}}{\text{divisor}}$

2. Calculate the remainder. Check if the remainder is zero.

   1. If the remainder is zero, the data packet suffered no transmission error.

   2. If the remainder is non-zero, the data packet suffered some transmission error.

Example

Suppose we'd like to send the data packet $100100$ and ensure data integrity using CRC. We agree with the receiver to use the divisor $1101$.

Before sending out the data packet, we need to generate its CRC using the previously detailed steps. It results in the following calculation:

After the calculation above, the original data packet is now appended with the remainder $001$ calculated above. The modified data packet is now equal to$100100001$ and is sent to the receiver.

The receiver takes this data packet and verifies its CRC to ensure the packet suffered zero transmission errors using the steps mentioned above. This results in the following calculation:

As the remainder is zero, the packet was indeed sent reliably.