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

СОЮЗ СОВЕТСИИХСОЦИАЛ ИОТИЧЕСНИХРЕСПУЬЛИИ 61 Н 03 М 7/1 ГОСУДАРСТВЕННЫЙ НОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТНРЬГТИПРИ ГКНТ СССР ОПИСАНИЕ ИЗОБРЕТЕН АВТОРСКОМУ СВИДЕТЕЛЬСТВУ 54) УСТРОЙСТ 30 ДЛЯ ФОР 1 ПРОВАНИЯ ОСАТЕЛ ПО РОИЗВОЬНОЮ 1 ОБУЛ 0 ОТ ЧСЛ У 2757) зобре вычислпние относитс ке и может б овых вычисли ыть испольтельных уст я - повыж ервый 3, элемент И э, первый бл ния кратно(5 б) Авторское свидет В 139 б 281, кл. Н 03 МАвторское свидетел по заявке Р 4387 б 33/2 кл, Н 03 М 7/18, 02.0 льство СССР 7/18, 1986. ство СССР -24,.88тельнои техн зсвано в цифр ройствах. Це ние быстродей введением в у ь изобретен ствия. Цель стройство, орой 2 счет 4, первый эк 6 определ остигаетсядержащееки, регистмент ИЛИ1580561 разом. ти, первый элемент 7 запрета и элемент 8 задержки, второго элементаИЛИ 9, третьего счетчика 10, второгоэлемента 11 запрета, коммутатора 12,четвертого счетчика 13 и второго блока 14 определения кратности чисел.Сущность изобретения заключается втом, что число делят на величину модулй, а затем определяют равна ли нулю дробная часть частного. Если ре" .зультат деления содержит дробнуючасть, отличную от нуля, то независимо друг от друга одновременно величину числа уменьшают и увеличива" 15ют на единицу и результаты делят навеличину модуля. Если снова получаИзобретение относится к вычислительной технике и может быть исполь зовано в цифровых вычислительных устройствах.Целью изобретения является повышение быстродействияНа чертеже представлена схема уст вройства для формирования остатка по произвольному модулю от числа.Устройство содержит первый 1 и второй 2 счетчики, регистр 3, элемент И 4, первый элемент ИЛИ 5, первый блок 6 определения кратности чисел, первый элемент 7 запрета, элемент 8 задержки, второй элемент ИЛИ 9, третий счетчик 10, второй элемент 11 запрета,40 коммутатор 12, четвертый счетчик 13 и второй блок 14 определения кратности чисел. Сущность изобретения состоит в том, что число Аделят на величину модуля Р а затем определяют, равна ли нулю дробная часть частного. Если результата деления содержит дробную часть, отличную от нуля, то независимо друг от друга одновременно величину числа Ак уменьшают и увеличивают на единицу и результаты делят на Р,. Если снова получаются числа, содержащие дробные части, отличные от нуля, то снова одновременно сумму А+1 уве.личивают на единицу, а разность А -1 У меньшают на единицу и результаты одновременно делят на Р; и т,д. до тех пор, пока дробная часть частного ются числа, содержащие дробные части,отличные от нуля, то снова одновременно сумму увеличивают на единицу,а разность уменьшают на единицу ирезультаты одновременно делят на величину модуля и т,д. до тех пор, пока дробная часть частного от деленияувеличенного или уменьшенного числана величину модуля не будет равнанулю. Если дробная часть чястного отделения увеличенного числа на величину модуля равна нулю, то остатокравен разности величины модуля и чис"ла увеличений, если уменьшенного числа, то остаток равен числу уменьшений. 1 ил. от деления увеличенного или уменьшенного Ак на Р не станет равна нулю. Если дробная часть частного от деления увеличенного А на Р равна нулю,К 1то а=Р; -г где го - число увеличений числа Ак, если уменьшенного Ак, то го =акВведение третьего счетчика обеспе-, чивает формирование значения а к при ААк. Введение четвертого счетчика обеспечивает запись числа А и формирование величин Ак+1, А+2, ,Ак+гВторой блок определения кратности чисел обеспечивает проверку на кратность чисел А + модулю Р . Второйкэлемент ИЛИ предназначен для объединения выходных сигналов блоков опре,деления кратности чисел, Коммутатор предназначен для выдачи через него кода остатка в зависимости от того, на каком счетчике (втором или третьем) он сформирован.Блоки 6 и 14 определения кратности чисел так же, как и в известном устройстве, реализованы на программируемых логических матрицах и реализуют функцию определения кратности чисел, поступающих на их входы. Они представляют собой дискретные устройства, алгоритм функционирования которых описывается скобочными формами логических функций, а быстродействие определяется быстродействием элементов И и ИЛИ, входящих в их состав.Устройство работает следующим об 5 1511 одуль Р ио которому необходимо сформировать остаток заданного числа Ак, задается параллельным двоичным кодом, подаваемым на входы параллельной записи регистра 3 и счетчика 10. Этот параллельный двоичный код чиспенно равеч значению задаваемого модуля. На входы параллельной записи счетчиков 1 и 13 воздействует двоичный код числа А. Сигнал запуска обнуляет счетчик 2, переключает в исходное состояние коммутатор 12, при котором ни один из его входов не скоммутирован на выход, а также обеспечивает запись двоичного кода числа А в счетчики 1. и 13 и двоичного коКда модуля в регистр 3 и счетчик 10. В результате на выходах счетчиков 1 и 13 образуются параллельные двоичные коды единиц и нулей числа А , а на выходах регистра 3 и счетчика 10 - параллельные двоичные коды модуля. Эти коды с выходов счетчиков 1 и 13 и регистра 3 поступают на входы блоков 6 и 14 определения кратности чисел, Одновременно сигнал запуска через первый элемент ИЛИ 5 поступает на вход элемента 8 задержки. Если число А делится на модуль Р; нацело, то на выходах блоков 6 и 14 определения кратности чисел появляются единичные потенциалы, которые объединяются на элементе ИЛИ 9, и единичный потенциал воздействует на управляющий вход элементазапрета и первый вход элемента И 5. Сигналы с выходов блоков 6 и 14 определения кратности чисел поступают также на элементзапрета, который под действием единичного потенциала, поступающего на его управляющий вход, размыкается, поэтому единичный потенциал только с выхода блока 6 определения кратности чисел поступает на второй управляющий вход коммутатора 12, под воздействием которого выход счетчика 2 коммутируется на выход устройстваОдновременно на вторые входы элемента И 5 и элемента 7 запрета с элемента 8 задержки, причем величина задержки равна длительности переходных процессов в счетчике 1 (регистре 3) и в блоке 6 определения кратности чисел, поступает единичный импульс сигнала запуска, за счет чего срабатывает элемент И 4, сигнал с выхода которого свидетельствует о том, что на выходе счетчика 2 сформирован ос 805616 пока одноне станети Ак+т=ОпойР; .блока 14 по 40 который чепает на пери запрета 7. элемента 8 45 50 5 О 5 20 25 30 таток а =ОшооР,; Код остатка с выходов счетчика 2 через коммутатор 12 снимается на выход устройства.Если чисго А не кратно модулю Р , то на выходах блсков 6 и 4 остаются нулевые потенциаль., поэтому с появлением импульса па объединенных вторых входах элемента 11 4 и элемента 7 запрета с выхода элемента 8 задержки срабатывает элемент 7 запрета, так как на его управляющий вход поступает нулевой потенциал с выхода второго элемента Ш 1 И 9. 11 л- пульсом с выхода элемента 7 запрета записывается едшшца в счетчик , вычитается единица из содержимого счетчиков 1 и 10 н прибавляется едпница к содержимому счетчика 13. Одно. временно через элемент ИЛИ импульс поступает на вход элемента Я задержки. Теперь блок б производит проверку на кратность числ А -1, а блок 4 - числа А +1 модулю 1, Если ии1одно из них не кратно модулю, то снова на выходе элемент ИЛ 9 остается нулевой потенциал, поэтому импульс с выхода элемента 8 задержки заставляет сработать элелент 7 запрета, и импульс с его выход обеспечивает запись второй единицы в счетчики 2 и 13 и вычитание второй единицы из содержимого счетчиков 1 и 10. Зател производится проверка на кратностьчисел А,"2 и А +2 модулю 1; .1 абота устройства в таком режиме продолжается до тех пор из чисел А,-г иш А,+г кратным модулю. опусти В этом случае на выходе явится единичный сигнал рез элемент 1 Е 1 И 9 посту вые входы элементов И 4 Поэтому сигнал с выхода задержки, поступая на вторые их входы, обеспечивает срабатывание элемента И 4, на выходе которого появляетсясигнал окончания процесса формирования остатка. Остаток от числа А к повыбранному модулю, численно равный Р,-г, с выхода счетчика 10 через коммутатор 12, срабатывающий под воздействием управляющего сш нала, поступившего на первый его вход через элемент 11 запрета с выхода блока 14, поступает на выход устройства и остается на его выходах до тех пор, покана информационные входы устройстване поступит следующее число А к, откоторого необходимо сформировать остаток по модулю Р; .Если А-г=ОшойР то на выходе блока 6 появляется сигнал логической единицы, поэтому управляющий сигнал5 появляется на втором входе коммутатора,12, на информационные выходы устройства скоммутированы информационные выходы счетчика 2. Остаток от, числа Ак по выбранному модулю Рчисленно равной г, поступает на вы-ход устройства.Если значение модуля четко, а а= =Р; /2, то. сигналы логической едини цы на выходах блоков 6 и 14 появляются одновременно, но так как под действием поступающего на его управляющий вход сигнала элемент 11 запрета размыкается 1 то на выход устройст ва скоммутируется содержимое счетчи- ка 2. При формировании остатка от числа Апо модулю Рработа элементов и блоков устройства осуществляется аналогично,.25формула из обретенияУстройство для формирования остат- ЗО ка по произвольному модулю от числа, содержащее первый и второй счетчики, регистр, элемент И, первый элемент ИЛИ, первый блок определения кратности чисел, первый элемент запрета и элемент задержки, причем входы числа и модуля устройства соединены соответственно с информационными входами первого счетчика и регистра, входы разрешения записи которых и вход 40 сброса второго счетчика соединены с входом запуска устройСтва, суммирующий вход второго счетчика соединен с вычитающим. входом первого счетчика, с выходом первого элемента запрета 45 и с первым входом первого элемента ИЛИ, выходы первого счетчика и регистра соединены соответственно с первым и вторым входами первого блока определения кратности чисел, второй 50 вход и выход первого элемента ИЛИ соединены соответственно с входом запуска устройства и с входом элемента задержки, выход которого соединен с информационным входом первого элемента запрета, управляющий вход которого соединен с первым входом элемента И, второй вход и выход которого соединены с выходом элемента задержки и с выходом окончания работы устройства соответственно о т л и ч а - ю щ е е с я тем, что, с целью повышения быстродействия, оно содержит нторой элемент ИЛИ, третий и четвер" тый счетчики, второй элемент запрета, коммутатор и второй блок определенияФ кратности чисел, причем выходы четвертого счетчика и регистра соединены соответственно с первым и нторым входами второго блока определения кратности чисел, информационный вход четвертого счетчика объединен с информационным входом первого счетчика, суммирующий вход четвертого счетччка соединен с вычитающим входом первого счетчика, вход разрешения записи четвертого счетчика соединен с входом запуска устройства, выход первого блока определения кратности чисел соединен с первым входом второго элемента ИЛИ, с управляющим входом второго элемента запрета, выход которого соединен с первым управляющим входом коммутатора, второй управляющий вход которого соединен с управляющим входом второго элемента запрета, выход второго блока определения краткости чисел соединен с информационным входом второго элемента запрета и с вто" рым входом второго элемента ИЛИ, выход которого соединен с управляющим. входом первого элемента запрета, вход запуска устройства соединен с входом блокировки коммутатора и с входом разрешения записи третьего счетчика, информационный вход которого соединен с информационным входом регистра, вычитающий вход третьего счетчика соединен с выходом первого элемента запрета, выходы второго и третьего счетчиков соединены с первым и вторым информационными входами коммутатора соответственно, выход которого является информационным выходом устройства.