如何計算CRC中使用的XOR餘數？

Question

我想記住算法是如何計算週期性冗餘校驗中XOR算法的其餘部分來驗證網絡消息的其餘位的。

我不應該丟掉那本教科書。

這很容易在代碼中完成，但是它是如何通過手工完成的？

我知道它看起來像一個標準的劃分算法，但我不記得從那裏去哪裏得到餘數。

 ___________ 
1010 | 101101000 

注：我沒有谷歌，但沒能找到他們映射盤算其餘的步驟的地方。

Answer 1

它是由二進制長分裂11.在Wikipedia上有一個例子。

Answer 2

1010 | 101101000 
     1010 
     0001 this result is 1011 XOR 1010 = 0001 
      1010 
      1010 
      0000 thus no remainder. 

因此101101000是完美的，沒有出現錯誤的發送/接收

Answer 3

以我的經驗更容易通過手工計算時，將其轉換爲一個多項式，特別是當有是有很多零的。

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）在除數（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，這表明，最有可能沒有錯誤的傳輸過程中發生。

注意：在上面的示例中，我縮短x^y爲xy以減少答案中的混亂，因爲SO不支持數學等式格式。

注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