УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ ЧИСЛА В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ Советский патент 1973 года по МПК G06F7/72 

1

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

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

Предложеииое устройство отличается тем, что в нем блок управления связан с каждым сумматором, выходы сумматоров соединены с входами блоков таблиц коэффициентов и с входами блоков таблиц остатков, выходы блоков таблиц коэффициентов - с элементами индикации блока управления, а выходы блоков таблиц остатков - с входами сумматоров, нодключенными к шинам ввода вычитаемых.

Это позволяет повысить быстродействие устройства.

Схема устройства показана на чертеже.

Устройство содержит блок / управления, сумматоры 2-7, блоки таблиц остатков 8-11, коэффициентов 12, остатков 13-16, коэффициентов 17, остатков 18-21, коэффициентов 22, остатков 23, коэффициентов 24 и 25, шины контроля величины числа 26-31, ввода вычитаемых 32-37, ввода исходных данных 38--43, выдачи остатка 44-49, элементы 50-54 индикации блока управления.

Задача предлагаемого устройства - вычислить модуль числа в диапазоие от О до р

Р, р2, Рз, , Рп Для этого необходимо вычислить коэффициенты t для :модуля числа X, записанного в полиадической системе счисления

Х Г1 + р. ti + Pip2t2 + PlP2P3t3+ .:, PlP2P3,

.-, P, 1,(I)

для случая взаимно простых модулей и 0 , -1.

, -, Q ti. p/.ul

- 1; /3 pi; р2 рз ..., Рп

Коэффициенты // можно находить из таблиц коэффициентов, которые составлены сопоставлением числовых значений остатка а;(/-ц) по модулю р(--1 числовым значениям коэффициента /(, получающихся в процессе деления чисел , Р2, Рз, : pi t на модуль при каждом значении коэффициента / О, 1, 2, 3, ..., р, J - 1. Ввиду того, что остаток а,-,;,,) и коэффициент // имеют одни и те же

то сопоставление

целочисленные значения, значений «///...jv значениям /; является однозначным.

Из таблицы коэффициентов с числовым значением остатка а/,/,, выбираем числовое

значение коэффициента / . Остатки ctj,/,. МОЖ1Ю находить, решая систему сравнений

ri Н- + «2,1 + аз„ +, -, )„

(mod р„ ),

получающуюся делением указанного выражения (1) на каждый модуль , 2,

3, ..., п).

Систему сравнений (2) нужно решать с помощью таблицы остатков, которая содержит однозначное соответствие между числовыми значениями остатка г,, по модулю р/,

и остатка оу по модулю /7у (для каждого значения I 1, 2, 3, ..., и -2 число / i + 2, г + 3, i + 4, ..., «), получающихся в процессе деления чисел pi, р2, PZ, -, Pi ti на каждый модуль рг, и /7у при каждом значении коэффициента О, 1, 2, 3, ..., /7,+ ( - 1. Ввиду того, что р;,.1 и ру взаимно просты и р/, ру и остатки а/г..)) и а/у совместно с коэффициентом t имеют по р;, разных значений, то соответствие между значениями «/(jj и а г/ является однозначным. Входная величина

для таблицы остатков - значение остатка «/(/+) а выходная величина - значение остатка Uij .

Чтобы решать систему сравнений, в устройстве необходимо иметь сумматоры по модулям р2, Рз Pi, ; Рп- Основное требование к сумматорам - выдавать результат в положительных числах (остатках).

В сумматоры по линиям ввода исходных данных вводятся остатки Г2, Гз, Г4, .-., г, затем по линиям ввода 1вычит-аемых в каждый сумматор и в соответствующий элемент индикации- остаток Г, после чего в сумматорах находятся разности - i (mod рг), Asissrs - ri (mod рз) и т.д., где . Эта операция равносильна переносу остатка Г в левую часть сравнений (2) и приводит к системе сравнений

A2iss «12(mod р2)

-f а2з(mod Рз)

;X4issi аи + а24 + аз4(mod р) (3)

Д„, а, + и.:,, + «:;„ +, ..„ + «(«-0,1

(mod р„ ),

что дает возможность в сравнении Д21 «12 (mod Р2) однозначно определить значение ai2 Д21, так как они оба положительны и каждый меньше р2. Следовательно, в сумматоре 2 находится известный остаток ai2.

Перед тем, как провести очередную математическую операцию, блок управления по линиям контроля анализирует величину разностей Д21, Дзь Д4ь Дл1 в сумматорах. Когда Дз Дз1 А41 ... АЛ О, то это значит, что все остатки а/у , стоящие в правых частях

сравнений (3) равны нулю, а само число X г, которое высвечено в первом элементе 50 индикации. В этом случае решение надо закончить и блок управления подает команду на останов. Если же хоть одна величина Ду( оказывается не равной нулю, то решение следует продолжить. Блок управления по шине 47 подает команду на выдачу остатка «12 из сумматора на выходы блоков таблицы остатков и коэффициентов. Эти таблицы выдают остатки 013, , ..., и коэффициент ti, из которых /1 высвечивается во втором элементе индикации, а остатки aia, аи, ..., заводятся соответственно в сумматоры 3-7 на входы ввода вычитаемых. В результате в этих сумматорах находятся разности Дз2 Аз1 - а (mod рз); -аи (mod р4); -ai5 (mod PS); Aes Aei -aie (mod pe), и т. д где d j. Эта операция равносильна

переносу в левую часть сравнений (3) остатков «13, аи, ais, ..., и приводит к системе сравнений

Аз2 «23 (mod РЗ) Д42 а24 -f «34 (mod р4) (4)

П- + «3,1 +, ..., + «{«).,

(mod р„),

что дает возможность в сравнении Дз2 а2з (mod РЗ) однозначно определить 023 Дз2 так как - 1 и . Следовательно, в сумматоре 3 находится известный остаток «23.

После нахождения разностей Дз2, Д42,..., А„ блок управления анализирует, нет ли случая, что Дз2 Д42 ... Д„2 0. Когда этот случай есть, то все остатки, стоящие в правых частях сравнений (4), равны нулю, а число X TI + pifi, о чем свидетельствуют светящиеся в индикаторных элементах числа TI и ti. Решение надо закончить и блок управления подает команду на останов. Если же хоть одна разность Ду2 оказывается не равной нулю, то

решение следует продолжить. Блок управления по шине 34 подает команду на выдачу

остатка 023 из сумматора в па входы блоков таблиц остатков и коэффициентов. Эти блоки выдают остатки а24, «25 ,«2б, ..., «2я и коэффициент /2 соответственно, из которых /2 высвечивается в третьем элементе индикации, а остатки «24, а25, «26, ..., «2« каждый поступает на свой сумматор 4-7 соответственно, на шину ввода вычитаемых. В этих сумматорах находятся разности - «24 (mod Р4),

Д53 Д52 -«25 (mod PS); АбЗ Аб2 -«26

(mod рб) и т. д. Когда блок управления обнаруживает что А4з ASS Аез ... А,, О, он подает команду на останов. Число х п + + + PiPztz- Если же хоть одна разность Ау: оказывается не равной нулю, то блок управления подает команду па продолжение решения. Так продолжается до нахождения модуля числа ,v.

Предмет и з о б р е т е л и я

Устройство для вычисления модуля числа в системе остаточных классов, содержащее блок управления с элементами индикации, сумматоры, блоки таблиц коэффициентов и

6

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

гз

-С2Э-

-П2

нин

-нжн-

Яш

-сюJZ

ЖЕ

ж

Sn

W42.

5

-CZD-J