CRCで使用されるXOR剰余をどのように計算しますか？

StackOverflow https://stackoverflow.com/questions/344961

  •  19-08-2019
  •  | 
  •  

質問

ネットワークメッセージの残りのビットを検証するために、巡回冗長検査でXORアルゴリズムの残りを計算するために数学がどのように計算されたかを思い出そうとしています。

その教科書を投げる必要はありません。

これはコードで簡単に実行できますが、手作業でどのように解決されますか？

標準の除算アルゴリズムのように見えることは知っていますが、残りを取得するためにそこからどこに行くべきか思い出せません。 

      ___________
1010 | 101101000

注： Googleで検索しましたが、残りの部分を把握するためのステップをマッピングした場所を見つけることができませんでした。

役に立ちましたか？

解決

バイナリ11による長い区分です。 Wikipedia に例があります。

他のヒント

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^8）の最大用語 を 最初の用語 <除数のem>（x^3）、x^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：(P(x) + a*C(x)) / C(x) = P(x)/C(x) + a*C(x)/C(x)のリマインダーは0なのでP(x)/C(x)はa*C(x)/C(x)と同じリマインダーを与えるため、配当から除数の倍数を加算/減算するとリマインダー0も与えられます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top