Параллельный сумматор Советский патент 1983 года по МПК G06F7/50 

ИЗ последовательно соединенных элементов задержки с первой по (N-1 ую соответственно, вторые выходы суммирующих ячеек с первой по N-yro соединены с информационными входами триггеров с CN+I У-ГО по (2N-1 )-й соответственно, тактовые входы которых подключены к первым выходам суммирующих ячеек с первой по N-ую соответственно, входы 1эазрядов регистра сдвига соединены с входными шинами параллельного сумматора, выходные шины которого подключены к выходам триггеров.

ПАРАЛЛЕЛЬНЬт СУММАТОР, содержёцций элементы задержки и N суммирующих ячеек, каждая из которых содержит одноразрядный сумматор, элемент И и три элемента задержки, выход элемента И соединён с первым входом одноразрядного сумматора, вход первого элемента задержки соединен с перВЕШ входом суммирующей ячейки, а выход с первым входом элемента И и первым выходом суммирукицей ячейки, второй и третий входы котсфюй подключены к соответствующим входам одноразрядного сумматора, выход суммл которого соединен с входом второго элемента задержки и вторым iвыходом суммирующей ячейки, выход переноса одноразрядного сумматора подключен к входу ; третьего элемента задержки, выход которого соединен с третьим выходам суммирующей ячейки, выход второго элемента задержки подключен к второ- . t входу элемента И, первый вход первой суммирующей ячейки подключен к шине запрета формирования суммы параллельного сумматора, первый вход каждой последующей суммирукщей ячейки соединен с первым выходом преда1ду, щей суммирующей ячейки, второй вход каждой суммирующей ячейки, начиная с второй, подключен к третьему выiходу предыдущей суммирующей ячейки, третий вход каждой j-й су1даирующей ячейки (,...N) соединен с выходом I цепочки из (J-1 ) соединенных прследовательно элементов задержки, от л ичающийся тем, что, с целью расширения функциональных возможностей за счет выполнения операций суммирования парных произведений и умножения, дополнительно содержит

Изобретение относится к вычислиФельяой технике и может быть исполь3OBUHO в арифметических устройствах ЭВМ и специализированных вычислительных устройствах, вычисляющих сум M|d парных произведений. Известно устройство для вычнсления сумм парных произведений, содержащее матрицу модулей сложения C1J° Недостатком такого устройства являются значительные аппаратурные затраты. Известен также параллельный сумма тор (Накапливающего типа, cкyJepжalций входные и выходные шины, N однор зрядных сумматоров, N элементов И, элементы задержки. Для удобства описания в дальнейшем часть параллельного сумматора, состоящую из элемент И, трех элементов задержки и одного одноразрядного сумматора, будем назы вать суммирующей ячейкой, в которой первый вход одноразрядного сумматора подключен к выходу элемента И, первы вход ifOToporo подключен к выходу первого элемента задержки, вход кото рого подключен к третьему входу суммирукйцей ячейки, а второй вход элемента И через второй элемент задержки подключен к первому выходу одноразрядного сумматора/ второй выход которого подключен ко входу третьего элемента задержки, выход которого подключен ко второму выходу суммирую щей ячейки, второй вход одноразрядного сумматора подключен к первому входу суммирующей ячейки, третий вхо одноразрядного сумматора подключен ко второму входу суммирующей ячейки, .первый выход суммирующей ячейки под-г ключён к первому выходу одноразрядного сумматора, а третий выход суммирующей ячейки подключен к первому входу элемента И, причем суммирующая ячейка i-rp разряда (i « 1,2,... N ) первым входом подключена к соответствующей входной шине через (i-1 ) элементов задержки, вторым и третьим входами подключена соответственно ко второму и третьему выходам суммирующей ячейки (i-1 у-го разряда, первым выходом соединена с соответствующей выходной ишной, а вторым и третьим выходами соединена соответственно со вторым и третьим входами суммирующей ячейки (i+1 го разряда C2j. Данное устройство не позволяет выполнять ни операцию умножения, ни получение парных произведений . вида А В +... +А| В. для вычисления которой требуется такой же такт работы сумматора как и при умножении. Цель изобретения - расширение функциональных возможностей за счет выполнения операций суммирования парных произведений и умножения. Поставленная цель достигается тем, что параллельный сумматор, содержащий элементы задержки и N суммирующих ячеек, каждая из которых содержит одноразрядный сумматор, элемент И и три элемента задержки, выход элемента И соединен с первым входом одноразрядного сумматора, вход первого элемента задержки соединен с первым входом суммирующей ячейки, а выход с первым входом элемента И и первым выходом суммирующей ячейки, второй и третий выходы которой подключены к соответствующим входам одноразрядного сумматора, выход суммы которого соединен с входом второго элемента задержки .и вторым выходом суммирующей ячейки, выход переноса одноразрядного сумматора подключен к входу третьего, элемента задержки, выход которого соединен с третьим выходом суммирующей ячейки, выход второго элемента задержки подключен к второму входу элемента И, первый вход первой суммирующей ячейки подключен к шине запрета формирования суммл параллельного сумматора, первый вход каждой последующей суммирующей ячейки соединен с первым выходом предыдущей суммирующей ячейки, второй вход каждой суммирую14ей ячейки, начиная со второй, подключен к третьему выходу предыдущей суммирующей ячейки, третий вход кгикдой j-ой суммирующей ячейки (j 2,3,..., N) соединен с выходом цепочки из соединенных .последовательно элементов задержки, дополнительно содержит (2N-1 ) триггеров, (2N-1 ) элементов И, элемент ИЛИ, регистр сдвига и (N-1 ) дополнительных суммируквдих ячеек. причем выходы разрядов регистра сдви га соединены с первыми входами соот ветствующих элементов И, вторые входы которых соединены с выходом элемента ИЛИ, первый вход которого соединен с шинрй множителя параллель ного сумматора, а второй вход - с шиной режима рйботы параллельного су матора, первый вход первой дополнительной суммирующей ячейки соединен дополнительной шиной запрета формиро вания суммы параллельнохх сумматора первый вход каждой последующей допол нительной суммирующей ячейки соединен с первым выходом предыдущей дополнительной суммирующей ячейки, второй вход каждой дополнительной суммирующейч ячейки соединен с третьи выходом предьвдущей дополнительной , суммирующей ячейки, выходы элементов И с первого по (N-1 й соединены с третьими входами соответствующих дополнительных суммирующих ячеек, вторые выходы которых подключены к информационным входам соответствующих -триггеров, тактовые входфл которых подключены к первым выходам соответствующих дополнительных суммирующих ячеек, первый и третий выходы (N-1 ) дополнительной суммирукхцей ячейки ° ° и вторым входами срответственно первой суммирующей ячейки, третий вход КОТОРОЙ подключе к выходу N-ro элемента И, выходы &лейентов ис (N+1 -го по (2N-1 )-й соединены с входами цепочек из последовательно соединенных элементов задержки с первой по (N-1 ю соотв1вт ственно, вторые выходы суммирующих ячеек с первой по N-ю соединены с информационными входами триггеров с ( -го по (2N-1 й соответственно, тактовые входы которых подключены к первым выходам суммирующих ячеек с первой по N-ю соответственно, входы разрядов регистра сдвига соединены с входными шинами параллельного сумматора, выходные шины которого подключены к выхвдам триггеров. На чертеже дана функциональная схема параллельного сумматора. Сумматор содержит входную шину 1 подключенную к соЬтвётствующйм входам (2N-1 )-разрядного регистра 2 сдвига, выходы которого соединены с первыми входами (2N-1 )-го элемента И 3. Вторые входы всех (2N-1 )-го элементов И соеди нены с выходом элемента ИЛИ 4, первый вход которого соединен с шиной 5 множителя, а второй вход соединен с шиной 6 режима работы. Выход i-ro элемента ИЗ (if N, ,..., 2N-1 ) подключен через (i-N) элементов 7 задержки к первому входу 8 i-ой суммирующей ячейки 9, а выход j-oro элемента 3 (j 1,2, ...,N-1 ) подключен k.первому входу 8 j-ой суммирующей ячейки 9. Третий вход 10 каждой k-той (k 1,2,..., 2N-1 ) суммирующей ячейки 9 соединен с третьим выходом 11 ( суммирующей ячейки 9, причем третий вход 10 первой суммирующей ячейки 9 соединен с дополнительной ишной 12 запрета формирования сумкы, а третий вход 10 k-ой суммирующей ячейки 9 соединен с шиной 13 запрета формирования суммы. Второй вход 14 каждой k-той хг jсуммирующей яче1(ки 9 соединен со вторым выходом 15 (к -1 -ой суммирующей ячейки 9. Первый выход 16 казкдо k-тоП суммирующей ячейки 9 соединен с первым входом 17 k-ro тактирующего триггера 18, а второй вход 19 k-ro трактируемого триггера соединен с третьим выходом 11 k-той суммирую1цей ячейки 9 того же разряда, Выходами cy в aтopa 20 являются выхоДЫ тактируемых триггеров 18. В кажд д -ой суммирующей ячейке 9 первый вход 8 соединен со вторым входом одноразрядного сумматора 21,первый вход которого подключен к выходу элемента И 22, первь1й вхдд„.которого подключен к вызсрду-TiepBoro элемента 23 .задержки,--вход которого подключен к третьему входу 10 ячейки. .Второй вход 1 ячейки подключен к третьему входу одноразрядного сумматора. Первый вы« одноразрядного сумматора 21 подJ к первому выходу ячейки 16 и ко входу второго элемента 24 задержки, выход которого соединен ко второму входу элемента И 22. Второй выход одноразрядного сумматора 21 под-, ключен через третий элемент 25 заг дёржки ко второму выходу 14 суммирующей ячейки 9. Третий выход 11 суммирующей ячейки 9 подключен к выходу первого элемента 23 задержки, Параллельный сумматор может рабо двух режимах: в режиме сумма р умножителя. Каждая из этих операций может выполняться либо с накоплением предыдущих результатов, либо без накопления. Длительность задержки на элементе 7 задержки такова, что сигнал на ее выходе появляется через время tT , равное интервалу подачи слагаемых на входные шины 1, Элементы 24 и 25 задержки таковы, что на их выходе сигнал появляется также через время Т , Режим сукматора. В исходном состоянии на входную шину 1 подают нулевой код. В процессе суммирования на N старших разрядов входной шины 1 через интервалы времени, равные V , подаются суммирующие числа, а на (N-1 )-ый «падишй разряд входной шины 1 подаюТ|г ся нули. На шину б режима работы поступает сигнал разрешения, открываюш й элементы И 3. Через время f первый разряд первого слагаемого проходит через сумматор 21 N-ой суммирующей ячейки 9, элемент 24 задержки 24 и элемент И 22 этой же суммирующей ячейки и попадает на первый вход сумматора 21. В это же самое время (t) на входную шину 1 подается новое слагаемое а на первый вход 8 {N + 1 )-ой суммиру щей ячейки 9, пройдя элемент 7 задержки,- попадает второй разряд первого слагаемого. В следующем такте (if}происходит суммирование в сумматоре 21 N-ой суммирующей ячейки 9 первых разрядо первого и второго слагаемых, и сумм их, через элемент 24 задержки и эле мент И 22 N-ой суммирующей ячейки 9 поступает на первый вход сумматора 20 той же суммиругацей ячейки 9. В это же время (2f) второй разряд первого слагаемого просуммируется в (N + 1 )-ой суммирукяцей ячейке 9 с нулем. Перенос, сформированный при су мированиии первых раэрядов, через элемент 25 задержки и второй выход 15 N-ой суммирующей ячейки 9 поступает на второй вход 14 (N+1 )-ой сум мирующей ячейки 9. Второй разряд второго слагаемого, пройдя элемент 7задержки., поступает на первый вхо 8той же суммирукицей ячейки. Третий разряд первого слагаемого, пройдя два элемента i задержки, поступает . на первый вход 8 (N+2 )-ой суммирующей ячейки 9.. В каждом последующем такте происходит суммирование,одноименных разрядов результата от сложения (т-р ) слагаемых, где р m,,..., 2,1 и (m-p-f-1 )-го слагаемого. Через время (т-1 )f в N-ой сумми рующей; ячейке 9 просуммируются перв разряды (m-l -го слагае1Уых, а на первый вход 8 этой же суммирующей ячейки поступает первый разряд т-го слагаемого, в следующем такте (тТ) происходит суммирование первьйс разрядов m слагаекых. Для очистки суммирующих ячеек 9 (перед началом суммирования следующего массива чисел ) на шину 13 запрета формирования суммы подается импульс, который, пройдя элемент задержки 23 и элемент И 22, разрывает цепь обратной связи первого выхода сумматора 21 с первым входом этого же сумматора. Этот процесс повторяется во всех суммирующих яче ках 9. Этот же импульс используется для занесения результата суммирования в триггеры 18. Таким образом, череэ время (m+N J результат суммирования N-тых разрядов m слагае « 1х записывается в (2N-1 )-ый тактируемый триггер 18, а на входных шинг1х 20 появляется ре эультат суммирования m N-разрядных слагаемых, В (т+1 ) Т такте на выходную шину 1 подается слагаемое из следующего массива и начинается накопление следующей cyMivta, т.е. на обработку одного слагаемого необходимо затратить (1+N/m) тактов. Режим умножения. В исходном состоянии на входных шинах 1 присутствуют нули. Множимое подается на N младших разрядов входной шины 1 и принимается в регистр 2. На шину 5 множителя поступает первый (младший ) разряд множителя, а на шину б режима работы подается нулевой код. На элементах И 3 формируется частичное произведение множимого на один разряд множителя. В первом такте в N младших суммирующих ячейкгис 9 происходит сложение частичного произведения множимого на первый разряд множителя с нулем. В следующем такте (2Т) . на шину 5 множителя поступает второй разряд множителя, в сдвиговом регистре 2 производится сдвиг множимого на один разряда влево. В (N-1 )-ой суммирующих ячейках 9 происходит суммирование частичного произведения, сформированного в первом такте, с (N-1 )-ым разрядом частичного произведения, сформированного во втором такте. При этом во второй суммирующей ячейке 9 формируется второй разряд результата умножения двух сомножителей. На первый вход 8 ( )-ой суммирующей ячейки 9, пройдя элемент 7 задержки, поступает старший разряд сформированного в этом такте частичного произведения. В следукядем тактеОТГ на шину 5 множителя поступает третий разряд множителя, в сдвиговом регистре 2 производится сдвиг мнржимого на один разряд влево. В (N-1 ой суммирующих ячейках 9 происходит суммирование накопленной в предыдущих тактах сумма частичных произведений с (N-2 -мя разрядами частичного произведения, сформированного в этом такте, и старшего разряда частичного произведения, сфоркшрованного в предыдущем такте. При этом в третьей суммирующей ячейке 9 формируется третий разряд результата умножения двух сомножителей с учетом переноса, образовавшегося при формировании второго разряда результата умножения этих же сомножи.телей. В (N+1 )-ой суммирующей ячейке 9 производится сложение старшего разряда частичного произведения, сфор мированного в предыдущем такте, с предварительным переносом, сфррмированным в предыдущем такте в N-ой суммирующей ячейке 9. Таким образом, в j-том такте (J 1,2,f,. ,N) на шину 5 множителя поступает j-ый разряд множителя, в сдвиговом регистре 2 производится (J-1 у-ыЯ сдвиг множимого. В j-ой суммирующей ячейке 9 формируется j-ый разряд результата умножения двух сомножителей с учетом переноса образовавшегоса при формировании (J -1 УТО разряда результата умноже- иия этих же сомножителей. СтлраиЛ разряд сформированиЪго частичного . произведения поступает иа вход эле ; меитд 7 задержки, выход которохчэ со диней через (j-2) элемента 7,за держки с первым входом 8 (N-j+1 )-ой суммирующей ячейки 9 В N-OM формируется частичное произведение множимого на старший разряд множителя. В N-ой суммИ: руккцей ячейке 9 формируется N-ый разряд результата умножения двух сомножителей. Через (N-1 ) такт сфор iмируётся старший (2N-t )-й разряд ре зультата умножения этих же сомножи;гелей. . В (N+1 У-ом такте производится прием в сдвиговый регистр 2 нового множимого. На шину 5 подается первый разряд нового множителя, и про,цесс умножения повторяется только с той разницей, что в N-разрядноМ параллельном сумматоре хранится резул .тат предыдущего умножения и одновре менно с вычислением произведения. двух новых сомножителей происходит суммирование результата умножения предыдущих сомножителей и сомножи- телей новых. ; Для очистки параллельного сумматора после вычисления суммы парных произведений вида .. .А,„Е ,6 момент времени N(m-1 )С(одноа1 еменно с приемом в -оегистр 2 последнего множимого) на шину 12 запрета формирования сумт подается импульс, который через время ..производит разрыв цепи Обратной связи в первой суммирукадей.ячейке 9 и, поступив с тр.етьего всхода 11 этой ячеЙЙ на второй 33toa 19 первого тактируемояз триггера 18, заносит первый разряд результата вычисления сум1иы парных произведений в первый триггер 18. Через (2N-1 -ый такт результат вычисления суммы парных произведений ступает на выходные 20, т.е на.вычисление выражения вида j А Bj +,. i+ АтВцгребуетря; время равное (Nra- -N-1 ) Г. Следовательно, на выпол- нение ОДНОГО умножения и сложения нфобх(имо затратить N(t+1/m) тактов. Использование новых элементов дополнительных сукмирующих ячеек, элементов И, элемента ИЛИ и регистр сдвига дает возможность выполнять ; не только суммирование и суммиррва-, ние с накоплением, но и опергщии умйо жения и вычисления суммы парных про- изведений вида А В. +... . Это, :во-первых, расширяет сферу примене- , ния сумматс а, во-вторых, позволяет исключить простои оборудования при выполнении операций умножения и копления сумм парных произведений, и,в-третьих, устраняет необходимост создания в вычислительных устройствах отдельных сумматора и умножителя.