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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН 4(51) С 06 Р 11/08 СПИ САНИ ЗОБРЕ ЕТЕЛЬСТВУ НИЯ АВТОРСКОМУ С(71) Курский политехнический институт и Институт проблем моделирования в энергетике АН Украинской СС(54)(57) 1. УСТРОЙСТВО ДЛЯ ЗАЩИТЫОТ ОШИБОК В ПАМЯТИ, содержащеепервый и второй регистры сдвига,первый блок буферной памяти, блок. формирования синдромов, блок вычисления ошибок и сумматор по модулюдва, причем вход первого регистрасдвига является информационнымвходом устройства, первый и второйвыходы регистра сдвига подключенык соответствующим информационнымвходам первого блока буферной памяти выход которого подключен к первому входу сумматора по модулю два,выход второго регистра сдвигаподключен к второму входу сумматора по модулю два, выход которогоявляется выходом устройства, о т -л и ч а ю щ е е с я тем, что,с целью повышения быстродействия,оно содержит второй и третий блокибуферной памяти и блок вычисленияопределителей, причем первый и второй выходы первого регистра сдвигасоединены с информационными входаорого блока буферной памяти,выход которого соединен с вторымвходом сумматора по модулю два,при этом блок вычисления определите.лей содержит регистр синдромов, четыре коммутатора, два блока памяти,два узла умножения и два накапливающих сумматора, при этом выходблока формирования синдромов под- Р ключен к входу регистра синдромов,группа выходов которого подключенак соответствующим группам управляющих входов коммутаторов, выходыпервого и второго блоков памяти подключены к первым группам информационных входов первого и второгокоммутаторов, вторые группы информационных входов которых подключены к шине задания константы "1",выходы первого и третьего коммутаторов соединены с входамипервогоузла умножения, выход которого через первый накапливающий сумматор .подключен к адресному входу первогоблока памяти, выходы второго и чет- вертого коммутаторов подключены ксоответствующим входам второго узлаумножения, выход которого через второй накапливающий сумматор подключенк адресному входу второго блокапамяти, выходы первого и второго коммутаторов соединены с соответствующими входами блока вычисления ошибокинформационный выход которого соединен с адресным входом третьего блокабуферной памяти, выходы которого соединены с входами второго регистрасдвига, сигнальный выход блока вычисления ошибок является выходомошибки устройстваФ2. Устройство по й. 1, о т л ич ю щ е е с я тем, что второй ми вт а ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ЯО 1161969 А1151969 блок буФерной памяти содержит четыре модуля памяти и коммутатору входыь модулей памяти попарно объединены и являются первым и вторым информацион ными входами блока, выходы модулей,памяти соединены с соответствующими входаии коммутатора, выход которого является выходом блока.3. Устройство по и, 1, о т л ич а ю щ е е с я тем, что третий блок буферной памяти содержит четы/ ре модуля памяти и два коммутатора, причем входы четырех модулей памяти.объединены и являются входом блока, а их выиоды попарно подключены к входам первого и второго коммутаторов, выходы которых являются выходами блока.4. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок выИзобретение относится к вычислительной технике, а именно к специализированным вычислительным устройствам защиты от ошибок внешней. памяти ЦВИ, и может быть испбльзовано для 5 автоматического контроля и исправления Ошибок,Цель изобретения - повышение быст родействия и упрощение устройства.1 ОНа фиг. 1 представлена блок-схема устройства для защиты от ошибок в памяти на Фиг. 2 - блок"схема второго блока буферной памяти; на Фиг. 3 - блок-схема третьего блока буферной памятиф на Фиг, 4 - блоксхема блока вычисления определителей, ка Фиг. 5 " блок"схема блока вычисления ошибок.Устройство для защиты от ошибок в памяти содержит информационный вход 20 .1, первый регистр 2 сдвиге, второй блок 3 буферной памяти, блок 4 Формирования синдромов, блок 5 вычисления определителей, блок 6 вычисления ошибок, третий блок 7 буферной памя ти, второй регистр 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.5 1 О 15 20 При описании работы устройстваиспользованы следующие обозначения:У; - значения символов ошибок длинойЦ бит в конечном поле Галуа СГ(2 ц);Х;,Хр - локаторы ошибок; 5 - синдромы;3 - коэффициенты полинома локаторовошибок; Ь - главный определитель,6 В- частные определители 1 - количество символов ошибок в БКС, БКС -базовое кодовое слово РС-кода,ОКС - обобщенное кодовое слово,содержащее перемеженные символы нескольких БКС; А - коэффициенты полинома ошибок, равные минорам элементов главной диагонали главногопределителя.Обозначения математических операций, использованные в математических выражениях, соответствуютобозначению операций в конечномполе Галуа.Устройство работает следующимобразом,Декодируемые ОКС в последовательном коде передачи блоками по444 бит с разделительными межблочными метками длиной 4 бита непрерывно поступают на вход 1 устройства.Первый регистр 2 преобразует последовательный код в параллельный ипередает каждое обобщенное кодовоеслово (ОКС) в первый блок 10 и вовторой блок 3 буферной памяти словами по 12 бит за 37 тактов записи.В первом блоке 10 буферной памятикаждое ОКС хранится до тех пор,пока оно не обработано в блоках3 - 6 и в третьем блоке 7 буфернойпамяти не сформирован его векторошибок.В процессе работы блока 10 буферной памяти один из его модулейпамяти находится в режиме записи,один - в режиме считывания, а двамодуля памяти - в режиме ожидания.Причем считывание производится натактовой частоте в 3/4 раза меньшейчем запись, с целью устраненияразрывов во времени в выходной информации устройства декодирования,которые могут образовываться в связи с отбрасыванием контрольныхсимволов и межблочной метки вкаждом кодовом слове,Во втором блоке 3 буферной памяти (фиг. 2) очередное ОКС записывается в одну из двух пар модулей памяти, например в модули 23 25 30 35 40 45 50 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 из его памяти считываются значения тех определителей и коэффициентов полинома ошибок, которые соответствуют имеющемуся в обработанном БКС числу ошибок.Определители вычисляются для известной линейной системы уравнений,Мсвязывающей значения синдромов ,)и коэффициентов б полкнома лока 3торов ошибок:5 +161-1 =О1Методом вложенных миноров последовательно вычисляются все главные 6 и частные определители 6 для всех 1 от 1 до 4,Завершается процесс вычисления определителей вычислением главного определителя пятого порядка:441 8 42436 44Частные определители Ь немогут быть вычислены, так как для каждого БКС формируется только по девять синдромов 5 .С целью повышения скорости вычисления определителей в блок 5 вычис-. ления определителей введен не один операционный узел, содержащий последовательно соединенные узел перемножения и накапливающий сумматор, .а два одинаковых операционных узла, работающих параллельно. Вычисление определителей выполняются по микро.программе за 57 микрокоманд.Синдромы в течение всего цикла их обработки в блоке 5 постоянно хранятся в регистре 33 синдромов, Необходимые при выполнении групп операций синдромы подаются на входы первого узла 38 и второго узла 39 ум ножения с помощью коммутаторов 34 - 37 в соответствии с мнкрооперацнями .данной микрокоманды местного устройства управления блока 5. Причем на входы коммутатора 34 подключены семь синдромов В -б, на вторую груп пу входов коммутатора 35 - пятьсиндромов 6-85, на втоРУю Группувходов коммутатора 36 - семь синдромов 6-8, на первую группу входовкоммутатора 3.7 - четыре синдромами,-1Такое распределение синдромов получено благодаря соответствующему построению микропрограммы и позволяет реализовать коммутаторы на типовых восьмиканальных мультиплексорах, Кроме того, с входа 32 блока 5 на первые входы коммутаторов 35 и 36 подается константа "1", являющаяся единичным злементом (Ы) конечного поля. Эта константа предназначена как для органи данных блока 5. 45 ошибок, накапливается в третьем регистре 45 в процессе вычисления оп 55 5 16 15 20 25 ЗО 35 зации передачи без искажения через коммутатор 37, узлы 39 и 41 значений синдрома б.и определителя 4 так и для использования ее в качестве одного из исходных данных, подаваемых на выход 16 блока 5 коммутатором 35.Эта же константа "1" используется для организации перегрузки содержимого 6 из блока 42 в блок 43 памяти при формировании массива выходных данных блока. Промежуточные результаты вычислений параллельных групп операций, выполняемых первым узлом 38 умножения, первым накапливающим устройством 40 и вторым узлом 39 умножения, вторым накапливающим сумматором 41, параллельно записываются .в блоки 42 и 43 памяти. Если при выполнении очередной микро- команды потребуется этот промежуточный результат, то она начина-. ется считыванием промежуточного результата из соответствующего моду ля памяти и подачей его на второй вход узлов 38 и 39 умножения с помощью коммутаторов 35 или 37.Введение в блок 5 вычисления определителей регистра 33 синдромов и коммутаторов 34 - 37 позволяет резко уменьшить время, требуемое на передачу синдромов из блока 4 в блок 5 устройства, а также существенно упрощает распараллеливание вычислительного процесса в блоке 5 и Формирование массивон выходных Быстрая классификация типов ошибок, т.е. выделение ситуаций, когда в данном БКС имеется одна, две, три или четыре ошибки, осуществляется в блоке 5 за одну микрокоманду. ИнФормация, являющаяся основанием для быстрой классиФикации типов ределителей, Для этого проверяется наличие нулевых значений главных определителей во втором накапли 5 б вающем сумматоре 41, а результаты проверок заносятся в регистр 45Если все пять главных определителей 6,=6,4,Ь нулевые, тоошибки в данном БКС отсутствуют.Если 1 ФОу а Ь= 44Ь - Оу тов данном БКС имеется только одинсимвол ошибок, Если Б ф О, а 4 -Ь 4=ошйбок, Если Ь Ф О, а 4= Ь= О, тов БКС три символа ошибок, Если Ь 4 ф ОЬ = О, то в БКС четыре символаошибок. И наконец, если Ь 5О, то вБКС обнаружено количество ошибок 9. 5В последнем случае образуется сигнал отказа от декодирования данногоБКС, по которому устройство управле.ния запрещает исправление ошибок в1 аданном БКС.После. этого блок 5 вычисленияопределителей принимает синдромыследующего БКС, обрабатывает ихи передает выходные данные в блок 615вычисления ошибок и так далее,Блок 6 вычисления ошибок на осгновании данных, полученных из блока5 синхронно вычисляет значенияполинома ошибок и полинома локаторов ошибок, а по обнулению значе 20ний последнего локализует ошибку ивычисляет значение ошибки, как частное от деления значения главного определителя на значение полинома ошибок,которое последний принимает в момент25ее локализации:Ьч-яц)Аналогично можно показать., что 30полинам Я(х 1, названный полиномомошибок, коэффициентами которогоявляются миноры 1 р, элементов глав, ной диагонали главного определителяпредставляет собой функцию вида: Э 5И (ХХ Афрр =2: П У;Х;Х(Х+Х,.км П П х+хОчевидно, что в момент локализации Р -й ошибки при 1-Мр значениеполинома ошибки имеет вид:1-45ц(х)=,П У;ГцП П Х+х 14 Ф 1г.е. оно отличается от выраженияглавного определителя только тем,что в нем отсутствует один сомножи Отель. Следовательно, значениеданной ошибки равно частному от деления значения главного определителя на значение полинома ошибок, котороепоследний принимает в момент лока 55лизации этой ошибки.Благодаря этому достигаетсясущественное упрощение блоков 5 и 6 устройства, так как отпадает необходимость дополнительного вычисления значений формальной производной поли- нома локаторов ошибок и коэффициентов полинома ошибок. Последнее объясняется тем, что указанные коэффициенты являются промежуточными результатами вычисления главного и частных определителей в блоке 5 вычисления определителей.Коэффициенты полинома ошибок и оп. ределители очередного БКС в течение пяти тактов вводятся соответст. венно по входам 6 и 17 в узел 44 - , вычисления значений полинома ошибок и узел 47 вычисления значений полинома локаторов ошибок. Значение главного определителя при этом записывается также в регистр 48,Значение полиномов в узлах 44 и 47 вычисляются за 37 тактов только для первых 37 элементов циклической группы конечного поля ч Г (2 ) .6 В каждом такте с помощью узлов 45 и 46 на выходе 18 блока 6 образу- ется частное от деления главного определителя на значение полииома ошибкиОднако запись этого частного в третий блок 7 буферной памяти в качестве значения ошибки производится лишь в тех случаях, в которых обнуляется значение на выходе узла 47, В этот момент на его выходе образуется нулевой сигнал, по которому устройство управления фор" мирует управляющий сигнал записи в блок 7 буферной памяти,Таким образом, по истечении 37 тактов работы блока 6 в ячейках . блока 7 буферной памяти, соответст. вующих номерам локаторов ошибок, записаны соответствукицие нм значения ошибок, т,е. в одном из модулей 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 хранятся неисправленные информационные части ОКС в пе ремеженном виде.Синхронно со считыванием из блока 7 вектора ошибок данного ОКС ипередачей его через регистр 8 напервый вход сумматора 9 по модулюдва из блока 10 считывается ОКС,соответствующее этому вектору ошибоки передается на второй вход сумматора 9.На выходе 11 сумматора 9 обра зуется исправленная информационнаячасть данного ОКС. В случае отказаот декодирования какого-либо БКСна выходе 18 блока 6 образуетсянулевой вектор ошибок данного БКС, 20 в соответствующем случае памяти блока 7 запрещается запись вектораошибок данного БКС, и поэтому символы этого БКС будут переданы навыход 11 устройства без исправления.1151969 Составитель И Текред Т,Фант зов Корректор М. СамборскаяПо писное актор А. Шанд Заказ 2325/38В по 3035атент", г, Ужгород, ул. Проектная,Тираж 710НИИПИ Государственного комитета СССРевам изобретений и открытийМосква, Ж, Раушская наб., д. 4/