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

 

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

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

РЕСПУБЛИН

А1 уу 4 Н 03 М 7/18

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4150879/24-24 (22) 24,11,86 (46) 15.05.88. Вюл, 9 18 (72) В.И.Петренко (53) 681.3 (088.8) (56) Авторское свидетельство СССР

Р 1105895, кл. G 06 F 11/08, 1983.

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

Р l185339, кл. 6 06 F 11/08, 1984. (54) УСТРОЙСТВО ДЛЯ.ФОРМИРОВАНИЯ

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

ЧИСЛА (57) Изобретение относится к вычислительной технике н может быть ис„„SU„„1396281 пользовано в цифровых вычислителвйых устройствах, а также в устройствах для формирования элементов конечных полей. Целью изобретения является повышение быстродействия. Поставленная пель достигается тем, что устройство для формирования остатка по произвольному модулю от числа, содержашее блоки 4, 13 элементов ИЛИ, блоки 11, 12 элементов И, регистр

9, вычитатель 14, содержит формирователи 2,3 импульсов, элементы ИЛИ

5 6, регистр -0 ri схему 15 сравнения с соответствующими связями. 1 ил, 1396281

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

Целью изобретения является повышение быстродействия.

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

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

Принцип работы устройства для формирования остатка по произвольному 25 модулю от числа заключается в реализации следующей идеи приведения по модулям чисел.

Из некоторого числа, поступающе- 30

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

35 тождественное равенство нулю числа.

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

В исходном состоянии все регистры обнулены, Модуль, по которому осуществляется формирование остатков чисел, задается параллельным двоичным кодом, подаваемым на вход 7 моду- 45 ля устройства. На вход 8 числа устройства поступает число в параллельном двоичном коде После подачи кодов числа и модуля на входы устройства на вход 1 пНачало вычисления подают импульС, который открывает блок 11 эле50 ментов И и, пройдя через элемент ИЛИ

5, поступает на вход разрешения схемы 15 сравнения. Код числа проходит через блок ll элементов И и через

55 блок 4 элементов ИЛИ на первый информационный вход схемы 15 сравнения, на второй информационный вход которой с входа 7 поступает значение модуля.

В результате сравнения могут возникнуть следующие ситуации.

Число по своему значению меньше модуля. В этом случае схема 15 сравнения выдает импульс по своему первому выходу, который поступает на первый вход элемента ИЛИ 6 и на вход разрешения записи регистра 9. На информационный вход регистра 9 в этот момент воздействует код числа с выходов блока 4 элементов ИЛИ, В результате код числа оказывается записанным в регистре 9 и поступает с его выхо" дов на выход 16 устройства, а на вы-; ход 17 "Конец вычисления" поступает импульс с выхода элемента ИЛИ 6.

Число по своему значению численно равно модулю. В этом случае схема 15 сравнения выдает импульс по своему второму выходу, который обнуляет регистр 9 и через элемент ИЛИ 6 поступает на выход 1|Конец вычислениячустройства. Число по своему значению численно больше модуля. В этом случае схема 15 сравнения выдает импульс по своему третьему выходу, который поступает на вход формирователя 2 импульсов и на вход разрешения вычитателя 14. На вход вычитаемого вычитателя 14 поступает значение модуля с входа 7 устройства,а на вход уменьшаемого — значение числа через блок

11 элементов И и блок 13 элементов

ИЛИ. Значение разности с выхода вычитателя 14 под воздеиствнем импуль . са, сформированного формирователем

2 импульсов, по фронту входного импульса записывается в регистр 10.

В этот момент времени заканчивается действие (длительность) импульса, сформированного на входе 1 устройства. По срезу импульса, сформированного формирователем 2 импульсов, формирователь 3 импульсов формирует импульс, который открывает блок 12 элементов И и поступает через элемент ИЛИ 5 на вход разрешения схемы

15 сравнения, Код числа, записанный в регистр 10, через блок 12 элементов И и блок 4 элементов ИЛИ поступает на первый вход схемы 15 сравнения, на второй вход которой посту пает с входа 7 код модуля„ Под действием импульса с выхода элемента

ИЛИ 5 схема 15 сравнения сравнивает. коды чисел, поступающие на его входы. В результате сравнения могут возникнуть три ситуации„ при кото1396281 рых схема 15 сравнения выдаст импульс в зависимости от результата сравнения на один из своих трех выходов. Далее работа устройства в зависимости от того, по какому из выходов схема 15 сравнения выдаст импульс, аналогична описанной. Процесс вычисления остатка по модулю от числа будет продолжаться до тех пор, пока полученное в результате вычитания число окажется меньше или равно величине модуля. В результате на выходе 16 устройства окажется остаток от числа по модулю, а на выходе

17 "Конец вычисления" — импульс, свидетельствующий о том,что остаток .найден.

Составитель А.Клюев

Техред Л.Сердюкова

Корректор Л.Пилипенко

Редактор Е.Копча

Тираж 928

Заказ 2504/57

Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

Ф о р М у л а и з о б р е т е н и я

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

5 вход Начало вычисления" устройства

tt соединен с первым входом первого элемента ИЛИ, выход которого соединен с входом разрешения схемы сравнения, выход Меньше которой соединен с входом разрешения записи первого регистра и с первым входом второго элемента ИЛИ, выход которого является выходом Конец вычисления

15 устройства, выход Равноп схемы <. сравнения соединен с вторым входом второго элемента ИЛИ и с входом ус- тановки в "0" первого регистра, информационный вход которого соединен

20 с выходом первого блока элементов

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

30 входом второго блока элементов И, t1 ныход Больше" схемы сравнения сое- . динен с входом разрешения вычитателя и через первый формирователь импульсов — с входом разрешения записи вто35 рого регистра и с входом второго формирователя импульсов, выход которого соединен с вторым входом второго блока элементов И и с вторым входом первого элемента ИЛИ.