подсчет контрольной суммы CRC, полиномиальная арифметика Опции

[Тёмный Эльф]

У меня есть примерный алгоритм по подсчету контрольной суммы, но он не до конца мне ясен. Кто сможет, объясните пожалуйста.
1. выбрать полином. Например если степень полинома 4, то можно выбрать полином 10011 (ну, а если степень полинома равна 8, то полином может быть думаю таким 100111111). т.е. степень полинома - это позиция самого старшего бита.
2. Затем код сообщения перевести в двоичную систему счисления. Здесь непонятно. Например если код полученного сообщения равен например 36 21 16, то что переводить в двоичную систему? их сумму, то бишь 36+21+16=73=1001001 или же сначала каждый символ переводить в двоичку а потом складывать, типа 36=100100
21=10101
16=10000 и теперь только складывать 100100+10101+10000=110101??
3.теперь нужно дополнить полученное сообщение нулями. если степень полинома 8, как в моем случае, то 8 нулями. предположим полученное сообщение это все-таки 110101 а не 1001001 ,тогда выравненное сообщение будет таким 11010100000000
4. теперь это выравненное сообщение нужно поделить (используя CRC арифметику) на полином, то бишь
11010100000000 надо поделить на 100111111 и найденный остаток и будет представлять собой контрольную сумму. Но как это вообще осуществить? это деление? у меня пока мало информации по этому поводу, знаю только, что там как-то замешаны XOR и сдвиги. Но этого мало, чтобы понять. =(

Сообщение отредактировано: Тёмный Эльф - 2.05.2007 22:39

[xds]

Суть в том, что можно договориться о вычитании по модулю 2 при делении многочленов. При этом теряются знаки при коэффициентах остатка (они всегда неотрицательны - 0 или 1), но это не принципиально для подсчёта КС, и , кроме того, упрощает реализацию.

Код

11010110110000 | 10011
10011          +----------
-----            1100001010
010011
.10011
.-----
.0000010110
......10011
......-----
......0010100
........10011
........-----
........001110