2
我正在嘗試編寫一個基於表的CRC例程，用於接收Mode S上行鏈路詢問器消息。在下行鏈路端，CRC是基於多項式P = 0x1FFF409的24位CRC。到目前爲止，這麼好 - 我寫了一個基於表的實現，遵循通常的字節一致的規則，並且工作正常。計算多項式除法結果以及餘數（CRC）
在上行鏈路上，事情變得很奇怪。的protocol specification說，計算目標上行鏈路地址是通過找到：
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）多項式除法運算的結果而不是餘數。其餘部分被有效丟棄。目標地址編碼與所傳送的校驗和，使得所述接收飛機可以通過將其與它的地址比較驗證校驗和。
這是偉大的，一切，我從上面的跟隨按位實現。請忽略多項式和校驗和的怪異換檔，這已經從this Pascal implementation那兒剽竊其假定32位寄存器，並基於這樣的假設的優化（第15頁）。實際上，消息和校驗和是一個單一的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
以上當然比在軟件糖蜜慢的，我真的希望能夠建立一個查找表，將允許接收到的地址的類似字節在-A-時間計算，或按摩剩下的部分（很快計算出來）就是一個商。
TL; DR： 給定一個消息，編碼多項式，其餘（由正常的CRC方法計算），是有更快的方式通過使用以獲得多項式除法運算的商數比移位寄存器做多項式除法「longhand」？