Запоминающее устройство с коррекцией групповых ошибок Советский патент 1989 года по МПК G11C29/00 

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

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

На фиг. 1 представлена функцио- .нальная схема ЗУ; на фиг. 2 и 3 - функциональная схема блока коррекции; на фиг. 4 и 5 - геометрическая интерпретация кодовой матрицы соответственно двух модифицированных трехмерных кодов, 28,16 () и 54,36 () с контролем по четности для всех К -разрядных комбинаций и с контролем по нечетности для всех нечетных комбинаций информационного сообщения.

Устройство содержит блоки 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 - с

Я

00

00 0

со

314

вторым информационным входом коммутатора 10, четвертый выход 79 - с входом первого элемента И 11, а пяты выход 80 является выходом окончания цикла обращения устройства, выходы 81-96 блока 8 коррекции соединены с одними из входов элементов НЕРАВНОЗНАЧНОСТЬ 12-27.

Устройство имеет информационные вхЪды 97, информационные выходы 98, вход 99 записи, вход 100 считывания Выход коммутатора 10 соединен с управляющим входом 101 блока 8. Выходы 102-104 блока 8 коррекции являются одними из информационных входов устройства, выходы 105-126 - индикаторным выходом 127 устройства. Установоные входы 128-131 являются установочными входами устройства, адресным входом 132 которого являются адресны входы блоков 1-7 памяти.

Блок 8 коррекции содержит регистр 133, первую группу блоков 134-137, вторую группу блоков 138-141 и треть группу блоков 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 группы мажоритарных элементов, пороговый элемент 210, реализующий функцию Ь 2, тринадцатую 211-213 и четырнадцатую 214-216 группы элементов И, с второго по шестой элементы И 217-221. Регистр 133 имеет выходы 222-252, блоки 134-141 - выходы 253- 260.

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

Мажоритарные элементы 204-206 и 207-209 служат для коррекции одиночных ошибок в разрядах р1, g% g , которые для устройства являются информационными разрядами входного и выходного сообщения, поступающими соответственно с информационных- вы

0

5

0

5

0

5

0

5

0

5

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

Блоки 201-203 служат для анализа ЗК-разрядного кода синдрома и формирования координат ti {|5} и {у} ошибочных информационных символов S1-S16 (в рассматриваемом примере К равно, например, четырем) в случае неисправности одного из блоков 1-4 памяти и формирования сигналов некорректируемой ошибки при ошибке в разных блоках памяти или полном отказе одного из блоков 1-7, которые через пороговый элемент 210 и элементы И 220 и 221 выдаются на выходы 120-122 устройства как сигналы НК01, НК02, НКОЗ (адрес соответствующего вектора прерывания).Схема подключения выходов 222-237 регистра и выходов элементов И 146-147, 211-216 к входам блоков 134-145, а также выходов блоков 201-203 к входам элементов И 170-185 определяется кодо- вой матрицей примененного в устрой- стве трехмерного кода.

На фиг. 4 и 5 обозначены: S1-S16, S17-S36 7 информационные разряды трехмерного кода; gl, g2, g3 - контрольные разряды общей четности входного и выходного сообщения в коде 3.1, занимающие в кодовой матрице фиктивные позиции (т.е. в кодовом слове в явном виде не присутствуют и, следовательно, в ячейки блоков памяти не записываются); al-ak, bl-bk, cl-ck - контрольные разряды формируемого для устройства кода (в режиме записи); cil-eЈk, , Jl-fk - разряды формируемого в устройстве синдрома (в режиме чтения).

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

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

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

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

Контрольные разряды С1-С4, соот-- ветствующие третьей координате С модифицированного трехмерного кода

(28-16), примененного в предлагаемом устройстве, формируются аналогично координатам А и В модифицированного двумерного кода (24,16), т.е. проверкой на четность () или нечетность (р, 1) четырех соответствующих диагоналей кодовой матрицы (фиг. 4).

Б общем случае для числа информа-

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

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

Q кодовой мгтрицы. Контрольные разряды, участвующие в формировании контрольных разрядов тре хмерного кода, поступают в режиме записи с входной магистрали вместе с Ка информацион5 ными разрядами и, следовательно, воспринимаются устройством как три дополнительных информационных разряда входного (К +3)-разрядного сообщения. Затем при занесении кодово0 го слова в блоки памяти контрольные разряды отбрасываются, т„е. в кодовом слове, хранящемся в ячейке блока памяти, не присутствуют. В режиме чтения параллельно с декодированием кодового слова независимо формируются три разряда общей четности. При этом контрольный разряд общей четности g трехмерного кода формируется в коде (3,1). Затем эти контрольо ные разряды участвуют в формировании трех групп разрядов синдрома oil-oik, |31-pk, jfl-jfk согласно кодовой матрице трехмерного кода и одновременно (после соответствующей коррек5 ции) поступают на выход устройства. Таким образом на выходную магистраль данных, как и с входной магистрали, также поступает (К2+3)-разрядное сообщение.

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

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

5

(т.е. в коде 3,1) контрольных разряда обпей четности g: g g2, g}, которые для устройства являются соответственно информационными разрядами S17, SI8, S19, на вход 99 - признак записи, а на вход 75 - сигнал Запуск, который через коммутатор 10 проходит на вход 101 блока 8, где заносит в регистр 133 информацию, находящуюся на входах 47-62 и 102- 104. После этого в блоке 8 начинается исправление на мажоритарных элементах 204-206 разрядов р 1, g4, общей четности входного сообщения и формирование координат А, В, С модифицированного трехмерного кода 28, 16 согласно кодовой матрице (фиг„4).

Контрольные разряды а1-а4 (координата А) формируются с помощью блоков 134-137, контрольные разряды Ц-Ь (координата В) - с помощью блоков 138-141, а контрольные разряды cl-c4 (координата С) - с помощью блоков 142-145.

На входе 100 блока 8 присутствует логический нуль (низкий уровень напряжения) , а на входе 99 - логическая единица (высокий уровень напряжения). В результате элементы И 146- 157 и 214-216 остаются закрытыми, и на их выходах находятся логические нули, а элементы И 211-213 открываются, пропуская на входы блоков 134- - 145 исправленные значения трех контрольных разрядов g1 , g4, .g3. Одновременно открываются блоки 158-169 и сформированные значения контрольных разрядов (координаты А, В, С трехмерного кода) поступают с их выходов на входы 63-74 блока 8 и на входы блоко 5-7.

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

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

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

коммутатор с выхода блока 9 задержки запрещается. Одновременно разрешается прохождение сигнала с выхода 78, поступающего позже сигнала с выхода 77 с задержкой, равной времени

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

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

5 последовательности.

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

5 считанные значения контрольных разрядов с выходов 241-252 регистра 133 через элементы И 146-157 поступают на соответствующие входы блоков 134-145.

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

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

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

ности одного из блоков 5-7 ошибки в контрольных разрядах блоками 201-203 игнорируются, что равносильно их исправлению, так как в данном случае никогда не произойдет неправиль- ной коррекции какого-либо информационного символа S1-S16, ибо работа элементов И 170-185, настроенных только на координаты «, /3, у искаженных информационных символов, блокируется (на входах каждого из них присутствует логический нуль).

Одновременно разрешается работа элементов И 186-197, настроенных только на унитарные координаты или , или Јj4 искаженных контрольных символов al-a4, или Ы-Ъ4, или cl-c4 одного из блоков 5-7.

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

Позиции ошибочных контрольных символов (логические единицы на выходах 108-119 устройства) определяются с помощью элементов И 186-197.

При обнаружении корректируемой

ческих нулей на установочные входы 128-131,

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

35

ошибки в одном из блоков 1-4 разреша- 20 блокирована, например, подачей логи- ется работа элементов И 170-185, каждый из которых настроен на трехмерные координаты oil, J}j, Jk одного информационного символа S1-SI6 (i,j, k - номер строки,- столбца и диагона- 25 ли кодовой матрицы), а работа элементов И 186-197 блокируется, так как на выходе элементов И 217-218 присутствуют логические нули. На выходах 81-96 вырабатываются сигналы коррекции, инвертирующие на элементах НЕРАВНОЗНАЧНОСТЬ 12-27 соответствующие информационные символы S1-S16. На выходах 108-122 сохраняются логические нули, а на выходы 123-126 выдается унитарный номер неисправного блока 1-4. Позиции ошибочных информационных символов (логические единицы на выходах 81-96 устройства) определяются с помощью элементов И 170-185.

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

При отсутствии некорректируемых отказов (на выходах 120-122 присутствуют логические нули)цикл Чтение заканчивается по сигналу с выхода 79 блока 9 задержки, проходящему через элемент И 11. Информационные раз40

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

45

50

55

ряды S1-S16, скорректировать при необходимости на элементах НЕРАВНОЗНАЧНОСТЬ 12-27, и три разряда общей четности g1, g, g3, скорректированные на мажоритарных элементах 207- 209, выдаются через элементы И 28-46 на информационные выходы 98 устройства. Затем на выход 80 выдается соотQ ветствующий сигнал.

При возникновении некорректируе- мых ошибок в одном или нескольких блоках памяти или некорректируемых отказов в самом устройстве контроля

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

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

блокирована, например, подачей логи-

блокирована, например, подачей логи-

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

I 1

14«

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

bbJ1

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

0 группы подключены к входу считывания устройства, входы первой и второй групп блоков сравнения первой группы подключены соответственно к первым выходам блоков свертки по модулю два первой и второй групп, входы первой и второй групп блоков сравнения второй группы соединены соответственно с прямыми выходами блоков свертки по модулю два первой и тред тьей групп, входы первой и второй групп блоков сравнения третьей группы подключены соответственно к прямым выходам блоков свертки по модулю два второй и третьей групп, выходы

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

5

0

5

выходы которых подк ii iMOHM к вторым и третьим входам племен гон И восьмой, девятой и двенадцатой групп, выходы мажоритарных элементов второй группы соединены с вторыми входами элементов И второй группы, входы первой группы информационных разрядов регистра и входы контрольных разрядов регистра соединены с выхо

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

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

128129130111

Фиг.

О О О О

j3T j32 J33 JJV

Редактор И.Шмакова

. О О О О О О

У3 J32 #3 J34 j}S J36 Фие.5

Составитель В.Рудаков Техред А.Кравчук

Корректор М.В

О&1

ОоСЗ О off

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