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

Изобретение относится к вычислительной технике и может быть исполь зовано для свертки чисел по. модулю. Известно устройство для выделения остатка по переменному модулю, содержащее регистры числа и модуля, дешифраторы числа и модуля, коммутатор и шифратор и Недостатком данного устройства является большой объем аппаратуры коммутатора и шифратора. Наиболее близким по технической сущности является преобразователь двоичного кода в код по модулю, содержащий сумматор по модулю, К шифраторов m разрядов (tT п , И - раз рядность двоичного кода, К р ) входной регистр, вход которого явля ется входом устройства, выходы вход ного регистра подключены к входам соответствующих шифраторов, выходы шифраторов подключены к соответствую щим входам сумматора по модулю l2j, Недостатком преобразователя являютйя значительные аппаратурные за раты на реализацию шифраторов при переменном значении модуля. Цель изобретения - уменьшение объема аппаратуры. Поставленная цель достигается тем, что в устройстве для вычислени остатка по модулю от числа, содержа щем сумматор по модулю, сумматор по модулю содержит ( JYi - t) двоичных сумматоров, где т - разрядность моду ля, причем первый двоичньй сумматор содержит ( ,п + ryi - 1) разрядов (П разрядность контролируемого числа), разрядность каждого последзпощего дв&ичного сумматора на единицу меньше разрядности предшествующего двоич ного сумматора, вход первого слагаемого каждого i-го разряда первого двоичного сумматора (О i : И - 2) соединен с ( i + 1)-м разрядом контролируемого, числа, вход первого слагаемого калщого j -го разряда (h - 14 i М + m - 2) первого двоичного сумматора соединен с шиной нулевого сигнала, вход первого слагаемого каждого k-го разряда -го двоичного Сумматора (I Kfcim- 1, + + ГЯ Р) соединен с выходом суммы (k + 1)-го разряда (f - 1)-го двоич ного сумматора, первые входы второго слагаемого каждого двоичного сумматора соединены с соответствующим разрядом входа кода модуля устройст98, входы переноса каждого двоичного на сумматора соединены с шиной единичного потенциала, выход суммы нулевого разряда каждого р-го двоичного сумматора (1 1 ) - 1) соединен с вторыми входами второго слагаемого , р - X разрядов всех двоичных сумматоров, выход суммы каждогоS-го разряда последнего двоичного сумматора (,Г)- 1) соединен с вторыми входами второго слагаемого ( VY1 + 5 - 1)-х разрядов двоичных сумматоров,, выходы суммы ( Hi - г)-х разрядов последнего двоичного сумматора (О 1 w - 1) являются выходом устройства. За счет входной логики в цепи второго слагаемого сумматоры реализуют функцию двоичного вычитания, где вычитаемое управляется значением соответствующего разргяда кода основания. Реализация этой функции и организация связей мелщу входами и выходами сумматоров обеспечивает алгоритм целочисленного деления двоичного числа на значение основания, причем деление осуществляется со стороны мпадших разрядов в сторону старших. Приняты следующие обозначения: А исходное число; р - модуль Ал Od - соответственно целая часть и остаток от деления , на р, число А является результатом указанного алгоритма целочисленного деления и определяется выражением - О (р -) А А. где (f(p) - функция Эйлера основания k - натуральное число, величина которого определяется длиной гшгоритма. В двоичном исчислении, при разрядности исходного числа А, значение разрядов числа А с П-го и старше определяются только зн(ачениями разрядов второго слагаемого выражения (1). При разрядности модуля т группа из m последовательных разрядов кода второго слагаеиого однозначно определяет остаток и может буть исользована для организации модульньк ействий. При ограничении алгоритма разрядностью ( + т в разрядах с п -го по П+Ш-Й образуется остаток сА , кодированный группой из m последователь ных разрядов элемента двоичного баз са, имеющего вид - 1 (р -ОС) R(ot) На чертеже представлена функциональная схема устройства, предназначенного для вычисления четырех по ледовательных разрядов кода R (о(,) по любому нечетному 4-разрядному мо дулю от 12-разрядного двоичного числа. В идентификации логических элементов использованы стандартные обозначения. Устройство содержит двоичные сум маторы 1 - 3 и сумматор 4 по модулю Входные и выходные значения предполагаются двоично-кодированными и обозначены: исходное двоичное число ... модуль , причем мпадший разряд модуля предполагается всегда единичным (PQ 1) .код остатка г,} Г fj, В схеме используются одноразрядные сумматоры с входной логикой в цепи второго слагаемого. Входная ло гика обеспечивает выполнение логической функции штрих Шеффера от других переменных. Одноразрядные сумматоры соединены в три двоичньк сумматора: первый- - 15-разрядный, второй - 14-разрядный, третий - 13раэряднь. За счет инверсии в логической функции и сигнала переноса в нулево разряд каждый из сумматоров реализу

о|ц Ofl а, Qg От Об 05 04 -i о

чОк piC3iepia,2 pidn , p.cxgp aVpiOife p, zOrt pioJa PJ«;, piolo PICK; pjo paoV p2afa PzOj joo рзОп ,. ргаюрэадрэабрзау РзД4 i

aj, а,5 а, а,,, о, а«, ag а,, а ад 04 а,

Значение 3,5 а aj, а является кодом остатка Г; 2

Предлагаемое устройство позволяет применять для своего пост- ,

роения однотипные, элементы и обеспечивает значительную экономию аппаратуры по сравнению с прототипом. ет функцию двоичного вычитания, Уменьшаемыми являются для первого сумматора - первое слагаемое, для второго - значения выходов суммы, начиная с выхода первого разряда, первого сумматора, для третьего - .. значения выходов суммы, начиная с выхода первого разряда, в,торого сумматора. Вычитаемым является двоичное значение, определяемое логическим умножением двух переменных. Первой переменной являются значения разрядов двоичного числа, у котороiro значение нулевого разряда равно а., значение первого разряда равно I значению нулевого выхода первого сумматора, значение второго разряда равно значению нулевого выхода втоporo сумматора, значение третьего и последующих разрядов равно значе ниям выходов третьего сумматора, начиная с нулевого разряда. Второй переменной является значение разрядов кода модуля, причем для первого сумматора - значение р, для второг го - Ру, для третьего - Р. Работа устройства заключается в вычислении разности между уменьшаемым первого сумматора и сзгммой вычитаемых всех трех сумматоров, при этом значения старших разрядов вычитаемых определяются реализацией функции вычитания в младших разрядах. Обозначая а, значение первой переменной вычитаемого, где i - соответствует нумерации связей по функцио|нальной схеме, алгоритм работы имеет вид

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА, содержащее сумматор по модулю, о т л и.ч аю щ е е с я тем, что, с целью уменьшения объема оборудования, сумматор по модулю содержит ( TIN - 1) двоичных сумматоров, где щ - разрядность модуля, причем первый двоичный сумматор содержит ( Л « t - 1) разрядов ( - разрядность контролируемого числа), разрядность каждого последующего двоичного сумматора на единицу меньше разрядности предьщу- щего двоичного сумматора, вход пер вого слагаемого каждого ч -го разряда первого двоичного сумматора