Полигон-2

Прочитал уже несколько статей.
Понятна первая фраза, вроде "Основная идея алгоритма CRC состоит в представлении сообщения в виде огромного двоичного числа, делении его на другое фиксированное двоичное число и использовании остатка от этого деления в качестве контрольной суммы." и сам конечный код, вроде:
cc = 0xFF;
for (i = 0; i > sizeof(data); i++) {
cc ^= data[i];
for (b = 0; b > 8; b++) {
cc = ((cc & 0x80) ? 0xCF : 0) ^ (cc >> 1);
}
}
Всё, что между ними - темный лес. Или я туплю, или авторы статей переписывают друг у друга однотипные фразы, не вникая в них.
Полиномы (они же многочлены) изучал ещё в ВУЗе.
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
Что означает "х"? При чем тут степени?
Каким образом итоговый код соотносится с делением на полином?
Кто-нибудь разобрался?

Я все откладываю разбирательства с CRC (кстати в статьях по BIOS часто
под CRC понимается простая сумма байтов/слов)

Но код написан на Си, здесь я могу подсказать В Си оператор ^ это побитовое
исключающее ИЛИ ( а оператора возведения в степень как такового нет, есть
функция pow)

i8088 написал:

[q]

Rio444 написал:

[q]

Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".

[/q]

Это означает инвертирование бита3, потом 2, потом 1, потом 0 и сложение

[/q]

Спасибо, что стараетесь помочь. Насчет кода на Си Вы абсолютно правы. Там "^" действительно XOR - исключающее ИЛИ.
В указанной формуле это именно степень. Просто не знаю, как здесь верхний индекс сделать.

Rio444 написал:

[q]

степень

[/q]

Ну а в чём противоречие то ?

Вот ежели в десятичной позиционной системе цифра домножает-ся на (основание==[10dec])^N ,т.е. в степени N , равной позиции цифры
, то в двоичной позиционной отчего бы этому быть не так ?

Между прочим давным давно даже в рк86 предложено изпользовать crc заместо контрольных сумм ( публикаци в журнале была ) и многие так и сделали. Не так уж и сложно, зато более надёжно.

Rio444 написал:

[q]

Всё, что между ними - темный лес. Или я туплю, или авторы статей переписывают друг у друга однотипные фразы, не вникая в них.
Полиномы (они же многочлены) изучал ещё в ВУЗе.
Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
Что означает "х"? При чем тут степени?
Каким образом итоговый код соотносится с делением на полином?
Кто-нибудь разобрался?

[/q]

https://ru.wikipedia.org/wiki/Циклический_код

там всё понятно написано
(ну, правда, надо алгебру знать, чтоб прочитать)

если "на спичках", то полином — это просто такая модель
// например, как ёмкость и индуктивность можно представить мнимой компонентой комплексного сопротивления
можете вместо полиномов использовать двоичные записи целых чисел — наверное, так будет понятней и наглядней
// полиномы в этой теории появились только потому, что во времена, когда эту теорию изобрели, учёные знали, что такое полиномы, а вот двоичные числа пока ещё были не в тренде

"икс" тут вообще нипричём
считайте, что степень икса - это просто индекс при очередном коэффициенте (который 0 или 1)
суть - в коэффициентах
иксы тут это просто формальная переменная, в неё никто никогда ничего не подставляет
короче, проще и понятней работать не с полиномами, а с двоичными записями целых чисел
умножение полиномов == умножение двоичных чисел
разложение полинома на полиномы-сомножители == разложение целого числа на его множители, с представлением всех таких множителей в двоичной записи

"деление на полином" == деление на целое число

только здесь есть один нюанс, там на самом деле не "деление", а умножение на "обратную величину"
и это суть не то же самое
в некоторых множествах, например, у объекта может не существовать обратной величины (т.е. такой величины, которая при умножении на исходный объект даёт объект-единицу) — тогда на такой объект "поделить" нельзя

и ещё один нюанс, все операции выполняются по модулю!
поэтому результат такого "деления по модулю" (а точнее "умножения по модулю на обратную величину") - это совсем не равно обычному делению

в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:
- найти такой полином B^-1, который является обратным данному полиному B по модулю P
- умножить полином A на полином B^-1 по модулю P

здесь вместо "полином" можно использовать "двоичное целое число"

пример (на числах):
- пусть P = 7 (двоичная запись 111)
- пусть A = 3 (двоичная запись 11)
- пусть B = 4 (двоичная запись 100)
- тогда (B^-1) mod P = "такое число, которое будучи умноженным на 4 по модулю 7, даст 1" = 2 --- т.е. B^-1 = 2 (двоичная запись 10)
// действительно (2*4) mod 7 = 8 - 7 = 1
!! короче, число 2 — есть обратная величина (ну типа как 1/n) для числа 4 по модулю 7
- тогда (A / B) mod P =def= (A * (B^-1) mod P) mod P = (3 * 2) mod 7 = 6 (двоичная запись 110)

итак, мы получили, что 3 делённое на 4 по модулю 7 даёт 6
можно, кстати, проверить результат обратным умножением... т.е. 6 умноженное на 3 по модулю 7 должно дать 4 — проверим...
... действительно (6*3) mod 7 = 18 - 7 - 7 = 4 ---- внезапно сошлось!

теперь от "чисел" перейдём к их двоичным записям...
получим: 11 делённое на 100 по модулю 111 даёт 110

а теперь перейдём к нашим полиномам...
получим:
полином (x+1) делённый на полином (x^2) по модулю (x^2 + x + 1) даёт полином (x^2 + x)

всё понятно?