[_Pasha 0]

Доброго времени суток.

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

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

[kolobok0 0]

... (адрес)-(данные)-(CRC) или (данные)-(CRC) - это две большие разницы.....чем можно оценить вероятность приема ложного сообщения во втором случае.

 

 

ИМХО (не по научному):

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

при не передаче адресса имеем:

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

2) на CRC возлагается не только задача подтверждения достоверности, но и механизма идентификации данных.

3) есть вероятность того, что при не правильном адрессе CRC совпадёт. при этом для сбоя необходимо испортить один байт. при передачи адреса - два.

 

где то так

(круглый)

[_Pasha 0]

ИМХО (не по научному):

***

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

3) есть вероятность того, что при не правильном адрессе CRC совпадёт. при этом для сбоя необходимо испортить один байт. при передачи адреса - два.

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

:)

ЗЫ

мы не можем до принятия всех данных, детекции конца фрэйма

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

[xemul 0]

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

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

[_Pasha 0]

(лень искать формулы).

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

[GetSmart 0]

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

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

[_Pasha 0]

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

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

[xemul 0]

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

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

CRC (с правильным полиномом) позволяет детектировать

- 2-кратные ошибки;

- любое нечётное количество ошибок;

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

 

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

 

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

 

UPD

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

[_Pasha 0]

и так 2^32 раза. :)

Ну, вообще-то 2^30 раз :)

Спасибо.

[DW0 0]

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

 

количество комбинаций на одну контрольную сумму k = m/(2^n)

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

количество совпадающих сообщений разделить на общее количество возможных сообщений.

 

p = k/m, p = (m/(2^n))/m, p = 1/(2^n),

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

 

[DW0 0]

Ну давайте рассудим так, имеем посылку длиной 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

 

[scifi 1]

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

Ничего удивительного.

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

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

[_Pasha 0]

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

Такое распределение было бы для случая непрерывной передачи битового потока.

Теперь, ближе к телу ©

у нас посылки по 8 бит , старт-бит==0 2стоп-бита==1. Плюс случайные задержки между пакетами.

Тут другое интересно. Вероятность неправильной интерпретации не зависит от длины сообщения. Но это - для переданых и принятых данных. А у нас - при подсчете ЦРЦ разные начальные значения сдвигового регистра. Это куда относить? :cranky:

[DW0 0]

Такое распределение было бы для случая непрерывной передачи битового потока.

 

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 должна равняться количеству пакетов за переданных год.

[i-mir 0]

Если кратко, то экспериментально были получены следующие цифры:

CRC8 устойчив к ошибкам 1х,2х,3х и далее всем нечетным и пропускает каждую 130 ошибку 4х, 6х и выше

Если нужна математика, то выбирается наиболее подходящая модель для вашего случая, например классически

по ГОСТ 26.205-88 и т.д. Расчет есть чистая комбинаторика - берете количество сочетаний на данную ошибку

совместно с вероятностью бита или области кристалла (в зависимости от модели).

Например при вероятности ошибки одного бита 0.1, посылка 24 бит + CRC8 даст вероятность необнаруживаемого

искажения 2*10-3. Если канал связи более-менее, p=10-3, то необнаруживаемая ошибка при тех же данных составит

уже 2*10-10 и т.д.

Самое важное это выбор полинома четко под вашу задачу. Я на форуме уже выкладывал кое-какие мысли по этому

поводу, но повторюсь что русскому хорошо то немцу смерть - сталкивался с случаями неприменимости распространенных

полиномов, т.к. пропускают буквально веь мусор в канале.

Изменено 21 марта, 2011 пользователем i-mir