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

(19) ПО тиво СС СОВ, го и АРСТНЕННЫЙ КОМИТЕТ СССРЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ ОПИСАНИЕ ИЗОБРЕ АВТОРСКОМУ СВИДЕТЕЛЬСТВУ(прототип).(54) (57) УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯЧИСЕЛ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАСсодержащее регистры кодов первовторого операндов, блок модульнумножигелей по основаниям вюсистемы счисления, формировательранга и регистр кода старшей частипроизведения, выход которого соединен с соответствующим выходом устройства, выходы регистров кодовпервого и второго операндов подключены к входам блока модульных умножителей по основаниям щ в 1,системы счисления, выход которогосоединен с входом формирователяранга, о т л и ч а ю ш е е с я темчто; с целью повышения его быстродействия,и расширения функциональныхвозможностей путем обеспечения возможности работы с числами различныхзнаков, устройство содержит регистры интервальных индексов первого ивторого операндов, первый и второйблоки хранения констант, регистркода младшей части произведения,вспомогательный регистр, блок вычисления интервального номера произведения, блок деления на дополнительный модуль, блок суммирования вычетов по ( Ъ + 1)-му модулю системы счисления, блок анализа интервального номера произведения, причем информационные входы первого блока хранения констант соединены с выходами регистров кодов первого и второго операндов, информационные,входы второго блока хранения констант соединены с выходами регистров кода и интервального индекса второго операнда, информационный вход регистра кода младшей части произведенияе подключен к выходу блока модульных умножителей по основаниям щ в 1,усистемы счисления, а выход - к первому информационному входу регистра кода второго операнда, информационный вход вспомогательного регист- - ра .подключен к выходу первого блока фаф хранения констант, первый выход ЭвМ блока деления на дополнительный1 модуль соединен с входом регистра кода старшей частипроизведения, а фф второй выход - с входом блока сумми- р рования вычетов по ( 1 с + 1)-му модулюсистемы счисления, при этом блок вычисления интервального номера произведения содержит ( к + 2) ячеек, 1-я ячейка блока вычисления интервального номера произведения (:1 = ф1, , В ) содержит узел суммирования вычетов по модулю Ь узел1 задержки, модульный умножитель, модульный вычитатель, два модульныхсумматора и пять регистров, 1-я ячейка блока вычисления интервального номера произведения ( т =. 1 с.+ 1.В + 2) содержит узел суммирования вычетов по модулю в, модульный умно- житель, модульный вычитатель, модульный сумматор и пять регистров, причем в ;-й ячейке блока вычисления интервального номера произведения входы узла суммирования вычетов по модулю а, соединены с соответствующими выходами вспомогательного регистра и второго блока хранения констант, входы узла задержки соединены с выходом регистра кода второго операнда и информационным входом регистра кода первого. операнда, входы модульного умножителя соединены с выходами узла суммирования вычетов по модулю ш. и узла задержки, в выход подключен к входу первого регистра, выход которого подключен к входу второго регистра и первому входу первого модульного сумматора, второй вход которого соединен с выходом второго регистра, входы модульного вычитателя соединены с выходами Формирователя ранга и узла суммирования вычетов по модулю щ; вьиоды модульного вычитателя и первого модульного сумматора подключены к входам соответственно третьего и четвертого регистров, выходы которых соединены с входами второго модульного сумматора, выход которого подключен к входу пятого регистра, в -й ячейке блока вычисления интервального номера произведения входы узла суммирования вычетов по модулю п соединены с соответствующими выходами второго блока хранения констант, а выход подключен к входу первого регистра и первым входаммодульного умножителя и модульного вычитателя, выход первого регистра соединен с вторым входом модульного умножителя, выход которого соединен с входом второго регист,;.ра, выход которого соединен с вторым входом модульного вычитателя, входы третьего и четвертого регистров подключены к выходам соответственно формирователя и модульного вычитателя, а выходы - к входам модульного сумматора, выход которого соединен с входом пятого регистра, выходы пятых регистров всех ячеек блока вычисления интервального номера произведения подключены к входамблока деления на дополнительныймодуль и блока анализа интервального номера произведения, выход регистра кода первого операнда подключен к второму информационному входу регистра кода второго операнда,выход регистра интервального индекса первого операнда подключен к первому информационному входу регистра интервального индекса второгооперанда, информационные входы регистров кода и интервального индекса первого операнда соединены с соответствующими входами устройства,третий информационный вход регистра кода второго операнда и второйинформационный вход регистра интервального индекса второго операндасоединены с соответствующими входамиустройства, выход регистра кодамладшей части произведения и выходычетвертых регистров ( % + 1)-й и(% + 2)-й ячеек блока вычисления интервального номера произведениясоединены с выходами младших разрядов произведения устройства, выходблока суммирования вычетов по( 1 + 1)-му модулю системы счислениясоединен с выходами старшей частипроизведения устройства, выход блока анализа интервального номерапроизведения является выходом признака переполнения устройства, первыйуправляющий вход устройства подключен к входам управления чтением регистров кода и интервального индекса первого операнда, второй управляющий вход устройства подключенк входам управления чтением регистров кода и интервального индексавторого операнда, третий и четвертый управляющие входы устройстваподключены к входам управления чтением соответственно первого и второго блоков хранения констант, пятыйуправляющий вход устройства подключен к входу управления чтениемрегистра младшей части произведенияи входу обнуления регистра интервального индекса второго операнда, шестой управляющий вход устройства подключен к входу управлениячтением вспомогательного регистра.1149254 фго устройства существенно ограничиИзобретение относится к вычисли-: тельной технике и предназначено для использования в быстродействующих вычислительных устройствах конвейерного типа, работающих н непозицион ных системах счисления.Известно устройство для умножения чисел в системе остаточных классов, содержащее регистры первого и второго операндов, регистр результата, .блок модульных .сумматоров, регистр сдвига и группы элементов И и ИЛИ с соответствующими связями 11.Однако быстродействие этого устройства является недостаточным, пос кольку оно, в сущности, реализует известный позиционный алгоритм умножения на один разряд.Наиболее близким к предлагаемому является устройство для умножения 20 чисел в системе остаточных классов, содержащее регистр памяти, блок мо.дульных умножителей, блок модульнь 1 х сумматоров и два блока для обработки соответственно первого и второго операндов, имеющих одинаковую структуру и состоящих из регистра операн" да, формирователя поправки операнда, вычитателя поправки операнда, блока деления и формирователя поправки преобразованного операнда, при этом выход регистра операнда подключен ко входу формирователя поправки операнда и к первому входу вычитателя поправки операнда, второй вход кото- З 5 рого соединен с первым выходом формирователя поправки операнда и с выходом формирователя поправки преобразованного операнда, а выход - со входом блока деления данного операнда, первый выход которого подключен к первому входу формирователя поправки преобразованного первого операнда, второй вход формирователя поправки преобразованного первого операнда подключен ко второму выходу формирователя поправки второго операнда, а второй вход формирователя поправки преобразованного второго операнда подключен ко второму выходу 50 формирователя поправки первого операнда, первый и второй входы блока модульных умножителей подключены соответственно к первым выходам блоков деления первого и второго 55 операндов, вторые выходы которых соединены со вторым и третьим входами блока модульных сумматоров соот-. ветственно, первый вход которого через регистр памяти соединен с выходом блока модульных умножителей, Это устройство формирует произведение двух дробей за четыре последовательных этапа, длительность которых определяется временем выполнения операции расширения диапазона 21,Однако быстродействие известновается наличием в реализуемом алгоритме последовательных этапов. Кроме того, известному устройству прису"ща большая для рассматриваемогокласса устройств абсолютная погрешность (до 3/М 1,- , гдекй,щ, , в 1, - модули системы счисления), невозможность работы с числами разных знаков, а также с целыми числами,Целью изобретения является повышение быстродействия и расширениефункциональных возможностей устройства путем обеспечения возможностиработы с числами различных знаков.Поставленная цель достигаетсяза счет того, что устройство дляумножения чисел в системе остаточных классов, содержащее регистрыкодов первого и второго операндов,блок модульных умножителей по основаниям е , е системы счисления, формирователь ранга и регистр .кода старшей части произведения,выход которого соединен с соответствующим выходом устройства, выходырегистров кодов первого и второгооперандов подключены ко входамблока модульных умножителей по основаниям в, , в, системы счисления, выход которого соединен совходом формирователя ранга, содержит регистры интервальных индексовпервого и второго операндов, первыйн второй блоки хранения констант,регистр кода младшей части произведения, вспомогательный регистр, блоквычисления интервального номера произведения, блок деления на дополнительный модуль, блок суммированиявычетов по (1 с + 1)-му модулю системы счисления, блок анализа интервального номера произведения, причеминформационные входы первого блокахранения констант соединены с выходами регистров кодов первого ивторого операндов, информационныевходы второго блока хранения констант соединены с выходами регистров кода и интервального индекса второго операнда, информационный вход регистра кода младшей части произведения подключен к выходу блока модульных умножителей по основаниям,щ, системы счисления, а выход - к первому информационному входу регистра кода второго операнда, информационный вход вспомогательного регистра подключен к выходу первого блока хранения констант, первый выход блока деления на дополнительный модуль соединен со входом регистра кода старшей части произведения, а второй выход - со входом блока суммирования вычетов ;по (% + 1)-му модулю системы счисления, при этом блок вычисления интервального номера произведения содержит (1 + 2) ячеек,-я ячейка блока вычисления интервального номера. произведения ( 1 = 1 1 ) содержит узел суммирования вычетов по модулю щ узел задержки, модуль ный умножитель, модульный вычитатель два модульных сумматора и пять регистров,-я ячейка блока вычисления интервального номера произведения ( 1 = 1 с + 1, В + 2) содержит узел суммирования вычетов по модулю е, модульный умножитель, модульный вйчитатель, модульный сумматор и пять регистров, причем в 1-й ячейке блока вычисления интервального номера произведения входы узла суммирования вычетов по модулю Ф, соединены с соответствующими выходами вспомогательного регистра и второго блока хранения констант, входы узла задержки соединены с выходом регистра кода второго операнда и информационным входом регистра кода первого операнда, входы модульного умно- жителя соединены с выходами узла суммирования вычетов по модулю в, и узла задержки, а выход подключен ко входу первого регистра, выход которого подключен ко входу второго регистра и первому входу первого модульного сумматора, второй вход которого соединен с выходом второго регистра, входы модульного вычитателя соединены с выходами формирователя ранга и узла суммирования вычетов по модулю в выходы модульного вычитателя и первого модульного сумматора подключены ко входам соответственно третьего и четвертого регистров, выходы которых соединены со входами второго модульного сумматора, выход которого подключен ко входу пятого регистра, в 1 -й ячейке блока вычисления интервального номера .произведения входы узла суммирования вычетов по модулю в соединены с соответствующими выходами второгоблока хранения констант, а выходподключен ко входу первого. регистраи первым входам модульного умножителя и модульного вычитателя, выходпервого регистра соединен со вторымвходом модульного умножителя, выходкоторого соединен со входом второгорегистра, выход которого соединенсо вторым входом модульного вычита- О теля, входы третьего и четвертогорегистров подключены к выходам со-".ответственно формирователя и модульного вычитателя, а выходы - ковходам модульного сумматора, выход 25 которого соединен со входом пятогорегистра, выходы пятых регистроввсех ячеек блока вычисления интерьвального номера произведения подключены ко входам блока деления надополнительный модуль и блока анализа интервального номера произведения, выход регистра кода первогооперанда подключен ко второму информационному входу регистра кодавторого операнда, выход регистраинтервального индекса первого операнда подключен к первому информационному входу регистра интервальногоиндекса второго операнда, информа ционные входы регистров кода иинтервального индекса первого операнда соединены с соответствующимивходами устройства, третий информационный вход регистра кода второго 45 операнда и второй информационныйвход регистра интервального индексавторого операнда соединены с соответствующими входами устройства,выход регистра кода младшей частипроизведения и выходы четвертых регистров (В + 1)-й и (Ъ + 2)-й ячеекблока вычисления интервального номера произведения соединены с выходамимладших разрядов произведения устройства, выход блока суммированиявычетов по ( 1 + 1)-му модулю системы счисления соединен с выходамистаршей части произведения устройства, выход блока анализа интервального номера произведения являетсявыходом признака переполнения устройства, первый управляющий входустройства подключен ко входам управления чтением регистров кода и интервального индекса первого операнда,второй управлянзций вход устройстваподключен ко входам управления чте 10нием регистров кода и интервальногоиндекса второго операнда, третий ичетвертый управляющие входы устройства подключены ко входам управления чтением соответственно первого15и второго блоков хранения констант,пятый управляющий вход устройстваподключен ко входу управления чте-.нием регистра младшей части произведения и входу обнуления регистра20интервального индекса второго операнда, шестой управляющий вход устройства подключен ко входу управления чтением вспомогательного регистра,На фиг. 1 приведена структурнаясхема устройства для умножения чиселв системе остаточных классов; нафиг. 2 и Э - структурные схемы соответственно 1-й ( 1 = 1, 2, , 1 с)и -й (= 1+ 1, Ь. + 2) ячеек блока,)вычисления интервального номерапроизведения,Устройство содержит регистр 1кода первого операнда, регистр 2интервального индекса первого операнда, регистр 3 кода второго операнда, регистр 4 интервального индекса второго операнда, блок 5 модульного умножения по основанияме, ,щ, системы счисления, пер-40вый и второй блоки 6 и 7 храненияконстант, регистр 8 кода младшейчасти произведения, вспомогательныйрегистр 9, формирователь 10 ранга,блок 11 вычисления интервальногономера произведения, блок 12 деленияна дополнительный модуль, блок 13анализа интервального номера произведения, регистр 14 кода старшей частипроизведения, блок 15 суммированиявычетов по (1 + 1)-му модулю системысчисления, вход 16 кода первого операнда, вход 17 интервального индексапервого операнда, вход 18 кода второго операнда, вход 19 интервального индекса второго операнда, первый,второй, третий, четвертый, пятый,шестой управляющие входы 20-25, выЭ)хщ - неотрицательный вычет,сравнимый с величиной кпо модулю в .В регистре 3 хранится нормированный код (11 , 7, 1, ) второгооперанда 66 чМ , М "1 в системе смодулями щ, , е 1, . В регистре 4хранится интервальный индекс 1 (В)второго операнда, Блок 12 осуществляет деление на дополнительный модуль в 1, = . Блок 15 осуществляетсуммирование вычетов по модулю2+ 1 - 1, Выход 54 формирователя 10. ранга подключен ко входамвычитателей 32 1-х ячеек и регистру 49 1-х ячеек блока 11. Входыузла 29 1 -й ячейки блока 11 соединены с выходами 551 и 561 регистра9,и блокасоответственно, Выходыузла 43 1-й ячейки блока 11 соединены с выходом 56- 1 блока 7, Выход57 регистра 3 и вход 16 соединены где ходы 26.1 и 26.2 младшей части произведения, выходы 27. и 27.2 старшей части произведения, выход 28 признака переполненияБлок 11 содержит (1 с + 2) ячеек, 1-я ( 1 =. 1.. 1 ) ячейка блока 11 (фиг. 2) содержит узел 29 суммирования вычетов по по 3 в, узел 30 задержки, модульный умножитель 31, модульный вычитатель 32, модульные сумматоры 33 и 34, регистры 35-39. Узел 29 содержит сумматоры 40 и регистры 41. Узел 30 .содержит регистры 42, 1-я (1 =%+ 1, Ъ+ 2) ячейка блока 11 (фиг. 3) содержит узел 43 суммирования вычетов по од, модульный умножитель 44, мо 1 эдульный вычитатель 45, модульный сумматор 46, регистры 47-51. Узел 43 содержит сумматоры 52 и регистры 53.В регистре 1 хранится нормированный остаточный код (О,К,, 41) первого операнда АЕ -9, 11 М в системе с модулями в 1, , щ . В регистре 2 хранится интервальный, индекс 1 (А) первого операнда (с;1, =А М, )вПроверка показывает, что в рамкахалгоритма, реализуемого известнымустройством, максимально возможноебыстродействие составляет 1 1+3101модульных операций, в то время какпредлагаемое устройство срабатываеза 6+2 31 о ( + 1) модульных операций. Конвейерная структура пред-,лагаемого устройства увеличиваетего пропускную способность до одного умножения двух дробей илн 5 двух целых чисел .с анализом напереполнение эа три модульныхтакта.1149254 дакт аказ 1894/34 Тираж 710 ВНИИПИ Государстве по делам изобр 113035, Москва, Ж, одписноетета СССР го тенин и открытийРаушская наб., д. 4