Устройство для обнаружения и исправления ошибок в блоках памяти Советский патент 1989 года по МПК G11C29/00 

из N n-входовых сумматоров 2|- 2,. по модулю два и п И-входовых сумматоров 3j- 3. по модулю два, первый и второй 5 блоки коррекхщи ошибок, каждый из которых состоит из (n-N) двухвходовьк сумматоров по модулю . два, блок 6 мажоритарных элементов, состоящий из (n, N) TpiexBxoAOBbK мажоритарных элементов, реализующих функцию ( 2), и блок 7 обнаружения ошибок, информационные входы 8

и выходы 9, а также первую 10--10., .. . и и вторую

1,м.

группы контрольных выходов устройства, 12,, 12., 12 - выходы некорректируемых ошибок устройства, выход 12 корректируемой ошибки устройства.

На фиг. 1 - 3 символами S1-SK обозначены информационные разряды модифицированного итеративного кода (n-N,K) ,где п иИ - соответственно чис до строк и столбцов кодовой матрицы (фиг. 2), К (п - 1) .(N - i) - 1; символом Ср обозначен контрольный разряд по нечетности входного (К+1) разрядного сообщения, поступающего в устройство для кодирования и записи в память; символами а а и в - в 1 - контрольные разряды по нечетности соответственно для N строк и п столбцов кодовой матрицы; а символом С - контрольный разряд общей четности сформированного (п- Г1)-разрядного модифицированного кода и одновременно - контрольньй разряд а для контрольной (N-й) строки и контрольный разряд в для контрольного (п-го) столбца кодовой матрицы (фиг. 2), причем для правильно закодированного кодового слова, значение контрольного разряда С общей четности всегда равно логической символами о(,- о( и , - /Ь„ обозначены разряды синдрома, формируемые в режиме Чтение соответственно на первой 10 д( и второй 1 1, группах контрольных выходов устройства.

На фиг о 2 а,б,в стрелками ( ) и ( 4 ) указаны группы разрядов, входящих в i-ю строку и j-и.столбец кодовой матрицы, участвующие в в коррекции (фиг. 3 а,б,в) симво- ла S6 (i,j), где i,j координаты символа S6, соответствующие занимаемой им позиции в каждой из трех кодовых матриц/ (а, б, в соответственно).

В общем случае для построения схемы коррекции (фзет. 3) каждого символа кодовой матрицы, имеющего, коор- динаты (ijj)} соответствующие занимаемой им позиции (фиг. 2)j необходимо каждый из (niJj) информационных входов 8,- 8 f устройства (фиг. ) связать с J-M входом сумматора 2-,

Q с i-M входом сумматора 3/, с первым входом двух (j-x) сумматоров блоков 4j и 5; коррекции ошибок, а также с первым входом одного (j-ro) мажори- -тарного блока 6,-, Второй и третий

5 входы этого мажоритарного элемента свя зать с выходами j-x сумматоров блоков 4. и 5. коррекции ошибок, а вторые входы этих сумматоров - с выходом сумматора 2 и с вькодом сум0 матора 3; генератора 1 кода ошибок.

Устройство (фиг. 1) для обнаруясе- ния и исправления п-разрядных ошибок в К блоках памяти (где п и N - четные числа) реализует модифицирован5 ный двумерный итеративный к.од с контролем по 1ечетности строк и столбцов и с параметрами, соответственно равными: число контрольных разрядов m п + N, число информационных разрядов К n-N - (п + N) кодовая матрица которого (для случая п N) представлена на фиг. 2.

Правило Ьормирования модифицированного итеративного кода наглядло иллюстрируется на примере построения трех конкретных кодов: на фиг, 2а представлена кодовая матрица (16,8) кода - для одного байта информации (п N - 4); на фиг. 2б - кодовая матрица (36,24) кода для трех байтов информации (n W 6); на фиг. 2в- кодовая матрица (64,48) кода для шести байтов информации (п Ы В). При отсутствии ошибок во входной информации и входное (К+1)-разрядное сообщение, и выходное (К+1)-разрядное сообщение, и сформированное для записи в память (п К)-разрядное сообщение, а также каждая п-разрядная строка и каждый N-разрядный столбец кодовой матрицы (фиг. 2)должны содержать нечетное количество единиц. При этом значение контрольного разряда С(а|, Ъ) всегда должно быть равно единице,

Кодирование информации в режиме записи ее в блоки памяти осуществляется посредством генератора 1 кода ошибок и одновременно блоком 7 обна0

5

0

5

0

5-

ружения ошибок, проверяется (на нечетность) входное (К+1)-разрядное сообщение, поступившее с информационного входа 8, Остальные блоки устройства в этом режиме работы не используются. На инверсных выходах сумматоров 2,- 2 н 3,- 3„ согласно кодовой матрице модифицированного итеративного кода (фиг. 2) формируются соответственно контрольные разряды по нечетности а строк и Ъ столбцов, которые затем по контрольным выходам 10, - 10, и i устройства поступают для анализа на входы блока 7 обнаружени ошибок, а также (вместе с (К+1) информационными разрядами входа 8 устройства) на входы блоков памяти в соответствии с кодо вой матрицей (фиг. 2). Учитывая, что контрольный разряд С(а, bj,) одновременно формируется на инверсных выходах двух сумматоров 2 1 и 3, и его значение при безошибочном кодировании всегда равно 1, так как на все входы сумматоров 2 N и 3 п в режиме Запись .поступают Логические нули, в п-й разряд N-ro блока памяти можно записать значение контрольного разряда С (Логическая единица), формируемое на. контрольном выходе 10| устройства, а выход Можно для записи в память не использовать.

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

Если же входное сообщение поступает с ошибкой (содержит четное количество единиц), то сформированные контрольные разряды а ,- а(н-11 и н , - в (п-и будут соответ-

5257466

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

10

НпЗп а + ,.,, а(.,,у VB,+ Bj-b ...+ в („-,1 Ь„;

где под значениями а и Ъ„ понимается появление нулевого (запрещенного) сигнала на выходе сумматора

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

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

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

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

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

100 000 000

оТТ

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

i (4 1 в fj модифицированного итеративного кода располагаются (для наглядности) на соответствующих им позициях в кодовой матрице (фиг. 2), ;контрольные разряды строк и столбцов

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

нуль .

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

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

iioj 1

.000 1

000 1

. ooF T

На входы блока 7 обнаружения ошибок поступает запрещенная комбинащ я J313 001 i, свидетельст- вующая об ошибке во входном сообще- НИИ. В результате на выходе 12,. блока 7 обнаружения ошибок сформируется сигнал НпЗп Логическая единица.

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

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

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

0

5

0

5

5 0 5

0

памяти значениями информационного входа 8. На выходах 12 блока 7 обнаружения ошибок сохраняются Логические нули.

Если возникшие ошибки ограничены разрядами только одного блока памяти, что является для устройства корректируемой ошибкой, то код ошибок, полученный на выходах генератора 1 кода ошибок, имеет следующий ввд: на первой группе контрольных выходов 10 10д) появляется только один единичный раэряд стщрома с/, (где i - номер неисправного или полностью отказавшего блока памя- ; ти), а на второй группе контроль ных выходов П J- П - один или несколько единичных разрядов синдрома 3, - f, соответствующих позициям искаженных разрядов зтого блока памяти.

На выходах всех п сумматоров rto модулю два первого блока 4; коррекции ошибок формируются инверсные вторые значения информационного входа 8,- , поступающие на входы второй группы мажоритарных злементов блока 6.J на входы первой группы которых поступают с информационного входа 8 j сигналы неисправного блока памяти. В результате на входах первой и второй групп мажоритарных элементов блока 6 ; появляются два инверс- ньк по отношению один к другому сигнала: 01 и 10, поэтому значение на выходах 9; этих мажоритарных элемен- Iтов будет определяться значениями сигналов (о или 1), поступающих на их входы третьей группы с выходов второго блока 5j коррекции ошибок. При этом на выходе одного или кольких (j-x) сумматоров по модулю два, соответствующих позициям искаженных символов (i-ro) неисправного блока памяти, формируются инверсные (по отношению к искаженным сигналам информационного входа 8j устройства) третьи значения, поступающие на третьи входы одного или нескольких (j-x) мажоритарных элементов блока 6j . В результате этого на информационных выходах 9; устройства формируются исправленные значения входного сообщения. Таким образом, в устройстве реализуется мажоритарный метод исправления групповых ошибок одного накопителя, заключающийся в том, что сигнал на выходе каждого

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

Каждый мажоритарный элемент блок 6 реализует логическую функцию

(niif/ SI S2VS1.S3VS2-S3,

где SI, S2 и S3 - соответственно значения сигналов на трёх входах мажоритарного элемента, а В (a,.i значение на его выходе, причем

S2 S3.

SI +С/5 SI +р.

где

i - номер неисправного блока

памяти к-одновременно номер

соответствующей строки кодовой матрицы; j - номер позиции искаженного

разряда и одновременно номер соответствующего столбца кодовой матрицы (фиг. 2).

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

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

ьт, R) 8б(„,„

«) (ьщ

.S6 . (S6 )У86 (S6 +/ь, )v V(S6 )-(S6 + /3, );

S6 - (S6 + )VS6 (S6 + /3.1 )V V(S6 + c{,).(S6 +A,,-);

S6 . (S6 +c/, )VS6 ; (S6 + p,Jv V(S6 +0, ) -{86 + PJ)

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

КО (р, ... ). о,(...Ус)у VO(( O/,V...VO(N)V...VO{(C, V(jV...v«i );

Эта формула означает, что сигнал ко формируется при появлении толь- ко одного единичного разряда синдрома о(, -о( на первой группе 10 контрольных выходов устройства, и при появлении только нечетного количества единичных разрядов синдрома /3, - р на второй группе контрольных выходов 11 устройства, что соответствует групповой ошибке только одног из блоков памяти.

Единичный сигнал НпЧт на выходе 12, блока 7 обнаружения ошибок, свидетельствующий о неисправности в самом генераторе 1 кода ошибок, формируется по формуле НпЧт ( о(, + + / + «/N) ( PI Pa

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

единиц, если генератор 1

выходе 12 блока 7 обнаружения ошибок формируется единичный сигнал ко (корректируемой ошибки) по формуле

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

единиц. Рассмотрим работу устройства в режиме Чтение в случае полного отказа одного из блоков памяти, например при реализации в устройстве модифицированного итеративного кода (36,24) с параметрами п N 6, кодовая матрица которого представлена на фиг. 2б. Кодовое слово при отсутствии ошибок имеет, например, следующий вид:

10000 01000 00100 00010 00001

обооо

о о о о о l

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

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

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

11111 01000 00100 00010 00001

ооооо

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

100000 011111

Анализируя данную комбинацию синдрома, блок 7 обнарз ения О1шибок сформирует на выходе 12 единичный сигнал ко, так как в разрядах син- 0,- d содержится только од(o(i), а в разрядах син дрома р - {Ь содержится нечетное количество (пять) единиц. На остальных выходах блока 7 обн.арзгжения ошибок сохраняются логические нули.

Одновременно согласно описанному выше алгоритму мажоритарного декодирования групповых ошибок (фиг. Зб) в мажоритарных элементах блока 6 происходит исправление пяти (из шести символов первой строки кодовой матрицы (фиг, 2б): S1, S2, S3, S4,

тлп

дрома. d на единица

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

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

Блок обнаружения ощибок 7 в этом случае формирует единичный сигнал НКО некорректируемой ошибки, и ра .бота устройства должна быть прерва- на для замены двух или нескольких неисправных блоков памяти, ибо при возникновении некорректируемых оши

бок (т.е. не ограниченных разрядами одного блока памяти) на информационный выход 9 устройства поступит неправильно скорректированное кодовое слово.

Рассмотрим работу устройства в ; случае возникновения некорректируемых ошибок (или отказов) нескольких блоков памяти, например, при реализации в устройстве модифицированного итеративного кода (64,А8) с параметрами: п N В, кодовая матрица которого представлена на фиг. 2в.

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

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

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

Генератор 1 кода ошибок сформи0

5

рует на выходах

10,lOg и

пг

11,

код синдрома, соответствующий двум групповым ошибкам нечетного веса, которьй будет иметь следующий вид:

10000010 0000001

Анализируя данную комбинацию синдрома, блок 7 обнаружения ошибок сформирует на выходе 12 единичный сигнал НКО некорректируемой ошибки, так как в разрядах синдрома «Х, с( в содержатся две единицы ( г/, и о(т), соответствующие отказам двух блоков памяти, а в разрядах синдрома /5| - fb - четное (запрещенное для корректируемой групповой ошибки) число единиц ( f, и . На вьсхо- дах 12, и 12 сохраняются Логические нули. По состоянию первой группы контрольных выходов lOf- 10, можно определить отказавшие блоки памяти (в данном примере - первый и седьмой), которые необходимо заменить.

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

НКО КО. Ы V o;-,jV... Vc/ V р, ...V р J .

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

В режиме Чтение в устройстве обеспечивается контроль всех цепей коррекции самого устройства. При

i зтом неисправности самого устройства исправляются или обнаруживаются наравне с ошибками в считьюаемой информации. Так неисправности в блоках 4 и 5 коррекции ошибок исправ- ляются на мажоритарных элементах блока 6, неисправности в генераторе 1 кода ошибок обнаружатся на входе блока 7 обнаружения ошибок, который при зтом сформирует сигнал НпЧт на выходе 12з, и, кроме того, эти неисправности в генераторе 1 кода ошибок также могут быть исправлены на мажоритарных элементах блока 6.

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

(и корректировать при необходимости) разряд GO по нечетности независимо от других информационных разрядов. При-этом он имеет свою собственную схему коррекции, аналогичную фиг. 3

выходе 12, сформируетср единичный сигнал НКО некорректируемой для устройства ошибки, ибо в разр5здах синдрома о, - с/м первой группе контрольных выходов 10, - 10 и будет содержаться (2 - N) единиц.

При возникновении некорректируемой ошибки четного веса в одном или нескольких блоках памяти на выходе 12 также сформируется сигнал НКО ибо в разрядах синдрома л на второй группе контрольных выходов 11,- П будет содержаться четное (2 - п) количество единиц.

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

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

О (Sbiv)

Со.(С, +о(, )vCe (Co + /S, )V

V(C, +о(, ) -(С, + р, ).

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

15

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

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

L

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

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

1525746

16

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

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

jii tt fiS

at

fl

JS

a)

Фа9.г

-