计算多项式除法和余数(CRC)

Question

我试图编写一个基于表的CRC例程，用于接收模式S上行链路询问器消息。在下行链路侧，CRC只是基于多项式p=0x1fff409的24位CRC。到目前为止，一切都很好--我编写了一个基于表的实现，它遵循了通常的每次字节约定，并且运行良好。

然而，在上行方面，事情变得很奇怪。协议规范说，计算目标上行链路地址是通过查找：

#This is the reference bit-shifting implementation. It is slow.
def uplink_bitshift_crc():
    p = 0xfffa0480 #polynomial (0x1FFF409 shifted left 7 bits)
    a = 0x00000000 #rx'ed uplink data (32 bits)
    adr = 0xcc5ee900 #rx'ed checksum (24 bits, shifted left 8 bits)
    ad = 0 #will hold division result low-order bits

    for j in range(56):
        #if MSBit is 1, xor w/poly
        if a & 0x80000000:
            a = a ^ p
        #shift off the top bit of A (we're done with it),
        #and shift in the top bit of adr
        a = ((a << 1) & 0xFFFFFFFF) + ((adr >> 31) & 1)
        #shift off the top bit of adr
        adr = (adr << 1) & 0xFFFFFFFF

        if j > 30:
            #shift ad left 1 bit and shift in the msbit of a
            #this extracts the LS 24bits of the division operation
            #and ignores the remainder at the end
            ad = ad + ((a >> 31) & 1)
            ad = ((ad << 1) & 0xFFFFFFFF)

    #correct the ad
    ad = ad >> 2
    return ad

上面所述的速度当然比软件中的糖蜜慢，我真的希望能够构造一个查找表，允许对接收的地址进行类似的每次字节计算，或者将余数（快速计算）调整为商。

给定一个消息、编码多项式和余数（用常规CRC方法计算），有没有比使用移位寄存器进行多项式“长和”除法更快的方法来获得多项式除法运算的商？

Answer 1

您可以看看PyCRC库，我想这可能会回答您的问题。