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

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

Иллюстрации

Показать все

Реферат

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

А1

„„SU„„525746

pg 4 G 11 С 29/00

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

М ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ГОСУДАРСТ8ЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОЖРЦТИЯМ

ПРИ ГКНТ СССР

1 (21 ) 4371434/24-24 (22) 04.01.88 (46) 30. 11.89. Бюл. № 44 (72) А.А.Воловник и А.Б.Савинова (53) 681.327.6(088.8) (56) Авторское свидетельство СССР № 765883, кл. G ll С 29/00, 1978.

Авторское свидетельство СССР

¹- 1070605, кл. G 11 С 29/00, 1984. (54) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ

И ИСПРАВЛЕНИЯ ОШИБОК В БЛОКАХ ПАМЯТИ (5?) Изобретение относится к вычислительной технике и может быть использовано в качестве устройства для обнаружения и исправления ошибок в цифровых блоках памяти. Целью изобретения является упрощение уст- ройства и повышение достоверности выдаваемой информации. Устройство содержит генератор кода ошибок, состоящий из первого и второго блоков сумматоров по модулю два, выходы коИзобретение относится к вычисли" тельной технике и может быть использовано в качестве устройства для исправления ошибок в цифровой памяти.

Цель изобретения — упрощения устройства и повышение достоверности выдаваемой информации.

На фиг. 1 представлена структурная схема устройства для обнаружения и исправления ошибок в блоках памяти, на фиг. 2 а,б,в — геометрическая интерпретация кодовой матрицы трех модифицированных итеративных кодов (16,8),(36,24) и (64,48) с параметрами, соответственно равными: а) n =

= N = 4; б) и = N =6; в) и = N = 8 а на фиг. 3 а,б в — схема коррекции одного (шестого) разряда информации

S6(i,J ) для каждого из трех модифицированных итеративных кодов, где (номер строки) и 1 (номер столбца) — координаты символа 86 в соответствующей кодовой матрице (фиг. 2 а, б, в).

Устройство (фиг. 1) содержит генератор 1 кода ошибок, состоящий

25746

10 !

100 0

000 1

000 1

011 1

5 -15 ружения ошибок, проверяется (на нечеткость).входное (К+1)-разрядное сообщение, поступившее с.информационного входа 8. Остальные блоки уст5 ройства в этом режиме работы не используются. На инверсных выходах сумматоров 2;- 2я и 3, — 3 „ согласно кодовой матрице модифицированного итеративного кода (фиг. 2) формируются соответственно контрольные разряды по нечетности а, — а строк и д, - д „ столбцов, которые затем по контрольным выходам 10 — 10 и

11, — 11 „ устройства поступают для анализа на входы блока 7 обнаружения ошибок, а также (вместе с (К+1) информационными разрядами входа 8 устройства) на входы блоков памяти в соответствии с кодовой матрицей (фиг. 2). Учитывая, что контрольный разряд С(а, д-„) одновременно формируется на йнверсных выходах двух сумматоров 2 я н 3„, и его значение при безошибочном кодировании всегда равно "1", так как на все входы сумматоров 2 р и 3 „ н режиме "Запись" поступают "Логические нули", н и-й разряд N-го блока памяти можно записать значение контрольного .разряда

С (" Логическая единица"), формируемое на. контрольном выходе 10 усти ройства, а выход 11„можно для за-: писи н память не использовать.

Работа блока 7 обнаружения ошибок в режиме записи в память запрограммирована следующим образом: при отсутствии неисправностей в генераторе 1 кода ошибок и при отсутствии ошибок но входном (К+1)-разрядном сообшении, поступающим с информационного входа 8 вместе с контрольным разрядом по нечетности С, контрольные разряды по нечетности а, — а <р, и в, — в „,1 модифицированного ите- ративного кода, сформированные на контрольных выходах 10 и 11, должны содержать четное количество "единиц". В этом случае на всех выходах блока 7 обнаружения ошибок сохраняются "Логические нули", что со" ответствует отсутствию .ошибок в принятом для записи (К+1)-разрядном сообшении.

Если же входное сообщение поступает с ошибкой (содержит четное количество "единиц ), то сформированные контрольные разряды а,а и и в, — н „, будут соответственно содержать нечетное количество "единиц". В данной случае на выходе 12 блока 7 обнаружения оши" бок формируется сигнал "НпЗП" (Некорректируемая ошибка записи ) по формуле.

"НпЗп" = a,+ а +.... + a«,1ч

va,+ в + ...+ a<„, Va vb„; где под значениями ая и д„ понимается появление "нулевого" (эапрешенного) сигнала на выходе сумматора

2 или на выходе сумматора 3„ при неисправности одного из них.

Работу устройства в режиме записи н память удобно рассмотреть для одного конкретного случая его применения, например при реализации в нем (16,8) модифицированного итеративного кода с параметрами n =

= Н = 4, кодовая матрица которого представлена на фиг. 2а.

В данном случае на входы 8, — 8 устройства поступает .цля записи в память очередное девятиразрядное информационное сообщение, например

100000000, информационные разряды

81 — $8 и один контрольный разряд

С по нечетности, воспринимаемый устройством как информационный разряд S, в результате чего правильно сформированное для записи в память

16-разрядное кодовое слово содержит четное количество единиц и будет иметь следующий нид:

Значения информационных разрядов

S — SK и сформированных разрядов о а,— ая и н „- н „модифицированного итеративного кода располагаются (для наглядности) на соответствующих им позициях в кодовой матрице (фиг. 2), 1 контрольные разряды строк и столбцов отделены. На входы блока обнаружения ошибок поступает комбинация

0111 0111, свидетельствующая об отсутствии ошибок, н результате на выходе 12 сохраняется "Логический нуль е

При поступлении на информационные входы 8 устройства ошибочного инфор- мационного сообшения S, — S >, например 110 000 000, содержащее четное

1525746 количество "единиц" сформированное для записи в память 16-разрядное ко-. довое слово будет содержать нечетное количество "единиц" и имеет (в геометрической итерпретации) следующий вид:

110 1

000 1

000 1

001 1

На входы блока 7 обнаружения ошибок поступает "запрещенная комбинация 1)1) 0011, свидетельствующая об ошибке во входном сообщении. В результате на выходе 12 . ! блока 7 обнаружения ошибок сформируется сигнал "НпЗп" "Логическая единицап.

Если ошибки во входной информа1 ции произошли в результате сбоев, а не отказов в цепях приема информации, то при повторении режима "Запись" на контрольном выходе 12 должен появиться "Логический нуль (сигнал пНпЗп снимается) и работа, устройства может быть продолжена: в конце цикла "Запись" сформирован ное 16-разрядное кодовое слово записывается в четыре четырехразрядных блока памяти, причем в кажцый блок памяти будет записана одна строка кодовой матрицы (фиг. 2а). На этом цикл "Запись" заканчивается.

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

При декодировании в режиме "Чтение используются все блоки устройства. При отсутствии ошибок считанная из блоков памяти информация проходит с информационного входа 8 устройства на информационный выход 9 без изменения, так как на выходах генератора 1 кода ошибок формируется "нулевой" синдром, поэтому вторые и третьи значения каждого сигнала, сформированные в блоках 4 и 5 коррскции ошибок, совпадают на входе каждого мажоритарного элемента блока 6 с первыми считанными из

10 памяти значениями информационного входа 8; На выходах 12 - 1? < блока

7 обнаружения ошибок сохраняются

"Логические нули".

Если возникшие ошибки ограничены разрядами только одного блока памяти, что является для.устройства корректируемой ошибкой, то код ошибок, полученный на выходах генератора 1 кода ошибок, имеет следующий вид: на первой группе контрольных выхо" дов 10„ - 10 появляется только

° один "единичный" разряд синдрома (где i — номер неисправного или

1 полностью отказавшего блока памяти), а на второй группе контрольных выходов 1 1 - 1 1, — один или несколько "единичных" разрядов сии20 дрома p, — 3 » соответствующих позициям искаженных разрядов этого блока памяти.

На выходах всех и сумматоров по модулю два первого блока 4; коррек" ции ошибок формируются инверсные вторые значения информационного входа 8„, поступающие на входы второй группы мажоритарных элементов блока 6,, на входы первой группы кото30 рых поступают с информационного входа 8; сигналы неисправного блока памяти. В результате на входах первой и второй групп мажоритарных элементов блока б, появляются два инверсных по отношению один к другому сиг35 нала: 01 и 10, поэтому значение на выходах 9 этих мажоритарных элемен1 тов будет определяться значениями сигналов (О или 1), поступающих на

40 их входы третьей группы с выходов

t второго блока S, коррекции ошибок.

При этом на выходе одного или нес» кольких (g-х) сумматоров по модулю два, соответствующих позициям иска45 женных символов (i-го) неисправного блока памяти, формируются инверсные (по отношению к искаженным сигналам информационного входа 8, устройства) третьи значения, поступающие на третьи входы одного или нескольких ()-х) мажоритарных элементов блока б.. В результате этого на информа1 ционных выходах 9; устройства формируются исправленные" значения вход55 ного сообщения. Таким образом, в устройстве реализуется мажоритарный метод исправления. групповых ошибок одного накопителя, заключающийся в том, что сигнал на выходе каждого

1525746

9 мажоритарного элемента совпадает со значением,, которое доминирует на его входах.

Каждый мажоритарный элемент блока

6 реализует логическую функцию

10 соответствунлцей строки кодовой матрицы; — номер позиции искаженного разряда и одновременно номер соответствуюшего столбца кодовой матрицы (фиг. 2).

8 (ык! где Sl S2 и S3 - соответственно значения сигналов на трех входах мажоритарного элемента, а S <

Ь1!к! значение íà его выходе, причем

Например, исправление ошибок в схеме коррекции одного разряда информации (S6), представленной на фиг. 3 (а,б,в), в случае реализации трех различных модифицированных кодов, кодовые матрицы которых пред-!

5 ставлены на фир. 2 (а,б,в), будет происходить по формулам (а,б,в соответственно): !

S2 * Sl + а(;

$3.- Sl + ;, где i — номер неисправного блока памяти и-одновременно номер а) 86< в„.86 ($6 +с()Y86 ($6 + р, )v

Ч($6 +И, )- (86 +, );

$6 . ($6 + о()Ч86 ($6 + p )v

Ч(86 + a ) ($6 +p );

86 ° ($6 + o(, )ч$6 ($6 + р,)ч

V(86 + о(, ) ($6 + р,) ) 861ьцк! в) 86 (ьы1,! (выходе 12 блока 7 обнаружения ошибок формируется единичный сигнал

"КО" (корректируемой ошибки) по формуле

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

0

О

00001

12 блока 7 обнаружения ошибок, свидетельствующий о неисправности в самом генераторе 1 кода ошибок, формируется по формуле "НпЧт" = (Ы1 +

+ P„). Эта формула означает, что при

1 исправном генераторе 1 кода ошибок синдром должен содержать четное количество "единиц", если генератор 1

00000 1

Прн.полном отказе первого блока памяти, в котором хранится первая

КΠ— (P, + P, +в ° е+ A„) L 1 (. " Cot (а(е ° ° „) i ° ° ° !< g((i 6 (ц 1! !

Эта формула означает, что сигнал кода ошибок неисправен, то синдром

"КО" формируется при появлении толь- 40 будет содержать нечетное количество ко одного "единичного" разряда синд- единиц". Рассмотрим работу устройрома e(, -Ы„ на первой группе 10 кон- ства в режиме "Чтение" в случае полтрольных выходов устройства, и при ного отказа одного из блоков памяти, появлении только нечетного количест- например при реализации в устройстве ва единичных разрядов синдрома 45 модифицированного итеративного кода

p - р„ на второй группе контрольных (36,24) с параметрами n = N = 6, ковыходов 11 устройства, что соответ- довая матрица которого представлена ствует групповой ошибке только одного на фиг. 2á. Кодовое слово при отсутиз блоков памяти. ствии ошибок имеет, например, слеЕдиничный сигнал "НпЧт" на выходе 50 дующий вид .

1525746

11111

00001

О

О

1ОООООО

II00000

1111110

О

О

О

00000 1

25

1010101 1

100000 Olllll

1111111

0000000

1010101

10000010 0000001 строка. кодовой матрицы (фиг. 2б), на его выходах возникает пакет однонаправленных ошибок, например, типа

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

В этом случае при считывании информации из памяти на информационные входы 81 в 8 устройства поступает кодовое слово, которое будет иметь следующий вид:

Генератор 1 кода ошибок сформирует на выходах 10„-10 и 11,- 11< код синдрома, соответствующий групповой ошибке нечетного веса, который будет иметь следующий вид:

Анализируя данную комбинацию синдрома, блок 7 обнаружения ошибок сформирует на выходе 12 "единичный сигнал "KO", так как в разрядах син.дрома. „- Ы содержится только одна "единица" (eC„), а в разрядах син дрома 8„ - р содержится нечетное ко6 ц

И личество (пять) "единиц . На остальных выходах блока 7 обнаружения оши- бок сохраняются логические "нули".

Одновременно согласно описанному выше алгоритму мажоритарного декодирования групповых ошибок (фиг. Зб) в мажоритарных элементах блока 6„ происходит исправление пяти (иэ шести символов первой строки кодовой матрицы (фиг. 26): Я1 S2, ЯЗ, Я4, 8,I, а разряд С проходит на выход

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

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

Блок обнаружения ошибок 7 в этом случае формирует "единичный" сигнал

"НКО" некорректируембй ошибки, и работа устройства должна быть прервана для замены двух или нескольких неисправных блоков памяти, ибо при возникновении некорректируемых ошибок (т.е. не ограниченных разрядами одного блока памяти) на информационный выход 9 устройства поступит неправильно скорректированное кодовое слово, Рассмотрим работу устройства в случае возникновения некорректируемых ошибок (или отказов) нескольких блоков памяти, например, при реализации в устройстве модифицированного итеративного кода (б4,48) с параметрами. и = Н = 8, кодовая матрица которого представлена на фиг. 2в.

Кодовое слово (б4,48) модицифи" рованного кода при отсутствии ошибок будет иметь, например, следующий вид:

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

В этом с :учае при считывании ин35 формации из памяти на информационные входы 8 — 8 Э устройства поступает кодовое слово, которое будет иметь следующий вид:

Генератор 1 кода ошибок сформирует на выходах 10 — 10 и II<- 11 код синдрома, соответствующий двум групповым ошибкам нечетного веса, который будет иметь следующий вид:

Анализируя данную комбинацию синдрома, блок 7 обнаружения ошибок сфор" мирует на выходе 12 единичный сиг1 нал "НКО" некорректируемой ошибки, так как в разрядах синдрома

1525746

14 а(содержатся две "единицы" (и

f соответствующие отказам двух блоков памяти, а в разрядах синдрома р - p — четное (запрещенное для корректируемой групповой ошибки)

5 число "единиц" (р, и p ). На выходах 12, 12> и 12 „ сохраняются «Логические нули". По состоянью первой группы контрольных выходов 10 - 10,, можно определить отказавшие блоки памяти (в данном примере — первый и седьмой), которые необходимо saменить.

Аналогично при возникновении многобитовых ошибок любой (2 - N) кратности или при полных отказах любого (2 - N) количества блоков памяти на г

«НКО» = "КО«. (d1 V ckr Ч... Vo(g V

r Эта формула означает, что сигнал

«НКО« формируется на выходе 12, при поступлении на входы блока 7 обнаружения ошибок "ненулевого" кода синдрома, который при этом не совпадает ни с одной из "разрешенных" комбинаций, соответствующих корректируемой ошибке "KO". Отсюда видно, что сама информация об ошибке на выходах 12, 30 (НКО) и 12 (КО) формируется в парафазном коде (01) или (10) °

В режиме "Чтение" в устройстве обеспечивается контроль всех цепей коррекции самого устройства. При этом неисправности самого устройства исправляются или обнаруживаются наравне с ошибками в считываемой информации. Так неисправности в блоках 4 и 5 коррекции ошибок исправ- 40 ляются на мажоритарных элементах блока 6, неисправности в генераторе

I кода ошибок обнаружатся на входе блока 7 обнаружения ошибок, который при этом сформирует сигнал «НпЧт« 45 на выходе 12>, и, кроме того, эти неисправности в генераторе 1 кода ошибок также могут быть исправлены на мажоритарных элементах блока 6.

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

При этом он имеет свою «собственную« схему коррекции, аналогичную фиг. 3, выходе 12 „сформируется "единичный" сигнал «НКО« некорректируемой для устройства ошибки, ибо в разрядах синдрома Ы, - J на первой группе контрольных выходов 10, — 10 „ будет содержаться (2 — N) "единиц", При возникновении некорректируемой ошибки четного веса в одном или нескольких блоках памяти на выходе

12, также сформируется сигнал »НКО", ибо в разрядах синдрома р, — р„ на второй группе контрольных выходов

ll, — 11 „ будет содержаться четное (2 — n) количество "единиц".

Таким образом, сигнал «НКО" на выходе 12, устройства формируется по формуле

, "P Р ) и независимо от параметров и и N (т.е. при реализации кода любой разрядности) исправление разряда С о считанного из первого блока памяти, всегда производится на первом мажо- . ритарном элементе блока 6 по формуле

c,„„„, = c. (c, +.с, )vc, (с, + p, ) м(с, +, ) (с, + р,). В устройстве реализован модифицированный двумерный итеративный код с контролем по нечеткости строк и столбцов, с простой геометрической структурой построения кодовой матрицы и высокими обнаруживающими свойствами, позволяющий применить в устройстве синдромно-мажоритарный алгоритм декодирования, эа счет этого полностью распараллелить декодирующую схему.и применить простые корректоры групповых ошибок: обнаруживать любые (2 — N) пакеты и-разрядных ошибок при отказах нескольких блоков памяти (где п — четное число), а также некорректируемые многобитные ошибки кратности (2 — N) в разных блоках памяти. Контролем охва" тываются все узлы самого устройства, за счет чего неисправности самого устройства исправляются (на мажоритарных элементах) или обнаруживаются (обнаружителем некорректируемых ошибок) наравне с ошибками, вызванными неисправностями в блоках ламяти.

1525746, 16

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

Сумматоры 2, †. 2 < и 3, — 3 „ по модулю два генератора 1 кода ошибок могут быть выполнены на интеграль-. ных микросхемах (ИИС) типа 133 ИП5, блок 6 мажоритарных элементов — на микросхемах типа 533 ЛПЗ., блок 7 обнаружения ошибок — на программируемой логике матричных БИС типа 556

РТ1 (РТ2).

О

Формула изобретения

Устройство для обнаружения и исправления ошибок в блоках памяти, содержащее генератор кода ошибок, первый блок коррекции ошибок, входы первой группы которого подключены к входам генератора кода ошибок и яв" ляются информационными входами устройства, N ab opoa генератора кода ошибок являются первой группой контрольных выходов устройства (где N —количество блоков памяти), о т л и— ч а ю щ е е с я тем, что, с целью

f упрощения устройства и повышения достоверности выдаваемой информации, в устройство введены второй блок коррекции ошибок, блок мажоритарных элементов и блок обнаружения ошибок, входы второй группы первого блока коррекции ошибок подключены к N выходам генератора кода ошибок и к входам первой группы блока обнаружения ошибок, и выходов генератора кода ошибок (где

n — - разрядность блоков памяти) подключены к входам второй группы второго блока коррекции ошибок и к входам второй группы блока обнаружения ошибок и являются второй группой контрольных выходов устройства, первый, третий и четвертый выходы бло2(I ка обнаружения ошибок являются выходами некорректируемых ошибок устрой-. ства, второй выход — выходом корректируемой ошибки устройства, входы первой группы второго блока коррекции ошибок подключены к входам первой группы первого блока коррекции ошибок и к входам первой группы блока мажоритарных элементов, выходы которого являются информационными выходами устройства, входы второй и третьей групп блока мажоритарных элементов подключены к выходам первого и второго блоков коррекции ошибок соответственно.

)525746

1525746 б/