Обнаружение и исправление ошибок

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

ного рода отказов и сбоев. Причиной отказов могут быть производственные де-

фекты, повреждение микросхем или их физический износ. Проявляются отказы

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

ется 0 или 1, вне зависимости от реально записанной туда информации. Сбой —

это случайное событие, выражающееся в неверном считывании или записи инфор-

мации в отдельных разрядах одной или нескольких ячеек, не связанное с дефекта-

ми микросхемы. Сбои обычно обусловлены проблемами с источником питания

или с воздействием альфа-частиц, возникающих в результате распада радиоактив-

ных элементов, которые в небольших количествах присутствуют практически

в любых материалах. Как отказы, так и сбои крайне нежелательны, поэтому в боль-

шинстве систем основной памяти содержатся схемы, служащие для обнаружения

и исправления ошибок.

Вне зависимости от того, как именно реализуется контроль и исправление оши-

бок, в основе их всегда лежит введение избыточности. Это означает, что контроли-

руемые разряды дополняются контрольными разрядами, благодаря которым и воз-

можно детектирование ошибок, а в ряде методов — их коррекция. Общую схему

обнаружения и исправления ошибок иллюстрирует рис. 5.15.

На рисунке показано, каким образом осуществляются обнаружение и исправ-

ление ошибок. Перед записью М-разрядных данных в память производится их об-

работка, обозначенная на схеме функцией ≪f≫, в результате которой формируется

добавочный К -разрядный код. В память заносятся как данные, так и этот вычис-

ленный код, то есть (М + К)-разрядная информация. При чтении информации по-

вторно формируется К -разрядный код, который сравнивается с аналогичным ко-

дом, считанным из ячейки. Сравнение приводит к одному из трех результатов:

• Нe обнаружено ни одной ошибки. Извлеченные из ячейки данные подаются

на выход памяти.

• Обнаружена ошибка, и она может быть исправлена. Биты данных и добавоч-

ного кода подаются на схему коррекции. После исправления ошибки в М-раз-

рядных данных они поступают на выход памяти.

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

о неисправимой ошибке.

Коды, используемые для подобных операций, называют корректирующими ко-

дами или кодами с исправлением ошибок.

Простейший вид такого кода основан на добавлении к каждому байту инфор-

мации одного бита паритета. Бит паритета — это дополнительный бит, значение

которого устанавливается таким, чтобы суммарное число единиц в данных, с уче-

том этого дополнительного разряда, было четным (или нечетным). В ряде систем

за основу берется четность, в иных — нечетность. Для 64-разрядного слова требу-

ется восемь битов паритета, то есть ячейка памяти должна хранить 36 разрядов.

При записи слова в память для каждого байта формируется бит паритета. Это мо-

жет быть сделано с помощью схемы в виде дерева, составленного из схем сложе-

ния по модулю 2. При чтении из памяти выполняется аналогичная операция над

считанными информационными битами, а ее результат сравнивается с битом па-

ритета, вычисленным при записи и хранившимся в памяти. Метод позволяет об-

наружить ошибку, если исказилось нечетное количество битов. При четном числе

ошибок метод неработоспособен. К сожалению, фиксируя ошибку, данный способ

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

исправления, в силу чего его называют кодом с обнаружением ошибки (EDC — Error

Detection Code).

В основе корректирующих кодов лежит достаточно простая идея [39]. Для кон-

троля двоичного информационного кода длиной М бит добавим к ней К дополни-

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

будет равна М + К разрядам. В этом случае из возможных N= 2М+К комбинаций

интерес представляют только L = 2м последовательностей, которые называют раз-

решенными. Оставшиеся N- L последовательностей назовем запрещенными. Если

при обработке (записи в память, считывании или передаче) разрешенной кодовой

последовательности произойдут ошибки и возникнет одна из запрещенных после-

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

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

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

множества запрещенных последовательностей на L непересекающихся подмно-

жеств и каждому подмножеству поставить в соответствие одну из разрешенных

последовательностей. Тогда, если была принята некоторая запрещенная последо-

вательность, входящая в одно из подмножеств, считается, что передана разрешен-

ная последовательность, соответствующая этому подмножеству, производится за-

мена, чем и исправляется возникшая ошибка.

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

битов паритета. Для этого биты данных представляются в виде матрицы, к каждой

строке и столбцу которой добавляется бит паритета. Для 64-разрядных данных

этот подход иллюстрирует табл. 5.1 [200]. Здесь D — биты данных, С— столбец

битов паритета строк, К — строка битов паритета столбцов, Р — бит паритета, кон-

тролирующий столбец С и строку К. Таким образом, к 64 битам данных нужно до-

бавить 17 бит паритета: по 8 бит на строки и столбцы и один дополнительный бит

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

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

инвертировать бит на пересечении этих строки и столбца. Если ошибка паритета

выявлена только в одной строке или только одном столбце либо одновременно в

нескольких строках и столбцах, фиксируется многобитовая ошибка и формирует-

ся признак невозможности коррекции.

Недостаток рассмотренного приема в том, что он требует большого числа до-

полнительных разрядов. Более эффективным представляется код, предложенный

Ричардом Хэммингом и носящий его имя (код Хэмминга). Логику этого кода для

четырехразрядных слов (М = 4) иллюстрирует диаграмма Венна1, приведенная на

рис. 5.16

Три пересекающихся окружности образуют семь сегментов. Четырем битам

данных назначаются внутренние сегменты (см. рис. 5.16, а), а остальные сегменты

заполняются битами паритета. Биты паритета выбираются таким образом, чтобы

общее число единиц в каждой окружности было четным (см. рис. 5.16, б). Так, посколь-

ку окружность А содержит одну единицу, бит паритета для нее принимается равным

1. Теперь, если в результате ошибки изменится один из битов данных (см. рис. 5.16, в),

это легко выявить. Путем проверки паритета обнаруживаются несоответствия

в окружностях А и В. Для окружности Б несоответствия нет. Только один из семи

сегментов присутствует в окружностях А и В и отсутствует в Б, и ошибка может

быть исправлена за счет изменения бита в этом сегменте (см. рис. 5.16, г).

Для пояснения концепции, положенной в основу кода Хэмминга, построим код,

обнаруживающий и исправляющий однобитовые ошибки в 8-разрядных словах

(пример взят из [47]).

Сначала определим требуемую длину корректирующего кода. В соответствии

с рис. 5.15, на вход схемы сравнения поступают два К -разрядных значения. Срав-

нение производится путем поразрядной операции ≪исключающее ИЛИ≫ (сложе-

ние по модулю 2) над входными кодами. Результатом является так называемое

слово синдрома. В зависимости от того, было ли совпадение входных кодов или

нет, соответствующий бит синдрома будет равен 0 или 1.

Слово синдрома состоит из К разрядов

--------------------------------------------------------------------

Слово синдрома состоит из К разрядов, то есть его возможные значения лежат

в диапазоне от 0 до 2К - 1. Значение 0 соответствует случаю, когда ошибки не об-

наружено, остальные 2К - 1 случая свидетельствуют о наличии ошибки и указывают

на ее местоположение. Поскольку ошибка может возникнуть в любом из М битов

данных или К контрольных битов, мы должны иметь 2К - 1 > М + К. Это выраже-

ние позволяет определить число битов, необходимое для исправления одиночной

ошибки в М -разрядных данных

В табл. 5.2 приведено количество корректирующих разрядов, нужное для конт-

роля данных различной разрядности. Из таблицы видно, что для 8-разрядных слов

требуется четыре корректирующих разряда.

Для удобства будем формировать четырехразрядный синдром со следующими

характеристиками:

• Если синдром содержит все нули, значит, не обнаружено ни одной ошибки.

• Если синдром содержит единственную единицу в одном из разрядов, это озна-

чает, что выявлена ошибка в одном из четырех корректирующих разрядов и ни-

какой коррекции не требуется.

• Если в синдроме в единичное состояние установлены несколько битов, то чис-

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

ления которой необходимо инвертировать бит в этой позиции.

Под контрольные разряды отводятся те биты, чьи позиционные номера пред-

ставляютсобой степень числа 2 (табл. 5.3). Отдельный контрольный разряд от-

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

теми битами Рi, которые делают справедливым соотношение 2, = п. Например, раз-

ряд данных с позиционным номером 710 (01112) контролируется битами 4, 2 и 1

(7 - 4 + 2 + 1), а разряд с номером 1010 (10102) - битами 8 и 2 (10 - 8 + 2).

Дата добавления: 2014-01-14