Помехозащищенное кодирование информации

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

В технических системах корректирующие коды получили чрезвычайно широкое применение: в настоящее время, вероятно, нет ни одной эффективно функционирующей сложной технической информационной системы, где бы многократно не использовались эти коды. В современных компьютерах, например, на основе кодов с обнаружением и кодов с автоматическим исправлением ошибок строится весьма разветвленный контроль достоверности многих блоков (ранее уже упоминалось об использовании в накопителях CD и DVD корректирующих кодов Рида–Соломона; в дисковых массивах RAID циклических кодов с исправлением ошибок, в технологии SMART и в модулях оперативной памяти кодов Хэмминга с исправлением ошибок и т. д.).

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

Познакомимся кратко с основами построения корректирующих кодов в произвольной системе счисления.

По общности построения корректирующих кодов все операции по преобразованию информации можно разделить на два класса.

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

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

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

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

Корректирующая способность кода, также как и метода контроля, определяется условными вероятностями (коэффициентами не-обнаружения, обнаружения, искажения или исправления) соответствующего класса ошибок: К_но, К_обн, К_иск, К_испр.

Основная идея обнаружения и исправления ошибок преобразования информации с использованием корректирующих кодов состоит в следующем.

При обнаружении ошибок все множество входных и выходных слов ИС преобразования разбивается на две категории: разрешенных слов множества и запрещенных слов множества. Если в результате преобразования получаем выходное слово, относящееся к категории разрешенных слов, считаем, что операция выполнена правильно; если выходное слово относится к категории запрещенных слов, значит, при выполнении преобразования была допущена ошибка.

Используем понятие кодового расстояния между словами (кодовыми словами). Кодовое расстояние — d — между двумя словами равно числу разрядов, в которых рассматриваемые слова различаются между собой. Для обнаружения однократной ошибки (ошибки в одном разряде) достаточно выбрать такие разрешенные слова, которые отличаются друг от друга как минимум в двух разрядах, то есть кодовое расстояниемежду разрешенными кодовыми словами должно быть d >= 2.

В общем случае для возможности обнаружения ошибки кратности l_обн (ошибки, исказившей l_обн символов в кодовом слове) минимальное кодовое расстояние между разрешенными кодовыми словами должно быть:

d_мин = l_обн + 1.

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

Для исправления однократной ошибки достаточно выбрать разрешенные кодовые слова так, чтобы они находились друг от друга на кодовом расстоянии d >= 3, а разрешенным кодовым словам поставить в соответствие все запрещенные слова, находящиеся от них на кодовом расстоянии d = 1 (действительно, однократная ошибка изменяет в слове только один символ, следовательно, может переместить искаженное слово только на расстояние d = 1 от правильного).

В общем случае, для возможности исправления всех ошибок кратности не больше, чем l_испр, необходимо иметь минимальное кодовое расстояние между разрешенными кодовыми словами:

d_мин = 2 · l_испр + 1.

Существуют коды, позволяющие автоматически исправлять все ошибки кратности не больше l_испр и, одновременно, обнаруживать все ошибки кратности не больше l_обн, причем l_обн >= l_испр. В этом случае необходимо иметь следующее кодовое расстояние между разрешенными кодовыми словами:

d_мин = l_испр + l_обн + 1.

Многие алгоритмы построения различных корректирующих кодов (в том числе и циклических, и итеративных) рассмотрены в работах [6, 8].

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