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

сд

00 со

ел Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных уст ройствах. Известно устройство для выделения остатка по переменному модулю, содер жащее два регистра, два дешифратора, коммутатор и шифратор ij. Недостатком этого устройства явля ется большой объем оборудования. Наиболее близким к предлагаемому является устройство для вычисления остатка по модулю от числа, содержащее счетчик, регистр и формирователь остатков, в состав которого входят три триггера, группа элементов И и группа элементов ИЛИ, причем счетный и тактовый входы счетчика являются соответственно управляющим и тактовым входами устройства, выход счетчи ка соединен с первым входом формирователя остатков, выход которого соединен с информационным входом регистра, выход которого соединен со вторым входом формирователя остатков, третий вход которого является информационным входом устройства, тактовый и управляющий входы регистра соединены соответственно с тактовым и управляющим входами счетчикаГз Недостатком этого устройства также является большой объем оборудования, при большом коде модуля. Цель изобретения - сокращение объема оборудования. Поставленная цель достигается тем что устройство для формирования остатка по произвольному модулю от чис ла, содержащее первый счетчик, элемент И, элемент ИЛИ, причем входы пе вого счетчика являются информационными входами, устройства, содержит также генератор тактовых импульсов, второй счетчик, группу сумматоров по модулю два, элемент ИЛИ-НЕ и два фор мирователя импульсов, причем выход генератора тактовых импульсов соединен с первнм входом элемента И, выход которого соединен со счетными входами первого и второго счетчиков, выхо ды первого счетчика соединены со вхо дам-и элемента ИЛИ, выход которого соединен со вторым входом элемента И и входом первого формиро-вателя импульсов, выход которого соединен с первым установочным входом второго счетчика, выходы которого являются выходами устройства и соединены с пе выми входами соответствующихсумматоров по модулю два группы, вторые входы которых являются входами кода модуля устройства, выходы сумматоров по модулю два группы соединены со входами элемента ИЛИ-НЕ, выход которого через второй формирователь импульсов соединен со вторым установоч ным входом второго счетчика. На чертеже схематически изображено устройство для формирования остатка по произвольному модулю от числа. Устройство содержит первый счетчик 1, элемент ИЛр 2, генератор 3 тактовых импульсов, элемент И 4, первый формирователь 5 импульсов, второй счетчик б, элемент ИЛИ-НЕ 7, группу 8 сумматоров по модулю два, второй формирователь 9 импульсов. Принцип работы устройства для формиров.ания остатка по произвольному модулю от числа заключается в реализации следующей идеи приведения по модулям любых чисел. Из некоторого числа А, поступающего на информационные входы устройства, вычитается с раз выбранный модуль , до тех пор, пока остаток разности а , не станет меньше или равным модулю , т.е. .P. ,- . При этом равенство остатка а, модулю Р означает тождественное равенство нулю числа А, т.е. А () 0fmod Р ). Устройство для формирования остатка по произвольному модулю от числа работает следующим образом. Первый счетчик 1 является вычитающим счетчиком. В исходном состоянии счетчик 1 находится в нулевом состоянии, генератор 3 тактовых импульсов формирует последовательность тактовых импульсов. Модуль Р- , по которему осуществляется формирование остатков любых чисел, задается параллельным двоичным кодом, подаваемым на входы кода модуля устройства. Данный параллельный двоичный код численно равен значению задаваемого модуля. На информационные входы устройства поступает число в параллельном двоичном коде. Двоичный код числа А , записывается на первый счетчик 1. В результате на выходе счетчика 1 образуется тоже параллельный двоичный код единиц и нулей числа А ц, который поступает на входы элемента ИЛИ 2, образуя на его выходе единичный потенциал, который открывает элемент И 4 и также поступает на вход первого формирователя 5 импульсов, на выходе которого формируется единичный импульс, поступающий на первый установочный вход второго счетчика б. Счетчик 6 обнуляется. Через открытый элемент И 4 тактовые импульсы от генератора 3 поступают на счетньой вход счетчика 1 и на счетный вход счетчика б. Последний осуществляет суммирование поступившего на его вход количества тактовых импульсов. Суммирование осуществляется до тех пор, пока на выходах счетчика б не образуется число в двоичном коде,численно равное выбранному модулю Р| и воздействующее на первые входы сумматоров по модулю

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

В течение этого времени хотя бы

ч

на одном .из выходов сумматоров группы 8 будет единичный потенциал. Следовательно, на выходе элемента ИЛИНЕ 7 .будет нулевой потенциал. Как счетчик б сосчитает количество тактовых импульсов, равных выбранному модулю Р-, опять происходит его обнуление. Такая операция происходит до тех пор, пока не обнуляется счетчик 1. А обнуление последнего произойдет в случае, когда количество поступивших на его второй вход, тактовых импульсов . будет численно равно числу Ац, записанному в счетчике 1 s двоичном коде, в результате

чего на выходе элемента ИЛИ 2 возни кает нулевой потенциал, элемент И 4 закрывается и тактовая последовательность перестает пост пать на входы счетчиков 1 и б. Поэтому на выходах счетчика6 остается остаток а числа А по выбранному модулю Р,- , численно равный a.f AV- ч- Ai , где ч,0, 1 ч

-L f « ««

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

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

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

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