ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 25.12.2021
Просмотров: 5259
Скачиваний: 8
2 3 6 Глава 5. Память
бы арбитража при одномоментном обращении к одной и той же ячейке. В то же
время есть и существенные отличия.
Первое состоит в том, что у микросхемы нет входов для указания адреса ячей-
ки, занесение и считывание данных производится в порядке их поступления через
одну входную точку и одну выходную.
Второе отличие связано с необходимостью слежения за состоянием очереди.
Для этого в микросхеме имеются регистры-указатели адресов начала и конца оче-
реди, а также специальные флаги, которые указывают на две ситуации: отсутствие
данных (в этом случае блокируется считывание из микросхемы) и полное запол-
нение памяти (блокируется запись).
Обнаружение и исправление ошибок
При работе с полупроводниковой памятью не исключено возникновение различ-
ного рода отказов и сбоев. Причиной
отказов
могут быть производственные де-
фекты, повреждение микросхем или их физический износ. Проявляются отказы
в том, что в отдельных разрядах одной или нескольких ячеек постоянно считыва-
ется 0 или 1, вне зависимости от реально записанной туда информации.
Сбой —
это случайное событие, выражающееся в неверном считывании или записи инфор-
мации в отдельных разрядах одной или нескольких ячеек, не связанное с дефекта-
ми микросхемы. Сбои обычно обусловлены проблемами с источником питания
или с воздействием альфа-частиц, возникающих в результате распада радиоактив-
ных элементов, которые в небольших количествах присутствуют практически
в любых материалах. Как отказы, так и сбои крайне нежелательны, поэтому в боль-
шинстве систем основной памяти содержатся схемы, служащие для обнаружения
и исправления ошибок.
Вне зависимости от того, как именно реализуется контроль и исправление оши-
бок, в основе их всегда лежит введение избыточности. Это означает, что контроли-
руемые разряды дополняются контрольными разрядами, благодаря которым и воз-
можно детектирование ошибок, а в ряде методов — их коррекция. Общую схему
обнаружения и исправления ошибок иллюстрирует рис. 5.15.
На рисунке показано, каким образом осуществляются обнаружение и исправ-
ление ошибок. Перед записью М-разрядных данных в память производится их об-
работка, обозначенная на схеме функцией «f», в результате которой формируется
добавочный
К
-разрядный код. В память заносятся как данные, так и этот вычис-
ленный код, то есть
(М + К
)-разрядная информация. При чтении информации по-
вторно формируется
К
-разрядный код, который сравнивается с аналогичным ко-
дом, считанным из ячейки. Сравнение приводит к одному из трех результатов:
• Нe обнаружено ни одной ошибки. Извлеченные из ячейки данные подаются
на выход памяти.
• Обнаружена ошибка, и она может
быть исправлена.
Биты данных и добавоч-
ного кода подаются на схему коррекции. После исправления ошибки в М-раз-
рядных данных они поступают на выход памяти.
• Обнаружена ошибка, и она не
может быть исправлена.
Выдается сообщение
о неисправимой ошибке.
Обнаружение и исправление ошибок
2 3 7
Рис. 5.15
Общая схема обнаружения и исправления ошибок [200]
Коды, используемые для подобных операций, называют
корректирующими ко-
дами
или
кодами с исправлением ошибок.
Простейший вид такого кода основан на добавлении к каждому байту инфор-
мации одного
бита паритета.
Бит паритета — это дополнительный бит, значение
которого устанавливается таким, чтобы суммарное число единиц в данных, с уче-
том этого дополнительного разряда, было четным (или нечетным). В ряде систем
за основу берется четность, в иных — нечетность. Для 64-разрядного слова требу-
ется восемь битов паритета, то есть ячейка памяти должна хранить 36 разрядов.
При записи слова в память для каждого байта формируется бит паритета. Это мо-
жет быть сделано с помощью схемы в виде дерева, составленного из схем сложе-
ния по модулю 2. При чтении из памяти выполняется аналогичная операция над
считанными информационными битами, а ее результат сравнивается с битом па-
ритета, вычисленным при записи и хранившимся в памяти. Метод позволяет об-
наружить ошибку, если исказилось нечетное количество битов. При четном числе
ошибок метод неработоспособен. К сожалению, фиксируя ошибку, данный способ
кодирования не может указать на ее местоположение, что позволило бы внести
исправления, в силу чего его называют
кодом с обнаружением ошибки
(EDC — Error
Detection Code).
В основе корректирующих кодов лежит достаточно простая идея [39]. Для кон-
троля двоичного информационного кода длиной
М
бит добавим к ней
К
дополни-
тельных контрольных разрядов так, что общая длина последовательности теперь
будет равна
М + К
разрядам. В этом случае из возможных
N= 2
М+К
комбинаций
интерес представляют только
L
=
2
м
последовательностей, которые называют
раз-
решенными.
Оставшиеся
N- L
последовательностей назовем
запрещенными.
Если
при обработке (записи в память, считывании или передаче) разрешенной кодовой
последовательности произойдут ошибки и возникнет одна из запрещенных после-
довательностей, то тем самым эти ошибки обнаруживаются. Если же ошибки пре-
вратят одну разрешенную последовательность в другую, то такие ошибки не могут
быть обнаружены. Для исправления ошибок необходимо произвести разбиение
множества запрещенных последовательностей на
L
непересекающихся подмно-
2 3 8 Глава 5. Память
жеств и каждому подмножеству поставить в соответствие одну из разрешенных
последовательностей. Тогда, если была принята некоторая запрещенная последо-
вательность, входящая в одно из подмножеств, считается, что передана разрешен-
ная последовательность, соответствующая этому подмножеству, производится за-
мена, чем и исправляется возникшая ошибка.
Простейший вариант корректирующего кода также может быть построен на базе
битов паритета. Для этого биты данных представляются в виде матрицы, к каждой
строке и столбцу которой добавляется бит паритета. Для 64-разрядных данных
этот подход иллюстрирует табл. 5.1 [200]. Здесь
D
— биты данных,
С—
столбец
битов паритета строк,
К
— строка битов паритета столбцов,
Р
— бит паритета, кон-
тролирующий столбец
С
и строку
К.
Таким образом, к 64 битам данных нужно до-
бавить 17 бит паритета: по 8 бит на строки и столбцы и один дополнительный бит
для контроля строки и столбца битов паритета. Если в одной строке и одном столбце
обнаружено нарушение паритета, для исправления ошибки достаточно просто
инвертировать бит на пересечении этих строки и столбца. Если ошибка паритета
выявлена только в одной строке или только одном столбце либо одновременно в
нескольких строках и столбцах, фиксируется многобитовая ошибка и формирует-
ся признак невозможности коррекции.
Недостаток рассмотренного приема в том, что он требует большого числа до-
полнительных разрядов. Более эффективным представляется код, предложенный
Ричардом Хэммингом и носящий его имя
(код Хэмминга).
Логику этого кода для
четырехразрядных слов
(М =
4) иллюстрирует диаграмма Венна
1
, приведенная на
рис. 5.16
Три пересекающихся окружности образуют семь сегментов. Четырем битам
данных назначаются внутренние сегменты (см. рис. 5.16,
а),
а остальные сегменты
заполняются битами паритета. Биты паритета выбираются таким образом, чтобы
Диаграмма Венна — это графическое представление операций над множествами, где множества обо-
значаются замкнутыми областями, содержащими внутри себя все элементы этих множеств. Диаграм-
ма используется для отображения логических отношений между элементами множеств. Так, заштри-
хованная область на рис. 5.16,
г
есть представление функции пересечения множеств А, Б и В
(математически это записывается как
Обнаружение и исправление ошибок 2 3 9
Рис. 5.16. Иллюстрация кода Хэмминга для четырехразрядного слова
общее число единиц в каждой окружности было четным (см. рис. 5.16, б). Так, посколь-
ку окружность А содержит одну единицу, бит паритета для нее принимается равным
1. Теперь, если в результате ошибки изменится один из битов данных (см. рис. 5.16,
в),
это легко выявить. Путем проверки паритета обнаруживаются несоответствия
в окружностях А и В. Для окружности Б несоответствия нет. Только один из семи
сегментов присутствует в окружностях А и В и отсутствует в Б, и ошибка может
быть исправлена за счет изменения бита в этом сегменте (см. рис. 5.16, г).
Для пояснения концепции, положенной в основу кода Хэмминга, построим код,
обнаруживающий и исправляющий однобитовые ошибки в 8-разрядных словах
(пример взят из [47]).
Сначала определим требуемую длину корректирующего кода. В соответствии
с рис. 5.15, на вход схемы сравнения поступают два
К
-разрядных значения. Срав-
нение производится путем поразрядной операции «исключающее ИЛИ» (сложе-
ние по модулю 2) над входными кодами. Результатом является так называемое
слово синдрома.
В зависимости от того, было ли совпадение входных кодов или
нет, соответствующий бит синдрома будет равен 0 или 1.
Слово синдрома состоит из
К
разрядов, то есть его возможные значения лежат
в диапазоне от 0 до
2
К
-
1. Значение 0 соответствует случаю, когда ошибки не об-
наружено, остальные
2
К
-
1 случая свидетельствуют о наличии ошибки и указывают
2 4 0 Глава 5. Память
на ее местоположение. Поскольку ошибка может возникнуть в любом из
М
битов
данных или
К
контрольных битов, мы должны иметь
2
К
-
1 >
М
+
К.
Это выраже-
ние позволяет определить число битов, необходимое для исправления одиночной
ошибки в
М
-разрядных данных.
В табл. 5.2 приведено количество корректирующих разрядов, нужное для конт-
роля данных различной разрядности. Из таблицы видно, что для 8-разрядных слов
требуется четыре корректирующих разряда.
Для удобства будем формировать четырехразрядный синдром со следующими
характеристиками:
• Если синдром содержит все нули, значит, не обнаружено ни одной ошибки.
• Если синдром содержит единственную единицу в одном из разрядов, это озна-
чает, что выявлена ошибка в одном из четырех корректирующих разрядов и ни-
какой коррекции не требуется.
• Если в синдроме в единичное состояние установлены несколько битов, то чис-
ленное значение синдрома соответствует позиции ошибки в данных, для исправ-
ления которой необходимо инвертировать бит в этой позиции.
Таблица 5.2.
Количество корректирующих разрядов, используемое в коде Хэмминга
Разрядность
8
16
32
64
128
256
Исправление одиночной ошибки
Контрольные
биты
4
5
6
7
8
9
% увеличения
длины кода
50
31,25
18,75
10,94
6,25
3,52
Исправление одиночной ошибки
Обнаружение двойной ошибки
Контрольные
биты
5
6
7
8
9
10
% увеличения
длины кода
62,5
37,5
21,875
12,5
7,03
3,91
Под контрольные разряды отводятся те биты, чьи позиционные номера пред-
ставляютсобой степень числа 2 (табл. 5.3). Отдельный контрольный разряд от-
вечает за определенные биты данных. Так, разрядная позиция
п
контролируется
теми битами Р
i
, которые делают справедливым соотношение =
п
. Например, раз-
ряд данных с позиционным номером 7
10
(0111
2
) контролируется битами 4, 2 и 1
(7 - 4 + 2 + 1), а разряд с номером 10
10
(1010
2
) - битами 8 и 2 (10 - 8 + 2).
Таблица 5.3. f
Десятичный
номер
позиции
Двоичный
код номера
позиции
Распределение разрядов
и контрольным кодом
12
1100
11
1011
10
1010
9
1001
12-разрядного слова между данными
8
1000
7
0111
6
0110
5
0101
4
0100
3
0011
2
0010
1
0001