Устройство для формирования остатка по произвольному модулю от числа

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 765896 А ИСАНИЕ ИЗОБРЕТЕНИЯ Бюл. М 3 кий инсти ции енский,Ю.Христен е свидетекл,6 06 Е е свидете л,НОЗМ тут инженеров гражА.Л.Кузьмин, Екольство СССР11/08, 1984.льство СССР7/18, 1988.(54) УСТРОЙСТВО ДОСТАТКА ПО ПРОИЗОТ ЧИСЛА ФОРМИРОВАНИЛЬНОМУ МОДУЛЮ ти го Наиболее бл ности к заявлен для формировани му модулю от чис элементов И, два читатель,два реги мента И, два фо схему сравнения устройства являизким по техническои сущному является устройство я остатка по произвольнола, содержащее два блока блока элементов ИЛИ, выстра, вычитатель, два элермирователя импульсов и Недостатком известного тся низкое быстродейстГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯПРИ ГКНТ СССР АВТОРСКОМУ СВИДЕТЕЛЬСТВ(21) 4876054 (22) 18,10.90 (46) 30.09.92 (71) Московс данской ави (72) С.Ж.Киш добных и О. (56) Авторск В 1185339,Авторск М 1396281,Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах и в устройствах для формирования конечных полей,Известно устройство для формирования остатка по произвольному модулю от числа, содержащее два блока элементов ИЛИ, два блока элементов И, вычитатель и первый регистр; недостатком известного устройства является низкое быстродействие,1)5 Н 03 М 7/18, 6 06 Г 7/49(57) Изобретение относится к области вычислительной техники и может быть использовано в цифровых вычислительных устройствах и в устройствах для формирования конечных полей, Целью изобретения является повышение быстродействия и расширение функциональных возможнбстей за счет вычисления частного от деления числа на модуль, Устройство для формирования остатка по произвольному модулю от числа содержит группу 1 элементов И, группу из К схем 2 сравнения, группу из К - 1 сумматоров 3, группу из К вычислителей 4, мультиплексор 5, дешифратор 6, два регистра 7 и 8 и формирователь 9 импульсов, соединенные между собой функционально. 3 ил. вие и узкие функциональные возможнос за счет отсутствия бпределенйя "частно а при выделении остатка, 4Целью изобретения является повышение быстродействия и расширение функциональных возможностей за счет выделения частного от деления числана модуль,Поставленная цель достигается тем, что О в устройство для вычисления остатка по произвольному модулю от чйсла, содержащее группу элементов И, первый и второй регистры, формирователь импудьсов, первую схему сравнения и первый вычитатель, причем вход числа устройства соединен с первыми входами элементов И группы, вторые входы которых соединены с входом "Начало вычисления" устройства, выход формирователя импульсов соединен с входом разрешения записи первого регистра, вход модуля устройства соединен с входами первых групп первой схемы сравнения и5 10 15 20 25 30 35 40 45 50 55 первого вычитателя, а выход второго регистра является первым выходом результата устройства, введены К - 1 схем сравнения, К - 1 вычитателей, К - 1 сумматоров, дешифратор и мультиплексор, причем вход модуля устройства соединен соответственно с входами первой и второй групп первого сумматора и с входами первых групп остальных К - 2 сумматоров, разрядные выходы -го сумматора = 1,К - 1, соединены соответственно с входами первых групп (+1)-й схемы сравнения и +1)-го вычитателя, и входами второй группы (+1)-го сумматора, выходы элементов И группы соединены соответственно с входами вторых групп К схем сравнения и К вычитателей, выходы "Больше или равно" К схем сравнения соединены соответственно с входами дешифратора, выход которого соединен с адресным входом мультиплексора и с информационным входом первого регистра, выход которого является вторым выходом результата устройства, выходы элементов И группы соединены соответственно с первым информационным входом мультиплексора, выход 1-го вычитателя соединен с (+1)-м информационным входом мультиплексора, выход которого соединен с информационным входом второго регистра, вход разрешения записи которого соединен с выходом формирователя импульсов, вход которого соединен с входом "Начало вычисления" устройства,На фиг,1 приведена структурная схема устройства для формирования остатка по произвольному модулю от числа; на фиг,2 - структурная схема дешифратора; на фиг,З - структурная схема мультиплексора.Устройство для формирования остатка по произвольному модулю от числа содержит группу 1 элементов И, группу К схем 2 сравнения, группу К - 1 сумматоров 3, группу К вычитателей 4, мультиплексор 5, дешифратор 6, первый и второй регистры 7 и 8, формирователь 9 импульсов, Вход 10 числа устройства соединен с первыми входами элементов группы И. Устройство также содержит вход "Начало вычисления" 12, вход модуля 11, первый и второй выходы 13 и 14 результата.Дешифратор 6 (фиг.2) .содержит группу К - 1 элементов 15 НЕ, группу К - 1 элементов 16 И и шифратор 17.Мультиплексор 5 (фиг,З) содержит группу одноразрядных мультиплексоров 18.Устройство работает следующим образом,В исходном состоянии регистры 7 и 8 обнулены. На вход 11 подается модуль, по которому осуществляется формирование остатка от числа. На вход 10 подается число. Число и модуль подаются в двоичном коде, После подачи на вход 11 модуля на выходах сумматоров 31, 32, .Зкформируются соответственно коды чисел 2 х М, 3 х М, , К - 1 х х М, где М - модуль,Подача положительного потенциала на входе 12 "Начало вычисления" открывает группу элементов И 1 и код числа поступает на вычитатели, на которых из него вычитаются числа, сформированные сумматорами 3. Одновременно входное число сравнива- ется на устройствах сравнения 2 с кодами чисел на выходах сумматоров 3. В том случае, когда на выходе соответствующего сумматора 3 код меньше по значению, чем код входного числа, соответствующая схема 2 сравнения формирует выходной положительный сигнал "Больше или равно".Сигналы со схем сравнения поступают на входы дешифратора 6, На выходах элементов И 16 в совокупности с выходным сигналом элемента НЕ .151 и сигналом с выхода 2 к формируется позиционный код типа "000010000", в котором номер разряда, в котором расположена "единица" соответствует вычитателю, выходной сигнал которого коммутируется мультиплексором 5 на выход устройства, В шифраторе 17 позиционный код преобразуется в двоичный, Этот двоичный код поступает на адресные входы мультиплексора 5 и в то же время является управляющим для него. Код с выхода дешифратора 6 является частным от деления исходного числа М на модуль М,С некоторой задержкой, обеспечиваемой формирователем 9 и необходимой для окончания переходных процессов в устройстве, с выхода формирователя 9 поступает импульс, по фронту которого в регистр 7 и роизводится запись частного, а в регистр 8 - остатка от деления К на М,Число одноразрядных мультиплексоров 18 в мультиплексоре 5 равно разрядности числа К, Одноименные выходы всех вычитателей 4 и соответствующего элемента И группы 1 подключены к информационным входам одного блока 18.В случае, когда ИМ, само число М является остатком, При этом не срабатывает ни одна схема 2 сравнения, на выходе шифратора 17 формируется код "0000"; на выход мультиплексора подключается сигнал нулевого адреса, то есть само число М, На выходе дешифратора 6 - также нулевой код частного.Если, например, й = 2 М, сработают первая и вторая схемы сравнения 2; на выходе дешифратора 6 - двоичный код числа "2"; на выход мультиплексора 5 подключается сигнал с выхода вычитателя 4 (сигнал й - 2 У=00 ОО), тоесть имеет место нулевой остаток и частное, равное м 2",Таким образом, устройство для формирования остатка по произвольному модулю от числа позволяет осуществить определение остатка за один такт работы; кроме того, формируется частное от деления исходного числа на выбранный модуль, по которому вычисляется остаток,Формула изобретения УстройсТво для формирования остатка по произвольному модулю от числа, содержащее группу элементов И, первый и второй регистры, формирователь импульсов, первую схему сравнения и первый вычитатель, причем вход числа устройства соединен с первыми входами элементов И группы, вторые входы которых соединены с входом "Начало вычислений" устройства, выход формирователя импульсов соединен с входом разрешения записи первого регистра, вход значения модуля устройства соединен с входами первых групп первой схемы сравнения и первого вычитателя, а выход второго регистра является первым выходом результата устройства, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет вычисления частного от деления числа на модуль, в него введены К - 1 схем сравнения, К - 1 вычитателей, К - 1 сумматоров, дешифратор и мультиплексор, причем вход значения модуля 5 устройства соединен соответственно с входами первой и второй групп первого сумматора и входами первых групп остальных К - 2 сумматоров,аарядныа выходы .го сумматора ( = 1,К - 1) соединены соответственно с 10 входами первых групп (+1)-й схемы сравнения и (1+1)-го вычитателя и с входами второй группы (+1)-го сумматора, выходы элементов И группы соединены соответственно с входами вторых групп К схем сравнения и К 15 вычитателей, выходы "Больше или равно" Ксхем сравнения соединены соответственно с входами дешифратора, выход которого соединен с адресным входом мультиплексора и с информационным входомпервого реги стра, выход которого является вторым выходом результата устройства, выходы элементов И группы соединены соответственно с первым информационным входом мультиплексора, выход 1-го вычитателя сое динен с (+1)-м информационным входоммультиплексора, вь 1 ход которогосоединен с информационным входом второго регистра, вход разрешения записи которого соединен с выходом формирователя импульсов, вход 30 которого соединен с входом "начало вычислений" устройства.1765896 Составитель Т. КишенсТехред М. Моргентал Редактор Т, Орловская Корректор И,Шмакова изводственно-издательский комбинат "Патент", г. Ужгоррд, ул,Гагарина, 1 аказ 3389 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СС 113035, Москва, Ж, Раушская наб., 4/5