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

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

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

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

Может тогда стоит считать/передавать CRC для каждого пакета, а не один раз для всего файла.

да, конечно- для каждого пакета рассчитывается CRC16 (согласно стандарту ZigBee).
если пакет неверный (сrc не совпала)- то он перезапрашиватеся.
Расчет CRC для всего файла необходим для исключения ошибок при записи пакетов на жесткий диск.
Т.е., если премник (в данном случае - ПК) принял пакет, подтвердил прием, но не записал пакет на HDD (или записал с искажением),
то в конце передачи это обнаружится, т.к. CRC всего файла не совпадет. Кроме того так исключаются возможные потери пакетов, и повторные записи.
Отсюда и вопрос.

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

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

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

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

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

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



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

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

Тутевич "Телемеханика". В одной из глав найдете оценку эффективности CRC.

так и не нашел эту книгу. Может есть у кого-нибудь?



СПасибо за пояснения, вроде чтот о прояснилось.
Насколько я понял,конечная вероятность записи искаженного блока на диск будет равна произведению вероятности необнаружения ошибки в блоке ( соответственно,1/2*16 или 1/2*32 для СRС16 и 32) и вероятности появления множественных ошибок в блоке при передаче по каналу связи.
Последняя зависит от свойств канала, ну и, наверное от длины самого блока - ведь, интуитивно - чем больше блок данных, тем больше вероятность его искажения при передаче.

ВИдимо, все зависиит от свойств канала в конечном счете.

Вот что нашел :
1)"Алгоритм CRC16/32 изначально предназначался для контроля целости данных от непреднамеренных искажений. Он широко используется в проводных и беспроводных сетях, магнитных и оптических носителях, а также микросхемах постоянной или перешиваемой памяти. "Надежность" CRC32 оценивается как 2^32 == 4.294.967.296, то есть вероятность, что контрольная сумма искаженного файла "волшебным" образом совпадет с оригиналом, оценивается (в среднем) как один против четырех миллиардов раз. Отсюда следует, что, передав восемь миллиардов пакетов через сильно зашумленный канал, мы рискуем получить пару "битых" пакетов, чьи искажения останутся необнаруженными. Но ведь в действительности все совсем не так! ! Природа большинства физических помех и дефектов носит групповой характер, с которым CRC32 легко справляется и в реальной жизни. Никакие искажения от CRC32 не ускользают! "

2)"CRC16 гарантируется обнаружение практически всех одиночных и двойных ошибок, всех нечетных ошибок, всех пакетов ошибок длиной до 16 знаков, а также всех 17-битовых ошибок с вероятностью 0,999969 и более длинных пакетов ошибок с вероятностью 0,999984. При использовании CRC-32 только один из 4 294 967 296 (232) плохих пакетов может иметь правильную CRC."

3)"Properties of CRCs
Undoubtedly CRCs have many obscure properties that mathematicians could discuss for far too long. From a practical standpoint, the properties we are interested in are the ones dealing with error detection. All the common generator polynomials cited in this paper have the following properties (Tannenbaum, p211):

1. Detect all single bit errors.
2. Detect all occurrences of two single-bit errors for frames less than 2n-1 bits in length.
3. Detect all odd number of bits errors.
4. Detect all burst errors with a length less the n.
5. Detect all but 1/2n-1 burst errors of length n + 1.
6. Detect all but 1/2n other errors.

Where n = number of bits in CRC."

из п.6 следует, что в самом худшем случае вероятность необнаружения ошибки равна 1/2*n.

Исходя из всего этого, думаю попробовать использовать CRC16 (а не CRC32) для проверки целостности всего файла.

Как раз нужная глава:
http://lord-n.narod.ru/download/books/wall...emechanika.djvu

спасибо, буду вникать