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

 

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА, содержащее первый счетчик, элемент и, элемент ИЛИ, причем входы первого счетчика являются информационными входами устройства, отличающееся тем, что, с целью сокращения оборудования, оно содержит генератор тактовых импульсов, второй счетчик, группу сумматоров по модулю два, элемент ИЛИ-НЕ и два формирователя и myльcoв, причем выход генератора тактовых импульсов соединен с первым входом элемента И, выход которого соединен со счетными входами первого и второго счетчиков, выходы первого счетчика соединены со входами элемента ИЛИ, выход которого соединен со вторым входом элемента И и входом первого формирователя импульсов , выход которого соединен с первым установочным входом второго счетчика, выходы которого являются выходами устройства и соединены с первыми входами соответствующих сумматоров по модулю два группы, вторые входы которых являются входами кода модуля устройства, выходы сумматоров по модулю два группы соединены со (Л входами элемента ИЛИ-НЕ, выход которого через второй формирователь импульсов соединен со вторым установочным входом второго счетчика.

СО10Э СОВЕТСНИХ

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

РЕСПУБЛИН

„„SU„„ l 105895 А

3(5П 0 06 11/08

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

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21 ) 3591038/18-24 (22) 11.05.83 (46 ) 30. 07. 84 . Бюл. 9 28 (72) И.И.Сныткин и В.И.Петренко (53) 681.3(088.8) (56) 1. Авторское свидетельство СССР

Р 928359, кл. G 06 F 11/08, 1980.

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

М 407313, кл. G 06 F 11/08, 1971 (прототип). (54 ) (57) УСТРОИСТВО ДЛЯ ФОРМИРОВАНИЯ

ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ

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

1105895

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

Известно устройство для выделения остатка по переменному модулю, содержащее два регистра, два дешифратора коммутатор и шифратор (1 1.

Недостатком этого устройстна является большой объем оборудования.

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

Недостатком этого устройства также является большой объем оборудования при большом коде модуля.

Цель изобретения — сокращение объема оборудования.

Поставленная цель достигается тем, 35 что устройство для формирования остатка по произвольному модулю от числа, содержащее первый счетчик, элемент И, элемент ИЛИ, причем входы первого счетчика являются информацион- QQ ными входами. устройства, содержит также генератор тактовых импульсов, второй счетчик, группу сумматоров по модулю два, элемент ИЛИ-HE и два формирователя импульсов, причем выход генератора тактовых импульсов соединен с первьм входом элемента И, выход которого соединен со счетными входами первого и второго счетчиков, выходы первого счетчика соединены со входами элемента ИЛИ, выход которого соединен со вторым входом элемента И и входом первого формирователя импульсов, выход которого соединен с первым установочным входом второго счетчика, выходы которого являются выходами устройства и соединены с первыми входами соответствующих сумматоров по модулю дна группы, вторые входы которых являются входами кода модуля устройства, выходы сумматороь 60 по модулю два группы соединены со входами элемента ИЛИ-НЕ, выход кото" рого через второй формирователь импульсов соединен со вторым установочным входом второго счетчика. 65

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

Принцип работы устройства для формирования остатка по произвольному модулю Р от числа заключается в реализации следующей идеи приведения по модулям любых чисел.

Из некоторого числа А, поступающего на информационные входы устройства, вычитается q, раз выбранный модуль Р„, до тех пор, пока остаток разности а не станет меньше или равным модулю Р„, т.е. А„- Р; = а <Р; °

При этом равенство остатка а модулю

Р; означает тождественное равенство нулю числа А„, т.е. Ak = (а„=Р;) -=

=0(mod P„).

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

Первый счетчик 1 является вычитающим счетчиком. В исходном состоянии счетчик 1 находится в нулевом состоянии, генератор 3 тактовых импульсов формирует последовательность тактовых импульсов. Модуль Р;, по которому осуществляется формирование остатков любых чисел, задается параллельным двоичным кодом, подаваемым на входы кода модуля устройства. Данный параллельный двоичный код численно равен значению задаваемого модуля.

На информационные входы устройства поступает число н параллельном двоичном коде. Двоичный код числа А записывается на первый счетчик 1. В результате на выходе счетчика 1 образуется тоже параллельный двоичный код единиц и нулей числа А, который поступает на входы элемейта ИЛИ 2, образуя на его ныходе единичный потенциал, который открывает элемент И 4 и также поступает на вход первого формирователя 5 импульсов, на выходе которого формируется единичный импульс, поступающий на первый установочный вход второго счетчика б. Счетчик б обнуляется. Через открытый элемент И 4 тактовые импульсы от генератора 3 поступают на счетный вход счетчика 1 и на счетный вход счетчика б.

Последний осуществляет суммирование поступившего на его нход количества тактовых импульсов. Суммирование осуществляется до тех пор, пока на выходах счетчика б не образуется число в двоичном коде, численно равное выбранному модулю Р. и воздействующее на первые входы сумматоров по модулю

1105895

Составитель В.Гречнев

Редактор С.Тимохина Техред М. Надь КорректорВ.Гирняк

Зака 5603/39 Тираж 699 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035 Москва, Ж«35, Раушская наб., д. 4/5

Филиал ППП "Патент", г.Ужгород, ул.Проектная, 4 два группы 8, выполняющих операцию равнозначности. На вторые же входы этих сумматоров воздействует (в течение времени формирования остатка) двоичный код выбранного модуля Р; (в параллельном коде ). В результате на выходе каждого сумматора по моду-. лю два группы 8 оказываются нулевые потенциалы, которые воздействуют на входы элемента ИЛИ-НЕ 7. На выходе последнего образуется единичный потенциал, который через второй формирователь 9 импульсов обнуляет счетчик б и подсчет тактовых импульсов начинается заново, т.е. на первые входы сумматоров по модулю два груп- 15 пы 8 воздействуют в параллельном коде двоичные коды чисел от "1" до

Р„. В течение этого времени хотя бы на одном .из выходов сумматоров группы 8 будет единичный потенциал. Сле- gp довательно, на выходе элемента ИЛИНЕ 7 .будет нулевой потенциал. Как только счетчик б сосчитает количество тактовых импульсов, равных выбранному модулю Р;, опять происходит его обнуление. Такая операция происходит до тех пор, пока не обнуляется счетчик 1. A обнуление последнего произойдет в том случае, когда количество поступивших на его второй вход 30 тактовых импульсов . будет численно равно числу А, записанному в счетчике 1 в двоичном коде, в результате чего на выходе элемента ИЛИ 2 возникает нулевой потенциал, элемент И 4 закрывается и тактовая последовательность перестает поступать на входы счетчиков 1 и б. Поэтому на выходах счетчика б остается остаток а чиск ла А „ по выбранному модулю Р;, численно равный а„ = А„- Ч, А;, где q=0, 1, 2, 3

В результате на выходах устройства сформировывается остаток а„ от числа Л „ по выбранному модулю Р

1 и остаток а остается на выходах уст» ройства до тех пор, пока на информа" ционные входы устройства не поступает следующее число В, от которого необходимо сформировать остаток по выбранному модулю Р; . Работа устройства при этом происходит аналогичным образом. Выбор модуля Р„-, по которому необходимо сформировать остаток от числа, происходит путем подачи этого модуля Р„ в двоичном коде на входы кода модуля устройства (т.е. на вторые входы сумматоров группы 8) в .течение времени формирования остатка.

Время формирования остатка определяется абсолютным значением числа АК.

Таким образом, предложенное устройство позволяет без увеличения и усложения оборудования формировать остатки чисел по любому простому модулю Р; .