Устройство для формирования остатка по произвольному модулю от числа Советский патент 1992 года по МПК H03M7/18 G06F7/49 

1

(21)4876054/24

(22)18.10.90

(46) 30.09.92. Бюл. № 36

(71)Московский институт инженеров гражданской авиации

(72)С.Ж.Кишенский, А.Л.Кузьмин, Е.Н.Надобных и О.Ю.Христенко

(56) Авторское свидетельство СССР Ns 1185339, кл.С 06 F 11/08, 1984. Авторское свидетельство СССР № 1396281, кл. Н 03 М 7/18, 1988.

(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА

(57) Изобретение относится к области вычислительной техники и может быть использовано в цифровых вычислительных устройствах и в устройствах для формирования конечных полей. Целью изобретения является повышение быстродействия и расширение функциональных возможностей за счет вычисления частного от деления числа на модуль. Устройство для формирования остатка по произвольному модулю от числа содержит группу 1 элементов И, группу из К схем 2 сравнения, группу из К-1 сумматоров 3, группу из К вычислителей 4, мультиплексор 5, дешифратор 6, два регистра 7 и 8 и формирователь 9 импульсов, соединенные между собой функционально 3 ил

у

Ё

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

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

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

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

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

XI

О

ел

00 О

о

первого вычитателя, а выход второго регистра является первым выходом результата устройства, введены К-1 схем сравнения, К-1 вычитателей, К-1 сумматоров, дешифратор и мультиплексор, причем вход модуля устройства соединен соответственно с входами первой и второй групп первого сумматора и с входами первых групп остальных К-2 сумматоров, разрядные выходы i-ro сумматора i 1.K-1, соединены соответст- венно с входами первых групп (1+1)-й схемы сравнения и (i+1)-ro вычитателя, и входами второй группы (i+1)-ro сумматора, выходы элементов И группы соединены соответственно с входами вторых групп К схем сравнения и К вычитателей, выходы Больше или равно К схем сравнения соединены соответственно с входами дешифратора, выход которого соединен с адресным входом мультиплексора и с ин- формационным входом первого регистра, выход которого является вторым выходом результата устройства, выходы элементов И группы соединены соответственно с первым информационным входом мультиплек- сора, выход i-ro вычитателя соединен с (1+1)-м информационным входом мультиплексора, выход которого соединен с информационным входом второго регистра, вход разрешения записи которого соединен с выходом формирователя импульсов, вход которого соединен с входом Начало вычисления устройства.

На фиг. 1 приведена структурная схема устройства для формирования остатка по произвольному модулю от числа; на фиг.2 - структурная схема дешифратора; на фиг.З - структурная схема мультиплексора.

Устройство для формирования остатка по произвольному модулю от числа содер- жит группу 1 элементов И, группу К схем 2 сравнения, группу К-1 сумматоров 3, группу К вычитателей 4, мультиплексор 5, дешифратор 6, первый и второй регистры 7 и 8, формирователь 9 импульсов. Вход 10 числа устройства соединен с первыми входами элементов группы И. Устройство также содержит вход Начало вычисления 12, вход модуля 11, первый и второй выходы 13 и 14 результата.

Дешифратор б (фиг.2) содержит группу К-1 элементов 15 НЕ, группу К-1 элементов 16 И и шифратор 17.

Мультиплексор 5 (фиг.З) содержит группу одноразрядных мультиплексоров 18.

Устройство работает следующим образом.

В исходном состоянии регистры 7 и 8 обнулены. На вход 11 подается модуль, по которому осуществляется формирование

остатка от числа. На вход 10 подается число. Число и модуль подаются в двоичном коде. После подачи на вход 11 модуля на выходах сумматоров 3i, За, ... Зк-1 формируются соответственно коды чисел 2 х М, 3 х М,... К-1х х М, где М - модуль.

Подача положительного потенциала на входе 12 Начало вычисления открывает группу элементов И 1 и код числа поступает на вычитатели, на которых из него вычитаются числа, сформированные сумматорами 3. Одновременно входное число сравнивается на устройствах сравнения 2 с кодами чисел на выходах сумматоров 3. В том случае, когда на выходе соответствующего сумматора 3 код меньше по значению, чем код входного числа, соответствующая схема 2 сравнения формирует выходной положительный сигнал Больше или равно.

Сигналы со схем сравнения поступают на входы дешифратора 6. На выходах элементов И 16 в совокупности с выходным сигналом элемента НЕ -15i и сигналом с выхода 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... на выход мультиплексора подключается сигнал нулевого адреса, то есть само число N. На выходе дешифратора 6 - также нулевой код частного.

Если, например, N 2 М, сработают первая и вторая схемы сравнения 2; на выходе дешифратора 6 - двоичный код числа на выход мультиплексора 5 подключается сигнал с выхода вычитателя 4, (сигнал N-2- М 00...00), то есть имеет место нулевой остаток и частное, равное 2.

Таким образом, устройство для формирования остатка по произвольному модулю от числа позволяет осуществить определение остатка за один такт работы; кроме того, формируется частное от деления исходного числа на выбранный модуль, по которому вычисляется остаток.

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

частного от деления числа на модуль, в него введены К-1 схем сравнения, К-1 вычитате- лей, К-1 сумматоров, дешифратор и мультиплексор, причем вход значения модуля устройства соединен соответственно с входами первой и второй групп первого сумматора и входами первых групп остальных К-2 сумматоров, разрядные выходы i-ro сумматора (i 1,K-1) соединены соответственно с входами первых групп (1+1)-й схемы сравнения и (i+1)-ro вычитателя и с входами второй группы (i+1)-ro сумматора, выходы элементов И группы соединены соответственно с входами вторых групп К схем сравнения и К вычитателей, выходы Больше или равно К схем сравнения соединены соответственно с входами дешифратора, выход которого соединен с адресным входом мультиплексора и с информационным входом первого регистра, выход которого является вторым выходом результата устройства, выходы элементов И группы соединены соответственно с первым информационным входом мультиплексора, выход 1-го вычитателя соединен с (1+1)-м информационным входом мультиплексора, йШоД которого соединен с информационным входом второго регистра, вход разрешения записи которого соединен с выходом формирователя импульсов, вход которого соединен с входом начало вычислений устройства.

К-1

17

ЁКгл

Фиг. 2

«о

5

Фиг.З