How to understand the CRC Algorithm from the CAN specification?

Question

I am trying to understand how the cyclic redundancy check (CRC) algorithm from the Controller Area Network (CAN) specification works. Here is the pseudocode.

CRC_RG = 0; // initialize shift register REPEAT CRCNXT = NXTBIT EXOR CRC_RG(14); CRC_RG(14:1) = CRC_RG(13:0); // shift left by CRC_RG(0) = 0; // 1 position IF CRCNXT THEN CRC_RG(14:0) = CRC_RG(14:0) EXOR (4599hex); ENDIF UNTIL (CRC SEQUENCE starts or there is an ERROR condition)

I do understand the standard algorithms but not the CAN algorithm. I have calculated it by hand and programmed it and it works fine. I just don't understand why/how it works.

Answer 1

CRC(x) is remainder of polynomial division of x by some fixed polynomial. Here bits of x, as well as bits of result, represents polynomial with binary coefficients, f.e. 0b101 may represent polynomial 1*x^2 + 0*x + 1.

So, the algorithm you have cited, is the most straightforward one - if q(x) = p(x) mod f(x), then p(x)*x mod f(x) is either just q(x)*x (if it doesn't contain x^N where N is order of f(x) polynomial), or q(x)*x - x^N + (x^N mod f(x)). As you may note, the last sum component is some fixed polynomial for given f(x).

So, each step of this cycle do the following:

• shift result by 1 bit left - equivalent to multiplication by x
• if result contains x^N then xor result by x^N mod f(x)

Oh, well, there are some more details. Please read a painless guide to CRC error detection algorithms for real explanation.