Устройство для вычисления модуля числа в системе остаточных классов
Союз Советских
Социалистических
Республик
409219
ОПИСАНИЕ
ИЗОБРЕТЕ Н ИЯ н AQTopcKQMY свидетепьствю
Зависимое от авт. свидетельства №вЂ”
Заявлено 15.1.1971 (№ 1614640/18-24) М.Кл. G 06f 7/38 с присоединением заявки №вЂ”
Гасударственный комитет
Совета 14инистрав СССР па делам изобретений и аткрытий
Приоритет—
Опубликовано ЗО.XI.1973. Бюллетень № 48
Дата опубликования описания 29.Ч11.1974
УДК 681.325.5 (088.8) Автор нзобрстепия
П. М, Орлов
Заявитель
УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ МОДУЛЯ ЧИСЛА В
СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ
Изобретение относится к автоматике и вычислительной технике.
Известно устройство для вычисления модуля числа в системе остаточных классов, содержащее блок управления с элементами индикации, сумматоры, блоку таблиц коэффициентов и таблиц остатков.
Предложенное устройство отличается тем, что в нем блок управления связан с каждым сумматором, выходы сумматоров соединены с входами блоков таблиц коэффициентов и с входами блоков таблиц остатков, выходы блоков таблиц коэффициентов — с элементами индикации блока управления, а выходы блоков таблиц остатков — с входами сумматоров, подключенными к шинам ввода вычитаемых.
Это позволяет повысить быстродействие устройства.
Схема устройства показана»a чертеже.
Устройство содер>кит блок 1 управления, сумматоры 2 — 7, блоки таблиц остатков 8 — 11, коэффициентов 12, остатков 18 — 1б, коэффициентов 17, остатков 18 — 21, коэффициентов
22, остатков 28, коэффициентов 24 и 25, шины контроля величины числа 2б — 81, ввода вычитаем ых 82 — 87, ввода исходных данных
88--48, выдачи остатка 44 — 49, элементы
50 — 54 индикации блока управления.
Задача предлагаемого устройства — вычислить модуль числа в диапазоне от 0 до р =
= />» ре, p, " p„. Для этого необходимо вычислить коэффициенты t,. для модуля числа х, записанного в полиадической системе счисления
X = i i + Р. ti + plp2t2 + plp2p3t3 + » .. plp2p3, Р -1 /— 1 .=-. .p — 1, (1) для случая взаимно простых модулей и
0 .-.= i i.- pl — 1.
10 Pi 1 — Р=Р1 > Рз Рз" Р„ Коэффициенты /т можно находить из таблиц коэффициентов, которые составлены сопоставЛЕНИЕМ ЧИСЛОВЫХ ЗНаЧЕНИй ОСтатКа атн 0 ! 3 по модулю р; числовым значениям коэффициента t;, получающихся в процессе деления чисел pi. р, рз, ..., р; ti на модуль р,+ при каждом значении коэффициента t, = О, 1, 2, 3, ..., p, — 1. Ввиду того, что остаток и,;,;, „и коэффициен" /т имеют одни и те же целочисленные значения, то сопоста>вление значений и,; „значениям ti является одно> 25 значным. Из таблицы коэффициентов с числовым значением остатка а,;, выбираем числовое значение коэффициента t., . Остатки ат(т„, 30 можно находить, решая систему сравнений 409219 3 (mod р!) (mod р2) (mod p3) (mod р4) (2) (mod рЗ) (mod р4) (4) 35 х=— r! =— Х— : )2 — — )1+ а!2 Х=:ХЗ ==) + аlз + Q23 Х =r4 = > 1 + (X14 + а24 + а34 х — =) „= — rl + а)„+ а2„+ аз. +, " а(-!) (mod р„), получающуюся делением указанного выражения (1) на каждый модуль р, (1 = 1, 2, 3, ...,n). Систему сравнений (2) нужно решать с помощью таблицы остатков, которая содержит однозначное соответствие между числовыми значениями остатка а; „по модулю р, (+ 1) и остатка а» по модулю р, (для каждого значения i=1, 2, 3, ..., n — 2 число j=i+2, i + 3, i + 4, ..., n), получающихся в процессе деления чисел р(, р2, p3, ..., р,, на каждый модуль р,„, и р, при каждом значении коэффициента 1 = О, 1, 2, 3, ..., р,, — 1. Ввиду того, что р,, и р,. взаимно просты и р,, (р, и остатки а...) и а» совместно с коэффи! ).1) циентом t имеют по р,, разных значений, г +1 то соответствие между значениями а! (,) и (+ а1; является однозначным. Входная величина для таблицы остатков — значение остатка а... „, а выходная величина — значение остатка а,- . Чтобы решать систему сравнений, в устройстве необходимо иметь сумматоры по модулям р2, рз, р4, ..., р„. Основное требование к сумматорам — выдавать результат в положительных числах (остатках). В сумматоры по линиям ввода исходных данных вводятся остатки Р2» r3» r4> ..., г„, затем по линиям»ввода:вычитаемых в каждый суммаfop и в соответству)ощий элемент индикации — остаток rl, после чего в сумматорах находятся разности A21= r2 — rl (mod р2); Л31.:1 3 rl (mod р3) и т. д., где О ==Ьу (р/ — 1 . Эта операция равносильна переносу остатка r! в левую часть сравнений (2) и приводит к системе сравнений - 21= а12 (mod р2) -Л31 = а!3 + а23 (mod рз) Л41 — = а14 + а24 + аз4 (mod p4) (3) Лп! —= -- Q !л + (X „+ (/3„+, "„+ u(n ))Ir (mod р„), lTo дает возможность в сравнении A21 = а!2 (mod р2) однозначно определить значение Q12 = A21, так как они оба положительны и каждый меньше р2. Следовательно, в сумматоре 2 находится известный остаток а!2. 15 25 4 Перед тем, как провести очередную математическую операцию, блок управления по линиям контроля анализирует величину разностей Л21, Лз(, Л41, ..., Л„, в сумматорах. Когда Л21 Л31 = Л41 = ... = A„) = О, то это значит, что все остатки а(;, стоящие в правых частях сравнений (3) равны нулю, а само число х = rl, которое высвечено в первом элементе 50 индикации. В этом случае решение надо закончить и блок управления подает команду на останов. Если же хоть одна величина Л,, оказывается не равной нулю, то решение следует продолжить. Блок управления по шине 47 подает команду на выдачу остатка а12 из сумматора на выходы блоков таблицы остатков и коэффициентов. Эти таблицы выдают остатки а!3, а14> ", а)„и коэффициент tl> из которых tl высвечивается во втором элементе индикации, а остатки Q13, а!4, ..., а„, заводятся соответственно в сумматоры 8 — 7 на входы ввода вычитаемых. В результате в этих сумматорах находятся разности A32= Лз! — а!3 (mod рз); Л42= Л41 — а14 (Гпо(1 p4) Л52 = Л51 — а15 (mod р5); Л62 — = Л6! — а!6 (гпо(1 р6), и т. д где О (Л, Cd,. Эта операция равносильна переносу в левую часть сравнений (3) остатков al3, а!4, а!5, ..., а,„и приводит к системе сравнений Л32 = а23 Л42= а24 + Q34 n — аЗn + аЗ)) +» + Q(rr — 1)3 (mod р,), что дает возможность в сравнении Л32= а23 (mod рз) однозначно определить a23 — — Л32 так как 0 После нахождения разностей Л32 Л42 .. Л„ блок управления анализирует, нет ли случая, что A32 — Л42 — ° .. = Л„, = О. Когда этот случай есть, то все остатки, стоящие в правых частях сравнений (4), равны нулю, а число х = rl + рА, о чем свидетельствуют светящиеся в индикаторных элементах числа rl u tl. Решение надо закончить и блок управления подает команду на останов, Если же хоть одна разность Л, 2 оказьгвается не равной нулю, то рсшепие следует продолжить. Блок управления по шине 84 подает команду на выдачу остатка а23 из сумматора 8 на входы блоков таблиц остатков и коэффициентов. Эти блоки выдают остатки а24, а25,а26,, а,„и коэффициент t2 соответственно, из которых t2 высвечивается в третьем элементе индикации, а остатки а24, а25, а26, ..., а З„каждый поступает на свой сумматор 4 — 7 соответственно, на шину ввода вычитаемых. В этих сумматорах í",õîдятся разности A43 = A42 — а24 (mod p4), Л53=Л52 а25 (mod р5)» AGÇ= Л62 а26 (mod р6) и т. д. Когда блок управления обна40921 Составитель Р, Акгурин Техред А. Камышникова Корректор Н. Аук Редактор И. Грузова Заказ 1767 Изд. № 1130 Тираж 624 Подписное ЦИИИПИ Государственного комитета Совета Министров СССР по делам изобретений и открытий Москва, Ж-35, Раушская иаб., д. 4/5 Загорская типография 5 руживает что Л4з = Лзз = Лаз = " Л,з = О, он подает команду на останов. Число х = r> + + р 4 + p p2t2. Если же хоть одна разность Л.з оказывается не равной нулю, то блок управлепия подает команду на продолжение решенич. Так продолжается до нахождения модуля числа х. Предмет изобретения Устройство для вычисления модуля числа в системе остаточных классов, содержащее блок управления с элементами индикации, сумматоры, блоки таблиц коэффициентов и 6 блоки таблиц остатков, отличающееся тем, что, с целью повышения быстродействия устройства, в нем блок управления связан с каждым сумматором по шинам ввода исходных данных, по шинам ввода вычитаемого, по шинам контроля величины числа и по шинам управления сумматорами;,выходы сумматоров соединены с входами блоков таблиц коэффициентов и с входами блоков таблиц ос атков, выходы блоков таблиц коэффициенчои соединены с элементами индикации блока управления, выходы блоков таблиц остатков соединены с входами сумматоров, подключенными к шинам ввода вычитаемых.
