Устройство для умножения

(19 (И 1 А 1 р 1) О 06 Р 7/52 ГО ПО ПР АВТОРСНОМУ во СССР1983р 1 ешепйаЕцпсйьопв аув.р,241-243. ЕХ Фиг,УДАРСТВЕННЫЙ КОМИТЕТИЗОБРЕТЕНИЯМ И ОТНРЫГИЯМГННТ СССР) Авторское свидетельст043642, кл. О 06 Г 7/52Мс Саппу 1,У. е 1 а 1, Тви оГ в 8 па 1 ргосеввдп 8п 8 1 - Ье вузео 11 с айагсСгоп. 1.ест., 982, 18. 2РОИСТВО ДЛЯ УМНОЖЕНИЯ бретение относится к вычисли- технике и может быть использопостроения быстродействующих в для обработки информации, х в масштабе реального вреь изобретения - повышение йствия, Устройство содержит 2 однобитовых умножителей де п - разрядность сомножибразующнх матрицу, каждый 1-й которой содержит п+1, где п, однобитовых умножителей 1,(54) УСТ (57) Изо тельной вано для устройст работающи мени. Цел быстроде (Зпф+и)/ (ОУ) 1, г телей, о столбец1608649 и портов. ввода битов первого сомножителя, 2 п портов ввода битов второгосомножителя, 2 п портов вывода битоврезультата, шину 2 нулевого сигнала. Изобретение относится к вычислительной технике и может быть использовано для построения быстродействующих устройств обработки информации,работающих в масштабе реального времени, 15Целью изобретения является повышение быстродействия.На фиг.1 представлена структурнаясхема устройства для умножения; нафиг;2 - функциональная схема однобитового умнэжитсля.Устройство для умнс"ения состоит изобразующих матрицу однобитовых умножителей (ОУ) 1 и содержит шину 2 нулезого сигнала, умножители 1 соединены 25между собой так, что входы 3 и 4 строки входы 5-7 столбцов ОУ. 1, соединены с выходами 8 и 9 строк ОУ 1и,-с выходами 10-12 столбцов ОУ;, , выходы 8 и 9 строк ОУ 1, соединены свходами 3 и 4 строк ОУ 1;+, выходы10-12 столбцов ОУ 1,1 соединены с входами 5-7 столбцов ОУ;+,1 . Входы 3строк, граничных с ОУ 1, являются портами ввода битов второго сомножителя:для бита Х- первого бита второгосомножителя - вход 3 ОУ 11 , для бита Х - второго бита второго сомножителя - вход 3 ОУ 1 ди т.д., длябита Хп-го бита и-разрядного второго сомножителя - вход 3 ОУ 11для нулевых битов Х .соответственно битов второго сомножителя, учитывающих расширение произведения двух и-разрядных операндов - входы 3 ОУ 1,,ОУ 1. Входы 5 ОУ 1 первой1строки матрицы - порты ввода битовпервого сомножителя, причемвход5 ОУ 1, - порт для ввода первогобита У первого сомножителя, вход 5ОУ 1, - порт ввода второго бита 7первого сомножителя и т,д вход 5ОУ 111 - порт ввода и-го бита Уп-разрядного первого сомножителя,Входы 6 и 7 ОУ 1 первой строки матрицы ивходы 4 строк граничных ОУ1 ,4.уфоуОУ 1ОУ 1 аСУ 1 дсоединены с шиной 2 для осуществлеКаждый ОУ выполнен в виде матрицыпростыхлогических и коммутационныхэлемейтов размерностью 45, 2,ил. ния установки нуля входных переносов и частичных произведений. Выходы 9 строк ОУ 1 последнего столбца матрицы являются портами вывода результата произведения удвоенной точности выход 9 ОУ 11 порт вывода первого бита ипроизведения, выход 9 ОУ 1- порт вывода бита п произведения и т,д., выход 9 ОУ 1- порт вывода 2 п-го бита и произведенияпудвоенной точности.ОУ 1 (фиг.2) содержит матрицу из двадцати синхронно управляемых логических и коммутационных элементов 13- 32, причем элементы 13,16 и 24 - коммутаторы "столбец-столбец и столбец- строка", элементы 14 и 29 - коммутаторы "столбец-строка и строка-столбец", элементы 15 и 17 - коммутатоРы "строка-столбец", элементы 18, 20, 21, 22 и 28 - коммутаторы "столбец" столбец и строка-строка", элементы 19 и 26 - элементы И с выводом результата в столбец и коммутацией "строка в стро", элемент 23 - коммутатор "столбец-столбец", элемент 25 - элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с выводом результата в строку и коммутацией "столбец-столбец", элементы 27 и 31 - элементы ИСКЛЮЧАЮЩЕЕ ИЛИ с выводом результата в столбец, элемент 30 - элемент И с выводом результата в строку, элемент 32 - коммутатор "столбец-строка".Элементы ОУ 1 соединены между собой локально так, что выход строки элемента 13 соединен с входом строки элемента 14, выход строки которого соединен с входом строки элемента 15, выход строки элемента 16 соединен с входом строки элемента 17, выход строки элемента 18 соединен с входом строки элемента 19, выход строки которого соединен с входом строки элемента 21, выход строки которого соединен с входом строки элемента 22. Выход строки элемента 24 соединен с входом строки элемента 25, выход строки которого соединен с входом строки элемента 26, выход строки которогосВссс тс сц гтнс б с бч с бс б ;1 д 1д пт Ц5 16 единен с входом строки элемента 27, ход строки элемента 28 соединен входом строки элемента 29, выход роки которого соединен с входом роки элемента 30, выход строки корого соединен с входом строки элента 31. Выход столбца элемента 13 единен с входом столбца элемента ,выход столбца которого соединен входОм столбца элемента 23, выход олбца которого соединен с входом олбца элемента 28. Выход столбца емента 14 соединен с входом столб- элемента 19, выход столбца которо- соединен с входом столбца элемен, выход столбца которого соедин с входом столбца элемента 29, ход столбца элемента 15 соединен входом столбца элемента 20, выход олбца которого соединен с входом олбца элемента 25, выход столбца торого соединен с входом столбца емента 30. Выход столбца элемента 16 соединен входом столбца элемента 21, выход олбца которого соединен с входом олбца элемента 26, выход столбца торого соединен с входом столбца емента 31. Выход столбца элемен соединен с входом столбца элента 22, выход столбца которого соенен с входом столбца элемента 27, ход столбца которого соединсн с одом столбца элемента 32. Вход 5 олбца элемента 13 является входом та первого сомножителя, вход 6 олбца элемента 14 является входом та частичного произведения, вход 7 олбца элемента 16 является входом реноса, вход строки 3 элемента 18 яется входом бита второго сомнотеля, вход 4 строки элемента 28 ляется входом транзитного бита стичного произведения, выход 8 роки элемента 22 является выходом та второго сомножителя, выход 9 роки элемента 32 является выходом та частичного произведения, выход столбца элемента 28 является выхом бита первого сомножителя, выход столбца элемента 29 является выхом транзитного бита частичного оизведения, выход 12 столбца элента 31 является выходом переноса следующий разряд. Задержка на один кт в каждом логическом и коммутаонном элементе осуществляется 08649 6Ю-триггером, установленным на выходе.Работа устройства заключается в5,следующем. Биты первого сомножителя У,У,в,УП поступают на портыввода первого сомножителя, начинаясо старшего бита, поступающего в первый слева столбец на вход 5.ОУ 1в первый временной интервал, который равен пяти тактам. Поступлениеочередных битов на соответстзуюгиепорты происходит с задержкой, равнойпяти тактам, по одному такту на одинстолбец матрицы ОУ 1. Биты первогосомножителя продвигаются по матрицесверху вниз по столбцам и в каждомочередном ОУ 1 столбца взаимодействуют с битамвторого сомножителя.20 Биты второго сомножителя Х,ХХреф)поступают на порты ввода второго сомножителя, начиная с младшего битаХ, поступающего в первую верхнююстроку матрицы на вход 3 ОУ 1в25 первый временной интервал. Поступление очередных битов второго сомножителя на соответствующие порты вводапроисходит с задержкой, равной четырем тактам, по одному тактУ на одну30 строку матрицы ОУ 1. Биты второго сомножителя синхронно продвигаютсяпо матрице слева направо по строками в каждом очередном ОУ 1 взаимодействуют с битами первого сомножитеТаким образом, в первый временнойинтервал в ОУ 1, взаимодействуютбиты Хи У, нулевой бит переносаи нулевые биты частичного произведе 40 ния. Во второй временной интервалбит Хпереходит в ОУ 1, , куда вэтот же временной интервал поступаетбит Унулевой бит переноса, нулевой бит частичного произведения-вход 45 ной транзитный бит частичного произведения от ОУ 1 . Во второй интервал времени бит У переходит в ОУ1, куда в этот же временной интервал поступает бит Х, бит переноса в 50 следуЮщий разряд от ОУ 11 , нулевойбит частичного произведения и тран-зитный бит от ОУ 1, , В третий вре-.менной интервал бит Х, переходит вОУ 1 для взаимодействия с битоми т д В и и временнои интервалбит Х, поступает в ОУ 1, где иразрядность операндов, для взаимодействия с битом второго сомножителя У,16086 том частичного произведения, такжеравным нулю (входной бит), бит частичного произведения от ОУ 1,который-транзитом проходит через ОУ 1,для взаимодействия с соответствующимибитами в ОУ 1,я Ь(п+1)"й временнойиитервап. В (и+1)-й временной интервал на порте вывода результата выход8 ОУ 116 появляетсЯ первый бит про Оизведения п,бит 7 взаимодействуетс битом Х 21 битом переноса от ОУ 1 л,битом частичного произведения отОУ 1 и , поступающим транзитом черезОУ 1 я., а бит частичного произведения от ОУ 1), транзитом проходитчерез ОУ 1для взаимодействия с соответствующими битами в ОУ 1,д .в(и+2)-й временной интервал и т.д,В (Зп+1)-й интервал последний бит п) 20появляется на порте выводарезультата . - выход 8 ОУ 1)Рассмотрим процесс взаимодействиябитов в ОУ 1; , В первый временнойтакт на вход столбца элемента 13 поступает бит первого сомножителя 71,во второй такт этот бит поступает соответственно на вход строки элемен;та 14 и вход столбца элемента 18, втретий такт транзитом через выходстолбца элемента 14 поступает на входстолбца элемента 19 для взаимодействия с битом второго сомножителя Х;,который во второй временной такт поступает на вход строки элемента 18, ав третий - на вход строки элемента 19, Бит частичного произведения поступает во второй временной такт навход столбца элемента 14 и транзитомчерез выход строки элемента 14 в третий временной такт поступает на входстроки элемента 15. Бит первого сомножителя в третий временной тактпоступает на вход столбца элемента 23.В четвертый такт на вход столбца эле мента 16 поступает бит переноса отпредыдущего ОУ 1, бит частичногопроизведения от элемента 15 - на входстолбца элемента 20, на вход строкиэлемента 15 - транзитный бит второгосомножителя от элемента 19, на входстолбца элемента 24 - результат логического умножения от элемента 19, навход столбца элемента 28 - бит второго сомножителя У, без изменения про.двигающийся по столбцу матрицы ОУ 155В пятый такт бит переноса поступаетна вход строки элемента 17 от элемента 16, который он минует без измене" 49 . 8ния, на вход элемента 21 поступает бит переноса также без изменения, на вход столбца элемента 25 для сложения по модулю "2" поступает бит частичного произведения, а на вход строки - бит результата логического умножения от элемента 19, без изменения переданный элементом 24 через выход строки, бит второго сомножителя покидает ОУ 11 через выход столбца элемента 28 и переходит на вход столбца элемента 13 ОУ 1 транзитный бит частичного, произведения, который в четвертый такт поступил на вход строки элемента 29 для передачи его через выход столбца элемента 29 в шестом такте на вход столбца элемента 14 ОУ 1,. В шестой временной такт бит переноса поступает на вход столбца . элемента 22 и на вход столбца элемента 26, на вход строки элемента 22 поступает транзитный бит первого сомножителя, на вход строки элемента 26 поступает результат сложения по модулю "2" от элемента 25, на вход столбца элемента 25 поступает бит частичного произведения от элемента 20, а на вход строки - бит результата логического умножения от элемента 19, без изменения переданный через выход строки элемента 29. В седьмой временной такт бит первого сомножителя Х1 покидает ОУ 1, через выход строки элемента 22 для поступления на вход строки элемента 18 ОУ 1. , бит переноса от элемента 22 поступает на вход столбца элемента 27, на вход строки которого поступает бит результата сложения по модулю "2" передан) ный без изменения через выход строки элемента 26, бит результата логического умножения от элемента 26 поступает на вход столбца элемента 31, на вход строки которого поступает результат логического .умножения от элемента 30 через выход его строки. В восьмой временной такт бит переноса покидает матрицу ОУ 1,через выход столбца элемента 31, результат сложения по модулю "2" от элемента 27 поступает на вход столбца элемента 32 для передачи его на девятом временном такте на выход строки элемента.32 и на вход строки элемента 22 ОУ 1;,Одновременно в ОУ 1 находятся биты восьми пар сомножителей, последовательно поступающие в каждый оче" редкой такт и синхронно продвигаю 1608 б 49щи тоод за занатаро тапо ся по элементам матрицы с частотактирования. Если длительность ого такта равна К и соответственно ержке одного элемента ОУ 1, то ержка ОУ 1 составит ЯК, а началь 5 задержка матрицы умножения сосит (Зп)к 8 К тактов. При умножедвух векторов размерностью М азрядные числа полное время форми ания результата произведения сосит (Зп) 8 К+ИК при условии, что дая пара сомножителей векторов тупает в матрицу в каждый такт.15рмула изобретения жащ леи обр бец одн ды та умндиВОГ рен жит телля со ум со са мат со(мат со ум вто бит, бит од ди ти би та оддивбио Устройство для умножения, содерЗтб+ие ( , ) однобитовых умножите 220 (и - разрядность сомножителей), зующих матрицу, каждый 1-Й стол- которой (1 щ 1п) содержит и+1 битовых умножителей, причем вхоервого сомножителя и входного би ереноса (1.,1)-го однобитового жителя матрицы (1=1п+1) соеены соответственно с выходами персомножителя и выходного бита песа (1-1,1)-го однобитового умноеля матрицы выход второго сомножи(1,1)-го аднобитового умножитеатрицы соединен с входом Второго ожителя (1.,+1)-го Однобитового ожителя матрицы, выходы первого ожителя и выходного бита перено- (с 1)-го однобитового умножителя ицы соединены с входами первого ожителя и входного бита переноса 1,1) ГО ОднобитОВОГО умножителя 40 ицы соответственно, выход второго ножителя (,1)-го однобитового Ожителя матрицы соединен с входом ого сомножителя (1,1+1)-го одно- ОВОГО умножителя матрицы ВыхОд 45 а частичного произведения (х,1)-го обитового умножителя матрицы соеен. с выходом транзитного бита часного произведения (1-1,1)-го одноового умножителя матрицы, вход бичастичного произведения (.,)-го обитового умножителя матрицы соеен с выходом бита частичного произ- ения (а,1-1)-го однобитового умноеля матрицы, выход транзитного а частичногс произведения (,1)-го. обитового умножителя матрицы соеен с входом бита частичного произ- ения (ь+1,1)-го однобитового умножителя матрицы, вход бита частичногопроизведения (х,)-го однобитовогоумножителя матрицы соединен со входомтранзитного бита частичного произведения (х,+1)-го однобитового умножителя матрицы, о т л и ч а ю щ е е с ятем, что, с целью повышения быстродействия, каждый однобитовый умножитель выполнен в виде матрицы размернос 1 ью 45 из синхронно управляемыхлогических и коммутационных элементов, первый столбец которой содержитпервый коммутатор "Столбец - столбеци столбец - строка", второй коммутатор "Столбец в столбец и строка -строка", третий коммутатор "Столбец -столбец", четвертый коммутатор "Столбец - столбец и строка - строка",второй столбец содержит пятый коммутатор "Столбец - строка и строка -столбец", первый элемент И с выводомрезультата в столбец и коммутацией"Столбец - строка и столбец - столбец, седьмой коммутатор "Столбец -сгрока и строка - столбец", третийстолбец содержит Восьмой коммутатор"Столбец - строка", девятый коммутатор "Столбец - столбец" и строка -строка", первый элемент ИСКЛЮЧАЮЩЕЕИЛИ с выводом результата в строку икоммутацией "Столбец - столбец", второй элемент И с выводом результатав столбец и коммутацией "Строка -строка", четвертый столбец содержит десятый коммутатор "Столбец -строка и столбец - столбец", одиннадцатый Коммутатор "Столбец - столбеци строка - строка", третий элементИ с выводом реузльтата в строку ивторой элемент ИСКЛЮЧАЮЩЕЕ ИЛИ с выводом результата в столбец, пятыйстолбец содержит двенадцатый коммутатор "Столбец - строка", тринадцатый коммутатор "Столбец - столбеци строка - строка", третий элементИСКПОЧАЯЕЕ ИЛИ с выводом результата в столбец и четырнадцатый коммутатор "Столбец - строка", при этом связи в матрице однобитового умножителялокальные В направлении строк истолбцов, вход столбца первого коммутатора является входом бита первогосомножителя, вход строки второго коммутатора является входом бита второгосомножителя, вход столбца десятогокоммутатора является входам переноса, вход столбца пятого коммутатораПуд Составитель В. БерезкинРедактор А. Шандор Техред М.Ходанич Кор Самборская. Тираж 563 Подписноерственного комитета по изобретениям и открытиям 113035, Москва, Ж, Раушская наб., д. 4/5 Заказ 36 ПЬНИИПИ Го ГКНТ СС твенно-издательский комбинат "Патент", г.Ужгород, ул. Гагарина,101 Произ 111608649 12,является входом бита частичного про-теля, выход строки четырнадцатогоизввдения, вход строки четвертогокоммутатора является выходом битакоммутатора является входом транзит- частичного произведения, выход столбного бита частичного произведения, ца. второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИвыход столбца четвертого коммутатора является выходом переноса, выходявляется выходом бита первого сомно- столбца седьмого коммутатора являетсяжителя, выход тринадцатого коммутато- выходом транзитного бита частичногора является выходом второго сомножи- произведения.