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

СО 1 ОЭ СО 8 ЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИН ЯО 105895 А 35 П 0 06 Р 11/08 1ОПИСАНИЕ ИЗОБРЕТЕНИЯ и К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ в дфкф ГОСУДАРСТ 8 ЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1. Авторское свидетельство СССРР 928359, кл. С 06 Р 11/08, 1980,2. Авторское свидетельство СССРи 407313, кл. С 06 Р 11/08, 1971(54) (57) УСТРОИСТВО ДЛЯ ФОРМИРОВАНИЯОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТЧИСЛА, содержащее первый счетчик,элемент И, элемент ИЛИ, причем входыпервого счетчика являются информационными входами устройства, о т л ичающее с я тем, что, с цельюсокращения оборудования, оно содержит генератор тактовых импульсов,второй счетчик, группу сумматоров помодулю два, элемент ИЛИ-НЕ и два формирователя импульсов, причем выход генератора тактовых импульсов соединен с первым входом элемента И, выход которого соединен со счетными входами первого и второго счетчиков, выходы первого счетчика соединены со входами элемента ИЛИ, выход которого соединен со вторым входом элемента И и входом первого формирователя импульсов, выход которого соединен с первым установочным входом второго счетчика, выходы которого являются выходами устройства и соединены с первыми входами соответствующих сумматоров по модулю два группы, вторые входы которых являются входами кода модуля устройства, выходы сумматоров Е по модулю два группы соединены со входами элемента ИЛИ-НЕ, выход которого через второй формирователь импульсов соединен со вторым установочным входом второго счетчика.Изобретение относится к вычислительной технике и может быть исполь"зовано в цифровых вычислительных устройствах.Известно устройство для выделенияостатка по переменному модулю, содержащее два регистра, два дешифратора,коммутатор и шифратор 1 г,Недостатком этого устройстна является большой объем оборудования.Наиболее близким к предлагаемомуявляется устройство для вычисленияостатка по модулю от числа, содержа"щее счетчик, регистр и формировательостатков, в состав которого входяттри триггера, группа элементов И и 15группа элементов ИЛИ, причем счетныйи тактовый входы счетчика являютсясоответственно управляющим и тактовым входами устройства, выход счетчика соединен с первым входом формирователя остатков, выход которого соединен с информационным входом регистра, выход которого соединен совторым входом формирователя остатков, третий вход которого является 25информационным входом устройства,тактовый и управляющий входы регистра соединены соответственно с тактовым и управляющим входами счетчика 23.Недостатком этого устройства также является большой объем оборудования при большом коде модуля.Цель изобретения - сокращение объема оборудования.Поставленная цель достигается тем, 31 что устройство для формирования ос" татка по произвольному модулю от числа, содержащее первый счетчик, элемент И, элемент ИЛИ, причем входы первого счетчика являются информацион ными входами. устройства, содержит также генератор тактовых импульсов, второй счетчик, группу сумматоров по модулю два, элемент ИЛИ-НЕ и два формирователя импульсов, причем выход генератора тактовых импульсов соединен с первым входом элемента И, выход которого соединен со счетными входами первого и второго счетчиков, выходы первого счетчика соединены со входами элемента ИЛИ, выход которого соединен со вторым входом элемента И и входом первого формирователя импульсов, выход которого соединен с первым установочным входом второго счетчика, выходы которого являются выходами устройства и соединены с первыми входами соответствующих сумматоров по модулю дна группы, вторые входы которых являются входами кода модуля устройства, выходы сумматороь 60 по модулю два группы соединены со входами элемента ИЛИ-НЕ, выход кото" рого через второй формирователь импульсов соединен со вторым установочным входом второго счетчика. 65 На чертеже схематически изображено устройство для формирования остатка по произвольному модулю от числа,Устройство содержит первый счетчик 1, элемент ИЛИ 2, генератор 3тактовых импульсов, элемент И 4, первый формирователь 5 импульсов, второйсчетчик б, элемент ИЛИ-НЕ 7, группу 8 сумматоров по модулю два, второйформирователь 9 импульсов,Принцип работы Устройства для формирования остатка по произвольномумодулю Р от числа заключается в ре"ализации следующей идеи приведенияпо модулям любых чисел.Из некоторого числа А, поступающего на информационные входы устройства, вычитается 9, раз выбранный модуль Р, до тех пор, пока остатокразности ане станет меньше или равным модулю Р, т.е. Ак-Р, = ак-Р;При этом равенство остатка а модулюР; означает тождественное равенствонулю числа А, т,е, А= (а=Р;) ==ОГтпоа Р).Устройство для формирования остатка по произвольному модулю от числа работает следующим образом,Первый счетчик 1 является вычитающим счетчиком. В исходном состоянии счетчик 1 находится в нулевом состоянии, генератор 3 тактовых импульсов формирует последовательность тактовых импульсов, Модуль Р;, по которому осуществляется формирование остатков любых чисел, задается параллельным двоичным кодом, подаваемым на входы кода модуля устройства, Данный параллельный двоичный код численно равен значению задаваемого модуля. На информационные входы устройства поступает число н параллельном двоичном коде. Двоичный код числа Азаписывается на первый счетчик 1. В результате на выходе счетчика 1 образуется тоже параллельный двоичный код единиц и нулей числа А, который поступает на входы элемейта ИЛИ 2, образуя на его ныходе единичный потенциал, который открывает элемент И 4 и также поступает на вход первого формирователя 5 импульсов, на выходе которого формируется единичный импульс, поступающий на первый установочный вход второго счетчика б. Счетчик б обнуляется. Через открытый элемент И 4 тактовые импульсы от генератора 3 поступают на счетный вход счетчика 1 и на счетный вход счетчика б. Последний осуществляет суммирование поступившего на его нход количества тактовых импульсов. Суммирование осуществляется до тех пор, пока на выходах счетчика б не образуется число в двоичном коде, численно равное выбранному модулю Р и воздействующее на первые входы сумматоров по модулю1105895 Составитель В.ГречневРедактор С.Тимохина Техред М. Надь КорректорВ.Гирняк Зака 5603/39 Тираж 699 ПодписноеВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж 35, Раушская наб., д. 4/5 Филиал ППП "Патент", г.ужгород, ул.Проектная, 4 два группы 8, выполняющих операциюравнозначности. На вторые же входыэтих сумматоров воздействует (в течение времени формирования остатка)двоичный код выбранного модуля Р,(в параллельном коде 1. В результатена выходе каждого сумматора по иоду-.лю два группы 8 оказываются нулевыепотенциалы, которые воздействуют навходы элемента ИЛИ-НЕ 7. На выходепоследнего образуется единичный потенциал, который через второй формирователь 9 импульсов обнуляет счетчик б и подсчет тактовых импульсовначинается заново, т.е. на первыевходы сумматоров по модулю два группы 8 воздействуют в параллельномкоде двоичные коды чисел от "1" доР. В течение этого времени хотя бына одном .из выходов сумматоров группы 8 будет единичный потенциал. Следовательно, на выходе элемента ИЛИНЕ 7 .будет нулевой потенциал. Кактолько счетчик б сосчитает количество тактовых импульсов, равных выбранному модулю Р;, опять происходит егообнуление. Такая операция происходитдо тех пор, пока не обнуляется счетчик 1. А обнуление последнего произойдет в том случае, когда количество поступивших на его второй вход 30тактовых импульсов будет численноравно числу Ак, записанному в счетчике 1 в двоичном коде, в результате чего на выходе элемента ИЛИ 2 возникает нулевой потенциал, элемент И 4 закрывается и тактовая последовательность перестает поступать на входы счетчиков 1 и б. Поэтому на выходах счетчикаб остается остаток а чиск ла Апо выбранному модулю Р; , численно равный а = А- Ч, А;, где =О, 1, 2, 3В результате на выходах устройства сформировывается остаток а от числа Ьпо выбранному модулю Р1 и остаток ак остается на выходах устройства до тех пор, пока наинформа" ционные входы устройства не поступает следующее число В, от которого необходимо сформировать остаток по выбранному модулю Р;Работа устройства при этом происходит аналогичным образом. Выбор модуля Р, по которому необходимо сформировать остаток от числа, происходит путем подачи этого модуля Р в двоичном коде на входы кода модуля устройства 1 т.е. на вторые входы сумматоров группы 8) в течение времени формирования остатка. Время формирования остатка определяется абсолютным значением числа АК.1Таким образом, предложенное устройство позволяет без увеличения и усложения оборудования формировать остатки чисел по любому простому мо" дулю Р; .