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

 

ОПИСАНИЕ

ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советскми

Социалистических

Республик (11962942 (61) Дополнительное к авт. свид-ву (22) Заявлено 16 ° 12 ° 80 (21) 3219203/18-24 (51)М Кп з

G 06 F 7/72 с присоединением заявки Мо

Государственный комитет

СССР по делам изобретений н открытий (23) Приоритет

Опубликовано 3Q09.82 Бюллетень Мо 36 (53) УДК 681. 325. (088.8) Дата опубликования описания 30.09.82

P.C. Белова, В.Г. Евстигнеев, A ..С. Новожилови В.Н. Сведе-Швец

i (72) Авторы изобретения (71) 3a яв ител ь (54 ) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ В СИСТЕМЕ

ОСТАТОЧНЫХ КЛАССОВ

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

Известно табличное устройство для модульного умножения в системе остаточных классов, содержащее дешифраторы, вентили, ключи, матрицу умножения, группы элементов ИЛИ, ферритовые линейки, блок арифметических таблиц (1).

Недостатком устройства является большой объем оборудования и невысокое быстродействие, связанное с применением нелинейных элементов.

Наиболее близким по технической сущности к предлагаемому является устройство для умножения, содержащее регистр множимого, регистр множителя, блок хранения констант, блок умножения по модулю р (где роснование системы остаточных классов), регистр памяти, сумматор по модулю р, причем входы регистра множимого являются входами первого операнда устройства, входы регистра множителя являются входами второго операнда устройства, выходы блока умножения по модулю р соединены соответственно с входами регистра па= мяти (2) .

Недостатком устройства является невысокое быстродействие.

Цель изобретения — повышение быстродействия устройства.

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

И и управляющими входами реги .тра первого макрокоэффициента мно "«Mîãñ и регистра второго макрокоэффициента множимого, выходы регистра llc p

962942

aoro макрокоэффициента множимого соединены соответственно с первыми входами первого и второго блоков умножения по модулю р, выходы регистра второго макрокоэффициента множимого соединены соответственно с первыми 5 входами третьего блока умножения по модулю р, вторые входы которого соединены соо"ветственно .с выходами регистра :-рвого макрокоэффициента множителя и вторыми входами пер- fQ вого блока умножения по модулю р, выходы регистра множителя соединены соответственно с первыми входами элементов И второй группы и являются выходами устройства, вторые входы элементов И второй группы соединены с вторым входом синхронизации устройства, входом элемента задержки, с первым входом второго элемента И и с управляющими входами регистра первого макрокоэффициента множителя и регистра второго макрокоэффициента множителя, выходы элементов И первой группы соединены соответственно с входами преобразователя двоичного кода в унитарный код, управляющий выход которого соединен с вторыми. входами первого и второго элементов И, выходы которых соединены соответственно с информационными входами первого и второго триггеров, единичный выход, третьего триггера соединен с третьим входом второго элемента И, единичные выходы первого и второго триггеров соединены соответственно с первым и вторым входами третьего элемента И, .35 выходы регистра. памяти соединены соответственно с перввыми входами элементов И третьей группы, выходы которых соединены соответственно с входами первой группы сумматора по ф) модулю р, входы второй группы которого соединены соответственно выходами элементов И пятой группы, первые входы которых соединены соответственно с выходами третьего бло ка умножения по модулю р, входы третьей группы сумматора по модулю р соединены соответственно с выходами элементов И четвертой группы, первые входы которых соединены соответствен но с выходами регистра первого макрокоэффициента множителя, выходы., .алИментов И второй группы соединены соответственно с входами преобразова еля двоичного кода в унитарный, оды которого соединены соответственно с входами второго блока хранения констант, выходы первой группы которого соединены соответственно с информационными входами регистра первого макрокоэффициента множителя, 6О информационные входы регистра второго макрокоэффициента множителя соединены соответственно с выходами второй группы второго блока хранения| констант, выходы преобразователя дво- 65 ичного кода в унитарный соединены соответственно с входами первого блока хранения констант, выходы первой группы которого соединены соответственно с информационными входами регистра первого макрокоэффициента множимого, а выходы второй группы — соответственно с информационными входами регистра второго макрокоэффициента множимого, выходы регистра второго макрокоэффициента множителя соединены соот-ветственно с вторыми входами второго блока умножения по модулю р, выходы которого соединены соответственно с первьми входами элементов И шетсой группы, выходы которых соединены соответственно с входами четвертой группы сумматора по модулю р, входы пятой группы которого соеди. нены с выходом третьего элемента И,. а выходы — соответственно с информационными входами регистра множителя, вторые входы элементов И пятой и шестой групп ббъединены и являются третьим входом синхронизации устрой-. ства, третий вход третьего элемента

И соединен с вторыми входами элементов И третьей.и четвертой групп и является четвертым входом синхронизации устройства,.управляющие входы первого, второго и третьего триггеров объединены и являются пятым входом синхронизации устройства.

На чертеже представлена функциональная схема устройства. устройство содержит регистр 1, множимого, регистр 2 множителя, элементы И 3. и 4,.преобразователь 5 двоичного кода в унитарный код, блоки 6 и 7 хранения констант, регистр

8 первогь макрокаэффициента множимого, регистр 9 второго макрокоэффициента множимого, регистр.10 первого макрокоэффициента множителя, регистр

11 второго макрокоэффициента множителя, блоки 12-14 умножения по модулю р, регистр 15 памяти, элементы.И 16-19, сумматор 20 по модулю р, элементы И 21 и 22, триггеры 23 и 24, элемент И 25, триггер 26, элемент 27 задержки, входы 28 первого операнда устройства, входы 29 второго онеранда устройства, входы 30-34 синхронизации устройства, выход 35 устройства.

В устройстве входы регистра 2 множимого являются входами 28 первого операнда устройства, входы регистра 2 множителя являются входами 29 второго операнда устройства, выходы блока 12 умножения по модулю р соединены соответственно с входами регистра 15 памяти, выходы регистра 1 множимого соединены соответственно с первыми входами элементов И 3, вторые входы которых ссединены соответственно с входом

962942

30 синхронизации устройства, пер- жителя соединены соответственно с вью входом элемента И 21 и управ- жгходами в торой группы блок а 7 храляющими входами регистра 8 первого кения констант, выходы преобразрвамакрокоэффициента множимого и ре- теля 5 двоичного кода в унитарный гистра 9 второго макрокоэффициента соединены соответственно с входами множимого, выходы регистра 8 первого 5 блока 6 хранения констант, выходы макрокоэффициента множимого соеди- первой группы которого соединены иены соответственно с первыми вхо- соответственно с информационными дами блоков 12 и 13 умножения по входами регистра 8 первого макромодулю р, выходы регистра 9 второго коэффициента множимого, а выходы макрокоэффициента множимого соеди- 1О второй группы — соответственно с иены соответственно с первыми вхо- информационными входами регистра 9 дами блока 14 умножения по модулю второго макрокоэффициента множимор, вторые входы которого соединены ro, выходы регистра.11 второго максоответственно с выходами регистра 10 f рокоэффициента множителя соединены макрокоэффициента множителя и вторыми 151 соответственно с вторыми входами входами блока 12 умножения по моду- блока 13 умножения по модулю р, вы-. лю р, выходы регистра 2 множителя ходы. которого соединены.соответстсоединены соответственно. с первыми венно с первыми входами элементов И входами. элементов И 4 и являются вы- .: 19, выходы которых соединены соответходами 35 устройства, вторые входы 20 ственно -с входами четвертой группы элементов И 4 соединены с входом 31 сумматора 20 по модулю р, входы пясинхронизации устройства, с входом той группы которого соединены с нязпемента 27 задержки, с первым вхо- ходом элемента И 25, а выходы— дом элемента И 22 и с управляющими соответственно с информационными входами регистра 10 первого макрокоэф- 25 Входами регистра 2 множителя, втофициента множителя и регистра 11 вто- Рые входы элементов И 17 и 19 объерого макрокоэффициента множителя, динены и являются входом 32 синхровыходы элементов . И 3 соединены соот- низации устройства, третий вход ветственно с входами преобразовате - элемента И 25 соединен с вторыми ля .5 двоичного кода в унитарный код, @30 входами элементов И 16 и 18 и являуправляющий выход которого соединен . ются входом 33 синхронизации устройс вторыми входами элементов И 21 и 22, ства, управляющие входы триггеров 23, выходы которых соединены соответст- 24 и 26 соединены и .являются входом венно с информационными входами триг-. - 34 синхронизации устройства.

repoa 23 и 24, единичный выход триг- 35 . В основу работы устройства пологера 26 соединен с третьим входом ..жен:известный алгоритм. Умножения с

I элемента H 22, единичные выходы . Разложением сомножителей. на макрокотриггеров 23 и 24 соединены соответ- . .эффициенты суть которого состоит в ственно с первым и вторьм входами . следующем. элемента И 25, выходы регистра 15 - 4О Если Рабочие основания системы памяти соединены соответственно с разбить на две группы, такие, что первыми входами элементов И 16, вы- > - P - У(Р = Q P}, то любое ходы которых соединены соответствен- число .лежащее в диапазоне (0 у ), но с входами первой группы сумматора можно представить в виде

20 по модулю р, входы второй группы которого соединены соответственно с . 45 > = AyP + @ выходами элементов И 17, первые: . где A — частное от деления числа входы которых соединены соответствен- »+ Р (первый макрокоэфно с выходами блока 14 умножения по фициент); модулю р, входы третьей группы сум- Ag — остаток от деления числа ьатора 20 по модулю р соединены co- . A íà P (второй макрокоэфответственно с выходами элементов фициент) °

И 18, первые входы которых .:соедине- Умножение двух чисел можно про«ы соответственно с выходами регист- изводить не в диапазоне y а в дира 10 первого макрокоэффициента множи- апазоне f с сокращением произведения теля, выходы элементов И 4 соедине- 55 на У ьы соответственно с входами преобра- Пусть A - множимое,  — множитель. зователя 5 двоичного кода в унитар- Представим их в виде: кий, выходы которого соединены со- A = A4PÄ+ A i; ответственно с входами блока 7 хра-  — В1P + В нения констант, выходы первой груп- ф Тогда :произведение чисел найпы которого соединены соответствен- дется следующим образом: но с информационными входами регист- АВ А В„Р+ А В Р1+А В Рр. + А д Ьг ра 10 первого макрокоэффициента мно- Р Р жителя, информационные входы.регист- АВ А1В Р„+А „РА В ра 11 второго макрокоэффициента мно- 65 =A s„„

962942

Последний член < (. и

АхВ

Р бросить . Так как Р„" P член запишем в виде

l (А Ь А,З„)Р DP D

Р ) его можно от.

Р, второй

D 5

1Р 1«2

Эт<Р и С =, =А.«В.«+Ъ).! где

«О

Устройство работает следующим образом., На регистры 1 и 2 поступают мно жимое и множитель в виде двоичных коцов остатков по всем основаниям системы остаточных классов. Дальнейшая работа происходит по тактам.

Первый такт. Разложение множимого A на макрокоэффициенты А,« и

Ат. На входы элементов И 3 и вход, 30 устройства подается сигнал, разрешающий преобразование операнда A.

Число A из регистра 1 через группу элементов И 3 поступает на преобразователь 5, содержащий дешифратор кода, с вьжода котрого поступает на вход блока 6, с выхода которого в виде макро коэффициентов А и А заносится соответственно в регистрй 8 и 9, так как

«и их управляющих входах есть разрешающий сигнал с входа 30 устройства. ЗО

Второй такт. Разложение множителя

В на макрокоэффициенты В) и В . Разложение происходит аналогично сигналу с входа 31 устройства.

Значение В4 и .В запоминаются на 35 регистрах 10 и 11.

Одновременно .в первом и втором тактах производится анализ знаков сомножителей преобразователем 5 с. целью коррекции знака результата в 4Q случае, если оба сомножителя отрицательны. Коррекция осуществляется элементами И 21 и 22 и триггерами 23, 24 и 26. Здесь принята искусственная форма представления чисел в ситеме остаточных классов (имеется в виду, что одно Из оснований системы четное, в частном случае Р« =2). Тогда отрицательные числа лежат в диапазоне (0;)«j2-1), положительные в диапазоне (Р/2 + 1; Я/2-1), в качестве нуля системы принято число g/2.

Перевести число из одного диапазона в другой можно, прибавив к числу ипи вычтя иэ него константу f/2, кот+ая по основанию Р имеет остаток — 1, а по остальным основаниям— нули. При разложении отрицательного числа на управляющем выходе преобразователя 5 появляется сигнал, которь«й, пройдя через первый элемент И

21 по сигналу с входа 30 устройства, запоминается на триггере 23, если преобразуемое отрицательное число— число А, или, пройдя через элемент

И 22 по сигналу с входа 31 устройства,d5 запоминается на триггере 24, если преобразуемое отрицательное число число В.

В результате элемент И 25 будет тюдготовлен для прохождения единичного сигнала (синала поправки) на пятый вход сумматора 20. Поскольку регистр

2 и преобразователь 5 используется не только для разложения множителя.

В, но и для разложения промежуточного значения величины

1«А<Ва. В1Ат р Ъ1Р + «)

I то для исключения ложного срабатывания элемента И 22 и триггера 24 сигнал с входа 31 устройства, задерханный на время чуть большее времени срабатывания преобразователя 5, элементом 27 задержки перебрасывает в момент преобразования числа В в триггер 26, закрывая тем самым эле«ент И 22 для повторного срабатывания при преобразовании величины D.

Третий такт. Вычиление величий

А1Ва Ая.В «3 А Ьх+АИч

Р P P p в блоках 13 и 14 и сумматоре 20. В результате в регистре 2 оказывается значение D/Р по сигналу с входа 32 устройства.

Четвертый такт. Разложение величины D/2 на макрокоэффициенты (?)«и

D ) которые запоминаются на триггерах 10 и 11.

Пятый такт. Вычисление величинЫ

А„В„и А„ В„+ D„. Вычисление производится с помощью блока 12, регистра 15 памяти, элементов И 16 и lg, сумматора 20 и элемента И 25 по сигналу с входа 33 устройства, в результате чего произведение заносится на регистр 2, с выхода которого поступает на выход 35 устройства.

Сигналом с входа 34 устройства триггеры 23, 24 и 26 устанавливаются в исходное положение: триггеры 23 и

24 — в нулевое состояние, триггер

26 — в единичное.

Перемножение двух чисел в известном устройстве выполняется не менее, чем за 10 тактов. Таким образом, предлагаемое устройство позволяет повысить быстродействие в два раза по сравнинию с известньм

Формула изобретения

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

962942

25. 30 умножения по модулю р (р — основание системы остаточных классов), регистр памяти, сумматор по модулю р, причем входы регистра множимого являются входами первого операнда устройства, выходы регистра множителя являются 5 .входами второго операнда устройства, выходы блока умножения по модулю р соединены соответственно с входами регистра памяти, о т л и ч а ю щ е- е с я тем, что, с целью повышения }О быстродействия устройства, в него введены шесть групп элементов И, элемент задержки, три триггера, три элемента И, второй блок хранения констант, регистр первого макрокоэф- }5 фициента множимого, регистр второго макрокоэффициента множимого, регистр первого макрокоэффициента множителя, регистр второго макрокоэффициента множителя, второй блок умножения по модулю р, третий. блок умножения по модулю р,преобразователь двоичного кода в унитарный код, причем выходы регистра множимого соединены соответственно с первыми входами элементов И первой группы., вторые входы которых соединены соответственно с первым входом синхронизации устройства, первьм входом первого элемента И и управляющими входами регистра первого макрокоэффициента множимого, выходы регистра первого макрокоэффициента множимого соединены соответ- ственно с первыми входами первого и второго блоков умножения по модулю р, выходы регистра второго макрокоэффициента множимого соединены соответственно с первыми входами третьего блока умножения по модулю р, вторые входы которого соединены соответственно с выходами регистра первого ьакрокоэффициента множителя и вторыми входами первого блока умножения по модулю р, выходы регистра множителя соединены соответственно с первыми нходами .элементов И второй группы и являются выходами устройства, вторые нходы элементов И второй группы соединены с вторым входом синхронизации устройства, входом элемента задержки, с первым входом второго элемента И и с управляющими входами регистра первого макрокоэффициента множителя и регистра второго макрокоэффициента множителя, выходы элементов И 55

llBpBoA группы соединены соответственно с входами преобразователя двоичного кода в унитарный код, управляющий выход которого соединен с вторыми входами первого и второго элементов Ю

И, выходы которых соединены соответственно с информационными входами первого и второго триггеров, единич- ный выход третьего триггера соединен с третьим входом второго элемента И,, 65 единичные выходы первого и второго триггеров соединены соответственно с первым и вторым входами третьего элемента И, выходы регистра памяти соединены соответственно с первыми входами элементов И третьей группы, жходы которых соединены соответственно с входами первой группы сумматора по модулю р, входы второй группы которого соединены соответственно с выходами элементов И пятой группы, первые входы которых соединены соответственно с выходами третьего блока умножения по модулю р, входы третьей группы сумматора по модулю р соединены .соответственно с н=тходами элементов И четвертой группы, первые входы которых соединены соответственно с выходами регистра первого макрокоэффициента множителя, выходы элементов И второй группы соединены соответственно с входами преобразователя двоичного кода в унитарный, выходы которого соединены соответственно с входами второго блока хранения констант, находы первой группы которого соединены соответственно с информационными входами регистра первого ьакрокоэффициента множителя, информационные входы регистра второго макрокоэффициента множителя соединены соответственно с выходами второй группы второго блока хранения констант, выходы преобразователя двоичного кода в унитарный соединены соответственно с выходами первого блока хранения констант, выходы первой группы которого соединены соответственно с информационными входами регистра первого макрокоэффициента множимого, а выходы второй группы — соответственно с информационными входами регистра второго макрокоэффициента лножимого, выходы регистра второго макрокоэффициента множителя соединены соответственно с вторыми входами второго блока умножения по модулю р, выходы которого соединены соответсвенно с первыми входами элементов И шестой группы, выходы которых соединены соответственно с входами четвертой группы сумматора по модулю р, входы пятой группы которого соединены с выходом третьего элемента И, а выходы — соответственно с информационными входами регистра множителя, вторые входы элементов И пятой и шестой групп объединены и являются третьим входом синхронизации устройства, третий вход третьего элемента И соединен с вторыми входами элементов И третьей и четвертой групп и является четвертьм входом синхронизации устрой тва, управляющие входы первого, второго и третьего триггеров объединены и

962942

20

Составитель Л. Медведева

Редактор Н. Гришанова Техред Т.Фанта К оррек тор Л. Бокша н, Эака э 7 51 4/69

Тираж 731 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Филиал ПНП Патент, r.Ужгород, ул. Проектная, 4 являются пятьи входом синхронизации устройства.

Источники информации, принятые во внимание при экспертизе

1. Авторское

9 550636, кл. G

2. Авторское

Р 579617, кл. G (прототип) . свидетельство СССР

06 F 7/52, 1977. свидетельство СССР

06 F 7/72, 1975