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

(51) С,06 Р 11/О БРЕТ ТВ орои гр ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ ПИСАНИЕ ИВТОРСНОМУ СВЩ(72) А.А,Коляда171) Научно-исследовательский инсти 1 ут прикладных физических проблем им.акад.А.Н.Севченко,56) 1, Авторское свидетельство СССР ф 714399, кл. С 06 Р 11/08, 1980,2, Журавлев НЛ., Котелюк Л.А. надежность и контроль ЭВМ. М., "Сов. радио", 1978, с. 137 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ К ИСПРАВЛЕНИЯ ОШИБОК В НЕПОЗИЦИОННОМ ЮДЕ, содержащее К +2 входных регистрОв, где .К- число информационных .оснований, и две группы сумматоров коррекции, при этом входы входных регистров являются информационными входами устройства, первые входы сумматоров коррекции первой и второй групп соответственно объединены, вторые входы сумматоров коррекции первой группы объединены, вторые входы сумматоров коррекции второй группы объединены, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены дешифратор, К +2 элементов задержки; два блока суммирования вычетов, первая и вторая группы вспомогательных регистров, трехразрядный регистр, К элементов И, группы мультиплексоровК +2 выходных регистров и элемент И,причем выходы К+2 входных регистров подключены к входам К+2 элементов задержки соответственно и к соответствующим входам первогои второго блоков суичирования вьщетов, первые выходы К +2 элементов задержки подключены соответственно к первым входам сумматоров коррекции первой ивторой групп, к вторым входам которых подключены выходы соответственновторого и первого блоков суммирования вычетов, подключенные также квходам дешифратора, первый, второй итретий выходы которого через трехразрядный регистр соединены соответственно с первыми входами мультиплексоров (К+1)-й и (К+2)-й групп и(К+1),-м входам элемента И, группавходов которого подключена к выходамК элементов И и к первым входаммультиплексоров К групп, вторые входыкоторых соединены с первыми входамиК элементов И и с выходами К вспомо"гательных регистров второй группы,а третьи входы - с вторыми входамиК элементов задержки, вторые выходы(К+1)-го и (К+2)-го элементов задержки соединены с вторыми входами мультиплексоров (К+1)-й и (К+2)-й групп,третьи входы которых соединены с выходами (К+1)-го и (К+2)-го регистровпервой группы, выход-го (1=1-вспомогательного регистра первой группы подключен к второму входу -гоэлемента И, выходы мультиплексоровК+2 групп подключены соответственнок входам (+2 выходных регистров, выходы которых являются информационными выходами устройства, выход элемента И является выходом отказа от декодирования устройства, выходы сумматоров коррекции первой и второй группподключены соответственно к входам вспомогательных регистров первои иИзобретение относится к вычислительной технике и предназначено дляиспользования в быстродействующихвычислительных устройствах конвейерного типа повышенной надежности, работающих в непозиционном коде,Известно устройство для обнаружения и исправления ошибок в непозиционном коде, содержащее входной регистр, входы которого являются входами устройства, блок свертки по контрольным модулям, входы которого подключены к первому выходу входногорегистра, сумматоры по контрольныммодулям, по входам подключенные квторому и третьему выходам входнОгорегистра и выходам блока модульнойсвертки по контрольным модулям, блокпамяти ошибок, входы которого соединены с выходами сумматоров по конт. Рольным основаниям, и блок сумматоровкоррекции по модулям непозиционнойсистемы счисления, первый вход которого подключен к выходу блока памятиошибок, второй, третий и четвертый 25входы - соответственно к первому,второму и третьему выходам входногоье гЕстра, а выход является выходомустройства, которое при соответствующей структуре блока модульной сверткиЗОпо контрольным основаниям осуществляет коррекцию однократных ошибок какпо информационныь, так и по контрольным модулям за 3+1 оц Кмодульныхопераций, где К - количество информа.ционных оснований, через 3 Х обозначается наименьшее целое число,неменьшее Х 13Недостаток устройства заключается в том, что используемый в нем .способ 40 формирования контрольных разрядов затрудняет применение устройства для контроля ошибок арифметических операций,Наиболее близким по своей сущности к изобретению является устройство для обнаружения и исправления ошибок в непозиционном коде, содержащее регистры информационных и контрольных разрядов кода, узел свертки по конт рольным основаниям, узел перевода остаточного кода в позиционный код, по входам подключенный к выходам регист" ра информационной части кода, а по выходам - к входам узла свертки по 55 контрольным основаниям, вычитатель,таблицу поправок и сумматор коррекции,-причем первые входы вычитателя соединены с выходами регистра контрольной части кода, вторые входы - к выходам узла свертки по контрольным основаниям, а выходы - к соответству ющим входам таблицы поправок, первые входы сумматора коррекции соединены с выходами регистра информационной части кода, а вторые входы - с выходами вычитателя 1 2.Устройство ориентировано на остаточное кодирование чисел рабочего диапазона по всем модулям системы в том числе и по контрольным, благода-. ря чему оно может использоваться для контроля ошибок как при передаче данных, так и при.выполнении арифметических операций. В рамках остаточного кодирования формирование контрольных признаков по информационным символам кода осуществляется с помощью операции расширения, которое в данном устройстве выполняется путем преобразования информационной части не- позиционного кода в позиционный код. Это приводит к низкому быстродействию устройства.Цель изобретения - повышение быстродействия устройства. Поставленная цель достигается тем, что в устройство для обнаружения и исправления ошибок в непозиционном коде, содержащее К+2 входных регистров, где К - число информационных ос. нований, и две группы сумматоров коррекции, при этом входы входных регистров являются. информационными входами устройства, первые входы сумматоров коррекции первой и второй групп соответственно объединены, вторые входы сумматоров корекции первой группы объединены, вторые входы сумматоров коррекции второй группы объединены, введены дешифратор, К+2 элементов задержки, два блока суммирования вычетов, первая и втоРая гРУппы вспомогательных регистров, трехразрядный регистр, К элементов И, группы мультиплексоров, К+2 выходных регистров и элемент И, причем выходы К+2 входных регистров подключены ко входам К+2 элементов задержки соответственно и к соответствующим входам первого и второго блоков суммирования вычетов, первые выходы К+2 элементов задержки подключены соответственно к первым вхо дам сумматоров коррекции первой и11349второй групп, к вторым входам которыхподключены выходы соответственно второго и первого блоков суммированиявычетов, подключенные также к входамдешифратора, первый, второй и третийвыходы которого через трехразрядныйрегистр соединены соответственно спервыми входами мультиплексоров (К+1)-й и (К+2)-й групп и (К+1)-м входомэлемента И, группа входов которого 1 Оподключена к выходам К элементов И ик первым входам мультиплексоров Кгрупп, вторые входы которых соединеныс первыми входами К элементов И и свыходами К вспомогательных регистров 15второй группы, а третьи входы - свторыми входами К элементов задержки,вторые выходы (К+1) и (К+2)-го элементов задержки соединены с вторымивходами мультиплексоров (К+1)-й и(К+2)-й групп, третьи входы которыхсоединены с выходами (К+1)-го и(К+2)-го регистров первой группы, выход 1-го (1=1-К) вспомогательного регистра первой группы подключен к вто рому входу 1-го элемента И, выходымультиплексоров К+2 групп подключенысоответственно ко входам К+2 выходных регистров, выходы которых являются информационными выходами устройст- З 0ва, выход элемента И является выходомотказа от декодирования устройства,выходы сумматоров коррекции первой и,второй групп подключены соответственно к входам вспомогательных регист 35ров первой и второй групп.На фиг,1 и 2 приведена структурная схема предлагаемого устройствадля обнаружения и исправления ошибокв непозиционном коде.40Устройство содержит информационныевходы устройства 1,1, 121 К+2(К- количество информационных модулей), входные регистры 2, 1, 2.22 К+2, элементы задержки 3.1, 3.2,45ЗК+2, блоки суммирования вычетов 4 К+1и 4 К+2 соответственно по первому ивторому контрольным модулям системы,сумматоры коррекции первой группы5.1, 5.25 К+2, сумматоры коррек- к 0ции второй группы 6.1, 6.26 К,дешифратор 7, вспомогательные регистры первой группы 8.1, 8.2 8 К+2,вспомогательные регистры второй груп-,пы 9,1, 9.2, , 9 К, трехразрядныйрегистр 10, элементы 11.1, 11.211 К, группы мультиплексоров 12.1,12,2, , 12 К+2, выходные регистры 41 413.1, 13,2,13 К+2, (К+1), входовый элемент И 14, информационныевыходы устройства 15. 1, 15.2,15 К+2, выход 16 отказа от декодирования устройства.Входные регистры устройства 2.1,2.2, , 2 К+2 предназначены для приема соответствующих цифр исходногонепозиционного кода 0.1 К1К,К"о , 3 ог о( . Если слово(К К.1,г,к-, ,ок-,к- к мк- фк 4 не содержитошибки, т.е. является кодовым, тоего компоненты определяются следукнцими соотношениями о, = АМ, щ, 1=1,2А=. Мк, К +1 кМК где М = -- (1=1,2К),М к-К.4М - П щщ у фуу МАК система информационных модулей; причем щк) 2 р+К, р - некоторое фиксированное натуральное число, щки щ к - контрольные основания, выбираемые из условия: щк, щ. (1=1,2,к+К; 3= 1,2) А - число рабочего диапазона системы, 0= 1 РМ к 1 ф РМк- + +1 рМк -1, черезХ 1,обозначается наименьший неотрицательный вычет, сравнимый с величиной Х по модулю щ.Элемент задержки 31 (1=1,2К+ +2) представляет собой цепочку из Т+1 последовательно соединенных регистров Т=1 о 8(К+1) , вход первого из которых является входом элемента задержки, а выходы Т-го и (Т+1)-го регистров - первым и вторым выходами соответственно. Вход элемента задержки 3.1 (1=1, 2, , +2 К) подключен к выходу регистра 2.1, первый выход - к одноименным входам сумматоров коррекции 5.1 и 6.1 (1 ФК+1, К+2, если )Ф 2),а второй выход соединен с третьим входом группы мультиплексоров21.Блок суммирования .вычетов 4.К+3 по -му контрольному модулю (1=1,2) имеет конвейерную структуру и служит для формирования за Т тактов 3-й компоненты Б синдрома Б=(Б,Б) не позиционного кода, определяемой по формулеК"41134941при этом г-й вход блока 4+К+1 (г= =1,2К) подключен к выходу регистра 2.г, (К+1)-й вход - к выходу . регистра 2.К+1, а выход подключен ко вторым входам сумматоров коррекцйи 5 1-й группы и 3-му входу дешифратора 7Дешифратор 7 предназначен для выделения значений синдромаЯ(Я,Я) кода, соответствующих сигналам10 1, если Б,ФО, а Б =-О(4)О в остальных случаях,Предлагаемое устройство реализует способ обнаружения и исправления ошйбок в непозиционном коде заключающийся в следующем.В соответствии с формулой (2) вычисляются компоненты Я и Яб синдрома Я=(Бе, Бу) кода. Если при этом Я=Я=О, то декодируемое слово не искажено, т.е, является кодовым.Если БО, а Я(,р=О (=1,2), то(11 уошибка произошла по 1-му контрольному модулю. В этом случае истинное значение (К+3)-й цифры кода совпадает с вьиетом1, если Б фО и Я фО 6 (5)0 в остальных случаях,Элемент И 11. вырабатывает сигнал 6 поразрядного совпадения входных величин Х 1 и У 6 10,1ш,1 в соответствии с формулой25б,г,ч, (В еу 1)(1) (1",где Х и У - 3-е цифры двоичных представлений вычетов Х, и У соответственно г=)1 о(1 ш.( =1,2 К, ;символом 8 обозначается операция сложения по модулю 2.Элемент И 11.3. (=1,2К) реализуется на сумматорах. по модулю 2 и г, - входовом элементе ИЛИ.35,Первый вход элемента 11. через вспомогательный регистр 8 соединен с выходом сумматора коррекции 5,х, второй вход соединен с вторым входом 2(0 группы мультиплексоров 12. и через вспомогательный регистр 9. с выходом сумматора коррекции 6., выход11. подключен к первому входу группы мультиплексоров 12.1 и -му входу 45 элемента И 14, (К+1)-й вход которого подключен к третьему выходу.трехразрядного регистра 10 (=1,2. К), Второй вход группы мультиплексоров 12.К+1 соединен с выходом вспомога тельного регистра 8.К+3, а первый вход - с -м выходом трехразрядного регистра 10, входы которого подключены к соответствующим выходам дешифратора 7 Ц=1,2). Выход группы мульти плексоров 12. соединен со входом выходного регистра устройства 13.хдля- всех 1=1,2, б К+2, Случай Я,ФО и ЯФО соответствует искажению одного из информационных символов; Для локализации и исправления такой ошибки достаточно:а) для каждого =1,2К в формуле (2) заменить -ю цифру кода на неизвестное 2 и затем найти его по контрольным модулям, используя ( 1) и (2). В результате получим вьиеты=К;,р б) если лля некоторого 1 е 11,2К выполняется Х=У 1, то заключаем,что 3 -я цифра кода искажена. Исправленным ее значением является вычетХ - У,в) случай, когда для всех =1,2,,К выполняется неравенство Х ФУуказывает на то, что произошла ошибка, кратность которой больше едини-цы, и в рамках используемого корректирующего кода она не может быть исправлена,Рассмотрим как работает предлагаемое устройство для обнаружения и исправления ошибок в непозиционном коде.Непдзиционный код (ск-1З с ,подлежащий койтролю, через входы 1.1, 1.2, , 1,К+2 устройства принимается на входные регистры 2,1, 2.2 2.К+2, откуда он подается на элементы задержки 3.1, 3,2, е, 3. К+2 и в блоки суммирования вьиетов 4 К+1 и 4.К+2, которые по941 8Д =О, то в регистре 13. появитсявычет Х; (в данном случае Х;=У для1 4 К), если же б =1, то в регистр13. поступит .-я цифра исходногокода, Перечень всех возможных ситуаций на выходах устройства представлен в табл.1. Нулевое значение сигнала Ч, вырабатываемого на выходе 16отказа от декодирования устройства,свидетельствует о том, что исходныйкод либо бып правильным, либо .содержал ошибку по одному из модулей системы, которая исправлена, единичноезначение сигнала Ч соответствуетошибке, кратность которой большеединицы. В рамках используемого корректирующего кода такая ошибка неможет быть исправлена.Непозиционный код, сформированныйв регистрах 13.1, 13.2, , 13.К+2 .устройства (исходный или исправленный), снимается с выходов 15. 1, 15.2,, 15.К+2 устройства, и на этомоперация обнаружения и исправленияошибок в непозиционном коде заканчивается.Быстродействие прототипа, главным образом, определяется скоростнымихарактеристиками входящего в его состав блока преобразования остаточногокода в позиционный код. Теоретическаянижняя оценка времени работы прототипа составляет 2(2+ 1 о 8 К) модульныхоп ер аций.Перечень возможных ситуаций навыходах устройстваФ 7 1134 истечении Т-го такта в соответствии с (2) сформируют синдром Я=(Я,Я) непозиционного кода.На (Т+1)-м такте компонента Я синдрома Я=1,2) с выхода блока суммирования вычетов 4.К+1 подается на 3-й вход дешифратора 7 и вторые входы сумматора коррекции 5+1 д, на первый вход которого с одноименного выхода элемента задержки 3. поступает -я 1 О цифра исходного непозиционного кода4,К-% ДК-Ф .а, К,К, КСф 1, КЛ )(д=1,2 К+2) и 6.х (3.=1,2К) получают соответственно вычеты Х, и У (см. формулы (7-9, которые с :вйходов сумматоров поступают в ре гистры 8. и 9. соответственно, а ф дешифратор 7 в соответствии с формулами (3-5) формирует сигналы 6 кд, б,и д , которые с первого, второго и третьего выходов дешифратора передаются в трехразрядный регистр 10.25На (Т+2)-м такте работы устройства элемент И 11, (=1,2К) производит анализ содержимых Х и У; соответственно регистров 8. и 9 вырабатывая сигнал д определяемый соотношением (6), который подается на первый вход группы мультиплексоров 12.д и х-й вход элемента И 14. Одновременно с этим на первый вход (К+1)-й группы мультиплексоров (3= =1,2) и (К+1)-й вход элемента И 14 с выходов 1-го и третьего разрядов регистра 10 подаются соответственно сигналы 6 и д , на вторые входы групп мультйплексоров 12. и 12 К+340 (1=1, 2К; 1=1, 2) подаются соответственно содержимые регистров 9.1. и 8.К+1,т,е. вычеты У н Х , а на третий вход группы муль иплексоров ,12.1 (з=1,2 К+2) со второго вы- хода элемента задержки З.д поступает д-я цифра контролируемого непозиционного кода Ок,,Ы выходах группы мультиплексоров 12.1, 12.2, , 12.К+2, а следовательно, и в выходных регистрах устройства 13.1, 13.2 13.К+2 сформируется. искомый непозиционный код, а на выходе 16 элемента И 14 вырабатывается управляющий сигнал Ч=66" д . Если для некоторого 3.61,2 К+2сигнал Значения сигнало Содержание ситуации Ошибка отсутствует, на информационных выходах уст. ройс гва формируется исходный код, М =О. Ошибка . ронзошла по первому контрольному модулю, на информационных выходах устройства 4 эрмируется исправленный код, У =О.11 З 4941 Значение сигналов Содержание ситуации Значение сигналов Содержание ситуации Произошла неоднократная ошибка,наинформационныхвыходах устройства формируетсяисходный код,Ч=1; Фиг. 11 родолжение таблицы 5Ошибка произошлапо второму контрольному модулю,на информационных. выходах устройства формируетсяисправленный код,Ч =О.Ошибка произошлапо 3 -му информациочному модулю,на информационныхвыходах устройства формируетсяисправленный код, 20Ч=О,11 родолжение таблицы Время выполнения одной операции контроля непозиционного кода в пред" лагаемом устройстве занимает 2+11 од(К+1)тактов, что в два раза меньше указанной выше нижней оценки для прототипа.1134941 актор А Заказ 528 Подписноего комитета СССРний и открытийРаушская наб., д.4/5 ент", г.ужгород, ул.Проектная, 4 ППП Составитель. И.СафроноваТехред М.Гергель Тираж 71 НИИПИ Государствен делам изобрете Москва, Ж