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

 

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

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

СОНИМИОТИЧИСНИХ

РЕСПУЬЛИИ (1) Н 03 И 7/18

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЬГГИЯМ

ПРИ ГКНТ СССР

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4612954/24-24 (22) 02. 12. 88 (46) 23.07.90. Бкл. Р 27 (72) Л.С.Сорока, A.Ф,Чипига и В.А.Краснобаев (53) 681.3 (088.8) (56) Авторское свидетельство СССР

У 1396281, кл. Н 03 M 7/18, 1986.

Авторское свидетельство СССР по заявке Р 4387633/24-24, кл. Н 03 N 7/18, 02.03.88.

2 (54) УСТРОЙСТ110 ДЛЯ ФОР1 П1РОВАШ1Я ОСTA .1.КЛ ЦО !1РОИЗВОЛЬ11011У МОЦУЛ10 ОТ. Ч .САГА (57) 11зобретепие относится к вычислительной технике и может быть использсвано в цифровых вычислительных устройств,-;х. Цель изобретения — повышение быстродействия. Цель достигается введением в устройство, содержащее первый 1 и второй 2 счетчики, регистр

3, элемент И 4, первый элемент ИЛИ э, первый блок 6 определения кратнос1580561 разом. ти, первый элемент 7 запрета и элемент 8 задержки, второго элемента

ИЛИ 9, третьего счетчика 10, второго элемента 11 запрета, коммутатора 12, четвертого счетчика 13 и второго блока 14 определения кратности чисел.

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

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

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

Устройство содержит первый 1 и второй 2 счетчики, регистр 3, элемент И

4, первый элемент ИЛИ 5, первый блок

6 определения кратности чисел, первый элемент 7 запрета, элемент 8 задержки, второй элемент ИЛИ 9, третий счетчик 10, второй элемент 11 запрета, 40 коммутатор 12, четвертый счетчик 13 и второй блок 14 определения кратности чисел.

Сущность изобретения состоит в том, что число А „ делят на величину модуля Р,, а затем определяют, равна ли нулю дробная часть частного. Если результата деления содержит дробную часть, отличную от нуля, то независимо друг от друга одновременно величину числа Ак уменьшают и увеличивают на единицу и результаты делят на Р;.

Если снова получаются числа, содержащие дробные части, отличные от нуля, то снова одновременно сумму А +1 уве.личивают на единицу, а разность А — 1

У меньшают на единицу и результаты одновременно делят на Р; и т.д. до тех пор, пока дробная часть частного ются числа, содержащие дробные части, отличные от нуля, то снова одновременно сумму увеличивают на единицу, а разность уменьшают на единицу и результаты одновременно делят на величину модуля и т.д. до тех пор, пока дробная часть частного от деления увеличенного или уменьшенного числа на величину модуля не будет равна нулю. Если дробная часть чястного от деления увеличенного числа на величину модуля равна нулю, то остаток равен разности величины модуля и числа увеличений, если уменьшенного числа, то остаток равен числу уменьшений. 1 ил. от деления увеличенного или уменьшенного Ак на Р не станет равна нулю.

Если дробная часть частного от деления увеличенного А на Р равна нулю, К 1 то а =Р; -rz, где го — число увеличений числа Ак, если уменьшенного АК, то ro=ак °

Введение третьего счетчика обеспе- .: чивает формирование значения а к при

А > Ак. Введение четвертого счетчика обеспечивает запись числа А и формирование величин АК+1, Ак+2,...,АК+Гь

Второй блок определения кратности чисел обеспечивает проверку на кратность чисел А +i модулю Р . Второй к 1 элемент ИЛИ предназначен для объединения выходных сигналов блоков опре,деления кратности чисел, Коммутатор предназначен для выдачи через него кода остатка в зависимости от того, на каком счетчике (втором или третьем) он сформирован.

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

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

11одуль Р,, ио которому необходимо сформировать остаток заданного числа АК, задается параллельным двоичным кодом, подаваемым на входы параллельной записи регистра 3 и счетчика 10. Этот параллельный двоичный код чиспенно равеч значению задаваемого модуля. На входы параллельной записи счетчиков 1 и 13 воздействует двоичный код числа Ак. Сигнал запуска обнуляет счетчик 2, переключает в исходное состояние коммутатор 12, при котором ни один из его входов не скоммутирован на выход, а также обеспечивает запись двоичного кода числа

А в счетчики 1. и 13 и двоичного коК да модуля в регистр 3 и счетчик 10.

В результате на выходах счетчиков 1 и 13 образуются параллельные двоичные коды единиц и нулей числя А, а на выходах регистра 3 и счетчика 10параллельные двоичные коды модуля.

Эти коды с выходов счетчиков 1 и 13 и- регистра 3 поступают на входы блоков 6 и 14 определения кратности чисел ° Одновременно сигнал запуска через первый элемент ИЛИ 5 поступает на вход элемента 8 задержки. Если число А„ делится на модуль Р; нацело, то на выходах блоков 6 и 14 определения кратности чисел появляются единичные потенциалы, которые объединяются на элементе ИЛИ 9, и единичный потенциал воздействует ня управляющий вход элемента 7 запрета и первый вход элемента И 5. Сигналы с выходов блоков 6 и 14 определения кратности чисел поступают также на элемент 11 запрета, который под действием единичного потенциала, поступающего на

его управляющий вход, размыкается, поэтому единичный потенциал только с выхода блока 6 определения кратности чисел поступает на второй управляющий вход коммутатора 12, под воздействием которого выход счетчика 2 коммутируется на выход устройства °

Одновременно на вторые входы элемента И 5 и элемента 7 запрета с элемента 8 задержки, причем величина задержки равна длительности переходных процессов в счетчике 1 (регистре 3) и в блоке 6 определения кратности чисел, поступает единичный импульс сигнала запуска, за счет чего сраба тывает элемент И 4, сигнал с выхода которого свидетельствует о том, что на выходе счетчика 2 сформирован ос80561

35 пока одно не стянет м Ак+г=ОпойР, . блока 14 по40 который чепает нл пери запрета 7. элемента 8

55

S !

О !

30 таток а =OmonP Код остатка с выходов счетчика 2 череэ коммутатор 12 снимается на выход устройства.

Если числo А не кратно модулю

Р;, то IIB выходах блсков 6 и !4 остаются нулевые потенциаль., поэтому с появлением импульса па объединенных вторых входах элемента 11 4 и элемента 7 запретя с выхода элемента

8 задержки срабатывает элемент 7 запретя, так как нл его управляющий вход поступает нулевой потенциал с выхода второго элемента 1!ЛИ 9. Импульсohl с вькодя эле .ентя 7 запретя записывается единица в счет шк ?, вычитается единица из содержимого счетчиков 1 и 10 !! прибавляется едпница к содержимому счетчика 13. Одновременно через элемент 11!1И импульс поступает на вход элемента Я задержки. Теперь блок 6 про,звод :т проверку ня кратность чт.слл Ак — 1, л блок ! 4 — числя A +1 мо iy!!!л I ° Если ии

l одно из них не кратно модулю, то сНОвл нл вькоде элемс нт; ИЛ1! 9 оо! àåòñÿ нулевой потенциал, поэтому импульс с выходя элемента 8 задержки заставляет сработать !! eh!oнт 7 запрета, и импульс с его вькодл обеспечивает запись второй е плицы в счетчики 2 и

13 и вычитание второй единицы из содержимого счетчиков 1 и 10. Злтем производится проверка ня кратность чисел А,--2 и А +2 модулю Р; .

Работа устройства в таком режиме продолжается до тех пор из чисел АК-1 иш А..+г

К кратным модулю. Допусти

В этом случае на вькоде явится единичный сигнал рез элемент 1Е1И 9 посту вые входы элементов И 4

Поэтому сигнал с выхода задержки, поступая на вторые их входы, обеспечивает срабатывание элемента И 4, на выходе которого появляется сигнал окончания процесса формирования остатка. Остаток от числа А < по выбранному модулю, численно равный

Р, -r, с выхода счетчика 10 через коммутатор 12, срабатывающий под воздействием управляющего сш нала, поступившего на первый его вход через элемент 11запрета с выхода блока 14, поступает на выход устройства и остается на его выходах до тех пор, пока на информационные входы устройства не поступит следующее число А> 1, от

1580561 которого необходимо сформировать остаток по модулю Р .

Е и А1-r=OmodP. то на выходе блока 6 появляется сигнал логической единицы, поэтому управляющий сигнал

5 появляется на втором входе коммутатора,12, на информационные выходы устройства скоммутированы информационные выходы счетчика 2. Остаток от. числа А по выбранному модулю P, численно равной r, поступает на вы ход устройства.

Если значение модуля четко, а a -=

=Р; /2, то. сигналы логической едини- 15 цы на выходах блоков 6 и 14 появляются одновременно, но так как под действием поступающего на его управляющий вход сигнала элемент 11 запрета размыкается то на выход устройст- 20 ва скоммутируется содержимое счетчика 2. При формировании остатка от числа А,, по модулю Р работа элементов и блоков устройства осуществляется аналогично,.

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

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

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

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

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