Доброго времени суток.
Дано: протокольчик связи между устройствами в одномастерной сети. Некое сообщение из, допустим, 4-х байт, защищено CRC7. Поле адреса устройства считается при подсчете CRC7, но реально не передается. Принимающая сторона при приеме сообщения учитывает свой адрес при подсчете CRC, проверяя таким образом валидность.
Я понимаю, что передать сообщение в виде (адрес)-(данные)-(CRC) или (данные)-(CRC) - это две большие разницы. Кто в теме, подскажите, чем можно оценить вероятность приема ложного сообщения во втором случае.

ИМХО (не по научному):
если устройств на линии только два - то это равнозначные подходы. т.е. и там и там надёэность передаваемых данных будет подтверждаться CRC.
при не передаче адресса имеем:
1) лишний гимор по времени и алгоритму с детекцией наших данных. т.е. мы не можем до принятия всех данных, детекции конца фрэйма, подсчёт CRC и только после этого имеем признак свой-не свой. т.е. в скорострельных протоколах это решение фууууу.
2) на CRC возлагается не только задача подтверждения достоверности, но и механизма идентификации данных.
3) есть вероятность того, что при не правильном адрессе CRC совпадёт. при этом для сбоя необходимо испортить один байт. при передачи адреса - два.

где то так
(круглый)

Это понятно, интересует как раз по-научному, дабы узнать, больно это или нет Тем более, что подразумеваемый байт адреса является априори передаваемым без искажений, что изрядно напускает туману на

и лишая это утверждение смысла.

ЗЫ

Об этом я не говорил. И оно в реале не так - есть начало фрейма и его фиксированная длина. Такшта... Но к топику это не относится, да и вообще, священная корова модбас так и работает, как Вы сказали, и никто не жужжит.

Второй случай можно рассматривать как сообщение с вероятностью появления 8-кратной ошибки, что существенно превышает детектирующие возможности CRC. Т.е. даже без каких-либо ошибок при передаче сообщение может быть принято более другим приёмником за своё с вероятностью >> 0 (лень искать формулы).

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

ИМХО имелось ввиду, что CRC может совпадать у некоторых комбинаций первого байта.

Еще забыл важную деталь. Байт адреса(подразумеваемый), содержал адреса 0..127, т.к. 1 бит из байта, содержащего crc7 все-таки был частью информационного сообщения.

С ходу, естесно, ничего не нашлось. Пригрезилось, что было что-то во 2-м или 3-м томе Кнута, но под рукой они у меня в djvu и без оглавления.
CRC (с правильным полиномом) позволяет детектировать
- 2-кратные ошибки;
- любое нечётное количество ошибок;
- бурстовые ошибки длиной менее разрядности полинома.

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

А эксперимент Вам нужно провести, имхо, другой: для одних и тех же данных проверять совпадение CRC для всех адресов, и так 2^32 раза.

UPD
можно проще: проверить 255 чисел 0x010000000000..0xff0000000000 на целочисленную делимость на образующий полином, те, что делятся, выкинуть из множества адресов.

Ну, вообще-то 2^30 раз
Спасибо.

Ну давайте рассудим так, имеем посылку длиной m бит, имеем длину полинома n бит.

количество комбинаций на одну контрольную сумму k = m/(2^n)
вероятность, что одна переданная посылка исказилась так, что контрольная сумма передаваемой совпала с контрольной суммой приемника равно:
количество совпадающих сообщений разделить на общее количество возможных сообщений.

p = k/m, p = (m/(2^n))/m, p = 1/(2^n),
вот сам пишу и удивляет то, что длина сообщения не влияет на вероятность сбоя, а вот количество посылок за единицу времени будет ее существенно повышать, если кто найдет ошибку, поправите буду благодарен.

хочу немного поправить, p = k/m, p = ((2^m)/(2^n - 1))/(2^m), p = 1/(2^n - 1), k = (2^m)/(2^n - 1), но на общий результат существенно не влияет.
p = 1/(2^n - 1) - это у нас вероятность получения неверных данных без обнаружения ошибки, речь идет о одном пакете защищенном контрольной суммой n-разрядов.

для получения вероятности отказа за какой либо промежуток времени, считаете количество переданных пакетов например j и получаем

P = 1 - e^(j*ln(1-p))
после небольших преобразований:

P = 1 - (1 - p)^j

P = 1 - (1 - 1/(2^n-1))^j

для n = 8 получим и скоростью передачи 100 посылок в секунду за сутки получим:

1 - (1 - 1/(2^8 - 1))^100*60с*60мин*24часа = 1 - 1,4211728172713606486967518108355e-14744

вероятность отказа достаточно высока

тоже самое для n = 64 получим 4,6837533851989031228382687390855e-13

Ничего удивительного.
Штука в том, что обычно вероятности ошибок распределены совсем не равномерно. Какие-то классы ошибок CRC отлавливает всегда (однобитовые, например), и эти классы ошибок преобладают в определённых системах связи.
Поэтому реалистичный анализ обязан учитывать особенности распределения вероятностей ошибок.

Такое распределение было бы для случая непрерывной передачи битового потока.
Теперь, ближе к телу ©
у нас посылки по 8 бит , старт-бит==0 2стоп-бита==1. Плюс случайные задержки между пакетами.
Тут другое интересно. Вероятность неправильной интерпретации не зависит от длины сообщения. Но это - для переданых и принятых данных. А у нас - при подсчете ЦРЦ разные начальные значения сдвигового регистра. Это куда относить?

P = 1 - e^(j*ln(1-p))

j - обращу внимание на эту переменную, которая задает как раз количество пакетов.
Эта формула естественно приблизительная, оговорю принятые допущения.

1. Считаем, что на каждую контрольную сумму припадает с одинаковой вероятностью количество вариантов данных k = (2^m)/(2^n - 1), 2^m - возможные варианты данных, 2^n - 1 - возможные варианты контрольных сумм. Блин опять промазал вычитать единицу, нужно из числителя, то есть одна то комбинация входных данных является корректной, k = (2^m - 1)/(2^n), ну это большой разницы не сыграет.

2. В этой модели не учитываются вероятности отказов, предполагаются любые отказы (сбои) равновероятные.

p = (2^m - 1)/2^(n+m) - вероятность не обнаруженного сбоя одного пакета. для больших m справедливой будет P = 1 - (1 - 1/2^n)^j

P = 1 - (1 - (2^m - 1)/2^(n+m))^j

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

Если кратко, то экспериментально были получены следующие цифры:
CRC8 устойчив к ошибкам 1х,2х,3х и далее всем нечетным и пропускает каждую 130 ошибку 4х, 6х и выше
Если нужна математика, то выбирается наиболее подходящая модель для вашего случая, например классически
по ГОСТ 26.205-88 и т.д. Расчет есть чистая комбинаторика - берете количество сочетаний на данную ошибку
совместно с вероятностью бита или области кристалла (в зависимости от модели).
Например при вероятности ошибки одного бита 0.1, посылка 24 бит + CRC8 даст вероятность необнаруживаемого
искажения 2*10-3. Если канал связи более-менее, p=10-3, то необнаруживаемая ошибка при тех же данных составит
уже 2*10-10 и т.д.
Самое важное это выбор полинома четко под вашу задачу. Я на форуме уже выкладывал кое-какие мысли по этому
поводу, но повторюсь что русскому хорошо то немцу смерть - сталкивался с случаями неприменимости распространенных
полиномов, т.к. пропускают буквально веь мусор в канале.

Сообщение отредактировал i-mir - Mar 21 2011, 21:01