#crc
#crc
Вопрос:
Как изменяется вероятность необнаруженной ошибки в зависимости от типа ссылки? связаны ли они вообще? Я имею в виду, если ссылка с потерями или имеет более высокую частоту ошибок в битах, как это повлияет на вероятность необнаруженной ошибки? Есть ли какая-либо формула для вычисления этого?
Ответ №1:
Что вы действительно подразумеваете под «типом канала», так это характеристики ошибок канала. На канале с высокой частотой ошибок в битах, например, количество битов в CRC (n) с ошибкой где-то в каждом сообщении (где каждое сообщение получает CRC), применяется обычная необнаруженная частота 2—n на сообщение. Это всегда, по крайней мере, так хорошо. Итак, вот ваша формула.
Предполагая, конечно, что ошибки являются случайными. Можно преднамеренно применять ошибки, рассчитанные так, чтобы оставить CRC неизменным, поэтому CRC не могут защитить от тех, кто имеет злонамеренный умысел.
Однако вероятность необнаруженных ошибок может быть лучше, чем эта формула, для более низких частот ошибок в битах.
Тогда это становится более сложным. Если вы никогда не ожидаете получить более чем однобитовую ошибку в сообщении, то CRC всегда обнаружит ошибку, независимо от длины сообщения. (CRC всегда обеспечивает проверку на четность.) Если многочлен CRC имеет коэффициент x 1, то он всегда будет обнаруживать нечетное количество битовых ошибок. CRC также имеют специальные свойства «пакетных» ошибок, в которые я не буду вдаваться. Давайте предположим, что у вас есть частота ошибок в битах, при которой любой бит в сообщении может быть перевернут с такой вероятностью. (Двоичный симметричный канал.)
Для заданного количества битов ошибок в сообщении вы обнаружите, что существуют конечные длины сообщений, для которых всегда будет обнаружено столько ошибок (или меньше).
На этой странице показаны эти свойства для многих 32-разрядных полиномов CRC. В качестве примера можно посмотреть запись для обычного 32-битного CRC с полиномом 0x04c11db7
. У него есть этот загадочный список чисел:
{4294967263,91607,2974,268,171,91,57,34,21,12,10,10,10}
Эти числа соответствуют соответственно 2, 3, 4 и т.д. битам ошибок в сообщении. Каждое число представляет собой длину в битах самого длинного сообщения (не включая CRC), для которого CRC, использующий этот многочлен, гарантированно обнаружит столько ошибок.
Таким образом, CRC всегда будет обнаруживать три или менее битовых ошибки в сообщениях длиной до 91 607 бит. Он всегда будет обнаруживать четыре или менее битовых ошибки в сообщениях длиной до 2974 бит.
В этом случае нет простой формулы, поскольку эти числа являются результатом исчерпывающего поиска «кодовых слов», которые представляют собой шаблоны, CRC которых равен нулю. Их можно рассматривать как шаблоны ошибок, которые могут быть применены к любому сообщению, которое не приводит к изменению CRC.
Существуют формулы для вычисления вероятности того, что сообщение из n бит содержит k или меньше ошибок, учитывая частоту ошибок в битах p. См. биномиальное распределение и его приближения.
Комментарии:
1. Вы упомянули, что «применяется обычная необнаруженная скорость 2 ^ (-n) на сообщение. Это всегда, по крайней мере, так хорошо», возможно ли, что более высокая частота ошибок в битах в канале приводит к тому, что CRC хуже, чем это? или вы имеете в виду, даже если у нас есть все биты с ошибкой, но мы можем обнаружить при аренде 2 ^ (-crc)
2. Если вы знаете шаблон ошибок, в данном случае каждый бит в сообщении перевернут, и вы знаете длину своего сообщения, вы можете точно определить, обнаружит ли CRC эту ошибку или нет. Так что это не вероятность. Если я считаю, что длина моего сообщения является случайной величиной, то да, только одна из 2 ^ 32 длин сообщений приведет к тому, что эти ошибки не будут обнаружены. Длина первого такого сообщения составляет 2 ^ 32-1 бит, или сообщение длиной в полгигабайта.
3. Итак, если я правильно понял, PUE не связан с ошибкой канала. если у меня есть 2 канала, 1 с частотой ошибок 10 ^ (-3) и один с частотой ошибок 10 ^ (-15) бит, PUE всегда один и тот же ( если размер пакета меньше 512 МБ).
4. У вас это неправильно. Это зависит от частоты ошибок в битах и размера пакета.
5. Но это не будет хуже, чем 2 ^ (-CRC), верно?