モード S アップリンク インテロゲーター メッセージを受信するためのテーブル ベースの CRC ルーチンを作成しようとしています。ダウンリンク側では、CRC は多項式 P=0x1FFF409 に基づく 24 ビット CRC です。これまでのところ、非常にうまくいっています。一度に 1 バイトずつという通常の慣習に従うテーブルベースの実装を作成しましたが、問題なく動作しています。
ただし、アップリンク側では、事態は奇妙になります。プロトコル仕様によると、ターゲット アップリンク アドレスの計算は、次を見つけることによって行われます。
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) 多項式除算演算の結果。残りは実質的に破棄されます。ターゲット アドレスは送信されたチェックサムでエンコードされるため、受信側の航空機はチェックサムをそのアドレスと比較して検証できます。
これは素晴らしいことであり、上記のビット単位の実装があります。多項式とチェックサムの奇妙なシフトは無視してください。これは、 32 ビット レジスタを想定し、その想定に基づいて最適化を行うこの Pascal 実装(15 ページ) から引用したものです。実際には、メッセージとチェックサムは 1 つの 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 メソッドによって計算される) が与えられた場合、シフト レジスタを使用して多項式除算を「手書き」で行うよりも、多項式除算演算の商を取得する高速な方法はありますか? ?