How to verify a CRC in receiver terminal?

Question

I am studying some computer knowledge by myself. I find a puzzle when I study the CRC. Now I know how to calculate a CRC value of a message, but I wonder how to verify it at the receiver when the rules require Refin.

Here is an example.

The message I want to check is 00010011.
The polynomial is 10011.
Init: 0x00
Refin: True
Reout: True
Xorout: 0x00

After calculation, the CRC value is 0100.

So the actual message to be delivered is 000100110100.

The receiver needs to verify the message with the CRC. How does it do this? There are two ways. First, it can compute the CRC via binary division, and compare the calculated and received CRC values. Second, it can directly append the CRC value to the data. The receiver then calculates using polynomial division and should get a zero remainder.

I have some questions here.

Probably because of Refin and Refout, I can not verify it directly using the polynomial division — it has non-zero remainder. If I want to obey the same rules to verify the message + CRC, 000100110100, it only has 12 bits, not enough for two bytes, so I can't complete the Refin. I tried to append zeros on the MSB side as well as the LSB side， but in the division process I still can not get all zeros remainder.

How does the receiver verify the CRC?

Answer 1

You know the message on the wire ends with the CRC. Get the received message, without CRC, then compute its CRC using precisely the same algorithm as the transmitter used.

Then compare the CRC you just computed with the one you received.

If they differ the message is corrupt -- has errors introduced by the comm channel from sender to receiver.

For what it's worth, messages sent over commonly used internet protocols have this sort of error detection thing built in. CRC is most useful over old-school analog synchronous serial communication protocols. And, in the 21st century you might be wise to use some sort of forward error correction code (FECC) protocol instead of a dirt-simple go- no go- protocol like CRC.

You can read about FECC.

Answer 2

All Refin and Refout tell you is how the bits in what is transmitted and received are turned into polynomials for the CRC calculation. In your example, the message is 00010011 as stored in a byte. Refin true tells you that the message polynomial is then 11001000, or x⁷+x⁶+x³. Your CRC polynomial is 10011, or x⁴+x+1. Upon dividing the message polynomial times x⁴ by the CRC polynomial, you get x, or 0010. That is appended to the message, or really added to the message times x⁴, to get x¹¹+x¹⁰+x⁷+x, or 110010000010.

Now Refout true means that the bits are reflected in the output bytes. So you get 00010011, ....0100, where values of the bits where there are periods are not part of this message + CRC. They may be filled in by a subsequent message.

The key is that when the receiver gets 00010011, ....0100, it reconstructs the polynomial version of the message + CRC by pulling bits from the least significant to most significant from each byte, resulting in: 110010000010..... To verify the CRC using polynomial division, you simply divide that by x⁴+x+1. You get:

110010000010
10011
------------
 10100000010
 10011
 -----------
   111000010
   10011
   ---------
    11110010
    10011
    --------
     1101010
     10011
     -------
      100110
      10011
      ------
        0000

The zero remainder indicates that the message + CRC was (most likely) transmitted faithfully.

Or you can save yourself the hassle, and simply use your first suggested approach, which is to repeat the CRC calculation on just the message and compare the result to the appended CRC.