ネットワークメッセージの残りのビットを検証するために、巡回冗長検査でXORアルゴリズムの残りを計算するために数学がどのように行われるかを思い出そうとしています。
その教科書を捨てるべきではなかった。
これはコードで簡単に実行できますが、手作業ではどのように行うのでしょうか?
標準の除算アルゴリズムのように見えることは知っていますが、そこから余りを取得するためにどこに行けばよいか思い出せません。
___________
1010 | 101101000
注: Google で調べましたが、残りを計算する手順をマップした場所を見つけることができませんでした。
1010 | 101101000
1010
0001 this result is 1011 XOR 1010 = 0001
1010
1010
0000 thus no remainder.
したがって、101101000 は完全であり、送受信でエラーは発生していません。
私の経験では、手で計算する場合、特にゼロが多い場合は、多項式に変換する方が簡単です。
1010 = 1*x^3 + 0*x^2 + 1*x^1 + 0*x^0 = x^3 + x = x3 + x
101101000 = x8 + x6 + x5 + x3
-------------------
x3 + x ) x8 + x6 + x5 + x3
次に、被除数の最大項( ) を除数の最初の項( ) で除算すると、 が得られます。その数値を上に置き、除数の各項を掛けます。これにより、最初の反復で次の結果が得られます。x^8x^3x^5
x5
-------------------
x3 + x ) x8 + x6 + x5 + x3
x8 + x6
各項に対して XOR を実行すると、新しい被除数が得られます: x5 + x3:
x5
-------------------
x3 + x ) x8 + x6 + x5 + x3
x8 + x6
-------------------
x5 + x3
被除数の最大項が除数の最大項よりも小さくなるまで、同じパターンに従います。計算が完了すると、次のようになります。
x5 + x2
-------------------
x3 + x ) x8 + x6 + x5 + x3
x8 + x6
-------------------
x5 + x3
x5 + x3
-------------------
0
この場合のリマインダーは 0 です。これは、送信中にエラーが発生しなかった可能性が高いことを示します。
注: SO は数式の書式設定をサポートしていないため、上記の例のように短くx^yして、回答の混乱を減らしました。xy
注 2: 除数の倍数を被除数に加算/減算すると、リマインダが 0 であるため(P(x) + a*C(x)) / C(x) = P(x)/C(x) + a*C(x)/C(x)と同じリマインダが得られるP(x)/C(x)ため、リマインダa*C(x)/C(x)も 0 になります。
バイナリ 11 による長い除算です。ウィキペディアに例があります。