Доброго времени суток.
Дано: протокольчик связи между устройствами в одномастерной сети. Некое сообщение из, допустим, 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 и т.д.
Самое важное это выбор полинома четко под вашу задачу. Я на форуме уже выкладывал кое-какие мысли по этому
поводу, но повторюсь что русскому хорошо то немцу смерть - сталкивался с случаями неприменимости распространенных
полиномов, т.к. пропускают буквально веь мусор в канале.

Это как?

вместо
addr,byte1,byte2,byte3,byte4,crc
передаётся
byte1,byte2,byte3,byte4,crc

при сравнении на приёме вместо addr подставляется свой адрес девайса, который девайс ессно знает.

Ваше объяснение ничего не объясняет. Это просто некорректная переформулировка некорректного первоначального описания.

Устройство что, на шине одно, если "адрес не передается"? Если действительно так - тогда нет никакой разницы в вероятности пропуска ошибки.

Описание вполне ясное. Все всё поняли, кроме Oldring-а

Устройств много. А передавать адрес не обязательно, т.к. в алгоритмах девайсов с неправильным адресом CRC все-равно не совпадёт и пакет не будет "принят". Только у девайса с правильным адресом CRC совпадёт.

Тогда надо значительно увеличивать кодовое расстояние.
Вот с википедии характеристика CRC8:

CRC7 будет соответственно обнаруживать одинарные, двойные и тройные ошибки ВО ВСЁМ сообщении.
То есть, максимально имеем 3 бита на адрес, и при этом любая дополнительная ошибка может перевести сообщение в разряд "правильных" для неправильного адреса.
В общем, подход весьма скользкий.

Он "скользкий" так же как и сама CRC, когда незнакомый с ней человек с ней знакомится.
Там всё просчитывается. Не на супер компутере, а скорее на калькуляторе.
Непереданный байт адреса не является ошибкой. Потому как можно взять 8 бит адреса и так работать. Что уже противоречит ограничению в 3 бита.

Конкретные параметры топикстартер не указал, поэтому принимаю вариант предложеный GetSmart c CRC8.
Задача: сравнить вероятности необнаруживаемого искажения посылок 6 байт и 5 байт для CRC8.
Вероятность искажения одного бита в канале связи принимаем p=10-3. Тогда:
Для 48 бит p(crc8)=1.4*10-9
Для 40 бит p(crc8)=6.8*10-10
Вывод: если адрес не передавать, то надежность будет выше в два раза.
PS. Лень сейчас модельку переделать для CRC7, поэтому привожу готовое для CRC8.
Порядок цифр примерно тот-же.

Если устройств много, тогда передавать адрес как раз обязательно. Иначе устройства не поймут, к кому пакет адресован. И принимать обязательно. Но при расчете CRC в устройстве эти биты известны заранее. Дело нt в том, понял я или нет, дело в чёткости формулировок, необходимой для анализа.

Потому что если адрес передается, то ошибки в нём точно так же приводят к неправильному приёму пакета. А дальше многое зависит от количества устройств на шине и распределения их адресов. В крайнем случае 128 устройств на шине, пакеты к которым посылаются с равной вероятностью, всё сводится просто к оценке вероятности пропуска ошибки в пакете длиной 39 бит. На самом деле, не сильно выше, чем для пакета, длиной 32 бита, особенно, если ошибки приема битов в блоке могут коррелировать. Если же устройств сильно меньше 128, то дополнительным выбором хорошего распределения их адресов можно дополнительно снизить вероятность ошибочного приема адреса.

Это не верно.
Чёткая формулировка - при отсутсвии искажений в канале связи передавать адрес не обязательно. Устройства 100% поймут кому адресован пакет. CRC содержит адрес девайса точно так же как простейшая контрольная сумма например в HEX файле, если из HEX строки убрать первый байт.

При наличии ошибок вопрос стоит только в их кол-ве, при котором пакеты будут правильно приниматься. Причём относительно ситуации с присутствием адреса в пакете, то бишь классическим свойствам CRC.

При гарантированном отсутствии помех и CRC считать смысла нет. Подал адрес, и всё!
В том-то и задача, что топикстартер хочет и от помех перестраховаться, и длину передачи уменьшить. Я так не делал бы. Чем более избыточный код, тем больше ошибок будет обнаружено.
Хотя, если проверка сводится к байту CRC, то как раз будет менее достоверной информация для более длинного пакета. Но дело в том, что искажения одного байта адреса менее вероятны, чем искажения по всей длине пакета. Поэтому вероятность ложного принятия чужого пакета будет меньше.
Что, если из-за многобитовой ошибки устройство посчитает своим пакет, предназначенный не ему?

Тогда я вас совершенно не понимаю.
Два устройства сидят на шине. Адрес не передается. Как устройства понимают, кому адресован пакет?

Через (квази) обратное преобразование из CRC.

Даже ViKo всё понял и задал правильный вопрос.

Если адрес передаваемого сообщения отличается от адреса приёмника более чем в 3 битах, CRC не выявит ошибки.
Вот это я хотел сказать.
Отсюда и ограничение в 3 бита адреса, не считая дополнительных ошибок.
Или мы опять друг друга не поняли.

Ровно та же ситуация и с обычной CRC. Вопрос только в относительности надёжности.

почему "даже"?


Не та же ситуация. Я чуть выше подкорректировал свой ответ. Зависит от длины сообщения.

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

Вас кто-то ввёл в заблуждение что CRC не выявляет ошибки более 3 бит.



Поняли. На половину хотя бы.
Просто "пугает" неизвестность. Правильных цифр здесь пока не знает никто.
Результат может быть приемлемым. А может быть и нет.

В данном случае передавать адрес без всяких ЦРЦ будет намного надёжнее, чем выковыривать его косвенно при помощи дохленького ЦРЦ7.

Возвращаемся к истокам

Я исходил из поставленной задачи.
CRC7 не выявит больше 3 ошибочных бит на всё сообщение, это можете не сомневаться.
Вообще, за это время можно уже модельку накидать.
И увидеть всё наглядно.

Воды долили? Принципиально ничего не изменилось.


Насколько? Без цифр пустой разговор.

Не знаю какой у вас полином, но если вы тоже ещё не знаете - возьмите полином из (63,56) БЧХ кода с корнями 0, 1, то есть примитивный двоичный полином степени 6, умноженный на полином x+1. У него минимальное расстояние будет равно 4. Вероятность пропуска ошибок при белом шуме с вероятностью ошибки одного бита p будет порядка (21*p)^4 для 128 устройств на шине, или порядка (17*p)^4 для одного устройства на шине. Вероятность пропуска полностью случайного блока будет N/16384, где N - число устройств на шине.



Для полного диапазона адресов в 128 устройств абсолютно бессмыссленное занятие. Вероятность неправильного приема не отличается от просто передачи 7 бит адреса вместо поля CRC.

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


А более точно можно посчитать только с учетом реального распределения кодовых слов, но результат кардинально хуже нормального дополнительного СRС поля и передаваемого адреса на белом шуме, и существенно хуже для полностью случайных блоков.

Но можно кое-что оценить исходя из 7 бит на адрес плюс проверку. Для двух устройств у нас остается один бит адреса и 6 бит проверочных, что позволяет использовать код Хэмминга с минимальным расстоянием 3 и еще довольно низкой вероятностью необнаружения одиночных ошибок. Для 2 бит адреса остается 5 проверочных бит, то есть двоичный циклический код неизбежно будет пропускать некоторые двойные ошибки. Однако можно получить линейный код с расстоянием 2 из кода Хэмминга длиной 63, выкинув, в том числе, 1 проверочный бит. Уже для 3 бит адреса такой метод гарантированно оставляет расстояние лишь 1, что бессмыссленно по сравнению с просто контролем четности.



Спорим, выявит 6 указанных мною ошибочных бит?

Кто сказал что диапазон адресов = 128? Паша вроде байт хотел сэкономить.

Но вообще, прошу заметить, что идея не моя Мне как и ТС любопытен был ответ в количественном виде.

Без знания вероятности искажений одиночного бита в канале связи ответ никогда не узнать.
А также - пары битов, тройки битов, четверки битов, и т.д.
А что, если имеется помеха, приводящаа к полному затыку канала на весь интервал передачи?

Передаем 4 байта. Один бит исказился. Сообщение ошибочное. 256 устройств высчитали CRC, добавив свой адрес. У кого-то CRC совпадет.
(В-принципе, CRC не обязательно у кого-то должен совпасть, но очень вероятно. Для этого, собственно, CRC и создан. Чтобы для любых даже слабо отличающихся кодов создать сильно отличающийся результат. Поэтому, представив, что результат вычисления CRC будет иметь равномерную плотность вероятности, получить можно любой код.)

Засчёт более короткого сообщения (по сравнению с махlen=127)? Возможно.
Под рукой таблиц нет, искать некогда.
Поверю на слово.


Лучше бы сказал, для чего он это хотел.

Странно, ведь задача не поставлена - а вы хотите в цифрах ответ.
Из-за этого куча шума на ветке, хотя вопрос далеко не сложный.
Мало того, можно и абсолютный уровень по безопасности вывести
для наиболее тяжелого условия работы канала связи (например
включаем рядом дрель, усиливаем и XOR в канал).
Все эти модели есть и прекрасно работают. Но для получения
ответа дайте корректное условие в цифрах.

За счет того, что любой систематический циклический код обнаруживает бурсты ошибок длиной, не превышающей его количества проверочных бит.

Для того и хотел, имхо. Укоротить длину сообщения.

Если нетрудно, ткните носом, где это написано. Полазил-полазил по википедии - не нашёл.
Меня заинтересовал вопрос зависимости оптимально применимой длины поля CRC от длины пакета. Т.е. для каких длин пакетов применяется CRC8, для каких CRC16 и т.д. Хотя бы "среднепотолочные" цифры, для распространённого случая.
Если кто знает, пошлите, пожалуйста, по ссылке )))

В свое время писал об этом.
http://electronix.ru/forum/index.php?s=&am...st&p=898290

ПС. Википедия не дает и не может давать глубоких ответов - только стартовую точку ...

Есть там.
Надо развернуть "плюсики" с приведёнными примерами.
Ну а если хотите серьёзно разобраться - это надо литературу читать.
Я в своё время диплом писал по корректирующим кодам, больше всего пользы извлёк из 500-страничной книжки с красной обложкой, автор какой-то японец.
То ли Токура, то ли что-то в этом роде...
Не эта ли?
Блин, а я в читальном зале часами сидел, домой не выдавали такие раритеты...

Вот ещё...

Ну и далее в том же духе.

До кучи

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



Если будет хоть немного конкретики - можно ответить на вопрос, предложить хороший полином,
проанализировать помехоустойчиовсть и т.д. Что передается, в каком объеме, в каких
условиях, требования к надежности/безопасности и т.д. ?

Конкретика: мы "от фонаря" порешали, что заголовок пакета специфического устройства размером 32 байта закрываем 8-битовой CRC, а поле данных длиной до 2 кБ закрываем 16-битовой CRC. Теперь, прочитав эту тему, я начинаю покусывать локти, что и там, и там, мы заложили недостаточный размер CRC, т.е. могу предположить, что надо было 16 бит и 32 бита соответственно.
Далее после добавления CRC весь пакет передаётся в канал, закодированный в 8B/10B. Канал связи - не радио, а проводной. Может быть либо медь, либо оптика. Медь - не более 3 метров, LVDS, по UTP. Оптика - до 2 км. По закону распределения ошибок в канале такого типа - сказать ничего не могу, т.к. мои познания в этом малы. Могу довериться вашему опыту.

Все равно нужно от чего-то оттолкнуться если нет экспериментальных данных.
Например ГОСТ 26.205-88 КОМПЛЕКСЫ И УСТРОЙСТВА ТЕЛЕМЕХАНИКИ, п.2.11.2.
Укажите согласно ГОСТу требования к вашему устройству на каналы связи.
Если это устройства "критического использования" - то нужно использовать
другие отраслевые документы.

После этого можно будет прикинуть помехозащищенность вашего протокола
и его соответствие требованием. Если уровень защиты CRC "в лоб" будет не
высоким, тогда рассматриваются другие типы кодирования.
Скажите в чем необходимость 8B/10B ? Выравнивание потока 0/1 для оптики ?

В качестве примера, для очень зашумленного канала (р=10е-3) вероятности
необнаруживаемого пропуска ошибок CRC8/16 привел на рис. Видно что
заголовок у вас защищен в три раза лучше чем поле данных.
Абсолютные значения вероятностей будут зависить от исходных данных
и выбранных вами требований.

Уважаемый i-mir, спасибо за конкретную помощь.
Спасибо за ГОСТ. Думаю, категория 3я, ну максимум 2я. Не критического использования. Внутри поля данных этого пакета будут инкапсулированы пакеты других протоколов, у них будет своя защита от ошибок. К тому же ещё 8B/10B часть ошибок выловит. Он ловит все единичные ошибки в пределах одного символа.

Да, устранение постоянной составляющей, самосинхронизация битов и байтовая синхронизация.

У меня здесь следующие непонятности:
1. Где Вы взяли такие графики? Их считает программа? А Вы могли бы ей поделиться?
2. Может быть, более наглядно было бы построить графики для той же вероятности, что фигурирует в ГОСТе (т.е. 1e-4)?
3. "вероятности необнаруживаемого пропуска ошибок" - этот термин какому соответствует в табл. 3 ГОСТа?
4. Как Вы рассчитали, что в 3 раза лучше заголовок защищён? Я смотрю на графики, там для CRC8 для длины 32 байта вероятность неотличима от нуля. Или это для длины в битах? Тогда для графика CRC16 нет данных для длины 2 кБ. В любом случае вижу, что защищённость поля данных никакая...
5. Как вообще трактовать такую вероятность? Это обратная величина от среднего количества пакетов, спустя которые ошибка в одном пакете не будет обнаружена? Например, смотрим на график для CRC8, для значения длины 256 (попугаев), вероятность 2,5e-5. Обратная величина это 40 000. Т.е. правильно ли я понимаю, что, 40 000 пакетов принимаются, если в них появляется ошибка, то она обнаруживается, а потом 40 001-й пакет проходит, и в нём ошибка не обнаруживается? Или как правильно трактовать?
Извиняюсь за глупые вопросы, в этом мои знания неглубоки, а вузовский курс тервера давно благополучно забыт, к сожалению.

Вероятность ошибки обычно считается на бит.
256 - длина блока в битах, то есть 32 байта.

Ну я так и предположил, что в битах. Но для сути 5го вопроса (трактование) это неважно, в каких попугаях измерять