Вероятность НЕ определения ошибки

[A_I]

Вроде этот раздел больше подходит, ну или математика..
Вопрос казался пустяковым. Но только на первый взгляд.
Собственно, дано:
интерфейс UART с проверкой байт на четность, в сообщении 12 байт, последний байт - контрольная сумма (простое сложение всех предыдущих 11 байт).
Ну и вопрос - какова вероятность, что "проскочит" ошибка?

[Mihr]

Чтобы задача стала математической, нужно её корректно сформулировать.
Какова вероятность ошибки в передаче (приёме) одного байта?
Одинакова ли эта вероятность для всех байтов заданного пакета из 12 байт?
Если да, то решение опирается на формулу Бернулли.

[A_I]

Mihr в сообщении #1616747 писал(а):

Какова вероятность ошибки в передаче (приёме) одного байта?
Одинакова ли эта вероятность для всех байтов заданного пакета из 12 байт?

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

[Null]

A_I в сообщении #1616786 писал(а):

Тут немного не так.

Это важно. Без этих данных задачу не решить.

[Dmitriy40]

A_I в сообщении #1616786 писал(а):

Ну и какова вероятность, что точно ошибочное будет не распознано.

Если забыть про контроль start и stop битов (его точно учесть сложно), то у вас передаётся 12 символов по 9 бит или всего 108 битов. Они могут принимать $2^{108}$ комбинаций, из которых допустимых лишь $2^{88}$ (11 байтов, последний однозначно определён этими), остальные ошибочные или по чётности, или по сумме. Если ошибка в канале переводит правильную комбинацию в любую другую случайным равновероятным образом, то вероятность в результате попасть на снова допустимую комбинацию будет порядка $2^{88}/2^{108}=2^{-20}\approx10^{-6}$. Вот вам и вероятность пропустить ошибку.

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

Например любые однократные, двухкратные и трёхкратные ошибки будут обнаружены, или чётностью (если все в разных байтах или все в одном), или суммой если пара в одном байте. Обнаруживаются также ошибки передачи постоянно одного и того же байта (сумма не совпадёт если он не нулевой и не 0x80). Четырёхкратные ошибки могут остаться не обнаруженными если произойдут ровно в двух байтах (любых), но строго на двух одинаковых позициях в каждом (сумма не изменится). Для принимаемых обычно каналов ошибки случайны и равновероятны и потому совпасть именно вот ровно так сложно. Как её точно оценить не уверен, а прикинуть можно так: каждая допустимая комбинация из $2^{88}$ первой ошибкой переводится в одну из 108 других комбинаций, второй ошибкой в одну из 107 ещё других комбинаций, третьей в одну из 106 следующих комбинаций, четвёртой в одну из 105 конечных комбинаций, итого получаем $108\cdot107\cdot106\cdot105=128618280$ конечных комбинаций, при этом чтобы они получились снова допустимыми надо чтобы вторая ошибка "выбрала" (попала в) тот же байт что и первая, т.е. не 107 вариантов, а лишь 8, третья ошибка может выбрать любой бит из двух (неправильных по первым двум ошибкам) в остальных 11 символах, это 22 варианта из 106, четвёртой же ошибке остаётся единственный возможный вариант, в том же байте что и третья ошибка и ровно в оставшемся одном неправильном бите байта, итого из всех $128618280$ допустимыми будут лишь $108\cdot8\cdot22\cdot1=19008$ вариантов ошибок, а значит вероятность $19008/128618280=1.48\cdot10^{-4}$. Это и можно считать вероятностью пропустить четырёхкратную ошибку если она точно произойдёт.
Выделенное жирным критично потому что часто ошибки не кучкуются (те что кучкуются это отдельный вопрос и класс), а случайные, потому случиться двойной ошибке в квадрат менее вероятнее чем одиночной, а уж четверной в 4-й степени менее вероятно одиночной. И чтобы все они вчетвером уложились в 108 битов надо чтобы итоговая вероятность стала порядка $1/108$ (или более), а значит вероятность одиночной ошибки должна быть не меньше порядка $\sqrt[4]{1/108}=0.31$, простите но такие шумные каналы просто не применяются (например скорее всего пакет будет ошибочным из-за искажения стартового или стопового бита, ведь их 24 штуки в пакете, а значит вероятность всем им быть правильными порядка $(1-0.31)^{24}=1.36\cdot10^{-4}$, т.е. лишь один пакет из более 7 тысяч будет правильным всего лишь по стартовым и стоповым битам и дойдёт до проверки чётности и контрольной суммы!) со столь простыми протоколами, нужен намного более сложный и отказоустойчивый.

Про кучкование ошибок, одиночная ошибка длиной до 3 битов включительно обнаруживается (либо как многократная выше если вся укладывается в 9-битовый символ, либо по искажению старт или стоп бита), почти любая длиной более 9 битов обнаруживается по искажению старт или стоп бита, любая нечётной длины обнаруживается чётностью (или старт/стоп битами если залезает на них), остаются лишь ошибки чётной длины 4-8, укладывающиеся в один 9-битовый символ, все они обнаруживаются контрольной суммой. Т.е. одиночный пакет ошибок (несколько ошибок подряд) любой длины обнаруживается всегда. Не обнаруженными могут оказаться лишь два пакета ошибок если они оба будут одинаковой длины 4, 6, 8 и в разных символах и не залезут на старт/стоп биты и при этом идеально совпадут по положению в символе. Для длины 8 есть лишь два варианта размещения пакета ошибок в любом из 12 символов, а для второго пакета лишь 11 вариантов (один вариант в любом из 11 символов). Общее же количество вариантов размещения пакетной ошибки длиной 8 среди 132 битов пакета (включая и старт и стоп) будет 125 для первой и 116 для второй (минимум один бит должен быть между ними), итого $125\cdot116=14500$, из которых не обнаруженным останется лишь $2\cdot12\cdot11=264$ варианта, так что вероятность пропуска таких ошибок если они точно произойдут будет $264/14500=1.82\cdot10^{-2}$. Для длин 6 и тем более 4 вариантов размещения будет больше, а не обнаруживаемых вариантов останется почти столько же, т.е. вероятность не обнаружения будет ещё ниже. И опять важно что пакеты ошибок обычно случайны (если ничего про них априори неизвестно), а значит два пакета квадратично менее вероятны чем один. А три и более ещё менее вероятны. И тем более маловероятно совпадение длин нескольких пакетных ошибок.

Можно поставить вопрос и по другому: какова предельная вероятность случайных равновероятных ошибок в канале чтобы они все ошибочные пакеты были обнаружены. Тут тоже всё просто: всего передаётся 132 бита (12 символов по 11 битов каждый), при этом общее количество возможных комбинаций $2^{132}$, допустимыми из которых являются лишь $2^{88}$ (старт и стоп биты имеют лишь одно допустимое значение каждый и количество комбинаций не увеличивают), значит вероятность принять случайный пакет за правильный составит $2^{88}/2^{132}=2^{-44}$, что отвечает вероятности ошибки $\sqrt[132]{2^{-44}}=0.79$. Т.е. пока вероятность ошибок менее 0.79 все ошибочные пакеты будут обнаружены. Но простите таких каналов уж тем более не применяется (уж точно не с UART), 4 из 5 битов неправильные, мрак ...

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

И уж совсем отдельный класс (точнее много разных классов) ошибок не случайных. Например дублирование стартового бита в младший каждого байта. Но таких классов ошибок столько, что без априорных знаний какие из них реально встречаются фантазировать можно долго и упорно, считать же насколько вероятно их обнаружение ... Развлечение так себе. Хотя навскидку почти все они будут обнаружены (очень трудно придумать функцию, переводящую каждую из $2^{88}$ комбинаций снова в допустимую при общем их количестве $2^{132}$, таких функций всего $2^{-44}$, одна на 17 триллионов от общего их количества). Если же будут априорные знания об категории/классе ошибок, то посчитать вероятность их не обнаружения можно примерно как выше.

-- 08.11.2023, 10:53 --

A_I
Надеюсь из длинного пояснения стало понятно что Ваш абстрактный вопрос не имеет однозначного ответа, всё зависит от принятой модели ошибок в канале. Что Вам и пытались сказать остальные.

[A_I]

Dmitriy40 в сообщении #1616813 писал(а):

Надеюсь из длинного пояснения стало понятно что Ваш абстрактный вопрос не имеет однозначного ответа, всё зависит от принятой модели ошибок в канале. Что Вам и пытались сказать остальные.

Спасибо за пояснения, но имеется ввиду безо всяких "старт- и стоп- битов" и проч. моделей ошибок. Да, считать всё равновероятным. Чисто математически разве нельзя точно посчитать хотя бы какую-нибудь типа границу снизу/сверху (хотя, думается, можно точно, просто я туплю)?..

[worm2]

A_I, Dmitriy40 расписал ситуацию оочень подробно, тут мало что можно добавить.

"Чисто математически..."
Помнится, у одного участника форума в подписи была фраза американского писателя-фантаста Роберта Шекли: "Чтобы правильно задать вопрос, надо знать бОльшую часть ответа".
Не могу сказать за всю математику, но к теории вероятности эта фраза применима в усиленном варианте: чтобы правильно задать вопрос по теории вероятностей, нужно знать 90% ответа. Нужно под завязку загрузить в эту теорию знания о реальном железе в реальных условиях, в которых вам нужно работать: каков характер ошибок, какие там помехи, внешние и внутренние, с какой статистикой, насколько они независимы друг от друга. И только после этого теория начнёт работать. Мы, конечно, можем что-то брать с потолка, "считать всё равновероятным" и т.д. (ну так самые простые модели вам уже привели), какой-то результат будет получен, но как он соотносится с реальной железякой — на этот вопрос не будет никакого ответа, пока не попробуете реальную железяку.

-- Ср ноя 08, 2023 21:44:17 --

Вот вам границы:
1) Между приёмником и передатчиком — злоумышленник, имеющий возможность подделывать переданные биты. В такой простейшей постановке вероятность ошибки 100%, тупым перебором можно легко найти фейковую последовательность с тем же контрольным байтом.
2) Всё работает идеально 99.9999% времени, изредка проскакивают одиночные ошибки, не чаще 1 раза на каждый переданный мегабит. Вероятность ошибки 0% (любая одиночная ошибка в пакете гарантированно ловится).

-- Ср ноя 08, 2023 21:54:56 --

Вот какой-то промежуточный вариант:
Характер помех такой, что бывают целые килобайты "мусора". Если считать "мусор" состоящим из равновероятно встречающихся 0 и 1, то вероятность пропустить его 1/256: в одном из 256 случаев случайный контрольный байт окажется подходящим.
Но если мы знаем, что в большинстве случаев помеха состоит главным образом из "единичек" или из "нулей", мы можем модифицировать алгоритм контрольной суммы так, чтобы пакетам, в которых много единичек, соответствовали контрольные суммы, в которых много нулей и наоборот, и тем самым резко уменьшить вероятность пропуска.

[A_I]

worm2 в сообщении #1616904 писал(а):

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

На скоростях более 4 Мбит/сек и длине проводников чуть более метра, поверьте, резко возрастает количество битых фреймов (конечно, тут комплекс - ещё и конкретная аппаратка влияет, но сейчас не об этом). Специально, конечно, не анализировал, но по-ходу, именно "рановероятно" - единиц, нулей, а на осциллографе даже и "половинок" каких-то (уровень не держится стабильно).
Но, ещё раз - не о том речь, и вот вы пишите, что мне уже описали ранее. Но у Dmitriy40 я не нашел конкретного (одного) значения вероятности.. Может, не понял, конечно..

-- 08.11.2023, 21:56 --

А по поводу общей вероятности возникновения ошибки, помнится, объяснение такое слышал о проверке на четность. Четность дает всего лишь 50% вероятности. Это - "казалось бы". Но, учитывая, что как мне объясняли, "практически всегда" либо байт полностью на распознается, либо максимум, один бит "покорежится". Поэтому, типа, проверка на четность почти всё перекрывает...
Но, во-первых, не нашел никакого подтверждения таким рассуждениям, во-вторых, недавно убедился, что это если где-то и работает, то точно не везде. Сейчас, так получилось, надо работать на скоростях до 30 Мбит/с и именно по уарт (и даже не усарт). Так здесь примерно 2-4% (надо ещё статистики набрать) битых байт, а это уже может быть критично. И это уже надо учитывать в прикладной логике...

[Dmitriy40]

worm2 в сообщении #1616904 писал(а):

2) Всё работает идеально 99.9999% времени, изредка проскакивают одиночные ошибки, не чаще 1 раза на каждый переданный мегабит. Вероятность ошибки 0% (любая одиночная ошибка в пакете гарантированно ловится).

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

A_I в сообщении #1616915 писал(а):

Но у Dmitriy40 я не нашел конкретного (одного) значения вероятности.. Может, не понял, конечно..

Потому что одного ответа просто нет (и быть не может). Существуют разные типы/классы/модели ошибок в канале и для каждого будет своя вероятность пропуска. И она будет меняться от 0% до 100%.
Вопрос обычно ставят по другому: какова вероятность пропуска для некоторых типичных ошибок. Которые наиболее вероятны для данной аппаратуры. Например равновероятных ошибок любого бита. И это может и реально будет зависеть от всех особенностей аппаратуры вплоть до физической среды передачи (в проводах вероятнее одни ошибки, в оптоволокне другие, в радиоэфире третьи, в лазерной связи четвёртые, и так далее).
Если ну прямо очень хочется одну цифру, то берите $2^{88}/2^{132}=2^{-44}$ - с такой вероятностью правильный пакет после произвольного искажения в канале связи превратится снова в допустимый (ошибка не будет обнаружена). Теоретически это соответствует шуму (вероятности ошибки для каждого бита) $\sqrt[132]{2^{-44}}=0.79$, т.е. из любых 5 битов 4 неправильных - при таком и меньшем шуме в канале факт ошибочности пакета обнаруживается (правда не знаю с какой вероятностью, возможно лишь 63% (1 сигма)). Но реально таких каналов просто не бывает.

A_I в сообщении #1616915 писал(а):

Так здесь примерно 2-4% (надо ещё статистики набрать) битых байт, а это уже может быть критично.

Даже 4% битых байтов для пакета из 12 байтов дают вероятность ошибки для каждого байта всего $1-\sqrt[12]{1-0.04}=0.0034$. Вероятность исказиться двум байтам в пакете квадратично ниже, $0.04^2=0.0016$, а чтобы такая ошибка оказалась необнаруженной контрольной суммой второй байт должен принять лишь одно из 256 значений, что ещё в 256 раз менее вероятно, т.е. такая вероятность порядка 6ppm или один раз на 160 тысяч байтов или более 13 тысяч пакетов.
Но при 4% ошибочных байтов практически каждый второй пакет будет ошибочным. Для такого шумного канала надо или вдвое увеличивать скорость передачи чтобы в среднем доходило половина пакетов т.е. сохранялся желаемый трафик, либо использовать коды коррекции ошибок, исправляющие один байт в пакете (насколько помню для этого достаточно Рида-Соломона с двумя дополнительными байтами, контрольная сумма тогда не нужна, а отказавшись и от контроля чётности можно уложиться даже в прежнюю битовую скорость).

-- 08.11.2023, 22:23 --

A_I в сообщении #1616915 писал(а):

Сейчас, так получилось, надо работать на скоростях до 30 Мбит/с и именно по уарт (и даже не усарт).

USART не сильно поможет, для 11-битовых символов уход частоты может быть до 2.5% кажется, это намного больше типичного разброса любого самого плохого кварца (и даже керамического резонатора, вы же не на RC генераторе надеюсь работаете), так что тактирование битов скорее всего правильное (надеюсь приёмник аппаратный и там честное сэмплирование в центре битов, т.е. применяется 8/16-ти кратная тактовая частота). Гораздо полезнее будет применить нормальный высокоскоростной физический протокол, типа RS485/422, вероятно кардинально понижающий вероятность ошибок.
Либо смотреть в сторону корректирующих кодов, исправляющих столь ошибочный канал (Рид-Соломон с 4-я дополнительными байтами исправляет два любых байта в пакете).

[Dmitriy40]

A_I

Dmitriy40 в сообщении #1616926 писал(а):

Если ну прямо очень хочется одну цифру, то берите $2^{88}/2^{132}=2^{-44}$ - с такой вероятностью правильный пакет после произвольного искажения в канале связи превратится снова в допустимый (ошибка не будет обнаружена).

И всё же эта цифра совершенно неадекватна для любого реального канала, это натуральная "средняя температура по больнице", ведь она предполагает что все $2^{240}$ (не хило, а!) функций искажений $f(): 2^{88} \to 2^{132}$ равновероятны, включая и совсем бредовые, например все $11! =39916800$ вариантов перестановок первых 11 байтов/символов (попробуй вообразить такой физический канал, ага! впрочем для строго реверсивной перестановки всех байтов пакета канал вообразить можно, он даже мог существовать реально когда были голосовые модемы 56К), кстати такая ошибка не обнаруживается, для чувствительности к порядку следует применять не простую сумму, а скажем CRC8, таблично считающуюся за то же время. Или $2^{176}$ (из 88 битов в новые 88 битов) функций выдающих фиксированное значение первых (или любых) 11 байтов, из которых будут не обнаружены в среднем (по всем возможным передаваемым данным) лишь $2^{-8}$. Или $2^{176}$ функций, выдающих фиксированное (или даже случайное) значение 11 байтов плюс правильный контрольный байт, такие ошибки будут пропущены с вероятностью 100% (только вообразить такой физический канал ещё труднее).
Другой пример, если все $2^{96}$ битов в 12 байтах абсолютно случайны, то такая ошибка будет пропущена с вероятностью $2^{-8}=1/256=0.4\%$ для любого метода расчёта контрольной суммы длиной в байт. Заметьте, всего лишь $2^{-8}$. К счастью, не бывает каналов искажающих исключительно информационные биты, физическая среда обычно не знает ничего о канальном уровне (где информационные биты, а где служебные). Если добавляется шум и в битах чётности, то она сразу падает на $2^{-12}$ и станет $2^{-20}$. А если и старт/стоп биты могут быть случайными, то и ещё на $2^{-24}$, до $2^{-44}$. И вот такие каналы уже реально бывают (шум забил весь сигнал). И кстати в таком случае нет никакой даже теоретической возможности определить ошибочный пакет с вероятностью 100%, сколько бы контрольных методов не навертели поверх физического канала.

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

-- 09.11.2023, 05:06 --

Dmitriy40 в сообщении #1616955 писал(а):

К счастью, не бывает каналов искажающих исключительно информационные биты,

Впрочем, кажется тот же голосовой модем 56К с подключением по UART вполне мог выступать в роли такого канала ... И похоже 2.5/5/10-гигабитный ethernet тоже может искажать только информационные биты (и тоже из-за символьного кодирования байтов, а не битов) если пользоваться только его физическим уровнем.
Так что вопрос хитрее чем даже мне думалось.

[A_I]

Dmitriy40 в сообщении #1616926 писал(а):

Если ну прямо очень хочется одну цифру, то берите $2^{88}/2^{132}=2^{-44}$ - с такой вероятностью правильный пакет после произвольного искажения в канале связи превратится снова в допустимый (ошибка не будет обнаружена).

Ну вот, какие-то конкретные значения. Пусть и теоретические.
А если говорить о символьном представлении байт в интерфейсе (у нас так), то видимо вы правы - тут даже теоретически, думается, другие "формулы рулят". А это уже интереснее.