Простой вопрос по защите данных с помощью CRC Опции

[_Pasha]

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

[kolobok0]

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

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

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

[_Pasha]

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

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

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

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

ЗЫ

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

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

[xemul]

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

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

[_Pasha]

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

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

[GetSmart]

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

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

[_Pasha]

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

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

[xemul]

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

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

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

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

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

[_Pasha]

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

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

[DW0]

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

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

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

[DW0]

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

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

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

[_Pasha]

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

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

[DW0]

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

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]

Если кратко, то экспериментально были получены следующие цифры:
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

[Oldring]

Поле адреса устройства считается при подсчете CRC7, но реально не передается.

Это как?

[GetSmart]

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

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

[Oldring]

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

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

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

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

[GetSmart]

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

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

[MrYuran]

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

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

MaxLen: 15 байт (127 бит) - обнаружение
одинарных, двойных, тройных и всех нечетных ошибок

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

[GetSmart]

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

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

[i-mir]

Конкретные параметры топикстартер не указал, поэтому принимаю вариант предложеный 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.
Порядок цифр примерно тот-же.

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

[Oldring]

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

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

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

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

[GetSmart]

...Иначе устройства не поймут, к кому пакет адресован.
...Дело на в том, понял я или нет, дело в чёткости формулировок, необходимой для анализа.

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

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

Сообщение отредактировал GetSmart - Mar 22 2011, 09:38

[ViKo]

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

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

[Oldring]

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

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

[GetSmart]

Как устройства понимают, кому адресован пакет?

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

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

[MrYuran]

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

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

[GetSmart]

Что, если из-за многобитовой ошибки устройство посчитает своим пакет, предназначенный не ему?

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

[ViKo]

Даже ViKo всё понял...

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

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

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

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

[GetSmart]

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

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

Или мы опять друг друга не поняли.

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

[MrYuran]

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

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

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

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

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

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

[GetSmart]

Я чуть выше подкорректировал свой ответ.

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

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

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

[Oldring]

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

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

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

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

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


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

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

CRC7 не выявит больше 3 ошибочных бит на всё сообщение, это можете не сомневаться.

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

[GetSmart]

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

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

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

[ViKo]

Мне как и ТС любопытен был ответ в количественном виде.

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

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

[MrYuran]

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

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

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

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

[i-mir]

Мне как и ТС любопытен был ответ в количественном виде.

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

[Oldring]

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

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

[ViKo]

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

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

[Krys]

Вот с википедии характеристика CRC8:

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

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

[i-mir]

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

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

Сообщение отредактировал i-mir - Apr 26 2011, 05:47

[MrYuran]

Если нетрудно, ткните носом, где это написано. Полазил-полазил по википедии - не нашёл.

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

Вот ещё...

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

[_Pasha]

До кучи

[i-mir]

Есть там. Надо развернуть "плюсики" с приведёнными примерами.

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

Хотя бы "среднепотолочные" цифры, для распространённого случая.

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

[Krys]

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

[i-mir]

По закону распределения ошибок в канале такого типа - сказать ничего не могу

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

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

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

Сообщение отредактировал i-mir - Apr 27 2011, 14:30

Эскизы прикрепленных изображений

 

Прикрепленные файлы

 _____26_205_88.pdf ( 983.09 килобайт ) Кол-во скачиваний: 998

 

[Krys]

Уважаемый i-mir, спасибо за конкретную помощь.

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

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

Скажите в чем необходимость 8B/10B ? Выравнивание потока 0/1 для оптики ?

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

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

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

[MrYuran]

5. Как вообще трактовать такую вероятность? Это обратная величина от среднего количества пакетов, спустя которые ошибка в одном пакете не будет обнаружена? Например, смотрим на график для CRC8, для значения длины 256 (попугаев), вероятность 2,5e-5.

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

[Krys]

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

[i-mir]

Проблема как раз в другом, и заключается в вопросе - чего вы собственно хотите?
Если у вас есть требования предъявляемые заказчиком - давайте обсудим.
Ели требований нет - тогда можно взять из ГОСТа любые понравившиеся.
Отсюда проблемы в трактовке и анализе уровня помехозащищенности.
На рис. приведены относительные уровни - для того чтобы показать лишь принцип.
Выводов может быть несколько:
1. Нет смысла дробить защиту на заголовок и тело в предложеном виде
2. Если уровня защиты хватит - можно остановиться лишь на общем CRC16
3. Для случая "обычного канала связи" где p=10е-4, P=7.4е-8 (для 2304 бит)
и вы попадаете в 3-ю колонку изделий по ГОСТ 26.205-88 , табл.3
4. Если уровня защиты не хватит - это предмет для обсуждения, но тогда
укажите подробнее о задаче.
5. Если у вас есть желание привести цифры к интенсивностям отказов (1/час)
и т.д. - тема отдельного разговора
6. Здесь все то что не вошло в предыдущие пять пунктов ...

PS. Прошу прощения - не увидел что речь идет именно о 2048 байтах данных,
это уж слишком большой блок для CRC16 по определению....
Вам нужно обратиться к стандарту Ethernet IEEE 802.3 (CRC32) в любом случае.







Сообщение отредактировал i-mir - Apr 29 2011, 06:15

[Krys]

6. Здесь все то что не вошло в предыдущие пять пунктов ... :)

Спасибо за ответы, я для себя в общем-то всё прояснил. Заголовок будем продолжать закрывать CRC8, а а для поля данных изменим CRC16 на CRC32. Тем более, что лишние 2 байта - это ничто по сравнению с 2048 байт, так что не жалко.

1. Нет смысла дробить защиту на заголовок и тело в предложеном виде

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

6. Здесь все то что не вошло в предыдущие пять пунктов ... :)

А всё же, по моему списку, не могли бы Вы разъяснить ответы на вопросы 1, 3, 5?

[i-mir]

Как ни банально звучит, в чистом виде ответов ни в инете ни в книгах нет.
Теорий и формул много, но на практике, с приемлемой точностью можно
использовать простую комбинаторику. Здесь принимается модель
последовательного канала связи с простейшим потоком ошибок (пуассонов).
Для работы например с ПЛИС, следует использовать другую модель,
где равновероятны любые сочетания и т.д.

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

Относительно вероятностей - нужно понимать опять-же что вам нужно.
Если задача привести ваш канал связи к уровню стандартов в системах
с повышенной безопасностью (интенсивность 10е-15 1/час), то это одно,
а вот просто сказать - что все ок, это другое. В последнем случае не
заморачиваясь, принимайте CRC32 на базе IEEE 802.3 - это общепринято,
правда для блоков до 1500 байт.

Остальные вопросы заданы в общем виде и слишком объемны для рамок форума.
Чтобы понять какой вам нужен уровень защищенности ответьте на вопрос:
достоточна ли защита блока данных от всех ошибок нечетных кратностей (1х, 3х, 5х ...),
защита от всех ошибок 2х кратности и защита от 129 ошибок из 130 кратности 4х, 6х ... ?
Это уровень обеспечивается CRC8. Под ошибками понимаем инверсию битов в блоке данных.
Пока не понятны ваши критерии оценки, как только они определятся, можно решить
задачу о требуемом протоколе канала связи.

[Krys]

Ладно, сдаюсь, применяем CRC32, и успокаиваемся. Особенно учитывая, что ещё будет снаружи 8B/10B. Остальные вопросы снимаю.

[i-mir]

8B/10B больше актуален для оптики в качестве выравнивателя потока 0/1 и имеет слабую помехозащищенность,
в среднем улучшение в 4 раза. Если особых требований нет, то конечно CRC32 + несложная доп. защита наиболее
ответственных блоков данных (поле адреса, поле управления и т.д.) с помощью CRC8.

[artix]

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

почитайте сообщение пользователя i-mir, возможно поможет
http://electronix.ru/forum/index.php?showt...%F1%F3%EC%EC%E0