Fast crc8

[kevinkk525]

I don't really know how to choose another polynome for 8 bits
I thought this could be it: x^8+ x^6 + x^4 + x^3 + 1

But I don't see how I get to the polynome byte from that

[Roberthh]

x^8+ x^6 + x^4 + x^3 + 1 = (2^8) + 2^6 + 2^4 + 2^3 + 2^0 = 0b01011001

The x^8 = 2^8 bit is ignored.

[kevinkk525]

Thanks, generated a new table with this! looks good.

[kevinkk525]

How do I get to crc4 from this:

Code: Select all

def crc8(*args, initial_value=0):
    _sum = initial_value
    table = _table
    for arg in args:
        for byte in arg:
            _sum = table[_sum ^ byte]
    return _sum

Since you created a script for the tables, you probably have an example code too?

[Roberthh]

Nibble-wise, like here:

Code: Select all

    for v in msg:
        nibble = (v >> 4) & 0xf
        crc = crc4_tab[crc] ^ nibble

        nibble = v & 0xf
        crc = crc4_tab[crc] ^ nibble
    crc = crc4_tab[crc]  # padding nibble

Obviously there is not need for the interim store to the variable nibble. it's just for clarity. This has a post-processing step, which is sometimes requested, sometimes not. Some use cases have also a specific start value for the crc. To know that, you need a description and a handful of test data pairs (data + crc).

[kevinkk525]

Thanks a lot! Interestingly this crc4 algorithm needs twice the time of my crc8 lookup table algorithm
On a 400Byte bytearray crc8 takes 2.5ms, this crc4 takes 6ms.

[Roberthh]

That's because it has two CRC steps per byte, and the nibble extraction. But usually the messages are shorter.

Edit: As per general use:
4 bit CRC is good for up to four nibbles = 2 bytes
6 bit CRC is good for up to eleven 6 bit data chunks
8 bit CRC is good for up to 64 bytes

n bit CRC is good for messages up to (2^(n + 1) - 1) bits.

[kevinkk525]

yeah the message is 4bit vs 8bit but if it takes longer, it won't help the transmission speed. Sending an additional byte takes 80us so it's faster to just send more.

[Roberthh]

See my edit in the previous post about suitable message sizes vs. CRC type.

[kevinkk525]

oh well.. then I would need a crc16 for up to 500Bytes? ... I just want some fast way to recognize garbae on my uart. Shouldn't crc8 be enough for that? Or is it recommended to use crc16?