CRC实现特定多项式。如何多项式涉及到在代码中使用的多项式？

Question

我有以下CRC功能：

#define CRC8INIT    0x00
#define CRC8POLY    0x18              //0X18 = X^8+X^5+X^4+X^0

// ----------------------------------------------------------------------------

uint8_t crc8 (uint8_t *data, uint16_t number_of_bytes_in_data)
{
    uint8_t  crc;
    uint16_t loop_count;
    uint8_t  bit_counter;
    uint8_t  b;
    uint8_t  feedback_bit;

    crc = CRC8INIT;

    for (loop_count = 0; loop_count != number_of_bytes_in_data; loop_count++) {
        b = data[loop_count];
        bit_counter = 8;

        do {
            feedback_bit = (crc ^ b) & 0x01;

            if (feedback_bit == 0x01) {
                crc = crc ^ CRC8POLY;
            }

            crc = (crc >> 1) & 0x7F;

            if (feedback_bit == 0x01) {
                crc = crc | 0x80;
            }

            b = b >> 1;
            bit_counter--;

        } while (bit_counter > 0);
    }

    return crc;
}

如何为0x18涉及多项式X ^ 8 + X ^ 5 + X ^ 4 + X ^ 0？

X ^ 8 + X ^ 5 + X ^ 4 + X ^ 0 = 100110001

为0x18 = 00011000

如果我定义为CRC8POLY代替0xEA（我已经看到了这）是什么，是否会代表什么多项式？

Answer 1

如何为0x18涉及多项式X ^ 8 + X ^ 5 + X ^ 4 + X ^ 0？

由于代码是右每个字节的移位CRC，“最显著位”是0x119位0的位而不是7.聚需要从100110001反转为100011001，这是0x119，右移位后，第0位被移位了，所以量0x118可以用来代替。代码使用第二if语句或（0x100的）>> 1 == 0x80的如果反馈位是1作为替代方案，因为feedback_bit是0或1，则（0-feeback_bit）可以被用作掩模（假设补数学）为聚而不是使用if语句。

typedef unsigned char uint8_t;
typedef unsigned short uint16_t;
#define CRC8INIT 0x00
#define CRC8POLY 0x8c   // 0x119 >> 1

uint8_t crc8 (uint8_t *data, uint16_t number_of_bytes_in_data)
{
    uint8_t  crc;
    uint16_t loop_count;
    uint8_t  bit_counter;
    uint8_t  b;
    uint8_t  feedback_bit;

    crc = CRC8INIT;

    for (loop_count = 0; loop_count != number_of_bytes_in_data; loop_count++) {
        b = data[loop_count];
        bit_counter = 8;
        do {
            feedback_bit = (crc ^ b) & 0x01;
            crc = (crc >> 1) ^ ((0-feedback_bit) & CRC8POLY);
            b = b >> 1;
            bit_counter--;
        } while (bit_counter > 0);
    }

    return crc;
}

Answer 2

这CRC代码编写，而奇怪的是，这里的多项式在两个不同的地方应用，打破了位。也就是说，在crc = crc ^ CRCPOLY和有条件crc = crc | 0x80。它通常会写更多像这样的：

unsigned crc8(unsigned char const *dat, size_t len) {
    unsigned crc = 0;
    for (size_t i = 0; i < len; i++) {
        crc ^= dat[i];
        for (int k = 0; k < 8; k++)
            crc = crc & 1 ? (crc >> 1) ^ 0x8c : crc >> 1;
    }
    return crc;
}

其中0x8c是多项式逆转，而X8项。

Answer 3

参照Wiki article on CRC，它是作为在达拉斯1线芯片中使用CRC8实现。请注意，polinomial可在常规表示，逆转，互惠和反倒数表示（见Polynomial representations）。看来，这是相反的相互代表与最高位省略。