2

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

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

U' = x^24 * U / G(x)

...其中 U 是接收到的消息，G(x) 是编码多项式 0x1FFF409，导致：

U' = x^24 * m(x) + A(x) + r(x) / G(x)

...其中 m(x) 是原始消息，A(x) 是地址，r(x) 是余数。我想要低阶商 A(x); 例如，GF(2) 多项式除法运算的结果而不是余数。剩余部分被有效地丢弃。目标地址使用传输的校验和进行编码，以便接收飞机可以通过将其与其地址进行比较来验证校验和。

这很棒，而且我有一个从上面开始的按位实现。请忽略多项式和校验和的奇怪移位，这是从这个 Pascal 实现（第 15 页）中抄录的，它假设 32 位寄存器并基于该假设进行优化。实际上，消息和校验和作为单个 56 位传输。

#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

上面当然比软件中的糖蜜要慢，我真的很想能够构建一个查找表，允许对接收到的地址进行类似的一次字节计算，或者按摩剩余部分（快速计算) 成商。

TL;DR：给定一条消息、编码多项式和余数（通过正常的 CRC 方法计算），有没有比使用移位寄存器“速记”进行多项式除法更快的方法来获得多项式除法运算的商?

4

2 回答 2

0

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

于 2015-05-25T23:33:08.360 回答
0

对于 OP 来说为时已晚，但我将其发布给可能会看到此问题的其他人。您可以生成两个表来一次操作一个字节。第一个 256 x 8 位表由被除数（消息）的当前前 8 位索引，8 位值是商。第二个 256 x 32 位表由 8 位商索引，32 位值是 8 位商乘以 25 位多项式的 32 位乘积（因为这是无进位乘法，乘积为 32 位，（x ^7 * x^24 = x^31))，将其异或到被除数的高 32 位，这将使被除数的高 8 位清零。然后循环返回被除数的下 8 位。

现代 X86 cpu 具有无进位乘法指令 PCLMULQDQ，它在 128 位 xmm 寄存器上运行，执行 64 位乘 64 位乘法以产生 128 位乘积（因为它是无进位乘法位 127 始终为 0，所以它实际上是 127位产品）。56 位消息乘以 41 位常数 2^64/G(x) 将产生 96 位乘积，其中高 32 位将是商（不使用低 64 位）。

于 2018-12-19T13:54:19.250 回答