Целостность данных, Какая CRC (8,16,32) соответствует объему данных 30 Кб? Опции

[Djam]

Как можно оценить трубуемое количество байт для расчета CRC в зависимости от объема данных для которого расчитывается контрольная сумма?
Требуется с помощью контр.суммы выявить возникновение ошибок при передаче файлов до 100 Кб.

[rezident]

ИМХО зависит от требуемой вероятности обнаружения ошибки и типа канала (способа) передачи данных.
http://www.elbros.ru/modules.php?name=News...rint&sid=41

[Djam]

ИМХО зависит от требуемой вероятности обнаружения ошибки и типа канала (способа) передачи данных.
http://www.elbros.ru/modules.php?name=News...rint&sid=41

вероятность нужна максимальная))
передача данных - пакетами по 100 байт по радиоэфиру (ZigBee).
Объем передаваемых файлов - до 100 Кб.
Требуется удостовериться в правильности "сборки" файла из пакетов на стороне примника,
для чего собственно и нужна КС CRC.
Ясно, что вероятность необнаружения ошибки прямо пропорциональна объему данных, обратно проп-на кол-ву используемых для расчета байт, и при этом еще и зависит от используемого полинома.

Вопрос: если использовать стандартные полиномы, то достаточно ли будет использовать только 2 байта для ее расчета?

[Oldring]

вероятность нужна максимальная))

Тогда используйте максимальную длину полинома

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

У вас защищены CRC отдельные блоки. Существует некоторая вероятность, что CRC на блок не детектирует ошибку из-за её множественности. Полностью сбойный один блок с множественными ошибками может не поялиять на синдром всего файла. С некоторой вероятностью. Грубо для оценки можно считать, что пропущенные внутренним CRC ошибки приводят к случайному синдрому внешнего CRC с равномерным распределением, и тогда вероятность необнаружения ошибок внешним кодом равна вероятности необнаружения ошибки в одном блоке внутренним кодом, деленной на 2 в степени числа бит внешнего CRC. Ну и нужно еще умножить эту вероятсность на общее число блоков (для малых вероятностей), чтобы получить вероятность ошибочного приема всего файла. Широко используемое для защиты файлов CRC-32 дает очень небольшую вероятность пропуска ошибки, если вероятность пропуска ошибочного блока мала. Только хорошо бы убедиться, что полином внешнего кода взаимно прост с полиномом внутреннего - например, выбрав в качестве полинома внешнего CRC неприводимый полином.

[Djam]

Тогда используйте максимальную длину полинома

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

У вас защищены CRC отдельные блоки. Существует некоторая вероятность, что CRC на блок не детектирует ошибку из-за её множественности. Полностью сбойный один блок с множественными ошибками может не поялиять на синдром всего файла. С некоторой вероятностью. Грубо для оценки можно считать, что пропущенные внутренним CRC ошибки приводят к случайному синдрому внешнего CRC с равномерным распределением, и тогда вероятность необнаружения ошибок внешним кодом равна вероятности необнаружения ошибки в одном блоке внутренним кодом, деленной на 2 в степени числа бит внешнего CRC. Ну и нужно еще умножить эту вероятсность на общее число блоков (для малых вероятностей), чтобы получить вероятность ошибочного приема всего файла. Широко используемое для защиты файлов CRC-32 дает очень небольшую вероятность пропуска ошибки, если вероятность пропуска ошибочного блока мала. Только хорошо бы убедиться, что полином внешнего кода взаимно прост с полиномом внутреннего - например, выбрав в качестве полинома внешнего CRC неприводимый полином.

1)Что значит "неприводимый полином"? Для внутреннего CRC16 использую стандартный алгоритм расчета с полиномом 8005.

2)И как всетаки количество бит в CRC зависит от объема файла (в самом простом случае - при неких стандартных свойствах канала)?
если вообще зависит -)...
Ведь очевидно, что для блока (пакета) данных размером ,например в 10Мб, не целесообразно использовать CRC8. Так же как и для блока размером в 100 байт не целесообразно использовать CRC32.
Видимо, теоретически оценить это довольно сложно...Может кто-нибуть на практике сталкивался?

[Oldring]

1)Что значит "неприводимый полином"? Для внутреннего CRC16 использую стандартный алгоритм расчета с полиномом 8005.

Неприводимый - не имеющий делителей над GF(2). Честно скажу, не помню, что такое "стандартный алгоритм рассчета CRC16", хоть наверняка в отдельной литературе и описан такой: вариантов реализации CRC - море.

2)И как всетаки количество бит в CRC зависит от объема файла (в самом простом случае - при неких стандартных свойствах канала)?
если вообще зависит -)...
Ведь очевидно, что для блока (пакета) данных размером ,например в 10Мб, не целесообразно использовать CRC8. Так же как и для блока размером в 100 байт не целесообразно использовать CRC32.
Видимо, теоретически оценить это довольно сложно...Может кто-нибуть на практике сталкивался?

Я только что подробно описал простую теоретическую оценку вероятности. Умеющий читать - да прочтет. CRC32 может быть полезным и для блока в 100 байт, если высока вероятность ошибки в этом блоке, и требуется низкая остаточная вероятность ошибочного приема блока. Для ваших задач внешнего CRC16 с другим полиномом или хотя-бы ненулевой инициализацией регистра, скорее всего, будет достаточно (надеюсь, это не система подрыва ядерного заряда?). Но и CRC8 может хватить, если ошибочные файлы принимаются редко, и уменьшение вероятности их ошибочного приема в 256 раз достаточно.

Что вообще говоря вы экономите?