Устройство для вычисления остатка по модулю от числа

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК И 9) 01)51) С 06 Г 11/08; С 06 Г 5/02 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) 1. Авторское свидетельство СССР В 928359, кл. С 06 р 11/08, 1980.2 Авторское свидетельство СССР В 902013, кл. С 06 Р 5/02, 1980 (прототип).(54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА, содержащее сумматор по модулю, о т л и ч аю щ е е с я тем, что, с целью уменьшения объема оборудования, сумматор по модулю содержит ( П) - 1) двоичных сумматоров, где щ - разрядность модуля, причем первый двоичный сумматор содержит ( И + и) - 1) разрядов ( М - разрядность контролируемого числа), разрядность каждого последующего двоичного сумматора на единицу меньше разрядности предцдущего двоичного сумматора, вход пер:вого слагаемого каждого 1 -го разряда первого двоичного сумматора (ОЙ йп- - 2) соединен с ( Ф + 1)-м разрядом контролируемого числа, вход первого слагаемого каждого-го разряда ( - 11 1и+- 2) первого двоич-. ного сумматора сЪединен с шиной нулевого сигнала, вход первого слагаемого каждого К -го разряда-го двоичного сумматора ( 14 6 4- 1, 0и + в -6) соединен с выходом суммы ( М + 1)-го разряда ( Р -1)-го двоичного сумматора, первые входы второго слагаемого каждого двоичного сумматора соединены с соответствующими разрядами входа кода модуля устройства, входы переноса каждого двоичного сумматора соединены с шиной единичного потенциала, выход суммы нулевого разряда каждого-го двоичного сумматора (1 6 Ри - 1) соединен с вторыми входами второго слагаемого- Х разрядов всех двоичных сумматоров, выход суммы каждого 9 -го разряда последовательного двоичного суииатора ( 1 В 41) соединеныс вторыми входами второго слагаемого ( с + б - 1) разрядов всех двоичных сумматоров, выходы суммы (-Ю" )-х разрядов последнего двоичного сумматора (О 4й е - 1) являются выходом устройства.1 О Изобретение относится к вычислительной технике и может быть использовано для свертки чисел по.модулю.Известно устройство для выделенияостатка по переменному модулю, содержащее регистры числа и модуля,дешифраторы числа и модуля, коммутатор и шифратор И .Недостатком данного устройстваявляется большой объем аппаратурыкоммутатора и шифратора.Наиболее близким по техническойсущности является преобразовательдвоичного кода в код по модулю, содержащий сумматор пб модулю, К шифраторов щ разрядов (1 й с 11 , И - разорядность двоичного кода, К = - ),входной регистр, вход которого является входом устройства, выходы входного регистра подключены к входам20соответствующих шифраторов, выходышифраторов подключены к соответствующим входам сумматора по модулю 2.Недостатком преобразователя являются значительные аппаратурные зат 25раты на реализацию шифраторов припеременном значении модуля.Цель изобретения - уменьшениеобъема аппаратуры,130Поставленная цель достигаетсятем, что в устройстве для вычисленияостатка по модулю от числа, содержащем сумматор по модулю, сумматор помодулю содержит ( Ф - 1) двоичныхсумматоров, где Ф - разрядность модуля, причем первый двоичный сумматорсодержит (, + 11 - 1) разрядов (Л -разрядность контролируемого числа),разрядность каждого последующегодвоичного сумматора на единицу мень 40ше разрядности предшествующего двоич.ного сумматора, вход первого слагаемого каждого-го разряда первогодвоичного сумматора (О1 6 И - 2)соединен с ( 1 + 1)-м разрядом конт 45ролируемого числа, вход первого слагаемого каждого 1 -го разряда (111 А4 и+ фи - 2) первого двоичногосумматора соединен с шиной нулевогосигнала, вход первого слагаемогокаждого 1 -го разряда 1 -го двоичногосумматора ( с 0 ь м - 1, О 6( и +(,с + 1)-го разряда (- 1)-го двоич,ного сумматора, первые входы второго 55слагаемого каждого двоичного сумматора соединены с соответствующимразрядом входа кода модуля устройства, входы переноса каждого двоичного сумматора соединены с шиной единичного потенциала, выход суммы нулевого разряда каждого р-го двоичного сумматора (1р1 - 1) соединен с вторыми входами второго слагаемого р - х разрядов всех двоичных сумматоров, выход суммы каждого 9 -го разряда последнего двоичного сумматора (1 с б 6 1 - 1) соединен с вторыми входами второго слагаемого ( 1 п + 5 - 1)-х разрядов всех двоичных сумматоров выходы суммы ( й - Р )-х разрядов последнего двоичного сумматора (Ое - 1) являются выходом устройства.За счет входной логики в цепи второго слагаемого сумматоры реализуют функцию двоичного вычитания, где вычитаемое управляется значением соответствующего разряда кода основания. Реализация этой функции и организация связей мекду входами и выходами сумматоров обеспечивает алгоритм целочисленного деления двоичного числа на значение основания, причем деление осуществляется со стороны младших разрядов в сторону старших вПриняты следующие обозначения: Ап - исходное число; р - модуль Ар, К - соответственно целая часть и остаток от деления А 11, на р, число А является результатом указанного алгоритма целочисленного деления и определяется выражениемц СР)кА = А-2 1 (р -")(1 ургде су(р) - функция Эйлера основанияру- натуральное число, величина которого определяется длиной алгоритма.В двоичном исчислении, при разряд- ности исходного числа А, значение разрядов числа А с и -го и старшеопределяются только значениями разрядов второго слагаемого выражения (1). При разрядности модуля и группа из 11 последовательных разрядов кода второго слагаемого однозначно определяет остаток и может быть использована для организации модульных действий.При ограничении алгоритма разрядностью 11 + 1 п в разрядах с 11 -го по 11 + 1 и-й образуется остаток 6 , кодиз 1 рованный группой нз п последовательных разрядов элемента двоичного базиса, имеющего вид111О 5 С Сг г О О а сг 8 а,7 ОЬ О 5 .г 3 асс 1 О 084798 4ет функцию двоичного вычитания.Уменьшаемыми являются для первогосумматора - первое слагаемое, дляторого - значения выходов суммы,.1 Жвто оР2) 5 начиная с выхода первого разряда,На че тпервого сумматора, для третьего - ,.а чертеже представлена функцио- значе инальная схема устн чен я выходов с мын че д уммы, начиная строиства, преднаэ- выхода первогначенного для вычисления четырех пос-о разряда, второго с мматора. Вычитаемым является воичледовательных разрядов кода к (4,) 1В двоичпо любому нечетному 4 О ное значение, оп еляеРед мое логичес"..числа В ид фдвоичного Ле войентификации логическихр переменной являются значенияэлементов использованы стандартразрядов двоичного числадартные го значен еу которообозначения,дарт чение нулевого разряда равноУстройство содержит двоичные с - зй15 а , значение первого аз я ар р д равноматоры - 3 и сумматор 4 по мо лю.1 - 3двоичные сум- ,значению нулевого выхода первого сумо модулю. матора, значение второго раз я аВходные и выходные значения предпозрядалагаются двоично-кодированными и,равно значению нулевого выхо а вт -д ообозначены: исходное двоичное чис- ирого сумматора, значение т етр ьегочис О и последующих разрядов равно значело а аа а ; модульо 1 о 2 1ниям выходов третьего суммато а напричем младший разряд модуля пред- чиная с нулевого разряда, Вто ойполагается всегда единичным ( =1) пторои,код остатка Г р Рр = ; переменной является значение разп ряВ схедов кода модуля, причем для первогосхеме используются одноразряд" 25 сумманые сумматоры с входной логикойтора - значение р ля втод ро-кои в го - р, для третьего - рцепи второго слагаемого, Входная ло- РаботаЗа ота устройства заключается вика о еспечивает выполнение логи- вычислческой функции штрих Шеффе а отлении разности м ежду уменьшаее ера от мым первого сумматора и суммой вычидругих переменных. Одноразрядные ЗО таемыхмых всех трех сумматоров, присумматоры соединены в три двоичныхсумматора первыи - 15-разрядный таемыхм гэтом значения старших разрядов вычи 1- ", емв определяются реализацией функвторо - 1 -разрядный, третий - 13- ции вычитанияразрядныйтания в младших разрядах.значая а; значение первой перемен.За счет инверсии в логическойн е аной вычитаемого г ео ческо .вует нумерации связей по функциоразряд каждый из сумматоров реалиэу- вид.,нальной схеме, алгоритм аботыр имеет,О О О 0 г с а ав а, аь а аф а аг о, аоа1 11 1 1 1 1Р а РаьРагРаРа 1 оРОе Р авРагР аьРа 5 РааР аэРотРаРао1 1Ргаь Ргаг Рг аю Рга 1 о Рта Рга 8 Ргаг Ргаь Рга 5 Ргали Ргали Ргали Рга Ргао1 1 6РгпРг РоРгарРзаьРзаг РзоьРзО 5 Рэ Рог Р 3 а РзаоЗначение а 5 а а а 2 является кодом остатка Г Г 2 г ГоПредлагаемое устройство позволяет применять для своего пост- ,роения однотипные. элементы и обеспечивает значительную экономию аппаратуры по сравнению с прототипом.