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

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

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

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

Устройство содержит первый 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

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

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

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

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