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

 

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

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

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

РЕСПУБЛИК (51) 4 Н 03 М 7/18

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

Н А ВТОРСНОМУ СВИД=ТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4387633/24-24 (22) 02.03.88 (46) О?.11.89. Бюл. У 41 (72) Л.С. Сорока, А,Ф. Чилига, В.И. Петренко и В.А, Краснобаев (53) 681.3 (088.8),(56) Авторское свидетельство СССР

В 1270774, кл. G 06 F 11/08, 1984.

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

Р 1105895, кл. G 06 F 1 1/08, 1983. (54) УСТРОИСТВО ДЛЯ ФОРМИРОВАНИЯ OCТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ

ЧИСЛА (57) Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах. Цель изобретения — повы»яи ц2йц37 А1

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

10 и дешифратора 11, регистр 3, элемент 4 запрета, элемент И 5, элемент 6 задержки и элемент ИЛИ 8 с соответствующими связями. 1 з.п. ф-лы, 1 ил.

1520667

У ) X„X X)Õ Õ е е Х„VX(Õ Х Х Хгл

Х Х Х Х Х ° ° ° Х 7 Х Х Х Х е е е

Х„„7 ° ° .Ф

1 где ш — разрядность счетчика 1;

1-. и.

Устройство работает следукнцим образом.

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

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

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

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

9 -9„ (п — количество значений модуля), элемент И-ИЛИ 10 и дешифратор 11.

Сущность изобретения состоит в Zp том, что число А делят на величину модуля Р, а затем определяют равна

1 ли нулю дробная часть частного. Если результат деления содержит дробную часть, отличную от нуля, то вели- 25 чину числа Л уменьшают на единицу и результат делят на P ° . Если снова получается число, содержащее дробную часть, отличную от нуля, снова уменьшают разность А — 1 на единицу и резул:ьтат делят на Р; и так далее до тех пор, пока дробная часть частного от деления уменьшенного А на

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

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

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

Сигнал запуска обнуляет счетчик 7, обеспечивает запись двоичного кода числа А, в счетчик 1, а двоичного кода модуля Р; — в регистр 3. В результате на выходе счетчика 1 образуется параллельный двоичный код единиц и нулей числа А, а на выходе регистра 3 — параллельный двоичный код модуля. Эти коды поступают на входы блока 2 определения кратности чисел. Одновременно сигнал запуска через элемент ИЛИ 8 поступает на вход элемента 6 задержки. Код модуля, поступая на входы дешифратора

ll, дешифрируется на нем, и на одном из выходов дешифратора, однозначно

Соответствующем коду модуля, появляется сигнал "l". Одновременно код числа А поступает на объединенные входы матриц 9. Если число А делится на модуль Р.; нацело, то на выходе соответствующей матрицы 9, реализующей функцию определения кратности по заданному модулю, появляется единичный потенциал, который через элемент

И-ИЛИ 10 поступает на выход блока

2 определения кратности чисел и воздействует на управляющий вход элемента 4 запрета и первый вход элемента И 5. Одновременно на вторые входы элементоз 4 запрета и первый вход элемента И 5 с. элемента 6 задержки (величина задержки равна длительности переходных процессов в счетчике

1 (регистре 3} и в блоке 2 определения кратности чисел) поступает единичный импульс сигнала запуска, за счет чего срабатывает элемент И 5, сигнал с выхода которого свидетельствует о том, что на выходе счетчика 7 сформирован остаток а а0/шодР; (.

Код остатка сб счетчика 7 снимается на выход устройства.

Если число А, делится на модуль

Р,; с остатком, то на выходе матрицы 9 остается нулевой потенциал, который поступает на выход блока 2.

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

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

Импульсом .с выхода элемента 4 запрета записывается единица в счетчик 7, а также вычитается единица из счетчика l в котором в двоичном коде было записано число А . Одновременно через элемент ИЛИ 8 импульс посту- 15 пает на вход элемента 6 задержки.

Теперь блок 2 производит проверку на кратность числа Ак- 1 модулю. Если число А — 1 снова не кратно модулю, то снова на выходе блока 2 остается нулевой потенциал, поэтому импульс с выхода элемента 6 задержки заставляет сработать элемент 4 зап рета и импульс с его выхода обеспечивает запись второй единицы в счет- 25 чик 7 и вычитание второй единицы из числа А„. Теперь производится проверка на кратность числа А„-2 модулю.

Работа устройства в таком режиме продолжается до тех пор, пока 30 число А»- г не станет кратным модулю.

В этом случае на выходе матрицы 9 появляется сигнал "1", который через элемент И-ИЛИ 10 поступает на выход блока 2 ° Поэтому сигнал с выхода элемента 6 задержки, поступающий на вторые входы элементов 4 запрета и И 5, обеспечивает срабатывание элемента

И 5, на выходе которого появляется сигнал окончания процесса формирова- 40 ния остатка, а остаток от числа Ак. по выбранному модулю, численно равный r, с выхода счетчика 7 поступает на выход устройства и остается на его выходах до тех пор, пока на ин- 4> формационные входы счетчика 1 не поступит следующее число А к+, от которого необходимо сформировать остаток по модулю Р . Работа устройства при

3 этом происходит аналогично описанно50 му.

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

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

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

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