Как считается CRC?

Все, что не подходит под определение "старого софта и железа", обсуждается здесь
Аватара пользователя
Rio444
Почётный пользователь
Сообщения: 26861
Зарегистрирован: 14.09.2014,19:11
Откуда: Ростов-на-Дону

Вклад в сообщество

Как считается CRC?

Сообщение Rio444 » 22.05.2018,15:12

Прочитал уже несколько статей.
Понятна первая фраза, вроде "Основная идея алгоритма 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".
Что означает "х"? При чем тут степени?
Каким образом итоговый код соотносится с делением на полином?
Кто-нибудь разобрался?
Электронка: Изображение копия Изображение

pahan
Advanced Member
Сообщения: 4455
Зарегистрирован: 13.03.2015,14:23
Откуда: Химки, М.О.

Вклад в сообщество

Сообщение pahan » 22.05.2018,15:41

Что означает "х"? При чем тут степени?
Я тоже уже всю математику забыл, да и никогда настолько хорошо не знал ;)
Практически - "степень" - на самом деле не степень, а битовая позиция, в которой в делителе есть 1.
Так что
x^8 + x^2 + x^1 + x^0
на самом деле - деление на 100000111
Наглядный пример в вики (конечно нерусской).


i8088
Advanced Member
Сообщения: 4383
Зарегистрирован: 30.01.2015,17:06
Откуда: г. Баку, Азербайджан

Конкурсы

Вклад в сообщество

Сообщение i8088 » 22.05.2018,15:41

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

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

i8088
Advanced Member
Сообщения: 4383
Зарегистрирован: 30.01.2015,17:06
Откуда: г. Баку, Азербайджан

Конкурсы

Вклад в сообщество

Сообщение i8088 » 22.05.2018,15:48

Rio444 писал(а):Мне непонятна запись полинома-делителя в виде "x^8 + x^2 + x^1 + x^0".
Приоритет сложения в Си выше, наверно имеется ввиду
c = (x^8) + (x^4) + (x^2) + (x^1);

Это означает инвертирование бита3, потом 2, потом 1, потом 0 и сложение результатов (сам x при этом не меняется)

Те если например X = 1100 (двоичные)

0100 +
1000 +
1110 +
1101 +
100111 (0x27)


Аватара пользователя
Rio444
Почётный пользователь
Сообщения: 26861
Зарегистрирован: 14.09.2014,19:11
Откуда: Ростов-на-Дону

Вклад в сообщество

Сообщение Rio444 » 22.05.2018,16:03

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

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

Аватара пользователя
Rio444
Почётный пользователь
Сообщения: 26861
Зарегистрирован: 14.09.2014,19:11
Откуда: Ростов-на-Дону

Вклад в сообщество

Сообщение Rio444 » 22.05.2018,16:27

Вот здесь http://radiohlam.ru/?p=1406 немножко поподробнее и попонятнее.
Электронка: Изображение копия Изображение

gtnhtyrj
Advanced Member
Сообщения: 459
Зарегистрирован: 12.03.2012,18:40
Откуда: из лесу, вестимо.

Сообщение gtnhtyrj » 22.05.2018,23:42

Rio444 писал(а):степень
Ну а в чём противоречие то ?

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

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

Аватара пользователя
Rio444
Почётный пользователь
Сообщения: 26861
Зарегистрирован: 14.09.2014,19:11
Откуда: Ростов-на-Дону

Вклад в сообщество

Сообщение Rio444 » 23.05.2018,07:58

petrenko писал(а):Ну а в чём противоречие то ?

Вот ежели в десятичной позиционной системе цифра домножает-ся на (основание==[10dec])^N ,т.е. в степени N , равной позиции цифры
, то в двоичной позиционной отчего бы этому быть не так ?
Так если бы было "2^8 + 2^2 + 2^1 + 2^0", то было бы вполне понятно.
Но
Что означает "х"? При чем тут степени?
Электронка: Изображение копия Изображение

Гость

Сообщение Гость » 23.05.2018,16:39

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

всё понятно?

;)

Аватара пользователя
Rio444
Почётный пользователь
Сообщения: 26861
Зарегистрирован: 14.09.2014,19:11
Откуда: Ростов-на-Дону

Вклад в сообщество

Сообщение Rio444 » 23.05.2018,18:35

xoiss писал(а):всё понятно?
Спасибо, почти.
xoiss писал(а):в общем, чтобы "разделить полином A на полином B по модулю P", надо сделать вот что:
Что такое разделить, понимаю.
Что значит "по модулю P"?
Электронка: Изображение копия Изображение


Ответить