Как вы вычисляете XOR Remainder, используемый в CRC?

Question

Я пытаюсь вспомнить, как выработана математика, чтобы вычислить оставшуюся часть алгоритма XOR в циклах циклической избыточности, чтобы проверить оставшиеся биты сетевого сообщения.

Я не должен был бросить этот учебник.

Это легко сделать в коде, но как это работает вручную?

Я знаю, что это выглядит как стандартный алгоритм деления, но я не могу вспомнить, куда идти оттуда, чтобы получить остаток.

 ___________ 
1010 | 101101000 

Примечание: Я Google, но не смог найти место, где они отображенные шаги в выяснении остатка.

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.