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

 

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)л Н 03 М 7/18, G 06 F 7/49

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4876054/24 (22) 18.10.90 (46) 30.09.92. Бюл. ¹ 36 (71) Московский институт инженеров гражданской авиации (72) С.Ж.Кишенский, А.Л.Кузьмин, Е.Н,Надобных и О.Ю.Христенко (56) Авторское свидетельство СССР № 1185339, кл, G 06 F 11/08, 1984.

Авторское свидетельство СССР

¹ 1396281, кл, Н 03 М 7/18, 1988. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

ОТ ЧИСЛА

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах и в устройствах для формирования конечных полей, Известно устройство для формирования остатка по произвольному модулю от числа, содержащее два блока элементов

ИЛИ, два блока элементов И, вычитатель и первый регистр; недостатком известного устройства является низкое быстродействие, Наиболее близким по технической сущности к заявленному является устройство для формирования остатка по произвольному модулю от числа, содержащее два блока элементов И, два блока элементов ИЛИ, вычитатель,два регистра, вычитатель, два элемента И, два формирователя импульсов и схему сравнения. Недостатком известного устройства является низкое быстродейст Ы„„1765896 А1 (57) Изобретение относится к области вычислительной техники и может быть использовано в цифровых вычислительных устройствах и в устройствах для формирования конечных полей, Целью изобретения является повышение быстродействия и расширение функциональных возможнбстей за счет вычисления частного от деления числа на модуль, Устройство для формирования остатка по произвольному модулю от числа содержит группу 1 элементов И, группу из К схем

2 сравнения, группу из К вЂ” 1 сумматоров 3, группу из К вычислителей 4, мультиплексор

5, дешифратор 6, два регистра 7 и 8 и формирователь 9 импульсов, соединенные между собой функционально. 3 ил. вие и узкие функциональные возможности за счет отсутствия Определенйя частного а и ри выделении остатка. 4

Целью изобретения является повышение быстродействия и расширение функциональных возможностей за счет выделения частного от деления числа на модуль, Поставленная цель достигается тем, что в устройство для вычисления остатка по произвольному модулю от чйсла, содержащее группу элементов И, первый и второй регистры, формирователь импульсов, первую схему сравнения и первый вычитатель, причем вход числа устройства соединен с первыми входами элементов И группы, вторые входы которых соединены с входом "Начало вычисления" устройства, выход формирователя импульсов соединен с входом разрешения записи первого регистра, вход модуля устройства соединен с входами первых групп первой схемы сравнения и

1765896 первого вычитателя, а выход второго регистра является первым выходом результата устройства, введены К вЂ” 1 схем сравнения, К вЂ” 1 вычитателей, К вЂ” 1 сумматоров, дешифратор и мультиплексор, причем вход модуля устройства соединен соответственно с входами первой и второй групп первого сумматора и с входами первых групп остальных

К вЂ” 2 сумматоров, разрядные выходы i-го сумматора i = 1,К вЂ” 1, соединены соответственно с входами первых групп (i+1)-й схемы сравнения и (i+1)-го вычитателя, и входами второй группы (i+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 подается модуль, по которому осуществляется формирование

55 остатка от числа. На вход 10 подается число.

Число и модуль подаются в двоичном коде, После подачи на вход 11 модуля на выходах сумматоров З, 32, ... Зк-< формируются соответственно коды чисел 2 х М, 3 х М, „, К вЂ” 1х х М, где М вЂ” модуль, Подача положительного потенциала на входе 12 "Начало вычисления" открывает группу элементов И 1 и код числа поступает на вычитатели, на которых из него вычитаются числа, сформированные сумматорами

3. Одновременно входное число сравнива- ется на устройствах сравнения 2 с кодами чисел на выходах сумматоров 3. В том случае, когда на выходе соответствующего сумматора 3 код меньше по значению, чем код входного числа, соответствующая схема 2 сравнения формирует выходной положительный сигнал "Больше или равно".

Сигналы со схем сравнения поступают на входы дешифратора 6. На выходах элементов И 16 в совокупности с выходным сигналом элемента НЕ .15 и сигналом с выхода 2к формируется позиционный код типа

"000...010...000", в котором номер разряда, в котором расположена "единица" соответствует вычитателю, выходной сигнал которого коммутируется мультиплексором 5 на выход устройства. В шифраторе 17 позиционный код преобразуется в двоичный. Этот двоичный код поступает на адресные входы мультиплексора 5 и в то же время является управляющим для него. Код с выхода дешифратора 6 является частным от деления исходного числа N на модуль М, С некоторой задержкой, обеспечиваемой формирователем 9 и необходимой для окончания переходных процессов в устройстве, с выхода формирователя 9 поступает импульс, по фронту которого в регистр 7 и роизводится запись частного, а в регистр 8— остатка от деления N на М, Число одноразрядных мультиплексоров

18 в мультиплексоре 5 равно разрядности числа N, Одноименные выходы всех вычитателей 4 и соответствующего элемента И группы 1 подключены к информационным входам одного блока 18.

В случае, когда N < М, само число N является остатком, При этом не срабатывает ни одна схема 2 сравнения, на выходе шифратора 17 формируется код "00...00"; на выход мультиплексора подключается сигнал нулевого адреса, то есть само число N, На выходе дешифратора 6 — также нулевой код частного.

Если, например, N = 2 М, сработают первая и вторая схемы сравнения 2; на выходе дешифратора 6 — двоичный код числа

"2"; на выход мультиплексора 5 подключает1765896 ся сигнал с выхода вычитателя 4 (сигнал

N — 2 У=00...00), тоесть имеет место нулевой остаток и частное, равное м2", Таким образом, устройство для формирования остатка по произвольному модулю от числа позволяет осуществить определение остатка за один такт работы; кроме того, формируется частное от деления исходного числа на выбранный модуль, по которому вычисляется остаток, Формула изобретения устройсТво для формирования остатка по произвольному модулю от числа, содержащее группу элементов И, первый и второй регистры, формирователь импульсов, первую схему сравнения и первый вычитатель, причем вход числа устройства соединен с первыми входами элементов И группы, вторые входы которых соединены с входом "Начало вычислений" устройства, выход формирователя импульсов соединен с входом разрешения записи первого регистра, вход значения модуля устройства соединен с входами первых групп первой схемы сравнения и первого вычитателя, а выход второго регистра является первым выходом результата устройства, о т л и ч аю щ е е с я тем, что, с целью повышения быстродействия и расширения функциональных возможностей за счет вычисления частного от деления числа на модуль, в него введены К вЂ” 1 схем сравнения, К вЂ” 1 вычитателей, К вЂ” 1 сумматоров, дешифратор и мультиплексор, причем вход значения модуля

5 устройства соединен соответственно с входами первой и второй групп первого сумматора и входами первых групп остальных К вЂ” 2 сумматоров, аарядныв выходы I-го сумматора (i = 1,К вЂ” 1) соединены соответственно с

10 входами первых групп (i+1)-й схемы сравнения и (i+1)-го вычитателя и с входами второй группы (!+1)-го сумматора, выходы элементов И группы соединены соответственно с входами вторых групп К схем сравнения и К

15 вычитателей, выходы "Больше или равно" К схем сравнения соединены соответственно с входами дешифратора, выход которого соединен с адресным входом мультиплексора и с информационным входом первого реги20 стра, выход которого является вторым выходом результата устройства, выходы элементов И группы соединены соответственно с первым информационным входом мультиплексора, выход 1-го вычитателя сое25 динен с (+1)-м информационным входом мультиплексора, вь1ход которого соединен с информационным входом второго регистра, вход разрешения записи которого соединен с выходом формирователя импульсов, вход

30 которого соединен с входом "начало вычислений" устройства.

1765896

Составитель Т. Кишенский

Редактор Т, Орловская Техред М.Моргентал Корректор И,Шмакова

Заказ 3389 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат "Патент", г. Ужгоруд, ул,Гагарина, 101