CRC / XOR / Modulo-2 筆算割り算電卓

CRC / XOR / Modulo-2 筆算割り算電卓の使い方

modulo-2 割り算で CRC を計算するには、次の4つの手順に従います.

• 最初の欄に二進メッセージ（データビット）を入力します.
• 2番目の欄に生成多項式を二進ビットで入力します.
• 電卓は (n − 1) 個のゼロビットを付加します.n は生成器の長さです.
• 計算をクリックしてメッセージを XOR し、余りを CRC として読み取ります.

CRC では通常、商は捨てられます.余りが送信前にメッセージに付加されるチェックサムです.

CRC と modulo-2 算術

巡回冗長検査は、メッセージを大きな二進多項式として扱い、合意された生成多項式で割ることで伝送エラーを検出します.割り算は modulo-2（GF(2)）算術で行われ、加算と減算は同一で XOR に等しく、繰り上がりも借りもありません.この割り算の余りが CRC です.受信側がメッセージに CRC を付加したものを同じ生成器で割ると、余り 0 は検出されたエラーがないことを意味します.この電卓はその正確なビット単位の処理を再現します.

modulo-2 CRC 割り算の仕組み

電卓は5つの内部処理で CRC を計算します.

• 生成器のビット数 n に対し、メッセージに (n − 1) 個のゼロビットを付加します.
• 現在の余りの最も左の 1 ビットの下に生成器を位置合わせします.
• それらのビットに生成器を XOR します（借りなしの modulo-2 減算）.
• 次の先頭 1 ビットへ移動し、XOR の位置合わせを繰り返します.
• 残りビットが生成器より少なくなったら止め、それらのビットが CRC です.

商の各ビットは生成器が XOR された場所が 1、それ以外が 0 ですが、CRC では最終的な余りだけが重要です.

CRC 割り算の公式

CRC / XOR / Modulo-2 筆算割り算電卓は GF(2) で CRC = (M(x) · xⁿ⁻¹) mod G(x) を計算します.M(x) はメッセージ、G(x) は n ビットの生成器で、すべての加算は XOR です.送信フレームは M(x)·xⁿ⁻¹ + CRC で、G(x) で割り切れます.受信側では余り 0 が整合性を確認します.

CRC / XOR の例題

これらの例は各手順で XOR する modulo-2 割り算を示します.

例1 — メッセージ 1101、生成器 101

1. 生成器の長さは 3 なので、2 個のゼロを付加: 1101 は 110100 になります.
2. 先頭ビットに 101 を繰り返し XOR: 110100 → 011100 → 001000 → 000010.
3. 最後の 2 ビット 10 が CRC 余りです.

例2 — 減算が XOR である理由

1. modulo-2 では 1 + 1 = 0 で 1 − 1 = 0 なので、加算と減算は同じ操作です.
2. その操作はまさに繰り上がりも借りもないビット単位の XOR です.
3. よって各割り算手順は、現在のビットへの生成器の1回の XOR です.

例3 — 受信側の確認

1. CRC をメッセージに付加し、同じ生成器で割ります.
2. 以前とまったく同じように XOR していきます.
3. 余り 0 はエラーが検出されなかったことを意味します.

生成器の長さは 3 なので、2 個のゼロを付加: 1101 は 110100 になります.
先頭ビットに 101 を繰り返し XOR: 110100 → 011100 → 001000 → 000010.
最後の 2 ビット 10 が CRC 余りです.

modulo-2 では 1 + 1 = 0 で 1 − 1 = 0 なので、加算と減算は同じ操作です.
その操作はまさに繰り上がりも借りもないビット単位の XOR です.
よって各割り算手順は、現在のビットへの生成器の1回の XOR です.

CRC をメッセージに付加し、同じ生成器で割ります.
以前とまったく同じように XOR していきます.
余り 0 はエラーが検出されなかったことを意味します.

CRC の解き方例

生成器 1011 で 10110 の CRC を計算するには？

生成器の長さ 4 なので 3 個のゼロを付加して 10110000 を得て、XOR していきます. 各先頭 1 の下に 1011 を位置合わせして XOR: 10110000 → 00100000 → 連続する XOR の後、最後の 3 ビットが CRC 余りになります.余りを 10110 に付加すると、フレーム全体が 1011 で割り切れます.

なぜ余り 0 はデータが無傷であることを意味する？

送信側は、送信フレームが生成器の倍数になるように CRC を選びました. G(x) の倍数を G(x) で割ると余り 0 です.伝送中にビットが反転すると、通常フレームは倍数でなくなり、受信側の割り算は非ゼロ余りを残してエラーを示します.

CRC / modulo-2 のよくあるミス

modulo-2 CRC 割り算では5つのよくある誤りがあります.

• XOR の代わりに借りのある通常の二進減算を使うこと.
• ゼロビットの数を間違えること（生成器の長さマイナス1でなければならない）.
• 先頭 1 ではなく 0 ビットの下に生成器を位置合わせすること.
• GF(2) 算術に繰り上がりがあるかのように扱うこと.
• 余りではなく商を CRC として報告すること.

CRC / XOR / Modulo-2 筆算割り算電卓は各手順で XOR し、正しいゼロを付加し、余りをチェックサムとして返します.

よくある質問