What does this CRC implementation mean by having a seed value?

Question

I am trying to implement a CRC algorithm in Verilog for the SENT sensor protocol.

In a document put out by the SAE, they say their CRC uses the generator polynomial x^4 + x^3 + x^2 + 1 and a seed value of 0101. I understand the basic concept of calculating a CRC using XOR division and saving the remainder, but everytime I try to compute a CRC I get the wrong answer.

I know this because in the same document they have a list of examples with data bits and the corresponding checksum.

For example, the series of hex values x"73E73E" has checksum 15 and the series x"748748" has checksum 3. Is there anyone who can arrive at these values using the information above? If so, how did you do it?

This is a couple of sentences copied from the document: "The CRC checksum can be implemented as a series of shift left by 4 (multiply by 16) followed by a 256 element array lookup. The checksum is determined by using all data nibbles in sequence and then checksumming the result with an extra zero value."

Solution 1

Take a look at RevEng, which can determine the CRC parameters from examples (it would need more examples than you have provided).

Solution 2

The seed is simply the initial value of your crc calculation. It is usual to have a non-zero seed to avoid the crc result being zero in the case of all zero data

Solution 3

I just had to find out the same thing. I was checking a CRC implementation for the CRC algorithm which was cryptic albeit working. So I wanted to get the "normal" CRC algorithm to give me the same numbers so I could refactor without problems.

For the numbers you gave I get 0x73E73E => 12, 0x748748 => 3.

As you can read in Koopman the seed value "Prevents all-zero data word from resulting in all-zero check sequence".

I wrote my standard implementation using the algorithm from Wikipedia in Python:

def nCRCcalc( poly, data, crc, n):
    crctemp = ( data << n ) | crc

    # data width assumed to be 32 bits
    shift = 32

    while shift > n:
        shift = shift - 1
        mask = 1 << shift
        if mask & crctemp:
            crctemp = crctemp ^ ( poly << (shift - n) )

    return crctemp

Poly is the polynomial, data is the data, crc is the seed value and n is the number of bits. So In this case Polynomial is 29, crc is 5 and n is 4.

You might need to reverse nibble order, depending on in which format you receive your data. Also this is obviously not the implementation with the table, just for checking.

Comments

[stardust]

Why sometimes an initial reminder value 0 is used, e.g. for CRC-16/XMODEM?