Устройство для защиты от ошибок в памяти Советский патент 1985 года по МПК G06F11/08 

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

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

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

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

ка.

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

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

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

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

Устройство для защиты от ошибок в памяти содержит информационный вход 1, первый регистр 2 сдвига, второй блок 3 буферной яамяти, блок 4 формировашы синдромов, блок 5 вычисления определителей, блок 6 вычисления ошибок, третий блок 7 буферной памяти, второй регистр 8 сдвига, сумматор 9 по мддугао дав, первый. блок 10 буферной пдаитй, в1жЬд 11 устройства, выходы 12 и 13 nispBoro регистра, выход 14 второго блока буферной памяти, выкод 15блока формирования синдромов, выходы 16 и 17 блока вычисления определителей, выход 18 блока вычисления ошибок, вькоды 19 и 20 третьего блока буферной памяти.

. Второй блок 3 буферной памяти соiдержит первый модуль 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) ц:оде1 8ит последовательно соединен|Ные узел 44 накопления значений полинома ошибки, узел 45 вычисления обратного значения, узел 46 умнсшени узел 47 накопления значений полинома локаторов ошибок, регистр 48. При описании работы устройства использованы следующие обозначения Y, - значения символов ошибок длин Q бит в конечном поле Галуа Q F(2 Xi,Xp- локаторы ошибокJ 5j - синдро 0. - коэффициенты полинома локатор ошибок; & - главный определительJ частные определители; i - кол чество символов ошибок в BKCJ БКС базовое кодовое слово PC-кода; оке - обобщенное кодовое слово, содержащее перемеженные символы не скольких БКС; A-tpp- коэффициенты п линома ошибок, равные минорам эле1ментов главной диагонали главного Ьпредейителя. Обозначения математических опер ций, использованные в математических вьфажениях, соответствуют обозначению операций в конечном поле Галуа. Устройство работает следуюшгим образом. - Декодируемые ОКС в последовательном коде передачи блоками по 444 бит с разделительнь1ми межблочными метками длиной 4 бита непреры но поступают на вход 1 устройства. Первый регистр 2 преобразует после довательный код в параллельный и передает каждое обобщенное кодовое слово (ОКС) в первый блок 10 и во второй блок 3 буферной памяти словами по 12 бит за 37 тактов записи В первом блоке 10 буферной памяти каждое ОКС хранится до тех пор, пока оно не обработано в блоках 3 - 6 и в третьем блоке 7 буферной памяти не сформирован его вектор ошибок. В процессе работы блока 10 буферной памяти один из его модулей памяти находится в режиме записи, один - в режиме считывания, а два модуля памяти - в режиме ожидания. Причем считывание производится на тактовой частоте в 3/4 раза меньше чем запись, с целью устранения разрывов во времени в выходной информации устройства декодирования, которые могут образовываться в свя зи с отбрасыванием контрольных символов и межблочной метки в каждом кодовом слове. Во втором блоке 3 буферной памяти (фиг. 2) очередное ОКС записывается в одну из двух пар модулей памяти, например в модули 23 и 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 из его памяти считьшаются значения тех определителей и коэффициентов полинома ошибок, которые соответствуют имеющемуся в обработанном БКС числу ошибок. Определители вычисляются для известной линейной системы уравнений, .1 связьшающей значения синдромов bj и коэффициентов Jy полинома локаторов ошибок: ,f,,,t. Методом вложенных миноров последовательно вычисляются все главные Д и частные определители йц для всех i от 1 до 4. Завершается процесс вычисления определителей вычислением главного определителя пятого порядка: ,9 + U4i 8 un5i -U4556 A445s Частные определители й, могут быть вычислены, так как для каждого БКС формируется только по девять синдромов 5; . С целью повьшеиия скорости вычис ления определителей в блок 5 вычисления определителей введен не один операционный узел, содержащий последовательно соединенные узел перемножения и накапливающий сумматор, а два одинаковых операционных узла работающих параллельно. Вычисление определителей выполняются по микропрограмме за 57 микрокоманд. Синдромы в течение всего цякла их обработки в блоке 5 постоянно хранятся в регистре 33 сийдромов. Необходимые при вьтолнении групп операций синдрркы подаются на входы первого узла 38-и второго узла 39 у ноЖения с помощью коммутаторов 34 37 в соответствии с микрооперациями .данной микрокоманды местного устрой ства управления блока 5. Причем на входы коммутатора 34 подключены семь синдромов , на вторую гру пу входов коммутатора 35 - пять синдромов . на вторую группу входов коммутатора 36 - семь синдромов первую группу входов коммутато15а 3.7 - четыре синдромаб,Такое распределение синдромов получено благодаря соответствуняцему построению микропрограммы и позволяет реализовать коммутаторы на типовых восьмиканапьных мультиплексорах. Кроме того, с входа 32 блока 5 на первые входы коммутаторов 35 и 36 подается константа 1, являющаяся единичным элементом () конечного поля. Эта константа предназначена как для органи696зации передачи без искажения через коммутатор 37, узлы 39 и 41 значений синдрома 5( . и определителя и у так и для использования ее в качестве одного из исходных данных, подаваемых на вькод 16 блока 5 коммутатором 35. Эта же константа 1 используется для организации перегрузки содержимогой25из блока 42 в блок 43 памяти при формировании массива выходных данных блока. Промежуточные результаты вычислений параллельных групп операций, вьтолняемых первым узлом 38 умножения, первым накапливающим устройством 40 и вторым узлом 39 умножения, вторьи накапливающим сумматором 41, параллельно записываются .в блоки 42 и 43 памяти. Если при выполнении очередной микрокоманды потребуется этот промежуточный результат, то она начина-г ется считыванием промежуточного результата из соответствующего моду ля памяти и подачей его на второй вход узлов 38 и 39 умножения с помощью коммутаторов 35 или 37, Введение в блок 5 вычисления определителей регистра 33 синдромов и коммутаторов 34-37 позволяет резко з еньшить время, требуемое на передачу синдромов из блока 4 в блок 5 устройства, а также существенно упрощает распараллеливание вычислительного процесса в блоке 5 и форм {рование массивов выходных данных блока 5. Быстрая классификация типов ошибок , т.е. вьщеление ситуаций, когда в Данном БКС имеется одна две, три или четыре ошибки, осуществляется в блоке 5 за одну микрокоманду. Информация, являющаяся основанием для быстрой классификации типов ошибок, накапливается в третьем регистре 45 в процессе вычисления оп ределителей. Для этого проверяется наличие нулевых значений главных определителей во втором какапливакяцем сумматоре 41, а результаты проверок заносятся в регистр 45. Если все пять главных определителей и,5,, ftj, й U4 5 нулевые, то ошибки в данном БКС отсутствуют. Если5,гЬО, а Д Д, Д4 i О, то в данном IBKC имеется только один символ ошибок. Если &2 0, а 4 4 &5 - О, то в БКС - два символа ошибок. Если Ь О, а Л( й О, то в БКС три символа ошибок. Если & &5 О, TQ в БКС четьфе символа ошибок. И наконец, если О, то в ВКС обнаружено количество ошибок t В последнем случае образуется сигнал отказа от декодирования данного БКС, по которому устройство управле ния запрещает исправление ошибок в данном БКС. После, этого блок 5 вычисления определителей принимает синдромы следующего БКС, обрабатывает их и передает выходные данные в блок 6 вычисления ошибок и так далее. . Блок 6 вьгчисления ошибок на оог новании данных, полученных из блока 5,, синхронно вычисляет значения полинома ошибок и полинома локаторов ошибок, а по обнулению значеНИИ последнего локализует ошибку и вычисляет значение ошибки, как част ное от деления значения главного оп делителя на значение полинома ошибо которое последний принимает в момен ее локализации: W(Xi) Аналогично можно показать., что полином Q(X1 , названный полиномом ошибок, коэффициентами элементов глав являются миноры НОЙ диагонали главного определител представляет собой функцию вида: t | ipp4u t-1 t; # р П П (. Ы ГП5К+ V KitpmjP . Очевидно, что в момент локализа ции Р -и ошибки при значение полинома ошибки имеет вид: , Ц(Хр).ПУ;П; ;ПП , jitt ,м k«( icrm+1 i т.е. OHO отличается от выражения главного определителя только тем, что в нем отсутствует один сомножи тель ь . Следовательно, значение данной ошибки равно частному от де ления значения главного определите ля, на значение полинома ошибок, ко рое последйий принимает в момент л лизации этой ошибки. Благодаря этому достигается существенное упрощение блоков 5 и устройства, так как отпа1дает необходимость дополнительного вычисления значений формальной производной полкнома локаторов, ошибок и коэффициентов полинома ошибок. Последнее объясняется тем, что указанные коэффициенты являются промежуточными результатами вычисления главного и частных определителей в блоке 5 вычисления определителей. Коэффициенты полинома ошибок и определители очередного БКС в течение пяти тактов вводятся соответственно по входам Т6 и 17 в узел 44 . вычисления значений полинома ошибок и узел 47 вычисления значений полинома локаторов ошибок. Значение главного определителя при этом записывается также в регистр 48, Значение полиномов в узлах 44 и 47 вычисляются за 37 тактов только для первых 37 элементов циклической группы конечного поля Q F (2 ) . В каждом такте с помощью узлов 45 и 46 на выходе 18 блока 6 образуется частное от деления главного определителя на значение полинома ошибки. Однако запись этого частного в третий блок 7 буферной памяти в качестве значения ошибки производится лишь в тех случаях, в которых обнуляется значение на выходе узла 47. В этот момент на его выходе образуется нулевой сигнал, по которому устройство зшравления формирует управляющий сигнал записи в блок 7 буферной памяти. Таким образом, по истечении 37 тактов работы блока 6 в ячейках . блока 7 буферной памяти, соответствующих номерам Локаторов ошибок, записаны соответствующие им значения ошибок, т.-е. в одном из модулей 26 - 29 памяти блока 7 сформирован вектор опмбок данного БКС. После этого блок 6 вычисления ошибок принимает коэффшщенты полинома ошибок и определители следующего БКС за 37 тактов работы вычисляет символы его ошибок, которые записываются в другой модуль сверхоперативной памяти блока 7 и так далее. После того, как сформированы в двух модулях блока 7, например, в модулях 26 и 27 векторы ошибок двух соседних БКС, входящих в состав одного из оке, эти модули переводятся в режим считьгоания, а другая пара модулей 28 и 29 - в режим поочередной записи: вначале запись вектора ошибок одного БКС в модуль 28, а затем запись вектора ошибок следующего БКС в модуль 29. При этом второй и третий коммутаторы 30 и 31 отключают от выходов 19 и 20. блока 7 выходы модулей 28 и 29 и подключают к ним выходы модулей 26 и 27. Считьшание из пары модулей 26 и 27 производится синхронно, и на выходы 19 и 20 за 28 тактов считывания словами по 12 бит передается вектор ошибки перемеженной информационной части ОКС, Таким образом, третий блок 7 буферной памяти осуществляет перемежение символов векторов ошибок Б .т.е. преобразует последовательност векторов ошибок БКС, поступающую на вход 18 блока 7, в последовательность векторов ошибок ОКС на в

12

13

Фиг 2

1lt

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

9

-S.

39

19

Д

ЛГ

j-n

15

M

3

/

г

Л

16

Ц

18 -

Чб

Фиг. 5