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

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

-и ячейке блока вычисления интервального номера произведения входы узла суммирования вычетов по модулю т- соединены с соответствзпощими выходами второго блока хранения констант, а выход подключен к входу первого регистра и первым входаммодульного умножителя и модульного вычитателя, выход первого регистра соединен с вторым входом модульного умножителя, выход которого соединен с входом второго регист.;.ра, выход которого соединен с вторым входом модульного вычитателя, входы третьего и четвертого регистров подключены к выходам соответственно формирователя и модульного вычитателя, а выходы - к входам модульного сумматора,выход которого соединен с входом пятого регистра, выходы пятых регистров всех ячеек блока вычисления интервального номера произведения подключены к входам блока деления на дополнительньй модуль и блока анализа интервального номера произведения, выход регистра кода первого операнда подключен к второму информационному входу регистра кода второго операнда, выход регистра интервального индекса первого операнда подключен к первому информационному входу регистра интервального индекса второго операнда, информационные входы реристров кода и интервального индекса первого операнда соединены с соответствунщими входами устройства, третий информационный вход регистра кода второго операнда и второй информационный вход регистра интервального индекса второго операнда соединены с соответствующими входам устройства, выход регистра кода младшей части произведения и выходы чет-вертьк регистров (1 + 1)-й и (|с + 2)-и ячеек блока вычисления, интервального номера произведения соединены с выходами младших разрядов произведения устройства, выход блока суммирования вычетов по ( К + 1)-му модулю системы счисления соединен с выходами старшей части произведения устройства, выход блока анализа интервального номера произведения является выходом признка переполнения устройства, первый управляющий вход устройства подключен к входам управления чтением регистров кода и интервального индекса первого операнда, второй управляющий вход устройства подключен к входам управления чтением регистров кода и интервального индекса второго операнда, третий и четвертый управляющие входы устройства подключены к входам управления чтением соответственно первого и второго блоков хранения констант, пятый управлякщий вход устройства подключен к входу управления чтением регистра младшей части произведения и входу обнуления регистра интервалного индекса второго операнда, шестой управляющий вход устройства подключен к входу управления чтением вспомогательного регистра.

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

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

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

Наиболее близким к предлагаемому является устройство для умножения чисел в системе остаточных классов, содержащее регистр памяти, блок модульных умножителей, блок модульньЬс сумматоров и два блока для обработки соответственно первого и второго операндов, имеющих одинаковую структуру и состоящих из регистра операнда, формирователя поправки операнда, вычитателя поправки операнда, блока деления и формирователя поправки преобразованного операнда, при этом выход регистра операнда подключен ко входу формирователя поправки операнда и к первому входу вычитателя поправки операнда, второй вход которого соединен с первым выходом формирователя поправки операнда и с выходом формирователя поправки преобразованного операнда, а выход - со входом блока деления данного операнда, первый выход которого подключен к первому входу формирователя поправки преобразованного первого операнда, второй вход формирователя поправки преобразованного первого операнда подключен ко второму выходу формирователя поправки второго операнда, а второй вход формирователя поправки преобразованного второго операнда подключен ко второму выходу формирователя поправки первого операнда, первый и второй входы блока модульных умножителей подключены соответственно к первым выходам блоков деления первого и второго операндов, вторые выходы которых соединены со вторым и третьим входами блока модульных сумматоров соответственно, первый вход которого через регистр памяти соединен с выходом блока модульных умножителей. Это устройство формирует произзедение двух дробей за четыре последовательных этапа, длительность которых определяется временем выполнения операции расширения диапазонаС2. Однако быстродействие известно4.ГО устройства существенно ограничивается наличием в реализуемом алгоритме последовательных этапов. Кроме того, известному устройству присуща большая для рассматриваемого

класса устройств абсолютная погреш- ность (до М. Пт. ; I

m , ..., модули системы счисления) , невозможность работы с числами разных знаков, а также с целыми числами.

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

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

системы счислет

1 ния, формирователь ранга и регистр

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

блока модульных умножителей по ост системы счиснованиям т.

1 ления, выход которого соединен со

входом формирователя ранга, содержит регистры интервальных, индексов

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

5 информационные входы первого блока хранения констант соединены с выходами регистров кодов первого и второго операндов, информационные

3

входы второго блока хранения констант соединены с выходами регистров кода и интервального индекса второго операнда, информационный вход регистра кода младшей части произведения подключен к выходу блока модульных умножителей по основаниям hi , ,..,1 системы счисления, а выход - к первому информационному входу регистра кода второго операнда, информационный вход вспомогательного регистра подключен к выходу первого блока хранения констант, первый выход блока деления на дополнительный модуль соединен со входом регистра кода старшей части произведения, а второй выход - со входом блока суммирования вычетов ,по (1 + 1)-му модулю системы счисления, при этом блок вычисления интервального номера произведения содержит (V + 2) ячеек, i-я ячейка блока вычисления интервального номера произведения ( i 1,..., 1; ) содержит узел суммирования вычетов по модулю т- , узел задержки, модульный умножитель, модульный вычитател два модульных сумматора и пять регистров, j-я ячейка блока вычисления интервального номера произведения ( j 1 + 1, fc + 2) содержит узел суммирования вычетов по модулю т-, модульный умножитель, модульный вычитатель, модульный сумматор и пять регистров, причем в i-й ячейке блока вычисления интервального номера произведения входы узла суммирования вычетов по модулю W; соединены с соответствуклцими выходами вспомогательного регистра и второго блока хранения констант, входы узла задержки соединены с выходом регистра кода второго операнда и информационным входом регистра кода первого операнда, входы модульного умножителя соединены с вькодами узла суммирования вьиетов по модулю т и узла задержки, а выход подключен ко входу первого регистра, выход которого Подключен ко входу второго регистра и первому входу первого модульного сумматора, второй вход которого соединен с выходом второго регистра, входы модульного вычитателя соединены с выходами формирователя ранга и узла суммирования вычетов по модулю т , выходы модульного вычитателя и первого модульного

92544

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

f5 первого регистра соединен со вторым входом модульного умножителя, выход которого соединен со входом второго регистра, выход которого соединен со вторым входом модульного вычита20 теля, входы третьего и четвертого регистров подключены к выходам cor ответственно формирователя и модульного вычитателя, а выходы - ко входам модульного сумматора, выход

5 которого соединен со входом пятого

регистра, выходы пятых регистров - всех ячеек блока вычисления интервального номера произведения подключены ко входам блока деления на

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

второго операнда, выход регистра

интервального индекса первого операнда подключен к первому информационному входу регистра интервального индекса второго операнда, информаQ ционные входы регистров кода и интервального индекса первого операнда соединены с соответствующими входами устройства, третий информационный вход регистра кода второго

5 операнда и второй информационный вход регистра интервального индекса второго операнда соединены с соответствукедими входами устройства, выход регистра кода младшей части

0 произведения и выходы четвертых регистров ( + 1)-й и (1 + 2)-й ячеек блока вычисления интервального номера произведения соединены с выходами младших разрядов произведения устройства, выход блока суммирования вь1четов по ( k + 1)-му модулю системы счисления соединен с выходами старшей части произведения устройства, выход блока анализа интерваль ного номера произведения является выходом признака переполнения устройства, первый управляющий вход устройства подключен ко входам упра ления чтением регистров кода и инте вального индекса первого операнда, второй управляющий вход устройства подключен ко входам управления чтением регистров кода и интервального индекса второго операнда, третий и четвертый управляющие входы устройства подключены ко входам управления чтением соответственно первого и второго блоков хранения констант, пятый управляющий вход устройства подключен ко входу управления чте-: нием регистра младшей части произведения и входу обнуления регистра интервального индекса второго операнда, шестой управлякяций вход устройства подключен ко входу управления чтением вспомогательного регистра. На фиг. 1 приведена структурная схема устройства для умножения чисе в системе остаточных классов; на фиг. 2 и 3 - структурные схемы соот ветственно i-й ( i 1, 2, ..., Я) и J-и ( j t.+ 1, К + 2) ячеек блок вычисления интервального номера произведения. Устройство содержит регистр 1 кода первого операнда, регистр 2 .интервального индекса первого операнда, регистр 3 кода второго операнда, регистр 4 интервального индекса второго операнда, блок 5 модульного умножения по основаниям п, ...,т системы, счисления, первый и второй блоки 6 и 7 хранения констант, регистр 8 кода младшей части произведения, вспомогательный регистр 9, формирователь 10 ранга, блок 11 вычисления интервального номера произведения, блок 12 делени на дополнительный модуль, блок 13 анализа интервального номера произв дения, регистр 14 кода старшей част произведения, блок 15 суммирования вычетов по (( + 1)-му модулю систем счисления, вход 16 кода первого опе ранда, вход 17 интервального индекс первого операнда, вход 18 кода вто рого операнда, вход 19 интервального индекса второго операнда, первый второй, третий, четвертый, пятый, шестой управляющие входы 20-25, выходы 26.1 и 26.2 младшей части произведения, выходы 27.1 и 27.2 старшей части произведения, выход 28 признака переполнения. Блок 11 содержит (1с + 2) ячеек, i-я ( i 1, ..., k ) ячейка блока 11 (фиг. 2) содержит узел 29 суммирования вычетов по узел 30 задержки, модульный умножитель 31, модульный вычитатель 32, модульные сумматоры 33 и 34, регистры 35-39. Узел 29 содержит сумматоры 40 и регистры 41. Узел 30 .содержит регистры 42, j-я (j 1 + 1, V.+ 2) ячейка блока 11 (фиг. 3) содержит узел 43 суммирования вычетов по mocfm- , модульный умножитель 44, модульный вычитатель 45, модульный сумматор 46, регистры 47-51. Узел 43 содержит сумматоры 52 и регистры 53. В регистре 1 хранится нормированный остаточньй код (l-f,х. , ...,о1) первого операнда ,АА| в системе с модулями гл , ,.., . В регистре 2 хранится интервальный , индекс I (А) первого операнда (йС,- ,-t ч А М. М..Г(А)/ , V - фиксированное натуральное где число-, 1х|т - неотрицательный вычет, сравнимый с величиной х по модулю m . В регистре 3 хранится нормированный код (Л1,Ч it.-k второго операнда Be , «j,, в системе с модулями т,тп , В регистре 4 хранится интервальный индекс I (В) второго операнда. Блок 12 осуществляет деление на дополнительный модуль п 15 осуществляет суммирование вычетов по модулю k+i 2 V 1« Выход 54 формирователя 10 ранга подключен ко входам вьгчитателей 32 i -х ячеек и регистру 49 i-X ячеек блока 11. Входы узла 29 1 -и ячейки блока 11 соединены с выходами 551 и 56i регистра 9, и блока 7 соответственно. Выходы узла 43 j-й ячейки блока 11 соединены с выходом 56-j блока 7. Выход 57 регистра 3 и вход 16 соединены со входами узлов 30 i -х ячеек бло ка П. Выход 58 регистра 8 и выход 59 (образованный выходами регистров 50 j-x ячеек) блока 11 соединены с выходами 26,1 и 26.2 устрой ства. Выходы регистра 14 и блока 15 соединены с выходами 27.1 и 27. устройства. Выход блока 13 соедине с выходом 28 устройства. Выходы регистров 39 1-х ячеек и регистров 51 j-X ячеек блока 11 образуют выход 60 блока 11, соединенньй со входами блоков 12 и 13. Блок 13 предназначен для формирования по входным величинам -0 , ..., + признака П мультипликативного переполнения по формуле о, если 1. N(-+2 k+Ztm ИЛИУ;(л)2 r+ 2 : .1, в остальных случаях Устройство работает следукяцим образом. Цифры е , ., ,f oi операнда А через вход 16 устройства поступают в регистр 1 и блок 11, интерваль ный индекс I (А) операнда через вход 17 устройства поступает в регистр 2, а йнтервально-остаточнь1й код (/i,,i , ..., fth -k -t (В)) операнда В со входов 1 и 19 устройства поступает в регистры 3 и 4, после чего начинается первый такт работы устройства. По сигналам разрешения чтения информации, подаваемым со входов 20 и 21, нормированный остаточный код (, , .,,, ,с ) числа Н1м, с выхода регистра 1 поступает входы блоков 5 и 6, а нормированны остаточный код (,ft , ..., fk1 числа I2i(;y с выхода регистра 3 подается на входы блоков 5, 6 и 11 Кроме того, интервально-остаточный код (, л 1,1 1 I (2) опб ранда В поступает на входы блока 7, а интервально-остаточный код , ..,, « k k ,1 (А)) операвда А пере- дается в узел 30. На входе блока 5 формируется нормированньа остатсочный код (fi,v, ... KJ( ) числа , где С АВ, T.i.,k/bi,. 1 1, , , который с выхода блока 5 передается в регистр 8 и на вход формирователя 10 ранга, а на выходе блока 6 и {-м выходе 8 4 7 формируются наборы вычетов блока «1 , .. i,,1., гле а.г 1,...,1 и слагаемые сумм дв) которые по сигналам отпирания выходов, поступающим в данном такте по входам 22 и 23,передаются соответственно в регистр 9 и в узлы 29 и 43 блока 11. Начиная со второго такта работы устройства, формирователь 10 и узлы 29 и 43 приступают к вычислению соответственно нормированного ранга Р(1С1м1 ) числа С./ и величины Z.(B) (i 1, ,.о, + 2). Параллельно с этим содержимое регистра 3 поступает на входы блоков 7 и 11, а содержимое регистра 4 подается на вход блока 7. На его выходах формируются слагаемые сумм И(А),.,., (А) t определяемых так же, как и для числа В; в узел 30 записывается цифра oi{ . Наряду с этим, по сигналу, подаваемому по входу 24, содержимое регистра 8 (нормированный остаточный код) ( , ,,,, ) числа |С|д подается на выход 26/1 устройства и в регистр 3, а регистр 4 обнуляется. На третьем такте работы устройства узлы 29 и 43 начинают вычисление величин Z (А) ,,.. .,Z (А), а блок 7 по входному интервально-остаточному коду с jpi , 0), поступающему с выходов регистров 3 и 4, формирует соответствукяцие слагаемые

считываемыми нз регистра 9, по сигналу, подаилемому на вход 25 устройства, передаются в узлы 29 и 43. Происходит поступление из регистра 3 в блок 11 очередного остаточного кода.

По истечении (Т + 1)-го такта на выходе узла 29 появится величина (В), а на последующих двух тактах величины ,-(А) и 2 (С) . Аналогично, по истечении (Т + 1)-го и (т + 2)-го тактов на выходе узла 30 появятся соответственно цифры и /5,), .

На (т + 2)-ом такте работы устройства модульный умножитель 31 по входным величинам i.- (В) и , V, определяет вычет

гК

(6)А,,.,(И.-.|,

который с выхода умножителя 31 передается в регистр 35. В то же время величина 2(В) ( 1, ) с выхода узла 43 передается в регистр 47.

На (Т + 3)-ем такте вычет Z,. из регистра 35 передается в регистр 36, а в регистр 39 поступает величина Zl { , Zi (Л) Ai, 1.) , получаемая умножителем 31. Параллельно с этим модульный умножитель 44 по входным величинам (А} и Zj(B) находит вычет Zj lMfcZjC/ JzIjCeil. который с выхода умнодителя 44 передается в регистр 48.

На (Т + 4)-ек такте ранг f ((С|уц) числа |С| с выхода формирователя 10 подается на входы вычитателей 32 и 45, на другие входы которых поступают величины (C), а содержимое регистров 35 и 36 подается на входы сумматоров 33. В результате на выходах вычитателей 32 и сумматора 33 сформируются соответственно величины j5(|CUj-,(С)|„. и |2.;+ 2.(п,. , которые записываются в регистры 37 и 38, В ( 1)-йи (V.+. 2)-и ячейках ранги Х1С1м) запоминаются в регистрах 49, а вычитатели 45 по входным величинам и j(C) определяют вычеты и (Sj )|щ. , которые передаются в регистры 50. Величина Г представляющая собой в случае отсутствия переполнения при умножении А на В интегральный индекс Г (С), с выхода регистра 50 подается на выход 26.2 устройства.

На (Т + 5)-ем такте сумматоры 34 (46) складывают по модулю (rr,) содержимое регистров 37 и 38 (49 и 50), завершая тем самьм вычисление остаточного кода (-0 , ..., ) интервального номера N(C) произведения С АВ. При этом цифра )( i 1, ..., k + 2) с выхода сумматора 34 (46) передается в регистр 39 (51)

На (Т + 6)-ом такте работы устройства остаточный код (V «««э V.) интервального номера N (С) подается на входы блоков 12 и 13 в соответствии с выражением (I) на своем выходе, являющемся вьгхо.1,ом

п 28 устройства, формирует признак мультипликативного переполнения. На выходах блока 12 соответственно формируются нормированный остаточ- ный код (у,ц , ..., TV.K числа I С I дд и набор вычетов

)В § , ...

V+l

м,

м

(l

.

где е.,

Vb

я, .

TfHc

т..

г

через х обозначается целое число,

ближайшее к х .Код ( )

с первого выхода блока 12 поступает в регистр 14, а набор вычетов , ..., |j со второго выхода блока 13 подается на вход блока 15, который в ходе очередных Т модульных тактов определяет интервальный индекс I (С) старшей части С произведения С АВ.

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

Проверка показывает, что в рамках алгоритма, реализуемого известным устройством, максимально возможное быстродействие составляет И+ЗЗЕо г Г модульных операций, в то время как предлагаемое устройство срабатывает за 6+2jeoi%2 ( + 1) модульных

операций. Конвейерная структура предлагаемого устройства увеличивает его- пропускную способность до одного умножения двух дробей или двух целых чисел с анализом на переполнение за три модульных такта.

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ, содержащее регистры кодов первого и второго операндов, блок модульных умножителей по основаниям т ,...,ni системы счисления, формирователь ранга и регистр кода старшей части произведения, выход которого соединен с соответствующим выходом устройства, выходы регистров кодов первого и второго операндов подключены к входам блока модульных умно.жителей по основаниям т ,..., т системы счисления, вькод которого соединен с входом формирователя ранга, отличающееся тем, что, с целью повьппения его быстродействия, и расширения функциональных возможностей путем обеспечения возможности работы с числами различных знаков, устройство содержит регистры интервальных индексов первого и второго операндов, первый и второй блоки хранения констант, регистр кода младшей части произведения, вспомогательный регистр, блок вычисления интервального номера произведения, блок деления на дополнительный модуль, блок суммирования вычетов по ( . + 1)-му модулю системы счисления, блок анализа интервального номера произведения, причем информационные входы первого блока хранения констант соединены с выходами регистров кодов первого и второго операндов, информационные,входы второго блока хранения констант соединены с выходами регистров кода и интервального индекса второго операнда, информационньй вход регистi ра кода младшей части произведения подключен к выходу блока модульных (Л умножителей по основаниям п t cиcтe вJ счисления, а выход - к первому информационному входу регистра кода второго операнда, информационный вход вспомогательного регистра подключен к выходу первого блока хранения констант, первый выход блока деления на дополнительный Ф ю ел модуль соединен с входом регистра кода старшей части произведения, а второй вькод - с входом блока суммирования вычетов по ( 1)-му модулю 4 систв счисления, при этом блок вычисления интервального номера произведения содержит (k + 2) ячеек, я ячейка блока вычисления интервального номера- произведения ( ; 1, ..., k) содержит узел суммирования вычетов по модулю hi, узел задержки, модульный умножитель, модульный вычитатель, два модульных сумматора и пять регистров, j-я ячейка блока вычисления интервального номера произведения ( т + 1.

25

Фиг. 1