Устройство для защиты от ошибок в памяти

 

1. УСТРОЙСТВО ДЛЯ ЗАЩИТЫ ОТ ОШИБОК В ПАМЯТИ, содержащее первь1й и второй регистры сдвига, первый блок буферной памяти, блок формирования синдромов, блок вычисления ошибок и сумматор по модулю два, причем вход первого регистра сдвига является информационным входом устройства, первый и второй выходы регистра сдвига подключены к соответствующим информационным входам первого блока буферной памяти ,, выход которого подключен к первому входу сумматора по модулю два, выход второго регистра сдвига подктччен к второму входу сумматора по модулю два, выход которого является выходом устройства, отличающееся тем, что, с целью повьшения быстродействия, оно содержит второй и третий блоки буферной памяти и блок вычисления определителей, причем первый и второй выходы первого регистра сдвига соединены с информационными входами второго блока буферной памяти, выход которого соединен с вторым входом сумматора по модулю два, при этомблок вычисления определителей содержит регистр синдромов, четыре коммутатора, два блока памяти, два узла умножения и два накапливающих сумматора, при этом выход блока формирования синдромов подключен к входу регистра синдромов, группа выходов которого подключена к соответствующим группам управляющих входов коммутаторов, выходы первого и второго блоков памяти подключены к первым группам информационных входов первого и второго коммутаторов, вторые группы информационных входов которых подключе (Л ны к шине задания константы 1, выходы первого и третьего коммутаторов соединены с входамипервого узла умножения , выход которого через первый накапливающий сумматор . подключен к адресному входу первого блока памяти, выходы второго и четСП вертого коммутаторов подключены к соответствзпощим входам второго узла а умножения, выход которого через второй накапливающий сумматор подключен к адресному входу второго блока Ф памяти, выходы первого и второго коммутаторов соединены с соответствующими входами блока вычисления ошибок, информационный выход которого соединен с адресным входом третьего блока буферной памяти, выходы которого соединены с входами второго регистра сдвига, сигнальный выход блока вычисления ошибок является выходом ошибки устройства. , 2. Устройство по iif. 1, отличающееся тем, что второй

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

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

РЕСПУБЛИН

4(51) G 06 F 11/08 т

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

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3454293/24-24 (22) 10.06.82 (46) 23.04.85. Бюл. к- 15 (72) А.П. Типикин, В.В. Петров, А.Г. Вабанин, А.Г. Пеньков, С.И. Егоров и С.Я. Солоницын (71) Курский политехнический институт и Институт проблем моделирования в энергетике АН Украинской ССР (S3} 681. 3 (088. 8) (56) Патент США Р 4162480, кл. G .06 Р: 11/12, опублик. 1981.

Патент США 0 4142174, кл. G 06 F 11/12, опублик. 1980, (54)(57) 1. УСТРОЙСТВО ДЛЯ ЗАЩИТЫ

ОТ ОШИБОК В ПАЖИТИ, содержащее первый и второй регистры сдвига, первый блок буферной памяти, блок . формирования синдромов, блок вычисления ошибок и сумматор по модулю два, причем вход первого регистра сдвига является информационным входом устройства, первый и второй выходы регистра сдвига подключены к соответствующим информационным входам первого блока буферной памяти,, выход которого подключен к первому входу сумматора по модулю два, выход второго регистра сдвига подклю.* ен к второму входу сумматора по модулю два, выход которого является выходом устройства, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит второй и третий блоки буферной памяти и блок вычисления определителей, причем первый и второй выходы первого регистра сдвига соединены с информационными входами второго блока буферной памяти, ÄÄSUÄÄ1161969 А выход которого соединен с вторым входом сумматора по модулю два, при этом блок вычисления определителей содержит регистр синдромов, четыре коммутатора, два блока памяти, два узла умножения и два накапливающих сумматора, при этом выход блока формирования синдромов подключен к входу регистра синдромов, группа выходов которого подключена к соответствующим группам управляющих входов коммутаторов, выходы первого и второго блоков памяти под. ключены к первым группам информационных входов первого и второго коммутаторов, вторые группы информационных входов которых подключены к шине задания константы "1", выходы первого и третьего коммутаторов соединены с входами первого узла умножения, выход которого через первый накапливающий сумматор . подключен к адресному входу первого блока памяти, выходы второго и чет вертого коммутаторов подключены к соответствующим входам второго узла умножения, выход которого через второй накапливакняий сумматор подключен к адресному входу второго блока памяти, выходы первого и второго коммутаторов соединены с соответствующими входами блока вычисления ошибок, информационный выход которого соединен с адресным входом третьего блока буферной памяти, выходы которого соединены с входами второго регистра сдвига, сигнальный выход блока вычисления ошибок является выходом ошибки устройства..

Ф

2. Устройство по if. 1, о т л и . ч а ю щ е е с я тем, что второй

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

3. Устройство по и. 1, о т л ич а ю щ е е с я тем, что третий блок буферной памяти содержит четы/ ре модуля памяти и два коммутатора, причем входы четырех модулей памяти.объединены и являются входом блока, а их выиоды попарно подключены к входам первого и второго коммутаторов, выходы которых являются выходами блока.

4. Устройство по п. 1, о т л и= ч а ю щ е е с я тем, что блок выИзобретение относится к вычислительной технике, а именно к специализированным вычислительным устройствам защиты от ошибок внешней, памяти ЦВИ, и может быть использовано для 5 автоматического контроля и исправления Ошн6 Ок, Цель изобретения - повышение быст-. родействия и упрощение устройства.

- 1О

На фиг. 1 представлена блок-схема устройства для защиты от ошибок в памяти на фиг. 2 — блок-схема второго блока буферной памяти, на фиг. 3 — блок-схема третьего блока буферной памяти, на фиг. 4 — блоксхема блока вычисления определителей, ка фиг. 5 - блок-схема блока вычисления ошибок.

Устройство для защиты от ошибок в памяти содержит информационный вход

1, первый регистр 2 с@вигв, второй блок 3 буферной памяти, блок 4 формирования синдромов, блок 5 вычисления определителей, блок 6 вычисления ошибок, третий блок 7 буферной памя- 2 ти, второй регистр 8 сдвига, сумматор 9 по модулю деа, первый блок

10 буферной памяти, выход 11 устройства, выходы 12 и 13 первого регистра, выход 14 второго блока буфер- ЗО ной памяти, выход 15 блока формирочисления ошибок содержит узел накопления значений полинома ошибки, узел накопления значений полинома локаторов ошибок, регистр, элемент

ИЛИ, узел умножения, узел вычисления обратного значения, причем вход узла накопления значений полинома ошиб ки является входом блока, а выход ". через узел вычисления обратного значения соединен с первым входом узла умножения, второй вход которого соединен с выходом регистра, а выход является информационным выходом блока, вход регистра объединен с входом узла накопления значений полинома локаторов ошибок и является соот-. ветствующим входом блока, выход узла накопления значений полинома ошибки является управляющим выходом бло- ка. вания синдромов, выходы 16 и 17 блока вычисления определителей, выход 18 блока вычисления ошибок, выходы 19 и 20 третьего блока буферной памяти.

Второй блок 3 буферной памяти со держит первый модуль 21, второй модуль 22, третий модуль 23 и четвертый модуль 24 памяти, выходы которых соединены с входами коммутатора 25.

Третий блок 7 буферной памяти содержит модули 26 — 29 памяти, входы которых соединены с входом 18 блока

7, а также коммутаторы 30 и 31.

Блок 5 вычисления определителей содержит шину 32 задания константы ."1", регистр 33 синдромов, коммутаторы 34 — 37, первый узел 38 умножения, второй узел 39 умножения, первый накапливающий сумматор 40, второй накапливающий сумматор 41 блоки 42 и 43 памяти.

Блок 6 вычисления ошибок (фиг, 5)

|содержит последовательно соединен:ные узел 44 накопления значений полинома ошибки, узел 45 вычисления обратного значения, узел 46 умножения, узел 47 накопления значений полинома локаторов ошибок, регистр 48.

1151969

При описании работы устройства использованы следующие обозначения:

У; — значения символов ошибок длиной

Ц бит в конечном поле Галуа 4 F(2a);

4,Хр локаторы ошибок; э — синдромьг;

3» — коэффициенты полинома локаторов ошибок, 6y — главный определитель, 6 - частные определители 1 — количество символов ошибок в БКС, БКС— базовое кодовое слово PC-кода, 0KC — обобщенное кодовое слово, содержащее перемеженные символы нескольких БКС; А — коэффициенты полинома ошибок, равные минорам элементов главной диагонали главного пределителя.

Обозначения математических операций, использованные в математических выражениях, соответствуют обозначению операций в конечном поле Галуа.

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

Декодируемые ОКС в последовательном коде передачи блоками по

444 бит с разделительными межблочными метками длиной 4 бита непрерыв но поступают на вход 1 устройства.

Первый регистр 2 преобразует последовательный код в параллельный и передает каждое обобщенное кодовое слово (ОКС) в первый блок 10 и во второй блок 3 буферной памяти словами по 12 бит за 37 тактов записи.

В первом блоке 10 буферной памяти каждое ОКС хранится до тех пор, пока оно не обработано в блоках

3 — 6 и в третьем блоке 7 буферной памяти не сформирован его вектор ошибок.

В процессе работы блока 10 буферной памяти один из его модулей памяти находится в режиме записи, один — в режиме считывания, а два модуля памяти — в режиме ожидания.

Причем считывание производится на тактовой частоте в 3/4 раза меньшей чем запись, с целью устранения разрывов во времени в выходной информации устройства декодирования, которые могут образовываться в связи с отбрасыванием контрольных символов и межблочной метки в каждом кодовом слове.

Во втором блоке 3 буферной памяти (фиг. 2) очередное ОКС записывается в одну из двух пар модулей памяти, например в модули 23

55 и 24. В каждый из модулей памяти записываются символы одного из двух базовых кодовых слов (БКС), перемеженных в составе ОКС, например в модуль 23 записываются 37 символов первого БКС, а в модуль 24-37 символов второго БКС. В это же время из другой пары модулей 21 и 22 памяти поочередно считываются первое, а затем второе БКС предыдущего ОКС. Считывание каждого БКС производится символами по 6 бит за

37 тактов. Первый коммутатор 25 в течение 37 тактов передает на выход 14 блока 3 символы БКС, считанные из одного из модулей памяти, а затем переходит к передаче на выход 14 символов другого БКС, считыьаемых из другого модуля памяти.

Общее количество тактов считывания ОКС из пары модулей 21 и 22 па— мяти составляет 74. По окончании записи — считывания во время проождения межблочной метки между оседними ОКС пары модулей памяти меняются местами, т.е. пара модулей

23 и 24 переводится в режим считывания, а пара модулей 21 и 22 в режим записи. Таким образом, второй блок 3 буферной памяти осуществляет деперемежение символов БКС, преобразуя последовательность ОКС в последовательность составляющих их БКС.

В первом блоке 10 буферной памяти

ОКС хранятся в перемеженном виде.

Считываемые посимвольно из. второго блока 3 буферной памяти БКС сра. зу же поступают в блок 4 формирования синдромов, в котором за 37 тактов параллельно вычисляются по девять синдромов для каждого БКС.

Блок 5 вычисления определителей (фиг. 4) поочередно обрабатывает каж— дое БКС в отдельности. Для каждого

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

Определители вычисляются для известной линейной системы уравнений, 1151969 данных блока 5. lt связывающей значения синдромов 5 и коэффициентов 6 . полкнома лока1 торов ошибок:

Методом вложенных миноров последовательно вычисляются все главные

6 и частные определители 6 для всех 1 от 1 до 4, Завершается процесс вычисления определителей вычислением главного определителя пятого порядка:

441 8 4й Э1 43 6 44 8

Частные определители 6< не могут быть вычислены, так как для каждого

БКС формируется только по девять синдромов 5> .

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

Синдромы в течение всего цикла их обработки в блоке 5 постоянно хранятся в регистре 33 синдромов.

Необходимые при выполнении групп операций синдромы подаются на входы первого узла 38 и второго узла 39 ум ножения с помощью коммутаторов 34—

37 в соответствии с мнкрооперацнями .данной микрокоманды местного устройства управления блока 5. Причем на входы коммутатора 34 подключены семь синдромов з -5>, на вторую груп пу входов коммутатора 35 — пять синдромов 6,"68, на вторую группу входов коммутатора 36 — семь синдромов 6 -58, на первую группу входов коммутатора 3,7 — четыре синдромами,- 1

Такое распределение синдромов получено благодаря соответствующему построению микропрограммы и позволяет реализовать коммутаторы на типовых восьмиканальных мультиплексорах. Кроме того, с входа 32 блока 5 на первые входы коммутаторов

35 и 36 подается константа "1", являющаяся единичным злементом

{Ы ) конечного поля. Эта константа предназначена как для органи5

16

ЗО

3S зации передачи без искажения через коммутатор 37, узлы 39 и 41 значений синдрома S .и определителя 4 т так и для использования ее в качестве одного из исходных данных, подаваемых на выход 16 блока 5 коммутатором 35.

Эта же константа "1" используется для организации перегрузки содержимого а азиз блока 42 в блок 43 памяти при формировании массива выходных данных блока. Промежуточные результаты вычислений параллельных групп операций, выполняемых первым узлом 38 умножения, первым накапливающим устройством 40 и вторым узлом

39 умножения, вторым накапливающим сумматором 41, параллельно записываются .в блоки 42 и 43 памяти. Если при выполнении очередной микрокоманды потребуется этот промежуточный результат, то она начина-. ется считыванием промежуточного результата из соответствующего моду. ля памяти и подачей его на второй вход узлов 38 и 39 умножения с помощью коммутаторов 35 или 37.

Введение в блок 5 вычисления определителей регистра 33 синдромов и коммутаторов 34 — 37 позволяет резко уменьшить время, требуемое на передачу синдромов из блока 4 в блок 5 устройства, а также существенно упрощает распараллеливание вычислительного процесса в блоке 5 и формирование массивон выходных

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

Если все пять главных определителей6,= 1 z 5з 44, Aq нулевые, то ошибки в данном БКС отсутствуют.

Если 1ФО а Ь а д4 6 0 то в данном БКС имеется только один

cHMBoJI oIHH6oK Если Б ф О, а 4 4=

" h8 = О, то в БКС вЂ” два символа

I 151969 ошибок. Если 5з j 00, а Ь = А = О то в БКС три символа ошибок. Если Ь4 ф 0 Ь = О, то в БКС четыре символа ошибок. И наконец, если h < P О, то в

БКС обнаружено количество ошибок >ф. 5

В последнем случае образуется сигнал отказа от декодирования данного

БКС, по которому устройство управле. ния запрещает исправление ошибок в

1а данном БКС.

После этого блок S вычисления определителей принимает синдромы следующего БКС, обрабатывает их и передает выходные данные в блок 6

1S вычисления ошибок и так далее.

Блок 6 вычисления ошибок на осг новании данных, полученных из блока

5,, синхронно вычисляет значения полинома ошибок и полинома локаторов ошибок, а по обнулению значе20 ний последнего локализует ошибку и вычисляет значение ошибки, как частное от деления значения главного опре. делителя на значение полинома ошибок, которое последний принимает в момент

25 ее локализации:

Ь ч *—

64({х;)

Аналогично можно показать, что 30 полинам Я (х1, названный полиномом ошибок, коэффициентами которого являются миноры р, элементов глав. ной диагонали главного определителя представляет собой функцию вида: . р-» (1 А рр> =X. П У;Х;Х(+)(,) x П П (х„+х„

Очевидно, что в момент локализации Р -й ошибки при 1 -Мр значение полинома ошибки имеет вид:

1-»

45, (>1)=.П 1;11ЦП О Х„+Xq

< » k=m+»

«Ф

-г.е. оно отличается от выражения главного определителя только тем, что в нем отсутствует один сомножитель >p . Следовательно, значение данной ошибки равно частному от деления значения главного определителя на значение полинома ошибок, которое последний принимает в момент лока55 лизации этой ошибки.

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

Коэффициенты полинома ошибок и определители очередного БКС в течение пяти тактов вводятся соответственно по входам 16 и 17 в узел 44 —, вычисления значений полинома ошибок и узел 47 вычисления значений полинома локаторов ошибок. Значение главного определителя при этом записывается также в регистр 48.

Значение полиномов в узлах 44 и

47 вычисляются за 37 тактов только для первых 37 элементов циклической группы конечного поля 4 Г (2 ) .

В каждом такте с помощью узлов 45 и 46 на выходе 18 блока 6 образу- ется частное от деления главного определителя на значение полииома ошибки..Однако запись этого частного в третий блок 7 буферной памяти в качестве значения ошибки производится лишь в тех случаях, в которых обнуляется значение на выходе узла 47. В этот момент на его выходе образуется нулевой сигнал, по которому устройство управления фор" мирует управляющий сигнал записи в блок 7 буферной памяти.

Таким образом, по истечении 37 тактов работы блока б в ячейках . блока 7 буферной памяти, соответствующих номерам локаторов ошибок, записаны соответству»ощие нм значения ошибок, т.:е. в одном Hs модулей 26 — 29 памяти блока 7 сформирован вектор ошибок данного ВКС.

После этого блок 6 вычисления ошибок принимает коэффициенты полинома ошибок и определители следующего БКС за 37 тактов работы вычисляет символы его ошибок, которые записываются в другой модуль сверхоперативной памяти блока 7 и так далее.

После того, как сформированы в двух модулях блока 7, например, в модулях 26 и 27 векторы ошибок двух соседних БКС, входящих в состав одного из ОКС, эти модули пере1151969

10 водятся в режим считывания, а другая пара модулей 28 и 29 — в режим поочередной записи: вначале запись вектора ошибок одного БКС в модуль

28, а затем запись вектора ошибок следующего,БКС в модуль 29. При этом второй и третий коммутаторы

30 и 31 .отключают от выходов 19 и

20. блока 7 выходы модулей 28 и 29 и подключают к ним выходы модулей

26 и 27.

Считывание из пары модулей 26 и 27 производится синхронно, и на выходы 19 и 20 за 28 тактов считывания словами по 12 бит передается вектор ошибки перемеженной информационной части ОКС.

Таким образом, третий блок 7 буферной памяти осуществляет перемежение символов векторов ошибок БКС .т.е. преобразует последовательность векторов ошибок БКС, поступающую на вход 18 блока 7, в последовательность векторов ошибок ОКС на выходах 19 и 20 блока 7. Это необходимо проводить в связи с тем, что в первом блоке 10 хранятся неисправленные информационные части ОКС в пе5 ремеженном виде.

Синхронно со считыванием из блока 7 вектора ошибок данного ОКС и передачей его через регистр 8 на первый вход сумматора 9 по модулю два из блока 10 считывается ОКС, соответствующее этому вектору ошиббк и передается на второй вход сумматора 9.

На выходе 11 сумматора 9 обра15 зуется исправленная информационная часть данного ОКС. В случае отказа от декодирования какого-либо БКС на выходе 18 блока 6 образуется нулевой вектор ошибок данного БКС, 20 в соответствующем случае памяти блока 7 запрещается запись вектора ошибок данного БКС, и поэтому символы этого БКС будут переданы на выход 11 устройства без исправления.

1151969

1151969

Составитель И. Хазова

Редактор А. Шандор Текред Т,Фанта Корректор N- Самборская.

Заказ 2325/38 Тираж 710 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4