Вероятность пропуска ошибки

Ошибки первого рода (англ. type I errors, α errors, false positives) и ошибки второго рода (англ. type II errors, β errors, false negatives) в математической статистике — это ключевые понятия задач проверки статистических гипотез. Тем не менее, данные понятия часто используются и в других областях, когда речь идёт о принятии «бинарного» решения (да/нет) на основе некоего критерия (теста, проверки, измерения), который с некоторой вероятностью может давать ложный результат.

Определения

Пусть дана выборка из неизвестного совместного распределения , и поставлена бинарная задача проверки статистических гипотез:

где  — нулевая гипотеза, а  — альтернативная гипотеза. Предположим, что задан статистический критерий

,

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

1. Распределение выборки соответствует гипотезе , и она точно определена статистическим критерием, то есть .

2. Распределение выборки соответствует гипотезе , но она неверно отвергнута статистическим критерием, то есть .

3. Распределение выборки соответствует гипотезе , и она точно определена статистическим критерием, то есть .

4. Распределение выборки соответствует гипотезе , но она неверно отвергнута статистическим критерием, то есть .

Во втором и четвертом случае говорят, что произошла статистическая ошибка, и её называют ошибкой первого и второго рода соответственно. ¹⁾²⁾

	Верная гипотеза
Результат  применения  критерия		верно принята	неверно принята  (Ошибка второго рода)
	неверно отвергнута  (Ошибка первого рода)	верно отвергнута

О смысле ошибок первого и второго рода

Из определения выше видно, что ошибки первого и второго рода являются взаимно-симметричными, то есть если поменять местами гипотезы и , то ошибки первого рода превратятся в ошибки второго рода и наоборот. Тем не менее, в большинстве практических ситуаций путаницы не происходит, поскольку принято считать, что нулевая гипотеза соответствует состоянию «по умолчанию» (естественному, наиболее ожидаемому положению вещей) — например, что обследуемый человек здоров, или что проходящий через рамку металлодетектора пассажир не имеет запрещённых металлических предметов. Соответственно, альтернативная гипотеза обозначает противоположную ситуацию, которая обычно трактуется как менее вероятная, неординарная, требующая какой-либо реакции.

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

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

В других областях обычно используют словосочетания со схожим смыслом, например, «ложное срабатывание», «ложная тревога» и т.п. В информационных технологиях часто используют английский термин false positive без перевода.

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

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

Слово «отрицательный» в данном случае не имеет отношения к желательности или нежелательности самого события.

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

В других областях обычно используют словосочетания со схожим смыслом, например, «пропуск события», и т.п. В информационных технологиях часто используют английский термин false negative без перевода.

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

Вероятности ошибок (уровень значимости и мощность)

Вероятность ошибки первого рода при проверке статистических гипотез называют уровнем значимости и обычно обозначают греческой буквой (отсюда название -errors).

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

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

В статистических тестах обычно приходится идти на компромисс между приемлемым уровнем ошибок первого и второго рода. Зачастую для принятия решения используется пороговое значение, которое может варьироваться с целью сделать тест более строгим или, наоборот, более мягким. Этим пороговым значением является уровень значимости, которым задаются при проверке статистических гипотез. Например, в случае металлодетектора повышение чувствительности прибора приведёт к увеличению риска ошибки первого рода (ложная тревога), а понижение чувствительности — к увеличению риска ошибки второго рода (пропуск запрещённого предмета).

Примеры использования

Радиолокация

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

Компьютеры

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

Компьютерная безопасность

Наличие уязвимостей в вычислительных системах приводит к тому, что приходится, с одной стороны, решать задачу сохранения целостности компьютерных данных, а с другой стороны — обеспечивать нормальный доступ легальных пользователей к этим данным (см. компьютерная безопасность). Moulton (1983, с.125) отмечает, что в данном контексте возможны следующие нежелательные ситуации:

• когда авторизованные пользователи классифицируются как нарушители (ошибки первого рода)

• когда нарушители классифицируются как авторизованные пользователи (ошибки второго рода)

Фильтрация спама

Ошибка первого рода происходит, когда механизм блокировки/фильтрации спама ошибочно классифицирует легитимное email-сообщение как спам и препятствует его нормальной доставке. В то время как большинство «антиспам»-алгоритмов способны блокировать/фильтровать большой процент нежелательных email-сообщений, гораздо более важной задачей является минимизировать число «ложных тревог» (ошибочных блокировок нужных сообщений).

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

Пока не удалось создать антиспамовую систему без корреляции между вероятностью ошибок первого и второго рода. Вероятность пропустить спам у современных систем колеблется в пределах от 1% до 30%. Вероятность ошибочно отвергнуть валидное сообщение — от 0,001 % до 3 %. Выбор системы и её настроек зависит от условий конкретного получателя: для одних получателей риск потерять 1% хорошей почты оценивается как незначительный, для других же потеря даже 0,1% является недопустимой.

Вредоносное программное обеспечение

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

Поиск в компьютерных базах данных

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

Большинство ложных срабатываний обусловлены сложностью естественных языков, многозначностью слов: например, «home» может обозначать как «место проживания человека», так и «корневую страницу веб-сайта». Число подобных ошибок может быть снижено за счёт использования специального словаря. Однако это решение относительно дорогое, поскольку подобный словарь и разметка документов (индексирование) должны создаваться экспертом.

Оптическое распознавание текстов (OCR)

Разнообразные детектирующие алгоритмы нередко выдают ошибки первого рода. Программное обеспечение оптического распознавания текстов может распознать букву «a» в ситуации, когда на самом деле изображены несколько точек.

Досмотр пассажиров и багажа

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

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

Биометрия

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

Массовая медицинская диагностика (скрининг)

В медицинской практике есть существенное различие между скринингом и тестированием:

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

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

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

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

Возможно, наиболее широкие дискуссии вызывают ошибки первого рода в процедурах скрининга на рак груди (маммография). В США уровень ошибок первого рода в маммограммах достигает 15%, это самый высокий показатель в мире.⁵⁾ Самый низкий уровень наблюдается в Нидерландах, 1%.⁶⁾

Медицинское тестирование

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

Ошибки второго рода вызывают серьёзные и трудные для понимания проблемы, особенно когда искомое условие является широкораспространённым. Если тест с 10%-ным уровнем ошибок второго рода используется для обследования группы, где вероятность «истинно-положительных» случаев составляет 70%, то многие отрицательные результаты теста окажутся ложными. (См. Теорему Байеса).

Ошибки первого рода также могут вызывать серьёзные и трудные для понимания проблемы. Это происходит, когда искомое условие является редким. Если уровень ошибок первого рода у теста составляет один случай на десять тысяч, но в тестируемой группе образцов (или людей) вероятность «истинно-положительных» случаев составляет в среднем один случай на миллион, то большинство положительных результатов этого теста будут ложными.⁷⁾

Исследования сверхъестественных явлений

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

См. также

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

Пусть при
кодировании данной информации простым
(помехоустойчивым) кодом передаваемое
сообщение состоит из

(
)
символов. Из-за введения избыточности
в это сообщение

.
Пусть скорость передачи информации по
каналу для обоих кодов одинакова. Найдем
эквивалентную вероятность ошибки

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

(
)
— вероятность правильного (ошибочного)
приема сообщения из

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

.
Отсюда (при

)

(1.2)

Для вычисления

надо знать вероятность

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

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

.

1.4. Обнаружение и исправление ошибок корректирующими кодами

Декодирование
сообщения в приемнике – это не просто
операция, обратная кодированию сообщения
в передатчике. Из-за разных искажений
и воздействия помех пришедший сигнал
может существенно отличаться от
переданного. Можно высказать ряд
предположений
о том, какое сообщение передавалось.
Задачей приемного устройства является
принятие
решения о
том, какое из возможных сообщений
действительно передавалось источником.
Принятие решения о принятом слове,
вообще говоря, предполагает анализ всех
сведений об источнике и канале связи.
Из-за введения избыточности
помехоустойчивый
код может обнаружить и исправить ошибки
в принятых словах. Это способствует
повышению достоверности передачи
информации. При передаче сообщений
ошибки возникают из-за действия помех
и обнаруживаются при приеме запрещенных
слов приемником. Долю обнаруживаемых
ошибок оценим как

,
где

(
)
— число разрешенных слов (их полное
число) в коде. Избыточность
корректирующего
кода

.
(1.3)

где
для простого кода

,
так как

.

Множество
запрещенных кодовых слов числом

разобьем на

подмножеств

,
где

.
Каждому подмножеству

сопоставим разрешенное кодовое слово

.
Зададим правило приема. Если принято
кодовое слово

или любое слово из подмножества

,
то считаем, что было передано кодовое
слово

.
Тогда исправляются все ошибки, не
выводящие передаваемое кодовое слово
за пределы подмножества

.
В подмножество

входят запрещенные слова

,
при приеме которых наиболее вероятна
передача слова

,
то есть удовлетворяющие условию

(1.4)

где

,

,

(
)
— априорная
вероятность передачи кодового слова

(
),

(
)
— переходная вероятность приема кодового
слова

при условии передачи слова

(
).

Вектор
ошибок

определяет различие между принятым
словом

и переданным

:

(1.5)

Если
нет ошибок при передаче двоичного
кодового слова

,
принятое кодовое слово

совпадает с

,
и вектор ошибок

во всех разрядах содержит

.
Число ненулевых символов в векторе
ошибок дает его вес

.

Рассмотрим
канал с независимо возникающими ошибками.
Пусть вероятности

передачи
разных сообщений

из их ансамбля

одинаковы. Тогда вероятность появления
ошибки уменьшается с увеличением
кратности ошибки. В первую очередь надо
исправлять однократные ошибки – они
встречаются наиболее часто, затем –
двукратные и т.д.

Пусть
в каждое из подмножеств

включены запрещенные слова

,
отличные от соответствующего разрешенного
слова

в меньшем числе символов, чем от других
разрешенных слов

,

.
Такой
подход к формированию подмножеств

соответствует декодеру, принимающему
решение о каждом переданном символе на
основании принятого символа, оптимальное
по критерию максимума правдоподобия.

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

при передаче любого символа одинакова
и не меняется во времени.

Пример
1.4.2. Пусть
число

,
перешедших в

в каждом кодовом слове из-за действия
помех, не равно числу

,
перешедших в

.
Тогда двоичные коды с постоянным весом

обнаруживают все ошибки кратности

.
В полностью асимметричном канале связи
возможен лишь один вид ошибок —
преобразование

в

или

в

.
В нем такой код находит все ошибки. В
симметричном канале с вероятностью
искажения символа

вероятность пропуска ошибки

в первом приближении определяется как
вероятность одновременного искажения
одной

и одного

.
Для телеграфного кода № 3

,
где

— число сочетаний из

элементов по

,

.

Пример
1.4.3. Каждое
кодовое слово наиболее простого из
линейных систематических двоичных
кодов

содержит

проверочный символ, равный сумме по

всех информационных символов. Это — код
с проверкой
на четность. Для
него кодовое расстояние

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

ом
приближении равна вероятности искажения

х
символов:

.

Есть
видоизмененный способ контроля на
четность. Последовательность информационных
символов

,
где

,
разбивается на

строк по

символов в каждой так, что

.
Контрольные разряды

,
где

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

Контроль
на четность делается по строкам и по
столбцам. Если, например, нарушение
четности обнаружено для

-ой
строки и

-ого
столбца, то символ

матрицы — ошибочный. Исправление
обнаруженной ошибки достигается заменой
этого символа (

— на

или

— на

).

Контроль по методу
четности (или нечетности) применяют при
записи-считывании информации в
запоминающих устройствах и при выполнении
арифметических операций на ЭВМ (см.
Приложение).

Пример
1.4.4. Нелинейные
коды Бергера, например, —

,

,

,

,

,

,

,

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

Р
50.1.015-98

РЕКОМЕНДАЦИИ ПО
СТАНДАРТИЗАЦИИ

КАЧЕСТВО
СЛУЖЕБНОЙ ИНФОРМАЦИИ

МЕТОДИКА ОЦЕНКИ БЕЗОШИБОЧНОСТИ
ПО ТЕХНОЛОГИЧЕСКИМ СХЕМАМ
ПЕРЕРАБОТКИ ИНФОРМАЦИИ

ГОССТАНДАРТ РОССИИ

Москва

Предисловие

1 РАЗРАБОТАНЫ Московским
научно-исследовательским центром (МНИЦ) Государственного, комитета Российской
Федерации по связи и информатизации и Московским государственным университетом
путей сообщения

ВНЕСЕНЫ Техническим комитетом по
стандартизации «Информационные технологии» (ТК 22)

2 ПРИНЯТЫ И ВВЕДЕНЫ В ДЕЙСТВИЕ
Постановлением Госстандарта России от 12 мая 1998 г. № 185

3 ВВЕДЕНЫ ВПЕРВЫЕ

Р
50.1.015-98

РЕКОМЕНДАЦИИ ПО СТАНДАРТИЗАЦИИ

Дата
введения 1999-01-01

ВВЕДЕНИЕ

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

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

Термины, применяемые в настоящих рекомендациях, — по ГОСТ
Р 51170. Условные обозначения элементов технологических процессов
переработки данных — по ГОСТ
Р 51168. Графические модели технологических процессов переработки данных —
по ГОСТ
Р 51167.

1 ОБЩИЕ ПОЛОЖЕНИЯ

1.1 Под данными понимают служебную информацию,
представленную в виде, пригодном для обработки автоматическими средствами при
возможном участии человека.

1.2 Под безошибочностью данных понимают их
свойство не иметь скрытых случайных ошибок. В качестве показателя
безошибочности используется вероятность Q наличия хотя бы одной ошибки в
данных определенного объема, для которого эта ошибка искажает содержание
данных.

1.3 При оценке безошибочности данные рассматривают как
продукт технологического процесса переработки данных (ТППД). В этом случае ТППД
рассматривают как совокупность операций обработки, контроля и исправления
ошибок, выполняемых с целью обеспечения пользователя ИС данными, удовлетворяющими
требованиям директивных документов к их безошибочности.

1.4 Операции объединены в технологические схемы переработки
данных (ТСПД) в соответствии с организацией их выполнения.

1.5 Для формализованного описания ТППД используются
информационные цепи (ИЦ), в которых состояниям данных (событиям) соответствуют
кружки, операциям обработки — сплошные стрелки; операциям контроля —
треугольники; операциям исправления ошибок — штрих-пунктирные стрелки.

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

2 СОСТАВЛЕНИЕ И РАЗМЕТКА ИНФОРМАЦИОННОЙ ЦЕПИ

2.1 Для составления информационной цепи,
соответствующей технологическому процессу переработки данных в ИС, необходимо
выполнить требования пунктов 2.2 — 2.10.

2.2 Используя описание процесса переработки
данных, определяют выполняемые в соответствии с ТППД операции обработки данных.

2.3 Составляют сетевой граф (СГ), включающий
операции обработки данных.

2.4 Используя описание процесса переработки
данных, определяют на СГ операции обработки, после выполнения которых
производится контроль данных.

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

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

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

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

2.9 По результатам выполнения 2.6 — 2.8 фиксируют
на каждой дуге возврата операцию исправления ошибок, если она имеется. Если
исправление ошибок перед повторной обработкой не проводится, то на дуге
возврата фиксируется фиктивная операция.

2.10 Выделяют и обозначают в ИЦ операции
однократного и локального контроля.

2.11 Проводят разметку ИЦ, построенную по 2.1 — 2.10.
Для этого выполняют требования пунктов 2.12
— 2.19.

2.12 В кружках, соответствующих событиям
ИЦ, проставляют номера i в порядке возрастания слева направо.

2.13 Для каждой операции контроля
устанавливают тип ТСПД, в состав которой входит данная операция контроля.
Технологические схемы переработки данных перечислены в приложении А.

2.14 Выделяют определенный объем данных
(символ, реквизит, документ и т.п.), для которого проводят оценку. При этом
учитывают, что для выделенного объема должно быть справедливо условие: наличие
хотя бы одной ошибки недопустимо, так как искажает содержание сведений.

2.15 Над каждой операцией обработки (i,
j), расположенной между событиями i и j, проставляют
значения вероятности q_ij внесения ошибки при выполнении
данной операции (следует различать этот показатель и вероятность Q,
определенную в 1.2).

2.16 Над каждой операцией контроля (i, j),
находящейся между событиями i и j, проставляют значения
вероятности β_i,j пропуска ошибок при контроле.

2.17 Над каждой операцией контроля (i, j)
проставляют значение числа k_i,j циклов контроля.

2.18 Над каждой операцией исправления ошибок,
соответствующей операции контроля (i, j), проставляют значение
вероятности q_иi,j (внесения ошибки при выполнении операции
исправления.

2.19 Над начальным событием ИЦ проставляют
значение Q_н вероятности наличия хотя бы одной ошибки в
исходных данных определенного объема.

3 ОЦЕНКА БЕЗОШИБОЧНОСТИ ДАННЫХ

3.1 Для оценки безошибочности данных на
выходе ТППД выполняют требования пунктов 3.2
— 3.14.

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

3.3 Каждой ТСПД с локальным контролем
сопоставляют значение вероятности Q_л из таблицы Б.1
приложения Б.

3.4 Заменяя каждую ТСПД с локальным
контролем эквивалентной операцией обработки, строят ИЦ, эквивалентную исходной.
В кружках, соответствующих событиям эквивалентной ИЦ, проставляют номера i
в порядке возрастания слева направо.

3.5 В ИЦ, построенной по 3.4, над каждой операцией, эквивалентной ТСПД с локальным
контролем, проставляют значение вероятности внесения ошибок q_экв = Q_л.

3.6 На ИЦ, построенной по 3.4, выделяют все особые точки (ОТ), т.е. события,
являющиеся началом выполнения операции контроля.

3.7 Определяют на ИЦ первую по порядку
возрастания номеров событий от начала процесса особую точку. При повторных
выполнениях особую точку определяют от предыдущей ОТ.

3.8 Определяют число операций обработки l, выполняемых от начального события до ОТ, определенной
по 3.7. При повторных выполнениях число l определяют от предыдущего события ОТ с номером ν
— 1 до ОТ, определенной по 3.7.

3.9 Вычисляют
значение вероятности наличия ошибки в данных Q_ν+l, соответствующих ОТ, определенной по 3.7, используя формулу, справедливую при значениях всех
вероятностей внесения и наличия ошибок в данных значительно меньших единицы:

где Q_v
— вероятность наличия хотя бы одной ошибки в данных, соответствующих событию v.
Если требование настоящего пункта выполняется первый раз, то Q_v = Q_н. Значение Q_н
определено в 2.19;

q_{v+j v+j+l}
— вероятность внесения ошибки при выполнении операции (v + j, v + j + 1)
между событиями v + j и v + j + 1. Значения q_{v+j v+j+l} определены в 2.15.

3.10 Если значение l,
определенное по 3.8, равно 1, переходят к
выполнению требований 3.13; если l > 1, то к выполнению требований 3.11.

3.11 Необходимо
заменить совокупность операций обработки от входа в ТСПД до операции контроля
эквивалентной операцией, для которой значение вероятности q внесения ошибки
определяют по формуле

где Q_ξ — вероятность наличия
хотя бы одной ошибки в данных определенного объема на входе ТСПД;

Q_v+l — вероятность наличия
хотя бы одной ошибки в данных определенного объема на входе операции контроля.

Значения Q_ξ и Q_v+l получены по 3.9 или при разметке ИЦ.

3.12 Строят ИЦ, эквивалентную исходной, в которой операции
обработки от входа в ТСПД (событие ξ) до операции контроля (событие v +
l) заменены эквивалентной операцией
обработки со значением вероятности q, определенным по 3.11.

3.13 Значение вероятности Q_v+l+1 наличия ошибки на выходе ТСПД определяют по
приложению Б.

3.14 Требования 3.7 — 3.13
выполняют до тех пор, пока не будет получено значение показателя для конечного
(выходного) события ИЦ Q_вых.

Оценку безошибочности данных считают выполненной.

4 АНАЛИЗ РЕЗУЛЬТАТОВ ОЦЕНКИ

4.1 Сравнивают полученное по 3.14 значение показателя Q_вых
безошибочности данных на выходе ИЦ с предельно допустимым значением Q_доп.

4.2 Если Q_вых ≤
Q_доп, значит исследуемый вариант ТППД
удовлетворяет предъявляемым к нему требованиям по безошибочности. Если Q_вых > Q_доп,
то необходимы мероприятия по повышению безошибочности данных.

5 ПРИМЕР ОЦЕНКИ БЕЗОШИБОЧНОСТИ ДАННЫХ

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

Решение. Согласно 2.1
составляют информационную цепь, соответствующую описанному выше ТППД. Для этого
выполняют требования пунктов 2.2 — 2.10.

Выполнение требований 2.2,
2.3

В ТППД выделяют две операции обработки: заполнение исходных
документов; ввод данных в ЭВМ с клавиатуры дисплея. На рисунке 1 изображен СГ, включающий эти операции.

Рисунок 1

Рисунок 2

Выполнение требований 2.4

На рисунке 2 изображен
СГ с выделенными знаком «×» операциями обработки, после выполнения
которых проводят контроль данных. Число знаков «×» равно количеству
выполненных подряд операций контроля после выделенной этим знаком операции
обработки. В данном СГ число циклов контроля не учитывается. Для условий
приведенного примера это визуальный контроль исходных документов после первой
операции обработки и по экрану дисплея, а также программный контроль после
второй операции обработки.

Выполнение требований 2.5

Включая в СГ логические элементы контроля — ромбы, получим
первоначальный вариант , информационной цепи, указанный на рисунке 3.

Рисунок 3

Выполнение требований 2.6,
2.7

Анализируя способы организации контроля данных, замечаем
следующее. В рассматриваемом случае применяют визуальный контроль заполнения исходных
документов, который, как правило, организуют как однократный контроль с
исправлением обнаруженных ошибок. На этапе ввода данных в ЭВМ с клавиатуры
дисплея осуществляется многократный контроль обнаруженных ошибок. Контроль и
необходимое исправление проводят до тех пор, пока в данных обнаруживаются
ошибки. После ввода в ЭВМ осуществляется программный контроль с выводом на
экран дисплея обнаруженных ошибок. В системе используется логический контроль,
который не позволяет определить истинные значения искаженных данных. В этом
случае имеет место многократный контроль без исправления ошибок с повторной
обработкой данных, в которых обнаружены ошибки. Число циклов контроля не
ограничено.

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

Рисунок 4

Рисунок 5

Выполнение требований 2.8

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

Выполнение требований 2.9

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

Рисунок 6

Рисунок 7

Выполнение требований 2.10

Построение ИЦ завершается выделением операций однократного и
локального контроля. Однократным является контроль заполнения исходных
документов, а локальным контролем является визуальный контроль по экрану
дисплея, так как он позволяет выявить несоответствие введенных данных исходным
документам, но как правило не позволяет обнаружить ошибки в самих документах.
На рисунке 7 изображена ИЦ,
соответствующая рассматриваемому ТППД.

Выполнение требований 2.11

Для разметки ИЦ выполняют требования пунктов 2.12 — 2.19.

Выполнение требований 2.12

Проставляют номера событий ИЦ в порядке возрастания слева
направо в соответствии с рисунком 8.

0, 1 — заполнение исходных документов; 1, 2 — визуальный
контроль исходных документов;
2, 3 — ввод данных в ЭВМ с клавиатуры дисплея; 3, 4 — визуальный (по экрану
дисплея)
контроль данных; 4, 5 — программный контроль данных

Рисунок 8

Рисунок 9

Примечание — Номера ТСПД — по приложению А

Выполнение требований 2.13

На рисунке 9 указаны порядковые
номера типов ТСПД согласно приложению А.

Выполнение требований 2.14
— 2.19

На рисунке 10
приведена ИЦ, для каждой операции обработки и контроля которой указаны значения
q_i,j
и β_i,j вероятностей внесения и пропуска ошибки в одном
символе, принятом за тот объем данных, для которого производят оценку.

Построение и размету ИЦ считают завершенной.

Рисунок 10

Выполнение требований 3.1

Для оценки безошибочности данных должны быть выполнены
требования пунктов 3.2 — 3.14:

Выполнение требований 3.2
— 3.5

Проводят расчет безошибочности
данных для ТСПД с локальным контролем. Заметим, что контроль 3, 4
между событиями 3 и 4 является локальным, поскольку основан на
посимвольном сравнении исходных и введенных данных и позволяет обнаруживать
ошибки, возникшие лишь при работе на клавиатуре дисплея. Совокупность операций 2,
3; 3, 4 соответствует ТСПД 7*. Принимаем равным нулю
значение вероятности Q₂ наличия ошибки в данных на входе
рассматриваемой ТСПД. (Здесь и далее индекс символа Q соответствует
номеру события, к которому относится значение показателя Q). Используя
приложение Б, находят значение
вероятности Q_л наличия ошибки в данных на выходе ТСПД 7 при
условии, что на ее вход поступают безошибочные данные, по формуле

Q_л
= q₂₃∙β₃₄
= 10^-3∙0,2 = 2∙10^-4,

где q₂₃
— значение вероятности внесения ошибки на операции 2, 3; β₃₄ — значение вероятности пропуска
ошибки при выполнении операции контроля 3, 4.

________________

*
Здесь и далее номер ТСПД соответствует номеру, указанному в таблице А.1
приложения А.

Заменяя рассматриваемую ТСПД с локальным контролем
эквивалентной операцией обработки, имеющей q_экв = Q_л
= 2∙10^-4, строим ИЦ, эквивалентную исходной. Обращаем внимание
на то, что при построении эквивалентной ИЦ осуществляется перенумерация событий
ИЦ и соответствующих обозначений q, β, как указано на
рисунке 11.

q₀₁ — вероятность внесения ошибок при выполнении операции
обработки 0, 1; β₁₂ —
вероятность пропуска ошибок при выполнении операции контроля 1, 2,
β₃₄ —
вероятность пропуска ошибок при выполнении операции контроля 3, 4;
k₁₂ и k₃₄ — максимально возможное
число циклов контроля на операциях 1, 2 и 3, 4
соответственно; q_и12 —
вероятность внесения ошибки при выполнении операции исправления; q_экв — вероятность внесения
ошибки на операции 2, 3 в ИЦ, эквивалентной исходной

Рисунок 11

Выполнение требований 3.6

На рисунке 12
изображена ИЦ с выделенными штриховкой особыми точками. Обозначения рисунка 12 соответствуют обозначениям рисунка 11.

Рисунок 12

Выполнение требований 3.7
— 3.9

Из рисунка 12 видно, что первая от начала особая точка
соответствует событию 1. Если от начала процесса до первой ОТ имеет место одна
операция обработки, то l = 1. В соответствии с
требованиями 3.9 значение Q_v
= Q_н = 0. При этом вероятность наличия ошибки в данных Q_v+l, соответствующих первой ОТ, определяют по формуле

Q_v+l = Q₁ = q₀₁ = 6,4∙10^-4.

Так как l
= 1, то выполняют требования 3.13.
Значение вероятности наличия ошибки на выходе операции контроля 1, 2
(согласно таблице Б.1 приложения Б)
определяют по формуле

Q₂
= q₀₁[β₁₂ + (1
— β₁₂)q_и12] = q₀₁β₁₂ = 6,4∙10^-4∙0,2
= 1,28∙10^-4.

Выполнение требований 3.14

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

Выполнение требований 3.7
— 3.9

Из рисунка 12 видно,
что следующая после события v — 1 = 1 особая точка соответствует событию
3. При этом число операций обработки l,
выполняемых от предыдущего события ОТ с номером v — 1 = 1 до ОТ с
номером v + 1 = 3, равно 1. Значение вероятности наличия ошибки в данных
Q_v+l = Q₃ определяют по требованию 3.9 по формуле

Q_v+l = Q₃ ≈ Q₂
+ q₂₃ = 1,28 10^-4 + 2∙10^-4
= 3,28∙10^-4.

Так как l = 1, выполняем
требования 3.13. Значение вероятности Q₄
наличия ошибки на выходе операции контроля 3, 4 находит;
используя приложение Б, по формуле

Q₄
= Q₃β₃₄ = 3,28∙10^-4∙0,03
≈ 1∙10^-5.

Таким образом значение вероятности наличия ошибки в символе
данных, используемых при решении задачи на ЭВМ, Q_вых
= 10^-5.

Оценку безошибочности данных считают выполненной.

ПРИЛОЖЕНИЕ А

(справочное)

ТЕХНОЛОГИЧЕСКИЕ СХЕМЫ ПЕРЕРАБОТКИ ДАННЫХ

Таблица А.1

ПРИЛОЖЕНИЕ Б

(справочное)

ВЕРОЯТНОСТИ НАЛИЧИЯ ОШИБОК В ДАННЫХ НА
ВЫХОДЕ ТЕХНОЛОГИЧЕСКИХ СХЕМ ИХ ПЕРЕРАБОТКИ

Таблица Б.1 —
Формулы расчета

ИНФОРМАЦИОННЫЕ
ДАННЫЕ

ССЫЛОЧНЫЕ НОРМАТИВНЫЕ ДОКУМЕНТЫ

СОДЕРЖАНИЕ

Assume that I have a huge file, which I split up into blocks. Each block is hashed with a hash function of $x$ bits. The chance of an error going undetected in a block should therefore be $1/2^x$.

Now, let’s assume a block is $y$ bytes in size, meaning there are $2^y$ possible values for that block of data. As $y$ gets bigger, there are more possible collisions for any given hash value, yet the chance of such a collision occurring seems to remain the same (correct?).

For my purposes, I need to split the data in many blocks, the more the better, but the more blocks, the more hashes which at some point take quite a lot of space to store. So I want to use a hash where $x$ can be small while still having a high chance of detecting errors.

So I got this idea that instead of hashing every block with a hash function of $x$ bits (illustation 1), I instead hash every block with a hash of $x/2$ bits. However to ensure that it is still possible to detect errors at the same rate as before, I add a second hash over every group of 4 blocks of $x/2$ bits (illustration 2):

Illustration 1

 |-----|-----|-----|-----|   4 hashes of x bits

 Total bits = 4*x

Illustration 2

 |-----|-----|-----|-----|   4 hashes of x/2 bits
 |-----------------------|   1 hash of x/2 bits

 Total bits = 5*x/2 = 2.5*x

Are these equivalent, how do they differ if not and how can I compare them?

Another possibility would be:

 |-----|-----|-----|-----|   4 hashes of x/2 bits
 |-----------------------|   1 hash of x bits

 Total bits = 4*x/2 + x = 3*x

I couldn’t find much on this topic through the usual sources.

Одним из очевидных методов проверки жгутов кодовых проводов и МЭСБ ДЗУ-8 с точки зрения максимальной вероятности обнаружения ошибки является метод сравнения с эталоном. Об этом свидетельствует формула вероятности обнаружения ошибки при использовании любого вида контроля:

,

где — число сочетаний из n no j;

р — вероятность одной ошибки (ошибки кратности 1);

Pj — вероятность появления ошибки j-й кратности;

P(P_np/Pj)- условная вероятность пропуска ошибки данным методом контроля при условии, что ошибка j-й кратности появляется с вероятностью Pj.

Выражение является вероятностью пропуска ошибки при выбранном методе контроля.

Однако, при контроле методом сравнения с эталоном необходимы исправные и проверенные на достоверность информации жгуты кодовых проводов и МЭСБ ДЗУ-8.

Приемлемым для автомата проверки жгутов кодовых проводов и МЭСБ ДЗУ-8 был признан контроль по mod 3, который не требовал большого объема контрольной аппаратуры и хорошо зарекомендовал себя при разработке и эксплуатации узлов, устройств и приборов ранее. При контроле по mod 3 проверяемый узел, в данном случае — жгут кодовых проводов, контролируется независимой схемой, использующей контрольные символы, являющиеся остатками от деления информационных слов на mod 3 .

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

Эталонная сумма может храниться в проверяемом узле или вне его, например, в сопровождаемой документации или в специальном запоминающем устройстве (или любом носителе информации).

Однако контрольное суммирование фиксирует сам факт неисправности или ошибки при считывании определенного массива информационных или кодовых слов, но не указывает место неисправности. В отличие от контрольного суммирования, контроль по mod 3 указывает адрес, по которому произошла ошибка или возникла неисправность.

Метод контрольного суммирования выгодно использовать при контроле больших массивов информационных или кодовых слов, что, однако, не исключает его применения при проверке жгутов кодовых проводов и МЭСБ ДЗУ-8. Метод контрольного суммирования вместе с контролем по mod 3 применим также и в приборах, в которых используются МЭСБ ДЗУ-8.

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

Была произведена оценка вероятности обнаружения ошибки при контроле по mod 3.

Оценка эффективности контроля по модулю.

— вероятность обнаружения ошибки или неисправности,

где — вероятность появления в интервале между проверками обнаруживаемой ошибки в массиве (n- число разрядов, m — число слов массива);

— вероятность появления ошибки (неисправности) в интервале между проверками, т.е. все ошибки — обнаруживаемые средствами контроля и необнаруживаемые;

Выразим и . Пусть:

— вероятность появления обнаруживаемой ошибки любой кратности в одном слове разрядности n;

— вероятность необнаружения ошибки любой кратности;

— вероятность необнаружения ошибки любой кратности во всех словах массива из m слов.

Тогда

— вероятность появления в интервале между проверками обнаруживаемых ошибок любой кратности среди всех слов массива.

Определение вероятности :

,

где — вероятность появления k-кратной ошибки (неисправности).

Применим биномиальный закон распределения случайной величины. Тогда, если q — вероятность появления ошибки в одном разряде слова, то получим:

— для ошибки кратности k.

В свою очередь, с учетом всех ошибок получим:

.

Осталось определить — вероятность обнаружения k-кратной ошибки средствами контроля по модулю Modul программным или аппаратным способом.

Примем во внимание, что кратность ошибки изменяется от 1 до n, т.е. k=1,2,…,n и что

.

Тогда

—

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

Подставим полученные выражения в формулу:

.

Учитывая, что q — вероятность появления ошибки в одном разряде слова, то:

— вероятность непоявления ошибки в одном разряде слова;

— вероятность непоявления ошибки во всех n разрядах m слов массива.

Тогда .

И теперь окончательно получаем выражение для оценки вероятности обнаружения ошибки или неисправности:

Это выражение может быть использовано для оценки эффективности контроля по модулю. В частности, может быть получена зависимость для носителей информации различной информационной емкости (0,5k; 1k; 2k; 4k; 8k; 16k и т.д.) и различной разрядности слов (8, 16, 32, 64 и т.д.) (рис. 1.18).

n=16

n=32

n=64

n=16

n=32

n=64

Рис. 1.18. Анализ разрядов оценки эффективности обнаружения ошибок.

Текст программы расчета и построения графиков приведен в разделе «Приложение».

Зависимости имеют выраженный минимум;

Условная вероятность обнаружения ошибки левее минимума повышается из-за увеличения надежности изделия ( и т.д.);

Условная вероятность обнаружения ошибки правее минимума повышается из-за увеличения вероятности появления ошибок, в том числе обнаруживаемых аппаратурой контроля по модулю 3;

Эффективность обнаружения ошибок при контроле по модулю 3 с увеличением числа разрядов информационных слов при q=const увеличивается;

Эффективность обнаружения ошибок при контроле по модулю 3 с уменьшением интенсивности ошибок увеличивается.

Построим зависимость Р_min=f(log₂ m) при n=16 (рис. 1.19).

m	log2 m	Pmin
0,5k=512	9	0,999424
1k=1024	10	0,999713
2k=2048	11	0,999857
4k=4096	12	0,999928
8k=8192	13	0,999964
16k=16384	14	0,999982
32k=32768	15	0,999991
64k=65536	16	0,999996
128k=131072	17	0,999998
256k=262144	18	0,999999

Рис. 1.19

Из графика видно, что с увеличением log₂m значение Р_min увеличивается, стремясь к единице. Т. е. эффективность обнаружения ошибок при контроле по модулю 3 с увеличением информационной емкости носителя информации (массива информации) увеличивается.

Высказанные выше соображения послужили основой для использования в совокупности контроля по mod 3 и контрольного суммирования для обеспечения обнаружения неисправности или ошибки с большой вероятностью. Была произведена оценка вероятности обнаружения ошибки при каждом рассмотренном выше виде контроля, а затем при их совместном исследовании. Вероятность появления ошибок j-й кратности в n-разрядном слове равна:

,

где — вероятность искажения одного разряда двоичного слова.

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

Были оценены вероятности обнаружения двойных и тройных ошибок. При этом рассмотрены представления массивов информационных и кодовых слов в виде матриц и выявлено общее число возможных двойных и тройных ошибок в слове, состоящем из n разрядов.

Общее число возможных двойных ошибок в n-разрядном слове равно:

.

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

Число пропускаемых ошибок двойной кратности, в случае если число разрядов кратно периоду повторения весовой функции , при контроле по mod 3 равно:

,

где — фиксируемое целое число, определяемое из выражения

( — модуль; если модуль равен 3, то и ) — период повторения весовой функции;

— коэффициент кратности;

— число разрядов слова.

Тогда вероятность пропуска двойной ошибки равна:

.

Для ошибок тройной кратности получим:

;

;

,

где — число возможных ошибок тройной кратности;

— число пропускаемых тройных ошибок;

— вероятность пропускания тройной ошибки.

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

где — число разрядов слова;

— число слов матрицы;

— текущий номер слова;

— текущий номер разряда слова;

— текущий разряд слова (текущий элемент матрицы).

Число возможных ошибок двойной кратности в этом случае равно:

.

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

.

Вероятность пропуска двойной ошибки равна:

.

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

Число возможных тройных ошибок было определено:

.

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

.

Вероятность пропуска тройных ошибок при использовании метода контрольного суммирования равна:

.

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

Оценены число и вероятность обнаружения двойных и тройных ошибок при совместном использовании контроля по mod 3 и контрольном суммировании:

,

где — число обнаруживаемых двойных ошибок по mod 3;

— число обнаруживаемых тройных ошибок по mod 3.

По методу контрольного суммирования все двойные ошибки, если они находятся в одном слове, обнаруживаются. Следовательно, ошибки, не обнаруженные контролем по mod 3, будут обнаружены методом контрольного суммирования. С другой стороны, если двойные ошибки находятся в разных словах (в разных строках матрицы ) и не могут быть обнаружены методом контрольного суммирования, то они будут обнаружены методом контроля по mod 3.

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