0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What is NXTBIT initialised to? $\endgroup$ – Peter Taylor Jun 17 at 11:53
  • $\begingroup$ @PeterTaylor NXTBIT is a function reading next bit of input data $\endgroup$ – Bulat Jun 17 at 12:41
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have read the painless guide but you explained it better. I understand it now. Thank you. $\endgroup$ – Max Jun 17 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.