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

Question

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

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

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

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

      ___________
1010 | 101101000

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

Answer 1

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

Таким образом, 101101000 является идеальным, и при передаче / приеме не было ошибок

Answer 2

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

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.

Answer 3

Это длинное деление на двоичное число 11. Есть пример на Википедии .