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

а

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

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

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

Устройство содержит первый счетчик 1 , блок 2 определения кратности чисел, регистр 3, элемент 4 запрета, элемент И 5, элемент 6 задержки, второй счетчик 7, элемент ИЛИ 8, а - также в блоке 2 определения кратности чисел группу логических модулей (п - количество значений модуля), элемент И-1-ШИ 10 и дешифратор 11

Сущность изобретения состоит В том, что число Л делят на величину модуля Р , а затем определяют равна ли нулю дробная часть частного. Если результат деления содержит дробную часть, отличную от нуля, то вели

чину числа Л к уменьшают на единицу и реэуль:Тат делят на Р- . Если снова получается число, содержащее дроб-. ную часть , отличную от нуля, снова уменьшают разность на единицу и результат делят на и так далее до тёк пор, пока дробная часть част-

ного от деления уменьшенного А на Р; не будет равна нулю. В этом случае количество уменьшений числа А равно остатку А.

Разрядность логических матриц 9 равна разрядности счетчика 1. Каждая логическая матрица 9.: реализует функцию определения кратности чис- ла Ац своему заданному модулю Р,- . Например, если матрица 9,- реализует функцию определения кратности по модулю три, то алгоритм ее функционирования описывается выражением

i - л XijjX X Xj . . X(y,VX XjX jXjjXj...

Z X( .«. ,

xj...,

где m - разрядность счетчика 1; i Ifn.

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

Модуль Р, по которому необходим сформировать остаток заданного числа, задается параллельным двоичным

кодом, подаваемым на входы параллельной записи регистра 3. Этот параллельный двоичный код численно равен значению задаваемого модуля. На входы счетчика 1 воздействует двоичный код числа А в параллельном коде. Сигнал запуска обнуляет счетчик 7, обеспечивает запись двоичного кода числа AJ, в счетчик 1 , а двоичного кода модуля PJ - в регистр 3. В ре зультате на выходе счетчика I образуется параллельный двоичный код единиц и нулей числа А,, а на выходе регистра 3 - параллельный двоичньй код модуля. Эти коды поступают на входы блока 2 определения кратности чисел. Одновременно сигнал запуска через элемент ПТИ 8 поступает на вход элемента 6 задержки. Код модуля , поступая на входы дешифратора 13, дешифрируется на нем, и на одном из выходов дешифратора, однозначно соответствующем коду модуля, появляется сигнал I. Одновременно код

0

5

0

0

5

числа А| поступает на объединенные входы матриц 9. Если число А делится на модуль нацело, то на выходе соответствующей матрицы 9, реализующей функциго определения кратности по за,цанному модулю, появляется единичный потенциал, которьй через элемент И-1-ШИ 10 поступает на выход блока i 2 определения кратности чисел и воздействует на управляющий вход элемента 4 запрета и первый вход элемента И 5 Одновременно на вторые входы элементов 4 .запрета и первый вход элемента И 5 с. элемента 6 задержки (величина задержки равна длительности переходных процессов в c4eT4iiKe 1 (регистре 3) -и в блоке 2 опраделе-- ния кратности Щ1сел) поступает еди- ничньй -импульс сигнала запуска, за счет чего срабатывает элемент И 5, сигнал с выхода которого свидетельствует о том, что на выходе счетчика 7 :сформирован остаток a 0/modPj /. Код остатка сЬ счетчика 7 снимается на выход устройства.

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

выходе дешифратора 11 присутствует единичны потенциал. Поэтому с появлением импульса на объединенных вторых входах элементов 4 запрета и И 5 с выхода элемента 6 задержки срабатывает элемент А запрета, так как на его управляющий вход поступает нулевой потенциал с выхода блока 2. Импульсом .с выхода элемента 4 запрета записывается единица в счетчик 7, а также вычитается единица из счетчика 1, в котором в двоичном коде было записано число А|. Одновременно через элемент ИЛИ 8 импульс посту пает на вход элемента 6 задержки. Теперь блок 2 производит проверку на кратность числа 1 модулю, Ес ли число 1 снова не кратно модулю, то снова на выходе блока 2 остается нулевой потенциал, поэтому импульс с выхода элемента 6 задержки заставляет сработать элемент 4 зап- рета и импульс с его выхода обеспечивает запись второй единицы в счетчик 7 и вычитание второй единицы из числа А,, Теперь производится проверка на кратность числа Ау(-2 модулю

Работа устройства в таком режиме продолжается до тех пор, пока число At-- г не станет кратным модулю В этом случае на выходе матрицы 91 появляется сигнал 1, которьй через элемент H-HJUi 10 поступает на выход блока 2. Поэтому сигнал с выхода элемента 6 задержки, поступающий на вторые входы элементов 4 запрета и И 5, обеспечивает срабатывание элемента И 5, на выходе которого появляется сигнал окончания процесса формирования остатка, а остаток от числа Ак по выбранному модулю, численно равный г, с выхода счетчика 7 поступает на выход устройства и остается на его выходах до тех пор, пока на информационные входы счетчика 1 не поступит следующее число Ак4-н от которого необходимо сформировать остаток по модулю Р:. Работа устройства при этом происходит аналогично описанно,МУ.

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

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

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

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

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

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

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

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