Прошу помощи по CRC

[e2e4]

Вот такая ситуация: передается пакет из n-байт (в байте - 8 бит) по последовательному каналу связи. В конце пакета - CRC. Подскажите, как там по теории, на сколько в среднем пакетов придется один пакет с нераспознанной ошибкой?
Я для себя прикидываю так:
вероятность ошибки в байте пакета - O
Кол-во бит в CRC - B
Кол-во полезныйх байт в пакете (защищенных CRC) - n

имеем вероятность ошибки в полезной информации: O*n
Вероятность ошибки в CRC: O*B/8
Вероятность того, что ошибка в CRC позволит нераспознать ошибку в данных: $\frac{1}{2^B}$
Итого: $O*n*O*\frac{B}{8}*\frac{1}{2^B}$
Прикидка грубая, но в целом - прав ли я?

[незваный гость]

Давайте разбираться. Пусть вероятность ошибки при передаче одного бита информации $p \ll 1$, длина полезной части пакета (payload) $n$ бит, а длина контрольной суммы $c$ бит.

Теперь начинаются предположения, которые важны для ответа:

1) Мы считаем все ошибки равновероятными. Это не обязательно правда. Например, канал может иметь тенденцию перекидывать 1 в 0, но не наоборот (то есть, $p\{1 \to 0\} > p\{0 \to 1\}$). Или вероятность ошибки может расти к концу сообщения (сказывается разница в тактовой частоте кристаллов, задающих синхронизацию). В общем, много чего может быть...

2) Конструкция (характеристики) контрольной суммы. Длина — это хорошо, а вот свойства — это вопрос отдельный. Например, алгоритм может гарантировать нахождение различного числа ошибок (причем произвольное наперед заданное число). Назовем порядком контрольной суммы среднее число ошибок $E \leqslant c$, которое он может обнаружить (очевидно, что среднее не меньше гарантированного, но как его вычислить — вопрос отдельный). Более того, это среднее может зависеть от длины сообщений (например, все «портящие статистику» случаи могут иметь слишком большую для практики длину).

3) Контрольные суммы неравномерно определяют ошибки: некоторые лучше, некоторые хуже. То есть, некоторые пакеты более удобны для «охраны», чем другие. Мы предполагаем однородность потока.

~~~

На вскидку:
Ошибка не будет обнаружена, если произошло более $E$ ошибок при передаче сообщения. Вероятность, что произошло ровно $k$ ошибок равна $C_{n + c}^{k} p^{k}{(1-p)}^{n+c-k}$, и, соответственно, имеем $p_{undetected} = 1 - \sum_{k \le E}C_{n + c}^{k} p^{k}{(1-p)}^{n+c-k} = $ $ \sum_{k > E}C_{n + c}^{k} p^{k}{(1-p)}^{n+c-k} $

~~~
Длина контрольной суммы, как видите, явно не участвует. Она опосредована через $E$.

P.S. Надеюсь, PAV увидит и поправит меня. Например, дополнит случай нецелого $E$.

[e2e4]

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

Цитата:

Пусть вероятность ошибки при передаче одного бита информации $$p \ll 1$

В общем случае это не так. Я зачастую работаю с каналами, где вероятность ошибки в одном байте - 1/10 (вычислено экспериментально). Бит в байте 8 + стартовый, 1 стоповый. Соответственно для бита - 1/100. Не так уж и мало.

Цитата:

Мы считаем все ошибки равновероятными.

Да.

Цитата:

Конструкция (характеристики) контрольной суммы.

CRC - это есть

Википедия писал(а):

CRC (англ. cyclic redundancy check) — проверка избыточности циклической суммы. Способ цифровой идентификации некоторой последовательности данных, который заключается в вычислении контрольного значения её циклического избыточного кода.

Я использую 8, 16, 32 бит CRC с нормальными (правильными) образующими полиномами.

[PAV]

Я не очень это все помню/знаю....

Конечно же, зависит и от того, насколько равномерно распределены в пространстве сообщения с одинаковым CRC, и от того, какова модель искажений. Сказать, что с некоторой информацией искажен байт - мало, правильнее работать с отдельными битами. Точнее так: можно ли утверждать, что при условии того, что в байте произойдет ошибка, распределение вероятностей искаженного байта равномерное или все-таки шанс, что мы попадем в "близкий" байт сильно выше?

Возьмем некоторые прикидки. Пусть мы хотим защитить $n$ байт и для простоты используем 8-бит CRC. Какова вероятность пропустить ошибку при условии того, что искажен ровно один байт?

Количество сообщений, отличающихся от нашего ровно в одном байте, равно $255n$. Примем что все они равновероятны (это не очень правильно). Поскольку всего значений CRC у нас 256, то в среднем можно ожидать, что примерно с вероятностью $\frac{1}{n}$ мы получим ошибку.

На самом деле если рассмотреть "большие" искажения, то так примерно и будет. Но если принять, что искажаются все-таки биты, то априорная вероятность получить "большое" искажение очень мала и этот член существенно не влияет. А вблизи нашего сообщения все не так, поскольку при равномерности CRC шанс получить именно такую CRC вблизи нашего сообщения мал.

Если исказится ровно 1 бит, то почти уверен, что CRC всегда будет различная. Отсюда следует, что для 2 бит (и достаточно большого $n$) уже не так, а для большего числа искажаемых бит тем более. Я очень сильно уверен, что при числе реально искажаемых бит порядка длины CRC мы уже будем наблюдать практически вероятность ошибки равную отношению длины сообщения к длине CRC (1/n в том, что я писал ранее).

Оценить можно в принципе методами, которыми строятся оценки для объемов кодов, исправляющих ошибки. Но для большей простоты (и одновременно большей надежности) можно провести статистическое моделирование. Только делать это нужно умно. Потребуется модель ошибок. Для наиболее естественного случая когда биты искажаются независимо с малой вероятностью нужно отдельно моделировать искажение ровно 1 бита, двух, трех и т.д. Моделирование покажет нам (достаточно точно) условную вероятность ошибки при условии искажения ровно заданного числа битов. Далее мы можем теоретически рассчитать априорные вероятности таких искажений и по формуле полной вероятности найти настоящую вероятность ошибки. При этом начиная с некоторого шага, когда априорная вероятность такого искажения станет пренебрежимо малой, ею можно пренебречь.

Нужно также помнить, что искажения нужно применять не к исходному сообщению (длины n), но к полному (включая CRC).

[незваный гость]

e2e4 писал(а):

CRC - это есть

Не все, что в Wiki, есть истина в последней инстанции.

1) CRC (cyclic redundancy check) строится следующим образом:
crc' = (crc ROT 1) + word, где ROT — это операция циклического сдвига (с переносом вытесняемого разряда в освободившийся бит), а word — слово данных (байт, два байта,…) Появилась она еще на до-байтовых компах, так что слово могло быть и 45 бит…

2) сейчас CRC практически не употребляется, и ее место заняла CS (checksum, контрольная сумма). Здесь уже алгоритм произволен, и то, что употребляете Вы называется контрольной суммой по праву. Я, впрочем, каюсь, грешен, и использую CRС и CS как синонимы. Пример другой эффективной CS — adler32.

3) Существует прямая связь между контрольной суммой и дайджестом сообщения в криптографии. Функция у них идентична, но вот критичность ошибки разная. Потому в криптографии не скупятся на вычислительные ресурсы при построении и проверке, а также при анализе свойств… Для Ваших же целей такие затраты, скорее всего, не оправданы: канал не будет «подделывать» данные, поэтому любое совпадение случайно.

e2e4 писал(а):

Я использую 8, 16, 32 бит CRC с нормальными (правильными) образующими полиномами.

По определению Вашей контрольной суммы: фактически, все сообщение рассматривается как очень большое число M (размещенное в последовательных байтах), а $cs = M \mod m_p$. Соответственно, поскольку $2^{\varphi(m_p)}-1 \equiv 0 (\!\!\!\mod m_p)$, мы привели пример необнаруживаемой ошибки (о $\varphi(m_p)$ битах). А вот для того, чтобы убедится, что они всегда обнаруживают 2 ошибки, надо проверить, что $\forall k: 2^k+1 \not \equiv 0 (\!\!\!\mod m_p)$ (я, впрочем, думаю, что это верно...)

Я думаю, можно найти и другие полезные для анализа свойства, надо только поискать (и задуматься, как применить — проклятая комбинаторика).

[e2e4]

PAV писал(а):

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

Шанс, что мы попадем в "близкий" байт сильно выше.

PAV писал(а):

Количество сообщений, отличающихся от нашего ровно в одном байте, равно 255n. Примем что все они равновероятны (это не очень правильно). Поскольку всего значений CRC у нас 256, то в среднем можно ожидать, что примерно с вероятностью 1/n мы получим ошибку.

Согласен.

PAV писал(а):

Но если принять, что искажаются все-таки биты, то априорная вероятность получить "большое" искажение очень мала и этот член существенно не влияет. А вблизи нашего сообщения все не так, поскольку при равномерности CRC шанс получить именно такую CRC вблизи нашего сообщения мал.

Согласен.

PAV писал(а):

Если исказится ровно 1 бит, то почти уверен, что CRC всегда будет различная.

Согласен, при условии здравомыслимой длины пакета.

PAV писал(а):

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

Исходя из этих же соображений, написана формула в моем первом сообщении. Там, правда, вероятность ошибки в байте в квадрате, в чем я не очень уверен, и сейчас думаю, что это ошибка.

PAV писал(а):

можно провести статистическое моделирование. Только делать это нужно умно. Потребуется модель ошибок. Для наиболее естественного случая когда биты искажаются независимо с малой вероятностью нужно отдельно моделировать искажение ровно 1 бита, двух, трех и т.д. Моделирование покажет нам (достаточно точно) условную вероятность ошибки при условии искажения ровно заданного числа битов.

Однако, посчитайте, сколько времени займет моделирование для пакета, скажем, 32 байта? (32*8)! чтоли?

PAV писал(а):

Нужно также помнить, что искажения нужно применять не к исходному сообщению (длины n), но к полному (включая CRC).

Согласен.

незванный гость писал(а):

Не все, что в Wiki, есть истина в последней инстанции.

1) CRC (cyclic redundancy check) строится следующим образом:
crc' = (crc ROT 1) + word, где ROT — это операция циклического сдвига (с переносом вытесняемого разряда в освободившийся бит), а word — слово данных (байт, два байта,…) Появилась она еще на до-байтовых компах, так что слово могло быть и 45 бит…

2) сейчас CRC практически не употребляется, и ее место заняла CS (checksum, контрольная сумма). Здесь уже алгоритм произволен, и то, что употребляете Вы называется контрольной суммой по праву. Я, впрочем, каюсь, грешен, и использую CRС и CS как синонимы. Пример другой эффективной CS — adler32.

1. CS - это есть контрольная сумма.
2. CRC - это есть определенный общепринятый алгоритм, который является частным случаем контрольной суммы.
3. Сейчас понятие CRC, также как и сам CRC употребляются повсеместно. Возьмите арихиваторы ZIP и RAR, возьмите связь по последовательным асинхронным интерфейсам. Я лично не знаю более сильного метода защиты информации с помощью такого маленького объема доп. данных.
4. Когда я задавал вопрос о вероятности необнаружения ошибочного пакета, я имел ввиду прикидочную ф-ию f(n,n_CRC), где n - кол-во полезных байт в пакете, n_CRC - кол-во байт в CRC.
5. Определение байта не ограничено 8-ю битами. Сошлюсь опять же на ту же Википедию:

Википедия писал(а):

Байт (англ. byte) — единица измерения количества информации, обычно равная восьми битам (в этом случае может принимать 256 (2^8) различных значений).

Вообще, байт — это минимально адресуемая последовательность фиксированного числа битов. В современных компьютерах общего назначения байт равен 8 битам.

CRC, естественно, может иметь произвольное число бит. Однако, в на практике широко применяются именно 8, 16, 32 - бит CRC, ибо это удобнее всего при работе с 8-битовыми байтами.

Добавлено спустя 7 минут 29 секунд:

незванный гость писал(а):

Существует прямая связь между контрольной суммой и дайджестом сообщения в криптографии. Функция у них идентична, но вот критичность ошибки разная. Потому в криптографии не скупятся на вычислительные ресурсы при построении и проверке, а также при анализе свойств… Для Ваших же целей такие затраты, скорее всего, не оправданы: канал не будет «подделывать» данные, поэтому любое совпадение случайно.

Такие затраты для моих целей не только неоправданны, но и невозможны. Обработка принятого сообщения происходит в прерывании, кол-во сообщение в секунду - от 60 до 3000. Канал данные не подделывает. Мне необходимо оценить средняя время, при котором я пропущу ошибочный пакет (это время зависит, ессесно от скорости передачи, как кстати, и вероятность ошибки). Разделю это время на 10, для надежности.
Тогда, я выбиру приемлемую скорость передачи, кол-во байт на сообщение и т.п., чтобы заведомо эта ошибка не происходила в среднем за все время работы устройства. При этом мне не придется заморачиваться такими вещами, как принятие к действию неверной информации.

незванный гость писал(а):

Я думаю, можно найти и другие полезные для анализа свойства, надо только поискать (и задуматься, как применить — проклятая комбинаторика).

Именно в этом и заключается сложность .

[PAV]

e2e4 писал(а):

Однако, посчитайте, сколько времени займет моделирование для пакета, скажем, 32 байта? (32*8)! чтоли?

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

Возможно, что если проанализировать формулу для вычисления CRC, то можно понять, при каком условии на искажения битов произойдет ошибка передачи и посчитать (или оценить) ее более точно.

[незваный гость]

Во-первых, относитесь cum granum salis к информации в Википедии. Она Вас очередной раз подводит: такое «обобщенное» определение байта не является общепринятым. 45-битное слово (БЭСМ-4) никто и никогда не называл байтом, поверьте. Несмотря на то, что оно было минимально адресуемой единицей памяти.

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

В-третьих, Вы не будете любезны опубликовать свои полиномы?

e2e4 писал(а):

PAV писал(а):

Если исказится ровно 1 бит, то почти уверен, что CRC всегда будет различная.

Согласен, при условии здравомыслимой длины пакета.

Одиночная ошибка диагностируется при любой длине пакета.

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

P.S. Некоторый анализ приводится в статье Wikipedia. См. «во-первых»

[e2e4]

незваный гость писал(а):

:evil:
Во-первых, относитесь cum granum salis к информации в Википедии. Она Вас очередной раз подводит: такое «обобщенное» определение байта не является общепринятым. 45-битное слово (БЭСМ-4) никто и никогда не называл байтом, поверьте. Несмотря на то, что оно было минимально адресуемой единицей памяти.

Незванный гость, прошу вас, вы придираетесь к пустякам, причем, зная вас по общению в данном форуме, я уверен, что вы понимаете, о чем идет речь, и все равно придираетесь... В байте может быть произвольное число бит. Распространенные реализации UART подразумевает байт с переменной длиной (от 4 до 9). Я склонен полностью соглашаться с определением Вики, а именно: байт есть минимальное адресуемое кол-во информации АЛУ (шиной, АУ) процессора.

Цитата:

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

Но они пишут CRC в документации. Я им верю. Если же они под CRC подразумевают вовсе не CRC, это их проблемы. CS есть CS, CRC есть CRC.

Цитата:

В-третьих, Вы не будете любезны опубликовать свои полиномы

Буду, но завтра.

[незваный гость]

e2e4 писал(а):

Я склонен полностью соглашаться с определением Вики,

Это Ваше право. (Я, кстати, нигде не настаивал на восьмибитности байта.)

e2e4 писал(а):

Но они пишут CRC в документации. Я им верю.

Козьма Прутков писал(а):

106. Если на клетке слона прочтешь надпись «буйвол», не верь глазам своим.

Правда, сомневаюсь, что неточное употребление термина кем бы то ни было может обосновывать незнание точного смысла термина (или, по меньшей мере, истории термина). Кроме того, не подвел ли Фила Каца (Phil Katz) английский язык ? Там, как Вы знаете, «пишется Ливерпуль, а читается Манчестер» .

[e2e4]

Для 16-битового CRC я использую 0x1021
Для 8-битового число осталось на работе, если будет интересно - посмотрю в пн.

Добавлено спустя 2 часа 56 минут 13 секунд:

незваный гость писал(а):

:evil:

e2e4 писал(а):

Я склонен полностью соглашаться с определением Вики,

Это Ваше право. (Я, кстати, нигде не настаивал на восьмибитности байта.)

Цитата ваша:

незваный гость писал(а):

Во-первых, относитесь cum granum salis к информации в Википедии. Она Вас очередной раз подводит: такое «обобщенное» определение байта не является общепринятым. 45-битное слово (БЭСМ-4) никто и никогда не называл байтом, поверьте. Несмотря на то, что оно было минимально адресуемой единицей памяти.

?
Напишите ваше общепринятое определение байта. А то, что на БЭСМ-4 никто не называл байтом размер минимально адресуемой ячейки, простите, не аргумент. У нас и флоппи-дисковод называли НГМД, и что дальше? И вообще, зачем вы постоянно придираетесь к терминам? Хотите уличить меня в неграмотности? Зачем вам оно надо?

незваный гость писал(а):

e2e4 писал(а):

Но они пишут CRC в документации. Я им верю.

Козьма Прутков писал(а):

106. Если на клетке слона прочтешь надпись «буйвол», не верь глазам своим.

Правда, сомневаюсь, что неточное употребление термина кем бы то ни было может обосновывать незнание точного смысла термина (или, по меньшей мере, истории термина). Кроме того, не подвел ли Фила Каца (Phil Katz) английский язык ? Там, как Вы знаете, «пишется Ливерпуль, а читается Манчестер» .

Это к чему?