Опять про Ross N.Williams:
Элементарное руководство по CRC- алгорит-
мам обнаружения ошибок.

Есть пример:
1101b полином которого x^3+x^2+x^0
и 1011b полином которого x^3+x^1+x^0

автор привел умножение этих полиномов:
(x^3+x^2+x^0)(x^3+x^1+x^0)=
=(x^6+x^4+x^3+x^5+x^3+x^2+x^3+x^1+x^0)=
=x^6+x^5+x^4+3*x^3+x^2+x^1+x^0

Это понятно.
Далее он говорит:"Для получения правильного ответа
нам необходимо указать, что х равен 2, и выполнить
перенос бита от члена 3*x^3, в результате получает-
ся:
x^7+x^3+x^2+x^1+x^0

Вопрос:
Как оно получил от это выражение? Как делать пере-
нос?

Буду рад, если найдется тот кто это объяснит, но
все равно спасибо, за то что хоть взглянули. Линку
на эту арифметику я тоже буду рад.

В четвертом разряде суммируются три единичных бита.
Правило сложения битов:
1 + 0 = 1 и переноса в старший разряд нет
1 + 1 = 0 и перенос 1 в старший разряд (там суммируем снова)
1 + 1 + 1 = 1 и перенос 1 в старший разряд

В примере, получается 1-ца в четвертом разряде, как результат 3*x^3 и 1-ца выталкивается в старший (пятый) разряд.
Там уже есть 1. Результат суммы - 0 и снова 1-ца выталкивается в старший (шестой) разряд. И т.д.

Куда тогда деваеся X^5 и X^4?

Имеем:

x7 x6 x5 x4 x3 x2 x1 x0
0  1  1  1  3  1  1  0

Значит:

x7 x6 x5 x4 x3 x2 x1 x0
0  1  1  1  1  1  1  0
            1
            1

Теперь, по правилам двоичного сложения, приведенным sd2000, осуществляем перенос в старший разряд:

x7 x6 x5 x4 x3 x2 x1 x0
0  1  1  1  1  1  1  0
         1

Продолжаем переносить:

x7 x6 x5 x4 x3 x2 x1 x0
0  1  1  0  1  1  1  0
      1

Ещё раз:

x7 x6 x5 x4 x3 x2 x1 x0
0  1  0  0  1  1  1  0
   1

И ещё:

x7 x6 x5 x4 x3 x2 x1 x0
1  0  0  0  1  1  1  0

Задолбался я в этих дебрях, но меня все не отпускает!

Итак возьму сообщение: 1011011b и распространенный
полином для crc16 - 15d=1111b отсюда видно, что w=3,
т.к. старший бит стоит на третей позиции.
Добавляем сообщение тремя нулями и получим:
1011011000b - А`
Начну делить это число на G, то бишь 1111b.
Просматриваю справа налево A` и формирую минимальную
последовательность большую или равную G, это 10110b
применяю к этому число вычетание с исключением заема
получаю 11001b.

Верны ли эти действия или следовало применить опера-
цию вычетания с исключением заема к числу 1011b и по-
лучилось бы 0100b?

Как в этой дури бы разобраться? Где тут ДЗЭН?

Забыл спасибо сказать!

1011011000 + 0000000XXX должно без остатка делиться на CRC. У меня получается что XXX = 111.

1011011000 + 0000000111 = 1011011111 = 735
735 % 15 = 0.

Я уже давал эту ссылку, но всё же...

Татарин бы сказал рэхмэт!

Quantum
Мне тут посоветовали Корн Корн, что скажешь поэтому поводу?

Quantum!
Объснение про перенос супер, а вот про деление не-
понял :(
Ту ссылку, что ты дал
Глянул, но там блин толи великого русско-
го не знают, толи повыделываться решили. Одним сло-
вом: Не хрен было первым прогерам ВАвилон.exe
создать, так бы говорили все на ассеме, а раз выде-
лываемся то бог наказал, все кто начем. Эх! :(

повторюсь:
1011011000b - наше сообщение, G - 15d полином, т.к.
w=3, имеет смысл: 1011011000.000(точка указывает что
мы добавили). Далее делим:

*
1011011000000|1111
01111 |----
----- |1
11001

так я должен был делать? как при обычном делении то-
ко xor`ить иногда

(обрати внимание на звездочки,т.к. при нормальном
делении фомируется минимальная последовательность
слева направо которая больше или равна делителю в на-
шем случае чуть больше)

или так:

*
1011011000000|1111
1111 |----
---- |1
0100

Делю на полный 1111, а не на 111, т.к. в Вильямсе гл.3
делится на полное число!

Заколебался выравнивать * долны быть над младшими битами последовательностей!

EvilsInterrupt
Итак возьму сообщение: 1011011b
повторюсь: 1011011000b - наше сообщение
Так какое же из них является "настоящим" сообщением? :-)

Нашёл! Рисунки должны быть вполне понятны для не англоязычных товарищей. Обрати внимание на "CRC Hardware Operation".

Quantum
Извини, что так долго достаю тебя вопросами, но на форуме кроме тебя как я понял больше ни кто это незнает.
Этот алгоритм я видел в коде, но я дал понять что я хочу видеть не только алгоритм, но и саму теорию. Вспомни ералаш где число 28 делят на 7 получают 13. Ну, так вот приставил графику, вот отсюда и вытекает мой вопрос, как бы это выглядело для 101101b и полинома 1111b? Графически! Чо под чем пишется что под чем отнимается с использованием crc арифметики?

EvilsInterrupt
но на форуме кроме тебя как я понял больше ни кто это незнает.
Знают, но молчат :-) Кстати, эта тема уже поднималась, но давно и я сам уже не могу найти её через поиск.

Как верно подмечает автор той статьи (см. ссылку выше), существует по крайней мере три различных представления алгоритма CRC:

1. Железячное представление путём сдвигов и XOR'ов.
2. Софтверное представление, которое ассоциируется с поиском в некоторой "магической" таблице.
3. Математическое... полиномиальное...

Ещё упоминается представление коалиции шифровальщиков, но оно слишком заумное, IMHO.

Так вот, теоретическое обоснование п2 не выдерживает никакой критики, а п3 я не люблю, т.к. всегда забываю перевести остаток от деления в модуль 2 и, понятное дело, получаю неверный CRC. Поэтому, всегда в уме пользуюсь п1, т.е. алгоритмом со сдвигами и xor'ами. Суть сего представления такова:

M  = 1011011000
G  = 1111
M' = 1011011000000

Начинаем сдвигать M' и xor'ить на G, когда MSB = 1:

1. 1011011000000
  ^1111
   0100
2. 100011000000
  ^1111
   0111
3. 11111000000
  ^1111
   0000
4. 0001000000
5. 001000000
6. 01000000
7. 1000000
  ^1111
   0111
8. 111000
  ^1111
   0001
9. 00100
A. 0100 <- CRC

Quantum
Что сказать тебе на это... всего и не выразишь и если в спасибо укладывается куча всех благодарных слов, тогда СПАСИБО!