Запоминающее устройство с коррекцией групповых ошибок

 

Изобретение относится к вычислительной технике ,в частности, к запоминающим устройствам /ЗУ/, и может быть использовано для построения высоконадежных блоков памяти с восможностью ремонта двух накопителей в процессе решения задачи. Цель изобретения - повышение надежности устройства и достоверности считываемой информации. Устройство содержит блоки памяти, количество которых должно быть нечетным /К+3/, где К≥4, блок коррекции, блок задержки, коммутатор, элементы И, элементы НЕРАВНОЗНАЧНОСТЬ, блоки свертки по модулю два, регистр 133, блоки сравнения, мажориторные элементы, пороговый элемент. 5 ил.

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

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

РЕСПУБЛИК

А1 (19) (11) (51)4G ll С 29 00

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

К А BTOPCHOMV СВИДЕТЕЛЬСТВУ () . Г. ч » 11, ц» 1 ь 11

»»А t Erl »»t » t .ь, .! "..- ° » и "

Е..ЬЛ 1О

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4197273/24-24 (22) 16,02,87 (46) 23.05.89, Бюл. № 19 (72) В,В.Абрамов, А.А.Воловник и А.Б.Савинова (53) 681.327(088,8) (56) Авторское свидетельство СССР

¹ 955207, кл. G 11 С 29/00, 1980.

Авторское свидетельство СССР № 1092570, кл. G ll С 29/00, 1983. (54) ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО С КОРРЕКЦИЕЙ ГРУППОВЫХ ОШИБОК (57) Изобретение относится к вычислительной технике, в частности к заИзобретение относится к вычислительной технике, в частности к запоминающим устройствам (ЗУ), и может быть использовано для построения высоконадежных блоков памяти с возможностью ремонта накопителя в процессе решения задачи.

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

На фиг. 1 представлена функциональная схема ЗУ; на фиг. 2 и 3— функциональная схема блока коррекции; на фиг. 4 и 5 — геометрическая интерпретация кодовой матрицы соответственно двух модифицированных трехмерных кодов, 28,16 (К=4) и 54,36 (К=6) с контролем по четности для всех К -разрядных комбинаций и с . контролем по нечеткости для всех непоминающим устройствам (ЗУ), и может быть использовано для построения вы- соконадежных блоков памяти с возможностью ремонта двух накопителей в процессе решения задачи. Цель изобретения — повышение надежности устройства и достоверности считываемой информации. Устройство содержит блоки памяти, количество которых должно быть нечетным (К+3), где Кз 4, блок коррекции, блок задержки, коммутатор,. элементы И, элементы НЕРАВНОЗНАЧНОСТЬ, блоки свертки по модулю два, регистр, блоки сравнения, мажоритарные элементы, пороговый элемент. 5 ил. четных комбинаций информационного сообщения.

Устройство содержит блоки 1-7 памяти, количество которых должно быть нечетным (К+3), блок 8 коррекции, блок 9 задержки,. коммутатор 10, первый элемент И 11, элементы НЕРАВНОЗНАЧНОСТЬ 12-27, первую группу элементов И 28-43, вторую группу элементов И 44-46, причем выходы 47.-62 блоков 1-4 и выходы 63-74 блоков 5-7 соединены соответственно с информационными и контрольными входами.. блока 8 коррекции, вход блока 9 задержки является входом 75 запуска устройства, первый выход 76 блока 9 задержкй соединен с первым информационным входом коммутатора 10, второй выход 77 — с входами синхронизации блоков 1-7, третий выход 78 — с

1481863 вторым информационным входом коммутатора 10, четвертый выход 79 — с входом первого элемента И 11, а пятый выход 80 является выходом окончания цикла обращения устройства, выходы

81-96 блока 8 коррекции соединены с одними из входов элементов НЕРАВНО.ЗНАЧНОСТЬ 12-27.

Устройство имеет информационные входы 97, информационные выходы 98, вход 99 записи, вход 100 считывания.

Выход коммутатора 10 соединен с управляющим входом 101 блока 8, Выходы ,102-104 блока 8 коррекции являются )5 одними из индюрмационных входов устройства, выходы 105-126 — индикатор-. ным выходом !27 устройства. Установочные входы 128-131 являются установочными входами устройства, адресным 20 входом 132 которого являются адресные . входы блоков )-7 памяти.

Блок 8 коррекции содержит регистр

133, первую группу блоков 134-137, вторую группу блоков 138-141 и третью 25 . группу блоков 142-145 свертки по модулю два, Блок 8 коррекции также содержит элементы И 146-197, образующие третью 146-149, четвертую 150-153, пятую 158-161, шестую 162-165, седьмую:

170-185, восьмую 186-189, девятую

190-193, десятую 154-157, одиннадцатую 166-169.и двенадцатую 194-197 группы элементов И, первый 198, вто. рой 199 и третий 200 блоки свертки по модулю два, первую 201, вторую

202 и третью 203 группы блоков сравнения, первую 204-206 и вторую 207- .209 группы мажоритарных элементов, 40 пороговый элемент 210, реализующий функцию Ь 2, тринадцатую 211-2!3 и .четырнадцатую 214-216 группы элементов И, с второго по шестой элементы

И 217-22). Регистр )33 имеет выходы

222«252, блоки 134-141 — выходы 253-

260.

Блоки 198-200 служат для формирования в коде (3,1) контрольного разряда g общей четности: g, g, g для выходного К -разрядного сообщения.

Мажоритарные элементы 204-206.и

207-209 служат для коррекции одиночных ошибок в разрядах р, g, g

4 2. Э которые для устройства являются информационными разрядами входного и выходного сообщения, поступающими соответственно с информационных выходов 239-241 регистра 133 (в режиме записи в память) или с выходов блоков 198-200 по модулю два (н режиме считывания из памяти). Блоки 134-145 служат соответственно для формирования координат А, В, С трехмерного кода (в режиме записи) и формирования трех групп разрядов синдрома

oc)-ga, P l-84, 1- 4 (в режиме считывания) согласно кодовой матрице примененного в устройстве кода (фиг. 4 и 5).

Блоки 201-203 служат для анализа

ЗК-разрядного кода синдрома и формирования координат (ol, $ P 1 и ( ошибочных информационных символов

Sl-S16 (в рассматриваемом примере К равно, например, четырем) в случае неисправности одного из блоков 1-4 памяти и формирования сигналов некорректируемой ошибки при ошибке в разных блоках памяти или полном отказе одного из блоков 1-7, которые через пороговый элемент 210 и элементы И 220 и 221 выдаются на выходы

120-122 устройства как сигналы HKOI

НКО2, НКОЗ (адрес соответствующего вектора прерывания). Схема подключения выходов 222-237 регистра и выходов элементов И 146-!47, 211-216 к входам блоков 134-!45, а также выходов блоков 201-203 к входам элементов И 170-)85 определяется кодо вой матрицей примененного в устройстве трехмерного кода, На фиг. 4 и 5 обозначены: S)-S16, S17-S36 -. информационные разряды трехмерного кода; gl 82, 83 — контрольные разряды общей четности входного и выходного сообщения в коде

Ю

3,1, занимающие s кодовой матрице фиктивные позиции (т,е, в кодовом слове в явном виде не присутствуют и, следовательно, в ячейки блоков памяти не записываются); a)-ak, bl"bk, Cl-Ck — K0HT o Hbie b cbopMHруемого для устройства кода (в режиме записи); K) k, 1 Pk, 1- k - .разряды формируемого в устройстве синдрома (в режиме чтения).

Устройство работает следующим образом.

В устройстве для коррекции одиночных групповых ошибок и обнаружения двух и более битовых ошибок реализован модифицированный код (К +3K, K ) с числом информационных разрядов К, с числом контрольных разря z

Я1863 6

50

5 14 доп ЗК ц беэ контрольного разряда общей четности, с помощьн которого

anэможна коррекция одиночной групповой ошибки в (К-1) раэрядах информации, расположенных на одной иэ диагоналей кодовой матрипы, а также выявление любых двух и более битовых ошибок, расположенных в разных диагоналях кодовой матрицы (а следовательно, в:разных блоках памяти). Геометрическая трехмерная структура данного кода и отсутствие в кодовом слове разряда g общей четности позволяют упростить алгоритм формирования контрольных разрядов, ибо в кодере отсутствует схема свертки по модулю два всех К разрядов входного сообщения, Ф реализовать в.устройстве очень простой алгоритм обнаружения ошибок в разных накопителях, ибо при декодировании данного кода на контрольных выходах в явном виде вырабатывается номер неисправных блоков памяти (третья координата ошибочных информационных символов), и выдавать выходную

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

Модифицированный трехмерный (АВС) код строится на основе двухмерного (АВ) итеративного кода с контрольным разрядом g общей четности, примененного в известном устройстве, путем модификации структуры его кодовой матрицы, в результате чего может быть получен двумерный интеративный код с кодовым расстоянием d=4, но без контрольного разряда g.

В результате данной модификации получается укороченный двумерный код (24, 16) с контролем по четности (g=0) для всех четных комбинаций входного шестнадцатиразрядного сообщения и с контролем по нечетности (g=l) для всех нечетных комбинаций входного шестнадцатиразрядного сообщения, Контрольные разряды С1-С4, соот-ветствующие третьей координате С модифицированного трехмерного кода (28-16), примененного в предлагаемом устройстве, формируются аналогично координатам А и В модифицированного двумерного кода (24, 16), т, е. провер5 кои на четность (g=0) или нечетность (g=1) четырех соответствующих диагоналей кодовой матрицы (фиг. 4).

В общем случае для числа информаг ционных разрядов К алгоритм построения контрольных разрядов модифици2 рованного трехмерного кода (К +ЗК,К) заключается в следующем: каждая координата А (al-ak) В (Ь1-bk)

С (cl-ck) формируемого арпа устройства -кода образуется проверкой на четность (g=0) или нечетность (g=l) соответственно каждой иэ К информационных строк, столбцов и диагоналей кодовой м:.трицы. Контрольные разряды, участвующие в формировании контрольных разрядов трехмерного кода, поступают в режиме записи с входной г магистрали вместе с К информационными разрядами и, следовательно, воспринимаются устройством как три дополнительных информационньх разг ряда входного (К +3)-разрядного сообщения. Затем при занесении кодового слова в блоки памяти контрольные разряды отбрасываются, т,е. в кодовом слове, хранящемся в ячейке блока памяти, не присутствуют ° В режиме чтения параллельно с декодированием

35 кодового слова независимо формируются три разряда общей четности. При этом контрольный разряд общей четности g трехмерного кода формируется в коде (3,1). Затем эти контрольные разряды участвуют в формировании трех групп разрядов синдрома

Ы1 k j31-Pk fl-| k согласно кодовой матрице трехмерного кода и одновременно (после соответствующей коррекции) поступают на выход устройства.

Таким образом на выходную магистраль данных, как и с входной магистрали, также поступает (К +3)-разрядное г сообщение.

Работу устройства рассмотрим, например, для случая реализации трехмерного кода 28,16 (К=4), кодовая матрица которого представлена на фиг, 4.

В режиме "Запись" на вход 132 устройства поступает адрес выбранной ячейки блока памяти, на вход 97очередное 19-разрядное сообщение, содержащее слово данных Sl-S16 и три

1481863

15

25

35

55 (т.е. в коде 3,1) контрольных разряда общей четности g: 8, g, g,, которые для устройства являются соответственно информационными разрядами $17, SI8, S19, на вход 99 — признак записи, а на вход 75 — сигнал

"Запуск", который через коммутатор

10 проходит на вход 101 блока 8, где заносит в регистр 133 информацию, находящуюся на входах 47-62 и 102I04. После этого в блоке 8 начинается исправление на мажоритарных элементах 204-206 разрядов p g2 яэ общей четности входного сообщения и формирование координат А, В, С модифицированного трехмерного кода 28, 16 согласно кодовой матрице (фиг.4).

Контрольные разряды аl-а4 (коор дината А) формируются с помощью блоков 134-137, контрольные разряды

Ь|-Ь (координата В) — с помощью блоков 138-141, а контрольные разряды

cI-c4 (координата С) — с помощью блоков 142-145.

На входе 100 блока 8 присутствует логический нуль (низкий уровень напряжения), а на входе 99 — логическая единица (высокии уровень напряжения). В результате элементы И 146157 и 214-216 остаются закрытыми, и на их выходах находятся логические нули, а элементы И 211-213 открываются, пропуская на входы блоков 134145 исправленные значения трех контрольных разрядов g,,g,,,,g . Одно1 2 Э временно открываются блоки 158-169 и сформированные значения контрольных разрядов (координаты А, В, С трехмерного кода) поступают с их выходов на входы 63-74 блока 8 и на входы блоков

5-7.

С появлением сигнала на выходе 77 блока 9 задержки производится запись кодового слова в блоки 1-7. В каждый из блоков 1-7 записывается по К (в данном примере К=4) соответствующих разрядов кодового слова, причем в бло ки 1-4 записываются информационные символы SI-S16, а в блоки 5-7 — координаты А, В, С этих информационных символов.

По окончании записи на выход 80 устройства выдается соответствующий сигнал.

В режиме "Чтение" на вход 132 устройства поступает адрес выбранной ячейки памяти, на вход 100— признак считывания, а на вход 75— сигнал Запуск". С появлением сигнала на выходе 77 блока 9 . адержки код< вое слово считывается из блоков 1-7 и поступает на входы блока 8, Так как на управляющем входе коммутатора 10 присутствует логическая единица, поступающая с входа 100.устройства, то прохождение сигнала через коммутатор с выхода блока 9 задержки запрещается. Одновременно разрешается прохождение сигнала с выхода

78, поступающего позже сигнала с выхода 77 с задержкой, равной времени выборки информации из блоков 1-7.

Пройдя коммутатор 10, этот сигнал поступает на управляющий вход 101 блока 8 и заносит считанное кодовое слово в регистр 133.

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

А, В, С трехмерного кода в следующей последовательности .

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

Так как в это время на входе 100 блока 8 присутствует логическая единица, то исправление значения разрядов через элементы И, 214-216, а считанные значения контрольных разрядов с выходов 241-252 регистра 133 через элементы И 146-157 поступают на соответствующие входы блоков

134-145, В дальнейшем три группы разрядов синдрома попарно анализируются в блоках 201-203.

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

45 групповых ошибок в одном из контрольных блоков 5-7 на выходах блоков 201203 .сохраняются логические нули (низкий. уровень напряжения). Это оз/ начает, что при обнаружении неисправности одного из блоков 5-7 ошибки в контрольных разрядах блоками 201-203 игнорируются, что равносильно их

"исправлению", так как в данном случае никогда не произойдет "неправильной" коррекции какого-либо информационного символа S I-S16, ибо работа элементов И 170-185, "настроенных" только на координаты c(, P, $ искаженных информационных символов, блокиру1481863

5

25

35

55 ется (на входах каждого из них присутствует логический нуль), Одновременно разрешается работа элементов И 186-197, "настроенных" только на унитарные координаты (К или gP), или Д искаженных контрольных символов al-a4, или Ы-Ь4, или сl-с4 одного из блоков 5-7.

На выходах 81-96 и 120-122 присутствуют логические нули. На выходах

123-126 логические единицы появляются только при неисправности блока 7 (ошибки в разрядах Сl-С4).

Позиции ошибочных контрольных символов (логические единицы на выходах 108-119 устройства) определяются с помощью элементов И 186-197, При обнаружении корректируемой ошибки в одном из блоков 1-4 разрешается работа элементов И 170-185, каждый из которых настроен на трехмерные координаты с, Pj, Iw k одного информационного символа 81-SI6 (i,j, k — номер строки,. столбца и диагонали кодовой матрицы), а работа элементов И 186-197 блокируется, так как на выходе элементов И 217-218 присутствуют логические нули. На выходах 81-96 вырабатываются сигналы коррекции, .инвертирующие на элементах

НЕРАВНОЗНАЧНОСТЬ 12-27 соответствующие информационные символы Sl-$16.

На выходах 108-122 сохраняются логические нули, а на выходы 123-126 выдается унитарный комер неисправного блока 1-4. Позиции ошибочных информационных символов (логические единицы на выходах 81-96 устройства} определяются с помощью элементов

И 170-185, В целом информация на выходах 81119 и 123-126 при возникновении корректируемой групповой ошибки в одном из блоков 1-7 может быть использована в режиме периодической диагностики для индикации отказавших разрядов и своевременного выявления и замены неисправного блока памяти, а также устранения неисправностей самого устройства контроля еще до возникновения в устройстве некорректируемых отказов.

При отсутствии некорректируемых отказов (на выходах 120-122 присутствуют логические нули)цикл "Чтение" заканчивается по сигналу с выхода .79 блока 9 задержки, проходящему че.рез элемент И 11. Информационные раэряды Sl-S16, скорректированные при необходимости на элементах НЕРАВНОЗНАЧНОСТЬ 12-27, и три разряда общей четности g, р, g, скорректированные на мажоритарных элементах 207209, выдаются через элементы И 28-46 на информационные выходы 98 устройства. Затем на выход 80 выдается соответствующий сигнал.

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

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

Запоминающее устройство с коррекцией групповых ошибок, содержащее блоки памяти, блок задержки, коммутатор, первый элемент И, элементы

НЕРАВНОЗНАЧНОСТЬ, первую и вторую группы элементов И и блок коррекции, содержащий регистр, первую и вторую группы блоков свертки по модулю два, с третьей по девятую группы элементов

И, с первого по третий блоки свертки по модулю два, причем входы первой и второй групп информационных разрядов регистра являются информационными входами устройства, выходы элементов

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

4б!ОЬЗ групп, входы признака считывания блоков памяти, управляющий вход коммутатора и первый вход первого элемента

И объединены и являются входом считывания устройства, выход первого элемента И соединен с первыми входами элементов И.первой и второй групп, выходы элементов И седьмой группы соединены с первыми входами элементов 10

НЕРАВНОЗНАЧНОСТЬ, вторые входы которых соединены с выходами блоков памяти, выходы элементов НЕРАВНОЗНАЧНОСТЬ .соединены с вторыми входами элементов И первой группы, первый выход блока задержки соединен с первым информационным входом коммутатора, второй выход блока задержки подключен к входам синхронизации блоков памяти, третий и четвертый выходы блока задержки соединены соответственно с вторым информационным входом коммутатора и вторым входом первого элемента И, пятый. выход блока задержки является выходом "Окончание цик- 25 ла обращения" устройства, выход коммутатора соединен с управляющим входом регистра, о т л и ч а ю щ ее с я тем,. что, с целью повышения надежности устройства и повышения З0 достоверности считываемой информации, в него введены третья группа свертки по модулю два, три группы блоков сравнения, первая и вторая группы мажоритарных элементов, пороговый .элемент, с десятой по четырнадцатую группы элементов И, с второго по шестой, элементы И, причем входы первой группы блоков свертки по модулю два третьей группы подключены 40 к выходам первой группы информационных разрядов регистра, группы выходы, блоков свертки по модулю два третьей группы соединены с первыми входами элементов И одиннадцатой группы, выхо 45 ды которых соединены с входами третьей группы контрольных разрядов регистра, входы второй группы блоков свертки по модулю два первой, второй и третьей групп соединены с соответ50 ствующими выходами элементов И. третьей, четвертой, десятой, тринадцатой и четырнадцатой групп, вторые входы элементов И.третьей группы и входы первого блока свертки по модулю два объединены поразрядно и соединены с выходами первой группы контрольных разрядов регистра, вторые входы элементов И четвертой группы и входы второго блока свертки по модулю два объединены поразрядно и подключены к выходам второй группы контрольных разрядов регистра, первые входы элементов И десятой группы и входы третьего блока свертки по модулю два поразрядно объединены и соединены с выходами третьей группы контрольных разрядов регистра, одноименные входы мажоритарных элементов первой группы объединены и подключены к выходам второй группы информационных разрядов регистра, выходы мажоритарных элементов первой группы соединены с первыми входами элементов

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

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

1481863

92

93

7È 789 8О 737 выходы к ) Toðt tõ и< лклк ч пы к вторым и третьим входам ..элементов И восb мой, девятой и jIBejjëäöëòîé групп, выходы мажоритарных элементов второй группы соединены с вторыми входами элементов И второй группы, входы первой группы информационных разрядов регистра и входы контрольных раэрядов регистра соединены с выходами соответствующих блоков памяти, выходы элементов И седьмой, восьмой девятой и двенадцатой групп, выходы

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

14818h3

14818б3

1481863

О

Ок2

Ом2

ОЫЗ

О<5

Оо б

Составитель В.Рудаков

Редактор И.Шмакова Техред А.Кравчук

Корректор М.Васильева

Заказ 2699/55 Тираж 559 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101 й

f7p

О О О O

f31 Я2 ЯЗ Я4

Фие. 9 й

О 0 0.0 О 0

J3t /32 ЯЗ,/3Ф ЯБ,/36

Фиа5