Устройство для умножения в системе остаточных классов Советский патент 1982 года по МПК G06F7/72 

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

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

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

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

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

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

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

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

20 унитарный код, причем выходы регистра множимого соединены соответственно с первыми входами элементов И первой группы, вторые входы которых соединепЫ соответственно с 25 первьм входом синхронизации устройства, первым входом первого элемента И и управляющими входами регистра первого макрокоэффициента мно«:имогс1 и регистра второго макрокоэффициен30та множимого, выходы регистра первого макрокоэффициента множимого соединены соответственно с первыми входами первого и второго блоков VM ножения по модулю р, вьаходы регистр второго макрокоэффициента множимого соединены соответственно с первыми входами третьего блока умножения по модулю р, вторые входы которого соединены соответственно -с выходами регистра т1-;рвого макрокоэффициента множителя и вторыми входами пе вого блока умножеиля по модулю р, вы хоцы регистра множителя соединены соответственно с первыми входами элементов И второй группы и являютс выходами устройства, вторые входы элементов И второй группы соединены с вторым входом Синхронизации устро ства/ входом элемента задержки, с первым входом второго элемента И и управляющими входами регистра перво макрокоэффициента множителя и регис второго макрокоэффициента множителя выходы элементов И первой группы сое динены соответственно с входами.пре образователя двоичного кода в уни; гарный код, управляющий выход .которого соединен с вторыми входами пер вого и второго .элементов И, выходы : которых соединены соотВ;етств.ённ.о. с информационными входами первого и второго триггеров, единичный .выход третьего триггера соединен с третьим входом второго элемента И, единичные выходы первого и второго триггеров. соединены еоответственно : с первым и вторым входами третьего элемента И, выходы регистра.памяти соединены соответственно с перввыми входами элементов И третьей группы, вьаходы к горых соединены соответственнос входами первой группы сумматора по модулю р, входы второй группу которого соединены соответственно с , выходами элементов И пятой группы, первые входы которых соединены .соответственно с выходами.третьего блр .ка умножения по модулю р, входы третьей группы сумматора по модулю р соединены соответственно с выходами элементов И четвертой группы, входы которых соединены соответствен но с выходами регистра первого макрокоэффициёнта множителя, выходы элементов И второй группы соединены соответственно с входами преобразователя двоичного кода в унитарный, ЁькоДы которого соединены соответственно с входами второго блока.хранения констант, выходи первой группы которого соединены соответственно с информационными входами регистр первого макрокоэффициента множителя информационные входы регистра второго макрокоэффициента множителя сое динены соответственно с выходами вто рой группы второго блока хранения констант, выходы преобразователя дво ичного кода в унитарный соединены соответственно с входами первого блока хранения констант, выходы первой группы которого соединены соответственно с информационными входами регистра первого макрокоэффициента множимого, а вых.оды второй группы - соответственно с информационными входами регистра второго макрокоэффициента множимого, выходы регистра второго макрокоэффициента множителя соединены соот-ветственно с вторыми входами второго блока умножения по модулю р, выходы которого соединены соответственно с первыми входами элементов И шетсой группы, выходы которых соединены соответственно с входами четвертой группы сумматора по модулю р, входы ПЯТОЙ группы которого соеди цены с выходом третьего элемента И, . а выхОды - соответственно с информационными входами регистра множителя, вторые входы элементов И пятой и шестой групп Объединены и являются третьим входом синхронизации устройства, третий вход третьего элемента И соединен с. вторыми входами эл.ементов И третьей и четвертой групп и является четвёртым входсм синхронизации устройства, управляющие входы первого, второго и третьего триггеров объединены и являются пятым входом синхронизации устройства. На чертеже представлена 4Ункциональная схема устройства, Устройство содержит регистр 1, множимого/ регистр 2 множители/ эле менты И 3 и 4,.преобразователь 5 двоичного кода в у нитарный кол/ блоки б и 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, вторые входы которых соединены соответственно с входом 30 синхронизации устройства, первьм входом элемента И 21 и управляющими входами регистра 8 первого макрокоэффициента множимого и регистра 9 второго макрокоэффициента множимого, выходы регистра 8 первог макрокоэффициента множимого соединены соответственно с первьлми входами блоков 12 и 13 умножения по модулю р, выходы регистра 9 второго макрокоэффициента множимого соединены соответственно с первыми входами блока 14 умножения по мэдулю р, вторые входы которого соединены саэответственно с выходами регистра макрркоэффициента множителя и вторым входами блока 12 умножения по модулю р, выходы регистра 2 множителя соединены соответственно, с первыми входами элементов И 4 и являются вы ходами 35 устройства, вторые входы элементов И 4 соединены с входом 31 синхронизации устройства, с входом эпемента 27 задержки, с первым входом элемента и 22 и с управляющими входами регистра 10-первого макроко фициен1:а множителя и регистра 11 вт рого макрокоэффициента множителя, выходы элементов;, И 3 соединены соот ветственно с входами преобра-збватёля 5 двоичного кода в унитарный код управляющий выход которого соединен с вторыми входами элементов И 21 и выхбды которых соединены соотвётственно с информационными входами три геров 23 и 24, единичный выход триг гера 2б соединен с третьим входом элемента И 22, единичные выходы триггеров 23 и 24 соединены соответ ственно с первым и вторым входами элемента И 25, выходы регистра 15 памяти соединены соответственно с первыми входами элементов И 16,. выходы которых соединены соответствен но с входами первой группы сумматор 20 по модулю р, входы второй группы которрго соединены соответственно с выходами элементов И 17, первые . входы которых соединены соответствен но с .выходами блока 14 умножения по 1ЛЭДУЛЮ р, входы третьей группы сумNHTOpa 20 по модулю р соединены соответственно с выходами элемё;|1.тов И 18, первые входы которых-.соединены соответственно с выходам регистра 10 первого макрокоэффициёнта множ теля, выходы элементов и 4 соединенл соответственно с входами преобразователя 5 двоичного кода в унитарный, выходы которого соединены соответственно с входами блока 7 хранения констант, выходы первой группы которого соединены соответственно с информационными входами регистра 10 первого макрокоэффициента множителя, информационные входы-регистра 11 второго макрокоэффициента множителя соединены соответственно с выходами второй группы блока 7 хранения констант, выходы преобразрвателя 5 двоичного кода в унитарный соединены соответственно с вхрдами блока 6 хранения констант, выходы первой группы которого соединены соответственно с информационными входами регистра 8 первого макрокоэффициента множимого, а выходы второй группы - соответственно с информационными входами регистра 9 второго макрокоэффициента множимого, выходы регистра 11 второго макрокоэффи«иента множителя соединены соответственно с вторыми входами блока 13 5 1ножения по модулю р, ЕЫ-. ходы которого соединеньа- соответственно с первыми входами элементов И 19, выходы которых соединены соответственно -с входами четвертой группы сумматора 20 по модулю р, вход пятой группы которого соединены с ЕЫходс 1 элемента И 25, а выходы соответственно с информационными входами регистра 2 множителя, вторые входы элементов И 17 и 19 объединены и являются входом 32 синхронизации устройства, третий вход элемента И 25 соединен.с вторыми входами элементов И 16 и 18 и являются входом 33 синхронизации устрой- ства, управляющие входы триггеров 23, 24 и 26 соединены н .являются входом 34 синхронизации устройства. В основу работы устройства положен: известный алгоритм умножения с разложением сомножителей, на макроко-эффициенты, суть которого состоит в следующем. Если рабочие основания системы разбить на две группы, такие, что V Р, ( к. % Р) , то любое число, лежащее в диапазоне О, f , можно представить в виде А + % где А - частное от деления числа А на Р (первый макрокоэффициент) ; R.2. остаток от деления числа А на Р (второй макрокоэффициент) . Умножение двух чисел можно производить не- в диапазоне р, а в диапазоне р с сокращением произведения на 5. Пусть А - множимое, В - множитель. Представим их в виде: А А,В ь а,р,+ В. , Тогда {произведение чисел найдется следующим образом: ДВ. А В Р4АлВаР-1-|-А7В-1Рз..В2 Я р АВ „. AgBg о -АлВ75 р Последний член---«.и его можно от бросить. Так как В, « Р р, второй член запишем в виде (AibiMiBOP DP . D -1,)2, где иС - -p--AiB -D Устройство работает следующим образом. ; На регистры 1 и 2 поступают множимое и множитель в виде двоичных .кодов остатков по всем основаниям системы остаточных классов. Дальнейшая работа происходит по тактам. Первый такт. Разложение множимого А на макрокоэффициенты А и А. На входы элементов И 3 и вход. 30 устройства подается сигнал, раз решающий преобразование операнда А. Число А из регистра 1 через группу элементов И 3 поступает на преобраз ватель 5, содержащий дешифратор код с выхода котрого поступает на вход блока 6, с выхода которого в виде м коэффициентов и А заносится соот ветственно в регистры 8 и 9, так как 1и их управляющих, входах есть разре цЕющий сигнал с входа 30 устройства Второй такт. Разложение множителя В на макрокоэффициенты В и В. Разложение происходит аналогично сигналу с входа 3i устройства. Значение В и В запоминаются на регистрах 10 и 11. Одновременно в первом и втором тактах производится анализ знаков сомножителей преобразователем 5 с иэлью коррекции знака результата в случае, если оба сомножителя отрицательны. Коррекция осуществляется элементами И 21 и 22 и триггерами 23 24 и 26. Здесь принята искусственная форма представления чисел в ситеме остаточных классов (имеется в виду, что одно, КЗ оснований системы четное в частном случае Р 2) . Тогда отрицательные числа лежат в диапазоне 0;jV2-l, положительные в диапазоне р/2 + 1; f/2-l, в качестве нуля системы принято число f/2. Перевести число из одного диапазо на в другой можно, прибавив к числу или вычтя из него константу jVjZ, котс ая по основанию Р имеет остаток сД. 1, а по остальным основаниям нули. При разложении отрицательного числа на управляющем выходе преобразователя 5 появляется сигнал, который, пройдя через первый злемент И 21 по сигналу с входа 30 устройства, запоминается на триггере 23, если преобразуемое отрицательное число А, или, пройдя через элемент И 22 по сигналу с входа 31 устройств запоминается на триггере 24, если преобразуемое отрицательное число число в. в результате элемент И 25 будет гюдготовлен для прохождения единичного сигнала, (синала поправки) на пятый вход сумматора 20. Поскольку регистр 2 и преобразователь 5 используется не только для разложения множителя В, но и для разложения промежуточного значения величины ./. р,т, то для исключения ложного срабатывания элемента VI 22 к триггера 24 сигнал с входа 31 устройства, задержанный на время чуть большее времени срабатывания преобразователя 5, элементом 27 задержки перебрасывает в момент преобразования числа В в триггер 26, закрывая тем самым элемент И 22 для повторного срабатывания при преобразовании величины D. Третий такт. Вычиление величин У 3) A-iajL+Agbi Р - р в блоках 13 и 14 и сумматоре 20. В результате в регистре 2 оказывается значение D/P по сигналу с входа 32 устройства. Четвертый такт. Разложение величины D/2 на макрокоэффициенты (D и D), которые запоминаются на триггерах 10 и 11. Пятый такт. Вычисление величины D. Вычисление производится с помощью блока 12, регистра 15 памяти, элементов И 16 и 1§, сумматора 20 и элемента И 25 по сигналу с входа 33 устройства, в результате чего произведение заносится на регистр 2, с выходи которого поступает на выход 35 устройства. Сигналом с входа 34 устройства триггеры 23, 24 и 26 устанавливаются в исходное положение: триггеры 23 и 24 - в нулевое состояние, триггер 26 - в единичное. Перемножение двух чисел-в известном устройстве выполняется не менее, чем за 10 тактов. Таким образом, предлагаемое устройство позволяет повысить быстродействие в два раза по сравнинию с известны . Формула изобретения Устройство для умножения в системе остаточных классов, содержащее регистр множимого, регистр множителя, блок хранения констант, блок

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

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

первого и второго триггеров, единич- ный выход третьего триггера соединен с третьим входом второго элемента И, ,

единичные ВЕЛХОДЫ первого и второго триггеров соединены соответственно с первым и вторым входами третьего

элемента И, выходы регистра памяти соединены соответственно с первыми входами элементов И третьей группы, выходы которых соединены соответственно с входами первой группы сумматора по модулю р, входы второй группы которого соединены соответст0венно с выходами элементов И пятой группы, первые входы которых соединены соответственно с выходами третьего блока умножения по модулю р, входы третьей группы сумматора по

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

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

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

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

5

являются пятьм входом синхронизации устройства.

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

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

свидетельство СССР 06 F 7/72, 1975