Бройдо В.Л. Вычислительные системы, сети и телекоммуникации (2002) (1186248), страница 157
Текст из файла (страница 157)
Во время оперативного !аппаратно-логического) контроля достоверности выполнение основных технологических операций пад информацией приостанавливается. Непрерывный контроль работоспособности— это уже ие контроль Лостовери ости и и формации, а контроль значений параметров компонентов системы с помощью встроенных в них датчиков. Классификация методов контроля достоверности по степени выявления и коррекции ошибок Г!о степени выявления и коррекции ошибок контроль делится па: ш обнарулшвающий, фиксирую~ций только сам фант пали шя илп отсутствия ошибкш 642 Глава 20.
Качество и эффективность информационных систем О 1окализующий, позволяющий определить как факт наличия, так и место опхнбки (например, символ, реквизит и т. д,); гз исправляющий, выполняющий функции и обнаружения, и локализации, и исправления ошибки. В работах [6, 8~ приведен обширный список методов контроля достоверности информации (более 100 методов), в том числе методы, использующие контрольные суммы и контрольные байты, коды с обнаружением и автоматическим исправлением ошибок (корректируюшие коды); методы семантического и балансового контроля, методы алгоритмического и эвристического контроля, методы верификации, прямого и обратного преобразования (передачи) информации и т.
д. Основные показатели качества контроля достоверности Функциональные показатели качества контроля (показатели его эффективности) должны количественно определять степень приспособленности и выполнения контролем поставленных перед ним задач. В обшем случае контроля такими показателями могут служить коэффициенты, численно равные условным вероятностям соответствуюших событий при условии наличия ошибки. Для обнаруживаюшего и локализуюшего контроля такими коэффициентами являются: о коэффициент обнаружения ошибок: К,„„-Льм/Лг, -Р „/Р „; гз коэффициент необнаружения ошибок: К„, - М,./Ф.„, = Р„„/Р.; гз коэффициент локализации ошибок К„,„для большинства методов локализующего контроля равен коэффициенту обнаружения, то есть К„,„= К,,г„,.
Методы контроля, исправляющие ошибки, характеризуются следующими коэффициентами: о коэффициент исправления ошибок К„„„= М„„„/М„„- Р, /Р„; й коэффициент искажения ошибок К„,, = У„„.„/М„„, = Р, „/Р й коэффициент обнаружения ошибок К„„- Кг„;„/Ф, - Рм„/Р„„; й коэффициент необнаружения ошибок К„. - Ж„./М„„, = Р„„/Р„„,. Достоверность информационных систем 643 В этих соотношениях: 1 Ср М вЂ” число структурных элементов (си~$волов, реквизитов, показателей и т. д.) в информационной совокупности; ГЗ М...М.ш„, КРв.ш ртми — число ошибок, которые в процессе контроля, соответственно, не обнаруживаются, правильно исправляются, неверно исправляются (искажаются), только обнаруживаются (факт наличия которых просто устанавливается, а сами они не исправляются); гз Р„ин Рмн, Рвш Рв„вш Рн„, — вероятности наличия ошибки, обнаружения, необнаружения, исправления и искажения ошибки соответственно.
Важными показателями качества контроля являются также: вз коэффициент выявления ошибок Квш та инин/т наш характеризующий суммарное относительное число выявляемых (Гн'. ) ошибок в контролируемой информационной совокупности; йз коаффициент трансформации ошибок Ктр и и /Хш характеризуроцгий суммарное относительное число необнаруженных и вновь внесенных при контроле (Фав, „„,) ошибок. Для контроля с исправлением ошибок: Книвнт Киаар+К +К ба~ Ктр К Кннн ' Для контроля с обнаружением ошибок: Кнш„=К, .-О; Канаш Кы Ктр Кна.
В качестве дополнительных функциональных показателей могут быть использованы значения вероятности правильного не обнаружения ошибки и ложного обнаружения ошибки, учитывающие надежность работы системы контроля: Рн, — вероятность правильного не обнаружения ошибки, то есть такого события, когда не вырабатывается информация о наличии ошибки при условии действительного ее отсутствия; ср Рл, — вероятность ложного обнаружения ошибки (ложной тревоги), то есть такого события, когда вырабатывается информация о наличии ошибки при реальном ее отсутствии.
Техыико-эксплуатационные показатели контроля: Ы алгоритмическая сложность контроля; йл вид и величина используемой избыточности; 644 Глава 20. Качество и эффективность информационных систем О надежносп контроля; к 1э универсальность (возможность использования на различных фазах технологического процесса, при решении различных задач и для различных групп и типов информационных ошибок) и т. д, Соответствующие коэффициенты К„р - Р„„/Р„„„К,„= Р.,/Р„„, могут быть существенно больше 1, поскольку Кв, ч- К„= (1 — Р„„,)/Р „,. Экономические показатели аффективности контроля — это затраты на контроль: Ы единовременные; ьз текущие; С3 материальные; а трудовые; временные.
Помехозащищенное кодирование информации Паиболес эффективными и перспективными методами контроля достоверности информации являются методы, использующие корректирующие коды с обнаружением и исправлением ошибок. При относительно небольшой избыточности (по сравнению с методами верификации, повторного преобразования и т.
п.) эти методы имеют высокую корректирующую способность. В технических системах корректирующие коды получили чрезвычайно широкое применение: в настоящее время, вероятно, нет ни одной эффективно функциопирукнцей сложной технической информационной системы, где бы многократно не использовались эти коды. В современных компьютерах, например, на основе кодов с обнаружением и кодов с автоматическим исправлением ошибок строится весьма разветвленный контроль достоверности многих блоков 1ранее мы упоминали об использовании в накопителях СП и ПЪ'П корректирующих кодов Рида Соломона; в дисковых массивах ВА1П циклических кодов с исправлением ошибок, в технологии ЗМАйТ и в модулях оперативной памяти кодов Хэмминга с исправлением ошибок и т.
д.). В арготехннческих компонентах ИС чаще используются обнаруживающие ошибки коды, а коды с автоматическим исправлением ошибок широкого использования пока не нагпли, вероятно, в связи с большей сложностью недвоичного исполнения этих кодов и малого знакомства с ними разработчиков и пользонателей информационных систем. Познакомимся кратко с основами построения корректирующих кодов в произвольной системе счисления. По общности построения корректирующих кодов все операции по преобразованию информации можно разделить на два класса; Достоверность информационных систем 645 1. Преобразования информации, в которых входные и выходные слова совпадают.
К этому классу преобразований отг1осятся операции передачи информации, хранения информации, перезаписи игй1юрмации с одного носителя на другой, ввода информации и вывода информации из компьютера. Практически этот класс преобразований охватывает почти все основные операции, выполняемые впе вычислительных машин, и многие операции внутри компьютеров.
2. Преобразования информации, в которых входные и выходные слова в общем случае не совпадают: арифметические и логические операции над информацией. Для разработчиков и пользователей ИС наибольший интерес представляют корректирующие коды для преобразований 1-го класса, ибо преобразования 2-го класса почти все выполняются внутри компьютера, где для обеспечения достоверности используются двоичные корректирующие коды, в том числе и арифметические. Во внемашинной сфере более предпочтительны недвоичные корректирующие коды, десятичные и буквенно-цифровые, в частности. При построении любых корректирующих кодов используется синтаксическая информационная избыточность преобразуемых данных, или, другимн словами, избыточность кодирования информации. Введение избьггочности, естествешю, приводит к увеличению объема перерабатываемой информации, к увеличению времени ее обработки, к усложнению аппаратуры.
Код, позволяющий достичь задашюго эффекта коррекции прп минимальной, теоретически допустимой избыточности, считается оптимальным. Корректирующая способность кода, так же как и метода контроля, определяезтя условными верояююстями (коэффициентами) необнаружения, обнаружения, искажения или исправления соответствующего класса ошибок: К„,, Кж, К ., К.... Основная идея обнаружения и исправления ошибок преобразования информации с использованием корректирующих кодов состоит в следуюьцем.
При обнаружении ошибок все множество входных и выходных слов ИС преобразования разбивается на две категории: разрешенных слов множества и запрещенныхх слов множества. Если в результате преобразования получаем выходное слово, относящееся к категории разрешенных слов, считаем, что операция выполнена правильно; если в результате преобразования получаем выходное слово, относящееся к категории запрещенных слов, значит, при выполнении преобразования была допущена ошибка. Используем понятие кодового расстояния между словами (кодовыми словами). Кодовое расстояние — д — между двумя словами равно числу разрядов, в которых рассматриваемые слова различаются между собой. Для обнаружения однократной ошибки (ошибки в одном разряде) достаточно выбрать такие разрешенные слова, которые отличаются друг от друга как минимум в двух разрядах, то есть кодовое расстояние между разрешенными кодовыми словами должно быть и >= 2.
В общем случае, для возможности обнаружения ошибки кратности 1ьъ (ошибки, исказившей 1м„символов в кодовом слове) минимальное кодовое расстояние между разрешенными кодовыми словами должно быть: г1„„, = 1ы. + 1. 646 Глава 20. Качество и эффективность информационных систем При исправлении ошибок все множество входных и выходных слов разбиваешься на группы, и каждому разрешенному кодовому слону ставится в соответствие офпа такая группа. Если в результате преобразования получили запрещенное слдво, входящее в состав одной из таких групп, то оно заменяется тем разрешенным словом, которому поставлена в соответствие данная группа. Для исправления однократной ошибки достаточно выбрать разрешенные кодовые слова так, чтобы они нахолились друг от друга на кодовом расстоянии г1>- 3, а разрешенным кодовым словам пос~авить в соответствие все запрещенные слова, находящиеся от них на кодовом расстоянии д = 1 (действительно, однократная ошибка изменяет в слоне только один символ, следовательно, может переместить искаженное слово только на расстояние г1 - 1 от правильного).
В общем случае, для возможности исправления всех ошибок кратности не больше, чем 1.„„, необходимо иметь минимальное кодовое расстояние между разрешенными кодовыми словами; г1„„„= 2 1„„„+ 1. Сушествуют коды, позволяющие автоматически исправлять все ошибки кратности не больше 1„„ч н одновременно обнаруживать все ошибки кратности не больше (ыы причем 1м„>= 1„„ч. В этом случае необходимо иметь кодовое расстояние между разрешенными кодовыми словами: г1.„„= 1„„„ч.
(,Гм ч 1. Многие алгоритмы построения различных корректирующих кодов (в том числе и циклических, и итеративных) рассмотрены в работах 16, 8]. Ниже познакомимся лишь с песколькимн конкретными корректирующими кодами с обнаружением н исправлением ошибок, предварительно заметив, что однократные ошибки в ИС обычно встречаются гораздо чаще двукратных, а последние— чагце трехкратных и т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
