Бройдо В.Л., Ильина О.П. Архитектура ЭВМ и систем (2006) (1186249), страница 153
Текст из файла (страница 153)
д.) в информационной совокупности; 0 №и, №снн, №,к, №вн — число ошибок, которые в процессе контроля соответственно, не обнаруживаются, правильно исправляются, неверно исправляются (искажаются), только обнаруживаются (факт наличия которых просто устанавливается, а сами они не исправляются); 0 Рнии Ран, Рн Ри„,р, Рис, — вероятности наличия, обнаружения, необнаружения, исправления и искажения ошибки соответственно. Важными показателями качества контроля являются также: а коэффициент выявления ошибок Ки„н, = №ил /№ин характеризующий суммарное относительное число выявляемых (№„н ) ошибок в контролируемой информационной совокупности; О коэффициент трансформации ошибок Кч, - №и, нн„/№нн характеризующий суммарное относительное число необнаруженных и вновь внесенных при контроле (№н,,„„) ошибок. Для контроля с исправлением ошибок: Кпыннл Кнсир+ Кнск+ Кпвн~ Кта Кнн Кисл Для контроля с обнаружением ошибок: Кисин Киск Ф К|пипл Клан~ Ктр Кнн В качестве дополнительных функциональных показателей могут быть использованы значения вероятности правильного необнаружения ошибки и ложного обнаружения ошибки, учитывающие надежность работы системы контроля: 675 Обеспечение достоверности информации д Рч, — вероятность правильного необнаружения ошибки, то есть такого события, когда не вырабатывается информация о наличии ошибки при условии действительного ее отсутствия; О Р, „— вероятность ложного обнаружения ошибки (ложной тревоги), то есть такого события, когда вырабатывается информация о наличии ошибки при реальном ее отсутствии.
Технико-эксплуатационные показатели контроля: О алгоритмическая сложность контроля; о вид и величина используемой избыточности; О надежность контроля; а универсальность (возможность использования на различных фазах технологического процесса, при решении различных задач и для различных групп и типов информационных ошибок) и др. Соответствующие коэффициенты Кн„= Р„„/Р„„н К,, = Р,,/Рпе могут быть существенно больше 1, поскольку Кнр ч. К„,, = (1 — Ри„)/Р „.
Экономические показатели эффективности контроля — это затраты на контроль: О единовременные; О текущие; О материальные; 0 трудовые; О временные. Помехозащищенное кодирование информации Наиболее эффективными и перспективными методами контроля достоверности информации являются методы, использующие корректирующие коды с обнаружением и исправлением ошибок. При относительно небольшой избыточности (по сравнению с методами верификации, повторного преобразования и т. п.) эти методы имеют высокую корректирующую способность. В технических системах корректирующие коды получили чрезвычайно широкое применение: в настоящее время, вероятно, нет ни одной эффективно функционирующей сложной технической информационной системы, где бы многократно не использовались эти коды. В современных компьютерах, например, на основе кодов с обнаружением и кодов с автоматическим исправлением ошибок строится весьма разветвленный контроль достоверности многих блоков (ранее уже упоминалось об использовании в накопителях С1) и РЧ1) корректирующих кодов Рида — Соломона, в дисковых массивах КАП) — циклических кодов с исправлением ошибок, в технологии БМАКТ и в модулях оперативной памяти — кодов Хзмминга с исправлением ошибок и т.
д.). В эргатехнических компонентах ИВС чаще используются обнаруживающие ошибки коды, а коды с автоматическим исправлением ошибок широкого использования пока не нашли, вероятно, в связи с большей сложностью недвоичного Глава 29. Достоверность информационных систем исполнения этих кодов и слабого знакомства с ними разработчиков и пользователей информационных систем.
Познакомимся кратко с основами построения корректирующих кодов в произвольной системе счисления. По общности построения корректирующих кодов все операции по преобразованию информации можно разделить на два класса: ьз Преобразования информации, в которых входные и выходные слова совпадают. К этому классу преобразований относятся операции передачи, хранения, перезаписи информации с одного носителя на другой, ввода информации и вывода ее из компьютера. Практически этот класс преобразований охватывает почти все основные операции, выполняемые вне вычислительных машин, и многие операции внутри компьютеров.
ьз Преобразования информации, в которых входные и выходные слова в общем случае не совпадают: арифметические и логические операции над информацией. Для разработчиков и пользователей ИВС наибольший интерес представляют корректирующие коды для преобразований 1-го класса, так как почти все преобразования 2-го класса выполняются внутри компьютера, где для обеспечения достоверности используются двоичные корректирующие коды, в том числе и арифметические. Во внемашинной сфере более предпочтительны недвоичные корректирующие коды, десятичные и буквенно-цифровые в частности.
При построении любых корректирующих кодов используется синтаксическая информационнал избыточяопль преобразуемых данных, или, другими словами, избыточность кодирования информации. Введение избыточности, естественно, приводит к увеличению объема перерабатываемой информации и времени ее обработки, к усложнению аппаратуры. Код, позволяющий достичь заданного эффекта коррекции при минимальной теоретически допустимой избыточности, считается оптимальным.
Корректирующая способность кода, так же как и метода контроля, определяется условными вероятностями (коэффициентами необнаружения, обнаружения, искажения или исправления) соответствующего класса ошибок: К„„, К»„, К„,„, Кнтьк Основная идея обнаружения и исправления ошибок преобразования информации с использованием корректирующих кодов состоит в следующем. При обнаружении ошибок все множество входных и выходных слов ИВС преобразования разбивается на две категории: разрешенных слов множества и запрещенных слов множества. Если в результате преобразования получаем выходное слово, относящееся к категории разрешенных слов, считаем, что операция выполнена правильно; если выходное слово относится к категории запрещенных слов, значит, при выполнении преобразования была допущена ошибка. Используем понятие кодового расстояния между словами (кодовыми словами).
Кодовое расстояние Н между двумя словами равно числу разрядов, в которых Обеспечение достоверности информации 677 рассматриваемые слова различаются между собой. Для обнаружения однократной ошибки (ошибки в одном разряде) достаточно выбрать такие разрешенные слова, которые отличаются друг от друга как минимум в двух разрядах, то есть кодовое расстояние между разрешенными кодовыми словами должно быть И > 2. В общем случае для возможности обнаружения ошибки кратности 1см (ошибки, исказившей 1;н символов в кодовом слове) минимальное кодовое расстояние между разрешенными кодовыми словами должно быть: п„,щ- 1ненч- 1.
При исправлении ошибок все множество входных и выходных слов разбивается на группы, и каждому разрешенному кодовому слову ставится в соответствие одна такая группа. Если в результате преобразования получили запретценное слово, входящее в состав одной из таких групп, то оно заменяется тем разрешенным словом, которому поставлена в соответствие данная группа. Для исправления однократной ошибки достаточно выбрать разрешенные кодовые слова так, чтобы они находились друг от друга на кодовом расстоянии Н > 3, а разрешенным кодовым словам поставить в соответствие все запрещенные слова, находящиеся от них на коловом расстоянии г1 - 1 (действительно, однократная ошибка изменяет в слове только один символ, следовательно, может переместить искаженное слово только на расстояние с( - 1 от правильного).
В общем случае для возможности исправления всех ошибок кратности не больше, чем 1н„,„, необходимо иметь минимальное кодовое расстояние между разрешенными кодовыми словами Ы ь= 21нтнрч- Е Существуют коды, позволяющие автоматически исправлять все ошибки кратности не больше 1ч„„, и одновременно обнаруживать все ошибки кратности не больше 1,е„причем 1„тн, > 1н„,„В этом случае необходимо иметь следующее кодовое расстояние между разрешенными кодовыми словами; ппм = 1нтнр+ 1обв+ Многие алгоритмы построения различных корректирующих кодов (в том числе и циклических, и итеративных) рассмотрены в работах (6, 8!.
Ниже познакомимся лишь с несколькими конкретными корректирующими кодами с обнаружением и исправлением ошибок, предварительно заметив, что однократные ошибки в ИВС обычно встречаются гораздо чаще двукратных, а последние — чаще трехкратных, и т. д. При независимости возникновения искажений в символах вероятность появления однократной ошибки подчиняется биномиальному закону так, что соотношение частот появления однократных и двукратных ошибок лежит в пределах 500-1000.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
