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

DDR

Таблица 6.1.Характеристика микросхем DDR

	DDR1	DDR2	DDR3
Буфер предвыборки,бит
Уровень сигналов,В	2.5	1.8	1.5
Частота шины	200,266,333,400	400,533,677,800	800,1066, 1330, 1600

Рис.6.15 Структура DDR SDRAM c иллюстрацией идеи n-битовой предвыборки

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

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

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

На рисунке показано, каким образом осуществляются обнаружение и исправление ошибок. Перед записью М-разрядных данных в память производится их обработка, обозначенная на схеме функцией ≪f≫, в результате которой формируется добавочный К -разрядный код. В память заносятся как данные, так и этот вычисленный код, то есть (М + К)-разрядная информация. При чтении информации повторно формируется К -разрядный код, который сравнивается с аналогичным кодом, считанным из ячейки. Сравнение приводит к одному из трех результатов:

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

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

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

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

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

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

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

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

Простейший вид такого кода основан на добавлении к каждому байту информации одного бита паритета. Бит паритета — это дополнительный бит, значение которого устанавливается таким, чтобы суммарное число единиц в данных, с учетом этого дополнительного разряда, было четным (или нечетным). В ряде систем за основу берется четность, в иных — нечетность. Для 64-разрядного слова требуется восемь битов паритета, то есть ячейка памяти должна хранить 36 разрядов.

При записи слова в память для каждого байта формируется бит паритета. Это может быть сделано с помощью схемы в виде дерева, составленного из схем сложения по модулю 2. При чтении из памяти выполняется аналогичная операция над считанными информационными битами, а ее результат сравнивается с битом паритета, вычисленным при записи и хранившимся в памяти. Метод позволяет обнаружить ошибку, если исказилось нечетное количество битов. При четном числе ошибок метод неработоспособен. К сожалению, фиксируя ошибку, данный способ кодирования не может указать на ее местоположение, что позволило бы внести исправления, в силу чего его называют кодом с обнаружением ошибки (EDC — Error Detection Code).

В основе корректирующих кодов лежит достаточно простая идея [39]. Для контроля двоичного информационного кода длиной М бит добавим к ней К дополнительных контрольных разрядов так, что общая длина последовательности теперь будет равна М + К разрядам. В этом случае из возможных N=2^M+KК комбинаций интерес представляют только L = 2^M последовательностей, которые называют разрешенными. Оставшиеся N- L последовательностей назовем запрещенными. Если

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

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

Простейший вариант корректирующего кода также может быть построен на базе битов паритета. Для этого биты данных представляются в виде матрицы, к каждой строке и столбцу которой добавляется бит паритета. Для 64-разрядных данных этот подход иллюстрирует табл. 5.1 [200]. Здесь D — биты данных, С— столбец битов паритета строк, К — строка битов паритета столбцов, Р — бит паритета, кон-тролирующий столбец С и строку К. Таким образом, к 64 битам данных нужно добавить 17 бит паритета: по 8 бит на строки и столбцы и один дополнительный бит для контроля строки и столбца битов паритета. Если в одной строке и одном столбце обнаружено нарушение паритета, для исправления ошибки достаточно просто

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

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

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

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

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

рис. 5.16

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

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

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

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

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

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

это легко выявить. Путем проверки паритета обнаруживаются несоответствия в окружностях А и В. Для окружности Б несоответствия нет. Только один из семи сегментов присутствует в окружностях А и В и отсутствует в Б, и ошибка может быть исправлена за счет изменения бита в этом сегменте (см. рис. 5.16, г).

Иллюстрация из Вернера, Основы кодирования, с.71

Для пояснения концепции, положенной в основу кода Хэмминга, построим код,обнаруживающий и исправляющий однобитовые ошибки в 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