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

Abstract

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

Description

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

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

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

Устройство содержит первый 1 и второй 2 счетчики, регистр 3, элемент И 4, первьй элемент ИЛИ 5, первый блок 6 определени  кратности чисел, первьй элемент 7 запрета, элемент 8 задержки , второй элемент ИЛИ 9, третий счет

чик 10, второй элемент 11 запрета, коммутатор 12, четвертый счетчик 13 и второй блок 14 определени  кратности чисел.

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

0

5

5

0

5

от делени  увеличенного или уменьшенного А на PJ не станет равна нулю. Если дробна  часть частного от делени  увеличенного А на Р(- равна нулю, то ,-г0, где rQ - число увеличений числа Ак, если уменьшенного А., то .

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

-k

А А«. Введение четвертого счетчика обеспечивает запись числа Ак и формирование величин Ац+1, Ак+2, . . . ,AK+rb .

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

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

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

51

Модуль Р , но которому необходимо сформировать остаток заданного числа Ац, задаетс  параллельным двоичным кодом, подаваемым на входы параллельной записи регистра 3 и счетчика 10. Этот параллельный двоичный код численно равен значению задаваемого модул . На входы параллельной записи счетчиков 1 и 13 воздействует двоичный код числа АК. Сигнал запуска обнул ет счетчик 2, переключает в исходное состо ние коммутатор 12, при котором ни один из его входов не скоммутирован на выход, а также обеспечивает запись двоичного кода числа Ак в счетчики 1 и 13 и двоичного кода модул  в регистр 3 и счетчик 10. В результате на выходах счетчиков 1 и 13 образуютс  параллельные двоичные коды единиц и нулей числа Ak, a на выходах регистра 3 и счетчика 10- параллельные двоичные коды модул . Эти коды с выходов счетчиков 1 и И и- регистра 3 поступают на входы блоков 6 и 14 определени  кратности чисел . Одновременно сигнал запуска через первый элемент ИЛИ 5 поступает на вход элемента 8 задержки. Если число А делитс  на модуль Р; нацело, то на выходах блоков 6 и 14 определени  кратности чисел по вл ютс  единичные потенциалы, которые объедин ютс  на элементе ИЛИ 9, и единичный потенциал воздействует на управл ющий вход элемента 7 запрета и первый вход элемента И 5. Сигналы с выходов блоков 6 и 14 определени  кратности чисел поступают также на элемент i1 запрета, который под действием единичного потенциала, поступающего на его управл ющий вход, размыкаетс , поэтому единичный потенциал только с выхода блока 6 определени  кратности чисел поступает на второй управл ющий вход коммутатора 12, под воздействием которого выход счетчика 2 ком мутируетс  на выход устройства.

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

таток ак ОтооР . Кед остатка с выходов счетчика 2 через коммутатор |2 снимаетс  на выход устройства. Если число А,, не кратно модулю

Р-, то на выходах блсгов 6 и 4 остаютс  нулевые потенциала, поэтому с по влением импульса на объединенных вторых входах элемента 11 4 ц (О элемента 7 запрета с выхода элемента 8 задержки ср батпвает элемент 7 запрета , так как на его управл ющий вход поступает нулевой потенциал с выхода второго элемента ИЛИ 9. Нм )5 пульсом с выхода элемента 7 запрета

записываетс  единица в счетчик 2, вычитаетс  единица из содер/шмох о счетчиков 1 и 10 и прибавл етс  единица к содержимому счетчика 13. Одно20 временно через элемент ИЛИ импучьс поступает на вход элемента 8 задерл- ки. Теперь блок 6 производит проверку кратность числа , л блок 14 - числа А +1 модулю . Если пи

25 одно из них не кратно модулю, то снова на выходе элемента ИЛИ 9 остаетс  нулевой потенциал, поэтому импульс с выхода элемента 8 задержки заставл ет сработать элемент 7 запрета, н

30 импульс с его выхода обеспечивает запись второй единицы в счетчики 2 и 13 и вычитание второй единицы из содержимого счетчиков 1 и 10. Затем производитс  проверка на кратность

js чисел Ак--2 и А),+ 2 модулю Р .

Работа устройства в таком режиме продолжаетс  до тех пор, пока одно

из чисел Аь-г или А +г не станет

кратным модулю. Допустим AK, + r OiucidPj .

40 В этом случае на выходе блока 14 по витс  единичный сигнал, который через элемент ИЛИ 9 поступает на первые входы элементов И 4 и запрета 7. Поэтому сигнал с выхода элемента 8

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

50 выбранному модулю, численно равный

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

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

Если A -r OmodP, , то на выходе блока 6 по вл етс  сигнал логической единицы, поэтому управл ющий сигнал по вл етс  на втором входе коммутатора 12, на информационные выходы устройства скоммутированы мнформаци- онные выходы счетчика 2. Остаток от. числа А к по выбранному модулю Р; , численно равной г, поступает на выход устройства.

Если значение модул  четно, а ак Р|/2, то сигналы логической единицы на выходах блоков 6 и 1А по вл ютс  одновременно, но так как под действием поступающего на его управл ющий вход сигнала элемент 11 запрета размыкаетс j то на выход устройства скоммутируетс  содержимое счетчика 2. При формировании остатка от числа АК + , по модулю Р: работа элементов и блоков устройства осуществл етс  аналогично.

10

15

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

20

25

Claims (1)

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

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

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