[SM 0]

Избавляется. Старший бит породил остаток и улетел в космос.

Не избавляется!!!!!! Измените хотя бы один бит в начале блока, и результат CRC будет уже совершенно другим. На то она и CRC, что контролирует весь блок в целом, следовательно, не избавляется (не забывает) ни один обработанный бит, где бы он не был. Так вот "аккумулятор" - это эквивалент "блока данных целиком", поэтому НЕЛЬЗЯ в нем ни от чего избавляться.

 

на делении полиномов проверять не буду, так как в экселе одним шевелением мизинца это не сделать.

[ViKo 1]

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

[SM 0]

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

Вам эксель файл с тестом что-ли сюда выложить? Чтобы Вы увидели, что в алгебраическом варианте НЕТ однозначности? Причем, почему, это теоретически понятно, даже не напрягая мозг - число, эквивалентное полиному - 311, а бит всего 8. Поэтому остаток от деления на 311 в некоторых случаях больше 8 бит, поэтому и повторы есть.

И, в аналогии для CRC - если полином, например, X^8+x^5+x^4+1, то и остаток от деления на него может содержать X^8, а может и не содержать, а при этом остальные члены будут одинаковые, вот и повтор. А сам X^8, это 0x100, это за пределами байта, его не видно.

 

Приведите пример нормальный, "космический". Простейший, CRC-4: x4 + x1 + 1

О! Даже эксель не нужен.

 

Первое данное:

 

x^4 + x^1

Он не делится на x^4 + x^1 + 1, поэтому остаток будет равен x^4 + x^1 (0x12) - а бит всего 4 - то есть, 0x02

 

Второе данное:

 

x^1

Он тоже не делится на x^4 + x^1 + 1, поэтому остаток будет равен x^1 (0x02) - а бит всего 4 - то есть, 0x02

 

Вот и дубль.

[AHTOXA 15]

Так ему однозначность нужна в другую сторону. Чтобы для закодированных данных crc получалась однозначной. А то, что закодировать можно несколькими способами - это не страшно.

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

[SM 0]

Так ему однозначность нужна в другую сторону. Чтобы для закодированных данных crc получалась однозначной.

Так а как раскодировать, если для двух разных данных может быть одинаковая CRC? Как принять решение, какое из этих двух данных корректное?

 

PS

Правда я не до конца уверен в том, что деление полиномов в данном случае корректно сравнивать с делением арифметическим, так как коэффициенты у полиномов находятся в поле GF(2), а там арифметика другая, по модулю. Поэтому я все же не уверен в том, что существуют такие остатки от деления, которые содержат член со самой старшей степенью из членов многочлена-делителя. По логике - должны. По факту - не уверен. Потому, что там, в этом поле, например, можно единицу разделить на x+1 и получить из этого единицу и остаток x, и это будет корректно, потому, что 1*(x+1) +x = x+1+x = 1

[ViKo 1]

В CRC-4 полином 5-битовый, а числа и остаток 4-битовые. Поэтому 0x12 не может получиться в принципе. То же относится к другим упоминаемым полиномам.

[SM 0]

В CRC-4 полином 5-битовый, а числа и остаток 4-битовые. Поэтому 0x12 не может получиться в принципе.

Вот поэтому, 0х02 и останется... А числа там не 4 битные, а N-битные, где N делится на 4 без остатка. Чтобы числа стали 4-битным, надо инициализировать CRC в ноль перед каждым таким числом. И, в таком случае, разумеется, обратимость гарантирована на 100%. А иначе все обработанные числа складываются в единый блок данных (единое число) длиной 4*n бит.

[krux 8]

я таки-извиняюсь, но предположу, что топикстартеру, вероятно, нужен FEC?

[SM 0]

я таки-извиняюсь, но предположу, что топикстартеру, вероятно, нужен FEC?

топикстартеру, похоже, хочется задействовать аппаратный блок подсчета CRC с целью шифрования/дешифрования поточных данных, по причине того, что он, гад, в это время бездействует, и его надо заставить хоть что-то делать :) :) А коррекция ошибок, да и обнаружение ошибок, не нужны.

[krux 8]

я опять-таки извиняюсь, но топикстартер в курсе про багофичи аппаратного блока CRC в STM32Fххх?

[ViKo 1]

Вот поэтому, 0х02 и останется... А числа там не 4 битные, а N-битные, где N делится на 4 без остатка. Чтобы числа стали 4-битным, надо инициализировать CRC в ноль перед каждым таким числом. И, в таком случае, разумеется, обратимость гарантирована на 100%. А иначе все обработанные числа складываются в единый блок данных (единое число) длиной 4*n бит.

Не согласен. Числа там такие, какие я задам. Для CRC-8 числа были бы 8-битовые. Для CRC-32 числа были бы (уже не хочу :rolleyes: ) 32-битовые. Однозначность расчетов мне очевидна.

Какая разница, чем инициализирован блок CRC, если он и при кодировании и при декодировании будет инициализирован одним и тем же. В пределах разрядности, в данном случае 32-х. Нулем ли он инициализирован или 0xFFFFFFFF, все эти биты продвинутся при расчетах на 32 шага, втянув за собой биты новых данных. Ну, не просто втянув, а еще и "подпортив" их в соответствии с CRC.

 

krux, топикстартер использует аппаратную CRC-32 для контроля достоверности данных в суперструктуре в Backup RAM, хранящей режимы работы прибора. При сбоях, просевшей батарейке, если CRC неверная, устанавливаются режимы по умолчанию. Все работает, как швейцарские часы.

 

Мне, наверное, пригодился бы CRYP, что есть в STM32F21x, но, по-моему, эти мк в Беларусь (и Россию) не поставляются.

 

топикстартеру, похоже, хочется задействовать аппаратный блок подсчета CRC с целью шифрования/дешифрования поточных данных, по причине того, что он, гад, в это время бездействует, и его надо заставить хоть что-то делать :) :) А коррекция ошибок, да и обнаружение ошибок, не нужны.

Именно. :rolleyes: Кроме "хоть что-то делать".

[SM 0]

Не согласен. Числа там такие, какие я задам.

Нельзя быть не согласным с определением CRC. Если Вы не согласны, значит Вы ведете разговор не о CRC, а о чем то другом. CRC - по определению - это остаток от деления полинома, соответствующему всему блоку входных данных в целом, на порождающий полином. !!! всему блоку !!!. Началом блока считается момент, когда инициализировали алгоритм деления полиномов, концом блока - когда считали CRC. Таким образом, чтобы данные были N-битные, следует каждые N бит инициализировать CRC. Если Вы считываете CRC через каждые, допустим, 8 бит, и не переинициализируете, то у вас первое CRC соответствует блоку данных из 8 бит, второе блоку из 16 бит, третье - блоку из 24 бит, четвертое - блоку из 32 бит, пятое - из 48 бит, и так далее, пока не переинициализируете его. И нельзя рассматривать деление полинома, соответствующее только последнему байту, когда до этого была еще куча байт - блок данных, он на части не делим (точнее делим, но переинициализацией CRC). Арифметический пример - число 123 при делении на 17 даст остаток 4. А если перед этим было число 1, то весь блок данных станет 1*256+123, то есть 379, и остаток от деления на 17 уже будет 5!.

[ViKo 1]

Нельзя быть не согласным с определением CRC. Если Вы не согласны, значит Вы ведете разговор не о CRC, а о чем то другом. CRC - по определению - это остаток от деления полинома, соответствующему всему блоку входных данных в целом, на порождающий полином. !!! всему блоку !!!. Началом блока считается момент, когда инициализировали алгоритм деления полиномов, концом блока - когда считали CRC. Таким образом, чтобы данные были N-битные, следует каждые N бит инициализировать CRC. Если Вы считываете CRC через каждые, допустим, 8 бит, и не переинициализируете, то у вас первое CRC соответствует блоку данных из 8 бит, второе блоку из 16 бит, третье - блоку из 24 бит, четвертое - блоку из 32 бит, пятое - из 48 бит, и так далее, пока не переинициализируете его.

Ну и пусть. Где здесь противоречие принципам CRC? Я вычислил CRC для первого байта и сохранил его. Потом продолжаю вычислять для двух байтов и, зная первую CRC, однозначно определю CRC для второго байта, если потребуется. И т.п.

Инициализация блока CRC - это не сброс автомата, а начальное значение. Если я буду каждый раз инициализировать его, например, 0x77776666 при расчете и при проверке, соответствие будет гарантировано. Если я с каждым новым словом буду инкрементировать начальное значение от 0 до 0xFFFFFFFF при расчете и проверке - тоже! Аналогично я могу инициализировать блок CRC предыдущим значением (не трогать, то есть), если при расчете и при проверке они одинаковые.

Главное, чтобы эти начальные значения совпадали при расчете и при проверке. Вот и вся сущность этой инициализации.

[SM 0]

и, зная первую CRC, однозначно определю CRC для второго байта, если потребуется. И т.п.

А я вот в этом сильно не уверен. Возвращась к арифметическому аналогу с делителем 311 и 8 битами... Повторю его еще раз... На аккумулятор не смотрим, так как "весь блок данных нам, типа, не важен". Я его удалил. Смотрим только на данные, и аналог CRC.

 

22 -> 22

33 -> 67

44 -> 91

11-> 37 или 66->37

 

И что дало такое априорное знание, что код был равен 91 перед тем, как стал 37? Это как-то может помочь в принятии решения, как декодировать число 37 - в 11, или в 66?

[ViKo 1]

Давайте возьмем примитивнейший пример. CRC-8 равна сумме того числа-байта, что занесено в блок вычисления и входного байта. И ограничена, естественно, 8 битами. Кодируем ту же последовательность, каждое число не более 8 битов:

22 -> 22

33 -> 55

44 -> 99

66 -> 165

166 -> 330 = 74

255 -> 329 = 73

и т.д. Очевидно, однозначность будет всегда.

 

 

И что дало такое априорное знание, что код был равен 91 перед тем, как стал 37? Это как-то может помочь в принятии решения, как декодировать число 37 - в 11, или в 66?

Это говорит о том, что предложенный вариант вычислений как CRC использовать нельзя.

Когда вы умножаете предыдущий результат на 256, вы сильно вылетаете за разрядность числа 311. Видимо, здесь ошибка.