Здравствуйте, netch80, Вы писали:

N>>>то у меня получается в самом коротком случае 3 байта испорченных, иногда 4, обычно же оно не находит случаев короче чем 8 байт. Для CRC-8 это очень хороший результат. А твой пример умудряется находить даже последовательности с изменением одного последнего байта, что заведомо показывает на ошибочность твоего кода (собственно почему я и стал рыть).
fk0>> Исправил. Так ведь получается. Вот пример для 1000 запусков:
N>Ничего неожиданного. Естественно, можно подобрать такие данные, что на них с подобной стандартной заменой получится "немного" не то, но с той же суммой.
N>Но для таких ситуаций надо вообще что-то принципиально другое придумывать, чем суммы. Я взял твой код и попытался сделать следующие варианты замен:
N>1) вместо CRC — младшие 8 бит суммы байт
N>2) то же но с переносом старшего бита в конец (не XOR, а добавлением) (в стиле IP?)

N>Результат удручает — ни одна сумма такой ситуации не ловит. Статистически лучше всего, похоже, просто младший байт суммы всех байт потока, но тоже качество обнаружения отвратительное.

16-битная сумма в 256-байтном пакете (и более коротких) гарантированно ловит такие ситуации. Вроде ж очевидно. 16-битный CRC тоже их ловить не будет, хотя и с меньшей вероятностью.


fk0>> Это CRC с указанным полиномом и его результат для любых входных значений полностью совпадает с побитным алгоритмом CRC. Указанный полином на сайте smbus.org... Указанные коэффициенты для ксорки берутся из результатов вычисления таблицы CRC побитным алгоритмом и взятия каждого 2^N-го члена для N=0..7. Это оптимизированный алгоритм просто. И, кстати, на мелких контроллерах он может работать быстрее табличного (на гарвардских архитектурах доступ к данным в программной памяти -- медленный).
N>Я не про способ вычисления — понятно, что он подбирается под реализацию. А про собственно алгоритм. Впрочем, я уже нашёл как его логически описать: он эквивалентен классическому, но с добавлением ещё одного нулевого байта в конце входной последовательности.

Да он полностью эквиэвалентен. Я ж написал -- я налажал в коде. И написал как исправить.

fk0>> Увы и ах. Именно так, именно для того он и предназначен. И в RS-232 будет замечательно работать. А где пакетная передача с обрывами посереди пакета и заполнением конца пакета одинаковым битом -- не канает CRC.
N>Как уже сказал — там никакая сумма "не канает" пока нет подтверждения собственно целостности канала.

Когда в канале не произвольные искажения, а исключительно об 00-вание или об FF-чивание, то сумма соответствующей разрядности просто гарантирует.

fk0>> Кстати ещё пример неправильного применения CRC -- контрольный код записи в FLASH-памяти. Догадываешься уже почему? Ровно та же проблема. Массовое FF-чивание отдельных блоков. Контрольная сумма подходящей разрядности (весьма небольшой) опять же справляется гарантировано и это очевидно математически.
N>Нет. Модифицируй свою программу и проверь: точно так же не справляется.

Это ж очевидно, что если в последовательности единиц и нулей часть последовательности заменить на единицы или нули, то сумма станет соответственно такой же или большей, или такой же (когда 0 заменяется на 0) или меньшей. Для одного разряда это так (проверь). И для каждого N+1 тоже (доказано). Если в сумме нет переполнений -- поэтому разрядность должна быть больше, чем log2(sum(все единицы)).