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

(51)5 0 06 Е 11/О СУДАРСТВЕННОЕ ПАТЕНТНОЕДОМСТВО СССРОСПАТЕНТ СССР);4; 4,АНИЕ ИЗОБРЕТЕНИЯ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ф 1) 4880204) 24( 1) Научно-исследовательский институт авоматических систем и Институт математии и механики АН КазССР72) А.В.Бондаренко, А.В.Шершавов,.М,Амербаев, Ю.А,Макеев, И,Т,ПакР, Н.Турмухамбетов6) Авторское свидетельство СССР. 1134941, кл. (з 06 Р 11/08, 1983,б 4) УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ИСПРАВЛЕНИЯ ОШИБОК7) Изобретение относится к вычислительой технике, в частности к устройствам длябнаружения и исправления ошибок быстодействующих вычислительных устройствконвейерного типа, Цель изобретения - поышение быстродействия. В предлагаемомустройстве используются три контрольных основания, что дает возможность определить ошибку в два этапа, Во втором блоке памяти хранятся константы ранга, в третьем блоке памяти - величины возможных ошибок при значениях вычетов невязки по двум контрольным основаниям и признаки выбора подтаблицы по третьему основанию, а в чет/вертом блоке памяти - пары величин возможных ошибок, соответствующих признаку выбора подтаблицы и значению третьего остатка невязки по третьему контрольному основанию. Это позволяет исключить вычисление возможных ошибок и тем самым достичь поставленной цели, Устройство для обнаружения и исправления ошибок также содержит две группы входных регистров, блоки сумматоров, группу элементов задержки, группы сумматоров, регистр, группы вспомогательных регистров, группу элементов сравнения, группы элементов ИЛИ и И, группу сумматоров коррекции, а первый блок памяти. 1 ил. рую группу входных регистров 4.1 - 4.3, четыре блока 5,1 - 5.4 сумматоров, необходимых для вычисления неточного ранга и остатков по контрольным основаниям, группу элементов задержки 6.1 - 6.3, второй блок 7.1 памяти, в котором хранятся константы ранга, третий блок 7,2 памяти, в котором хранятся величины возможных ошибок при значениях вычетов невязки по двум контрольным основаниям и признаки выбора подтаблицы по третьему основанию, четвертый блок 7.3 памяти, в котором хранятся пары величин возможных ошибок, соответствующих признаку выбора подтаблицы и изобретения являетсяОодействия устройства,ртеже представлена стская схема устройства.иство для обнаружениябок имеет входы 1,1-1й части слова, первуегистров 2,1 - 2.6, входо контрольным основа вышерукту и исправ- ,6 инфорю группу ы 3.1-3.3 ниям, втоИзобр)стройства ок быстр устройств Целью(ие быстр На че лектриче Устро ения оши ационно входных ртение относится к вычислителье и может найти применение в х контроля и исправления ошиодействующих вычислительных 1837293 А 1значению третьего остатка невязки по третьему контрольному основанию, первую группу сумматоров 8.1 - 8,3, вторую группу сумматоров 9,1-9.3, необходимых для определения невяэки по контрольным основаниям, регистр 10, первую группу вспомогательных регистров 11,1 - 11.6, группу элементов 12,1 - 12.12 сравнения, вторую группу вспомогательных регистров 13,1 - 13,6, группу элементов ИЛИ 14.1 - 14.6, третью группу вспомогательных регистров 15.1 - 15.6, группу многовходовых элементов И 16.1-16.6, группу сумматоров коррекции 17,1-17,6, первый блок 18 памяти. Причем на чертеже не показаны синхронизирующие и тактирующие цепи, необходимость и подключаемость которых общеизвестны и не требуют дополнительного раскрытия.В предлагаемом устройстве ошибка определяется в два этапа, что дает возможность исключить вычисление возможных ошибок,Элементы сравнения 12.1-12,12 представляют собой схемы, вырабатывающие логическую "1" при совпадении всех разрядов сравниваемых чисел, Сумматоры коррекции 17.1 - 17.6 могут быть как позиционными, так и модульными.Кодировка блока 7.1 памяти должна быть выполнена в соответствии с принятой моделью арифметики. В данном случае константы для вычисления ранга имеют вид22а(а + (Р - 1/2р а= 1;п (и = 6), где а - остатки числа по информационным основаниям; Р - основания; и - мультипликативно обратные велии чины к П Р/Р по модулю Р,5 -хр - остаток по модулю Р, б - параметр точности (б )од 2 и. Константы для вычисления остатков по контрольным основаниям имеют видЬЕ =-щ(а+(Р - 1)/2) Рп/Ррь где Рк - контрольные основания; Рп - произведение информационныхи оснований Рп = П Р8 = Константы ранга имеют вид Ь.+1,=рч Р.+(Р.-1)/г) р, 1= и+1, и+2,где Ич - рангчисла М,В этом случае ранг вычисляется в соответствии с формулойпричем Ич - это старшие остатки а разрядов суммы (1); всего сумма требует Зс бит, т.е. все разряды суммы слева от запятой.Остатки по контрольным основаниям вычисляются по формуле 10ч+1Йр=Ь, рк, с= и+1, и+2, , (2) 35 Р+Рп; Рп+2 Рп+12 Рп Рп(Р 1Р 2. Рп). В этом случае объем требуемой памятиблока 18 постоянной памяти для определения ошибки по невязке должен составлять2 слов, Использование трех контрольныхоснований позволяет определить ошибку вдва этапа таблично, исключая вычисления.Схема представлена для девяти разрядных оснований, из которых 6 - информационные, а 3 - контрольные,В этом случае ошибку Ьпо невязке ( д 11,д 1 з) находят из уравнения 50Щ бр Рпр Р и)11,1 з = (д 11, д 1 з), (3)Р гдепринимает значения 0,1. Отсюда име 55 ют Л = д 11,1 з+ дРп) г- - (4)Р РпиР11,13 Р Из этих формул ясно, что четвертый15блок 5.4 сумматоров состоит из позиционныхсумматоров разрядности Зб, а первый, второй и третий блоки 5,1-5,3 сумматоров вычисления остатков по контрольнымоснованиям - из модульных сумматоров поконтрольным основаниям. Здесь возможноиспользование и позиционных сумматоров,если выполняется приведение к остатку результата суммирования каким-либо способом перед входом в блоки 7,2, 7.3 памятиили, например, простым увеличением адресного пространства этих блоков 72, 7.3памяти для хранения величин допустимыхошибок,В соответствии с теоремой об обнаружении и исправлении ошибок по невязке вусловиях использования неточного ранга вмодели контрольные основания для обнаружения и исправления одиночных ошибокдолжны удовлетворять условиямДва основания обеспечивают единств нно возможное решение( д Ь ) для дан ного.Полученное значение т/ и невязка д 17 с ужат входом в таблицу решений уравне ния:щЬр Р./Рп17= д 17, (5)1еРр 17 д 17+ т/Рп) Р (6)Это дает не более двух значений возм жного Л при заданных /д и д 17,Таким образом, обьем требуемой памят составляет в данном случае 11 х 132 с ов для блока 7.2 памяти подтаблиц 2 х 17 х 2 с ов 6 х 2 х 2 слов = Зх 2 для подтаблиц. О щий объем 2 +Зх 2 =2 слов.в в 1 оУстройство работает следующим образ м.Вычеты представления числа по информ ционным и контрольным основаниям пос упают соответственно на входы 1,1 - 1,6 и в оды 3.1 - 3.3 устройства, Значения остатк в по информационным основаниям с вых дов входных регистров 2.1 - 2.6 являются а ресами, по которым из блока 18 постоянн й памяти извлекаются константы для выч сления ранга и константы для р сширения на контрольные основания для к ждого из них, Константы для вычисления р нга поступают в четвертый блок 5,4 сумм торов для вычисления ранга, с выхода к торого значение ранга поступает на вход б ока 7,1 памяти, Эти константы вместе с к нстантами для расширения на контрольн 1 е основания суммируются с помощью сумматоров 8.1 - 8.3 первой группы, образуя о татки числа, представленного вычетами и информационным основаниям, по контр льным основаниям, На сумматорах 9,1 - 9, второй группы они вычитаются из о татков, поступивших по контрольным вход м 3.1 - 3.3, через входные регистры 4,1 - 4.345 вт рой группы, образуя невязку, Величины н вязки по двум наименьшим контрольным основаниям образуют адрес, по которому из второго блока 7.2 памяти извлекаются величины возможныхошибок Ь и бит выбора(1)подтаблицы юиз третьего блока 7.3 памяти и третьему контрольному основанию, пост пающему с выхода регистра 10, Бит выбора подтаблицы 1 и величина невязки по третьему основанию образуют адрес, по которому из соответствующей подтаблицы блока 7.3 памяти извлекэютсява значения воэможных ошибок Л и Ьг по каждому из 1 информационных оснований, На элемен тах 12,1 - 12.12 эти значения сравниются с ранее полученными значениями Л . В слуЯ чае совпадения это возможно только для одной пары Ьг, Л гзначение ошибки(клчерез соответствующие элементы ИЛИ 14.1 - 14.6 и элементы И 16,1 - 16.6 поступает на сумматоры коррекции 17.1 - 17.6, где величина ошибки складывается с соответствующим неверным остатком, благодаря чему нэ выходе устройства формируется исправленныйй результат.Первый, второй и третий блоки 5.1 - 5.3 сумматоров вместе с элементами задержки 6.1 - 6.3 служат для расширения на контрольные основания, причем элементы задержки 6,1 - 6,3 обеспечивают задержку промежуточной суммы констант расширения.Входные регистры 4.1 - 4,3 второй группы, входы которых соединены с входами 3,1 - 3.3 устройства, обеспечивают хранение остатков по контрольным основаниям и подачу их на вторые входы сумматоров 9,1 - 9.3 второй группы, При этом входы 1,1 - 1.6 остатков по информационным основаниям соединены с вспомогательными регистрами 15,1 - 15,6 третьей группы, необходимыми для синхронной работы всего устройства. Для этой же цели служат и вспомогательные регистры 11.1 - 11,6 и 13,1 - 13.6 первой и второй групп,Для лучшего понимания работы устройства может быть рассмотрен один числовой пример.Пусть число ч 35963 представлено своими остатками по основаниям 31, 29, 27, 25, 23, 19:(3, 2, 26, 13, 14, 15). Для этой системы оснований имеютР 31 29 27 25 23 19Рп/Рр 11 3 1 1 5 12щ 17 10 1 1 14 8Остатки числа й по контрольным основаниям 17, 13, 11 есть (8, 5, 4),Пусть произошла ошибка по третьему основанию М = 21 и получилось число ч (3, 30, 20, 13, 14, 15, 8, Я, 4) .Вычисляют ранг числаМРп (3, 3, 20,13, 14, 15):Р 31 29 27 25 23 19с 4 3 3 20 13 14 15Р/2 15 14 13 12 11 918 17 6 0 2 5гп 17 10 1 1 14 81 в(бу+ ) р 27 25 6 0 5 2б = 3 и константы для вычисления рангаблока 2 будуа 55 55 14 0 13 6Ич =Ха/2 )=2,23)=2,1837293 по третьему основанию по шестому основанию 1,1,.5 7м, расйирение на коня дает остатки Ь(7+1, Таки рольныеР м образ основан17 9 5 13 в 1 Л 1 Р 1= 41417=6+1 17й ) Рз=3 невязки на 9.3 второй по пятому основан начение признак ени наче- новающий ыходе льтат,гл 1 й+п(1 Р по вт му основанию 8,8)х(12,6) + рР 2 14343И ПрИ Р 2 а О, НИ ПрИтом случае может в 2 ЙР 270+ фРР 2 ешений нет оррекция в вая); тенияения и исправпервую группу ационные вхоми информацит.е, р 1 (к нулебыт Вычисляют константы расширения наконтрольные основания:в(а+ ),27 25 6 О 5 2Р(7/Р 17 11 10 12,15 3 9 5(т(а+ ),27 25 6 О 5 2Р(7/Р 117 2 12 10 3 1 6 10 изЬ 13, 11 12 5 0 8 1 (в(а+ - ),27 25 6 О 5 2 Р(7/Р 11 4, Е: 5 1 3,.10 15 .Ь(11 9 6 8 О 4 9ЬИ 1 253072Константы ранга также легко вычислить:Рл+ 17 13 1 20 РРм 1 210 3 178 2:2 22 Вш % Б 4Следовательно, значениыходе сумматоров 9.1, 9.2 руппы составляет854 Вход в блок 7.2 памяти даекоррекции возможной ошибкивыбора подтаблицы, По первому основанию= (6,6) + узРз143 = 6,Ьз= 6 1 Р 6=6, юР; по четвертому основаниюв 4 йР 4 =(8,8)х(9,1) + 4 Р 41113 = = (7,8)+ 4 Р 41113 = 85+ 4 Р 4 143 т.е, решения нет;4по пятому основанию в 5 й Р 5= (8,8)х(1,4)+ 7 р,Р 51113=(8,10) + РУ 5 Р 5 143 21,й = 21 14 23 = 18, УрБ = 0;в 6 66Р 6 =(8,8)х(11,10) + Ц 6 Р 61113 = (10,3)+ д 6 Р 6 143 =36,решения нет, Обращение в блок 7,3 памяти да по первому основанию 1 -1 юпзьЗ РЭ 41 О( 17+2взй)Рз=6; 1=0, в3(2) 6 3(з) в 5 Ь 5,р 5= 46 17=7+ 1в 5 Ь 5 Р 5=7, к=6,Ь 5 =1Ь 6(3) не существует (й = 0),ентах 12.1-12.12 срав нований 31, 27, 23;25 Ф 22 6 Ф 6 18 Ф 12, и ии Аз 6 по третьему о пает на соответству ррекции 17.1-17,6, на в азуется правильный резу На элем еют для ос25 Ф 23 .коррекц ю посту матор ко орого обр Формула изобр Устройство для обнар ения ошибок, содержащ ходных регистров, инфо ы которых являются вхооннорой дер креги ттовстрореги тцельройс вгистроявляосноти, грненагруппыров, хрого бвыхоблокдинеров,входыветст увходыветстблокоров, иходамгруппрой авыховторогистрматорблока части слова устройства, первый и втооки сумматоров, группу элементов заи, первую группу вспомогательных ров, группу многовходовых элеменвторую группу вспомогательных регигруппу сумматоров коррекции, р,отличающееся тем,что,сповышения быстродействия, в усто введены вторая группа входных рев, информационные входы которых 10 тся входами остатков по контрольныманиям устройства, первый блок памяппа адресных входов которого соедивыходами входных регистров первой , третий и четвертый блоки суммато оды которых и входы первого и втолоков сумматоров соединены с ами первого блока памяти, второй амяти, адресный вход которого соес выходом четвертого блока суммато ервая группа сумматоров, первые которых соединены с выходами соотющих элементов задержки группы, которых соединены с выходами, соотенно, первого, второго и третьего 25 сумматоров, вторая группа сумматорвые входы которых соединены с высоответствующих регистров второй , третий блок памяти, первый и вторесные входы которого соединены с 30 ми соответствующих сумматоров группы, информационный вход ресоединен с выходом третьего сумвторой группы, выход второгоамяти соединен с вторыми входами 35 сумматоров первой группы, выходы которых соединены с вторыми входами соответствующих сумматоров второй группы, четвертый блок памяти, первый адресный вход которого соединен с выходом регистра, а второй адресный вход третьего блока памяти и информационные входы вспомогательных регистров первой и второй групп подключены к выходу третьего блока памяти, группу элементов сравнения, первые входы которых соединены с выходом четвертого блока памяти, а вторые входы 21-го и (21-1)-го элементов сравнения группы соединены с выходом 1-го вспомогательного регистра первой группы (1=1,6), группу элементов ИЛИ, причем первый и второй входы 1-го элемента ИЛИ группы соединены с выходами 21-го и (21-1)-го элементов сравнения группы, третью группу вспомогательных регистров. информационные входы которых соединены с информационными входами соответствующих входных регистров первой группы, выходы элементов ИЛИ группы соединены с первыми входами соответствующих многовходовых элементов группы И, другие входы которых соединены с выходами соответствующих вспомогательныхрегистров второй группы, входы многовходовых элементов И группы соединены с первыми входами соответствующих сумматоров коррекции, вторые входы которых соединены с выходами соответствующих вспомогательных регистров третьей группы, выходы сумматоров коррекции являются выходами устройства,1837293 Составитель И. Ванюхехред М.Моргентал инРедактор Т. Коляда Т Корректор П. Гере роизводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина аказ 2866 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГК 113035, Москва, Ж, Раушская наб., 4/5