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

(5 СР84. тельство Р 11/08, льство С Р 11/08, ФОРМИРОВ МУ МОДУЛЮ 983.ИЯ ОСОТ(57) Изобрлительнойпользованоустройства чистение относится к ехнике и может быт в цифровых вычислиЦель изобретения ис- льных пов ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБР,(56) Авторское свид В 120774, кл. О 06Авторское свидет У 1105895, кл. О 06 (54) УСТРОЙСТВО ДЛЯ ТАТКА ПО ПРОИЗВОЛЬНЧИСЛА 2шение быстродействия. Цель достигае ся тем, что остаток формируют как величину, равную количеству уменьше ний на единицу величины числа, от которого необходимо вычислить остаток по заданному модулю, причем уменьшение производят до тех пор, п ка отношение величины, получаемой в результате уменьшения, к величине модуля не станет целым числом. Устройство содержит счетчики 1 и 7, блок 2 определения кратности чисел, состоящий из группы программируемых логических матриц 9, элемента И-ИЛИ 10 и дешифратора 11, регистр 3, элемент 4 запрета, элемент И 5, элемент 6 задержки и элемент ИЛИ 8 с соответствующими связями. 1 з.п.ф-лы, 1 ил.40 У- ХХХ Х, Х е е Х ЧХ Х Х Х Х- еХ 7Х ХХХХ 5Х 7 Х ХХХеХ 7вгде ш - разрядность счетчика 1;1-. и.Устройство работает следукцимобразом,Модуль Р , по которому необходимо сформировать остаток заданного числа, задается параллельным двоичным Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах,5Целью изобретения является повышение быстродействия,На чертеже представлена схема устройства для формирования остатка попроизвольному модулю от числа. ОУстройство содержит первый счетчик 1, блок 2 определения кратности чисел, регистр 3, элемент 4 запрета, элемент И 5, элемент б задержки,второй счетчик 7, элемент ИЛИ 8, атакже в блоке 2 определения кратности чисеп группу логических модулей9-9 (п - количество значений модуля), элемент И-ИЛИ 1 О и дешифратор 11.Сущность изобретения состоит в 20том, что число А делят на величинумодуля Р , а затем определяют равнали нулю дробная часть частного. Если результат деления содержит дробную часть, отличную от нуля, то величину числа Л уменьшают на единицу ирезультат делят на Р , Если сноваполучается число, содержащее дробную часть, отличную от нуля, сновауменьшают разность А -1 на единицуи резул:ьтат делят на Р;и так далеедо тех пор, пока дробная часть частного от деления уменьшенного АнаР; не будет равна нулю. В этом случае количество уменьшений числа Аравно остатку А.Разрядность логических матриц 9равна разрядности счетчика 1. Каждая логическая матрица 9,:реализуетфункцию определения кратности числа А своему заданному модулю Р;,Например, если матрица 9; реализуетфункцию определения кратности по модулю три, то алгоритм ее функциони"рования описывается выражением кодом, подаваемым на входы параллельной записи регистра 3. Этот параллельный двоичный код численно равен значению задаваемого модуля, На входы счетчика 1 воздействует двоичный код числа Ак в параллельном коде. Сигнал запуска обнуляет счетчик 7, обеспечивает запись двоичного кода числа А, в счетчик 1, а двоичного кода модуля Р; - в регистр 3. В результате на выходе счетчика 1 образуется параллельный двоичный код единиц и нулей числа Ак, а на выходе регистра 3 - параллельный двоичный код модуля. Эти коды поступают на входы блока 2 определения кратности чисел. Одновременно сигнал запуска через элемент ИЛИ 8 поступает на вход элемента 6 задержки. Код модуля, поступая на входы дешифратора 11, дешифрируется на нем, и на одном из выходов дешифратора, однозначно Соответствующем коду модуля, появляется сигнал , Одновременно код числа Апоступает на объединенные входы матриц 9. Если число А делится на модуль Р.; нацело, то на выходе соответствующей матрицы 9, реализующей функцию определения кратности по заданному модулю, появляется единичный потенциал, который через элемент И-ИЛИ 1 С поступает на выход блока 2 определения кратности чисел и воздействует на управляющий вход элемента 4 запрета и первый вход элемента И 5, Одновременно на вторые входы элементоз 4 запрета и первый вход элемента И 5 с. элемента 6 задержки (величина задержки равна длительности переходных процессов в счетчике 1 (регистре 3) и в блоке 2 определения кратности чисел) поступает единичный импульс сигнала запуска, за счет чего срабатывает элемент И 5, сигнал с выхода которого свидетельствует о том, что на выходе счетчика 7 сформирован остаток а аО/шодР; . Код остатка сб счетчика 7 снимается на выход устройства.Если число А, делится на модуль Р,; с остатком, то на выходе матрицы 9 остается нулевой потенциал, который поступает на выход блока 2. Сигналы с других матриц 9, реализующих функцию определения кратности для других модулей и оказавшихся кратным числу А, на выход блока 2 не проходят, так как только на одномвыходе дешифратора 11 присутствуетединичньи потенциал, Поэтому с появ - пением импульса на объединенных вторых входах элементов 4 запрета и И 5с выхода элемента 6 задержки срабатывает элемент 4 запрета, так как на его управляющий вход поступаетнулевой потенциал с выхода блока 2.Импульсом .с выхода элемента 4 запрета записывается единица в счетчик 7,а также вычитается единица из счетчика 1, в котором в двоичном кодебыло записано число А. Одновременно через элемент ИЛИ 8 импульс посту пает на вход элемента 6 задержки. Теперь блок 2 производит проверку на кратность числа Ак модулю, Если число А - 1 снова не кратно модулю, то снова на выходе блока 2 остается нулевой потенциал, поэтому импульс с выхода элемента 6 задержки заставляет сработать элемент 4 запрета и импульс с его выхода обеспечивает запись второй единицы в счетчик 7 и вычитание второй единицы из числа А. Теперь производится проверка на кратность числа Амодулю,Работа устройства в таком режиме продолжается до тех пор, пока 30число А- г не станет кратным модулю,В этом случае на выходе матрицы 9появляется сигнал "1", который черезэлемент И-ИЛИ 10 поступает на выходблока 2Поэтому сигнал с выхода элемента 6 задержки, поступающий на вторые входы элементов 4 запрета и И 5, обеспечивает срабатывание элемента И 5, на выходе которого появляется сигнал окончания процесса формирова ния остатка, а остаток от числа Ак. по выбранному модулю, численно равный г, с выхода счетчика 7 поступает на выход устройства и остается на его выходах до тех пор, пока на ин формационные входы счетчика 1 не поступит следующее число Ак, от которого необходимо сформировать остаток по модулю Р. Работа устройства при3этом происходит аналогично описанно 50 му.Формула изобретения1. Устройство для формированид остатка по произвольному модулю от числа, содержащее первый и второй счетчики, регистр, элемент И и элемент1 ИЛИ, причем входы числа и модуля устройства соединены соответственно с информационными входами первого счетчика и регистра, входы разрешения записи которых и вход сброса второго счетчика соединены с входом запуска устройства, выход остатка которого соединен с выходом второго счетчика, суммирующий вход которого соединен с вычитающим входом первого счетчика, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит блок определения кратности чисел, элемент запрета и элемент задержки, причем выходы первого счетчика и регистра соединены соответственно с первым и вторым входами блока определения кратности числа, выход которого соединен с первым входом элемента И и с управляющим входом элемента запрета, выход которого соединен свычитающим входом первого счетчика и с первым входом элемента ИЛИ, второй вход и вывыход которого соединены соответствен" но с входом запуска устройства и с входом элемента задержки, выход которого соединен с информационным входом элемента запрета и с вторим входом элемента И, выход которого является выходом окончания работы устрой" ства,2, Устройство по п.1, о т л и - ча ю щ е е с я тем, что блок определения кратности чисел содержит группу логических модулей, элемент И-ИЛИ и дешифратор, причем первый вход блока определения кратности чисел соединен с входами логических модулей группы, выходы которых соедине-, ны с соответствующими входами первой группы элемента И-ИЛИ, выход которого является выходом блока определения кратности чисел, второй вход ко" торого соединен с входом дешифратора, выходы которого соединены с соответствующими входами второй группы элемента И-ИЛИ.