Пристрій для підсумовування трьох n-розрядних операндів

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих арифметических устройств. Известен [Угрюмов Е.П. Проектирование элементов и узлов ЭВМ: Учеб. пособие для спец. ЭВМ вузов. М.: Высш. шк., 1987, С.191, рис. 11.11.а] η-разрядный сумматор с групповой структурой, состоящий из m kразрядных групп (каскадов), причем в группах осуществляется параллельный перенос, а между группами последовательный; группа включает в себя блок сумм и блок переносов, которые обрабатывают слагаемые в пределах группы и перенос из предыдущей группы. Недостаток такого сумматора - малое число операндов (всего два), что приводит к снижению скорости суммирования множества операндов. Известен также трехслойный сумматор Глассера [Патент США № 3906211, 23.05.74], имеющий групповую структуру, отличительной особенностью которого является двухбитовый последовательный перенос, причем биты имеют одинаковый вес. Данный сумматор выбран в качестве прототипа, как имеющий наибольшее число совпадающих с предлагаемым изобретением признаков. Сумматор в патенте представлен в двух вариантах: в первом варианте сумматор состоит из множества однобитовых суммирующих каскадов, принимающих по одному биту от каждого из трех суммируемых слов; сумматор по второму варианту содержит множество двухбитовых каскадов, принимающих по два смежных бита каждого из трех слов слагаемых. В первом сумматоре коммутация линий переноса выполняется в каждом разряде, а во втором - в каждом паре соседних разрядов; переносы между каскадами в обоих случаях осуществляются последовательно. Каскад в обоих вариантах может быть представлен в виде двух блоков: блока сумм (БС) и блока распространения переносов (БП). Рассмотрим подробнее сумматор по второму варианту, как более быстрый. БП каждого каскада работает в соответственно с суммарным весом слагаемых (СВС), т.е. количества бит слагаемых, поступающих на каскад, которые имеют значение 1; при этом БП либо непосредственно генерирует логическую 1 на выводах переноса, либо осуществляет коммутацию линий переноса, выходного и входного. Кодировка бит переносов C(i) (основного) и C(l) (вспомогательного), где і - номер старшего разряда предыдущего каскада, осуществлена в соответствии с табл. 1. Отметим, что одновременные переносы (относительно старшего разряда предыдущего каскада) в следующий разряд и через разряд невозможны, т.к. максимальное значение суммарного веса входов (СВВ) (слагаемых и переносов) при к разрядах в каскаде равно (2^к - 1) 3 + 2 =- 2^(к+1) + 2^к - 1; перенос "1" через разряд эквивалентен переносу двух "1" в следующий разряд. На каждый БС подается 6 бит слагаемых, которые в комбинации с входными переносами на выводах БС генерируют в соответствии с СВВ 2 бита суммы, причем второй бит суммы имеет двойной вес по сравнению с первым. Недостатком прототипа является относительно малое быстродействие, что связано с двумя причинами: малое число разрядов, обрабатываемых каскадом, а также неоптимальность структуры каскада сумматора Глассера, что выражается в вычислении весов СВС и СВВ блоками БС и БП отдельно, хотя при формировании результатов используется некоторая одинаковая информация. Задачей предполагаемого изобретения является повышение быстродействия прототипа за счет увеличения разрядности каскадов, а также улучшения структуры каскада путем выделения из схем БП и БС подсхемы (блока) вспомогательных функций. В устройство для суммирования трех n-разрядных операндов, содержащее m k-разрядных каскадов, каждый из которых содержит блок сумм и блок переносов, причем каскады соединены последовательно двумя однобитовыми линиями переносов, а биты переносов имеют одинаковый вес, входы разрядов слагаемых устройства являются соответствующими входами разрядов слагаемых каскада, выходы блока сумм каскада соединены с соответствующими выходами каскада, которые являются выходами сумм устройства, входы переносов каскада соединены с соответствующими входами блоков сумм и переносов, а выходы блока переносов соединены с соответствующими выходами переносов каскада, при этом входы переносов первого каскада и выходы переносов m-го каскада являются соответствующими входами и выходами переносов устройства, дополнительно введены в каждый каскад по блоку формирования вспомогательных функций, входы которого соединены со входами разрядов слагаемых каскада, а его выходы - со входами как блока сумм, так и блока переносов. Изобретение иллюстрируется на фиг. 1 - 3. Структурная схема заявляемого сумматора представлена на фиг.1, а структурная схема его каскада - на фиг, 2; на фиг. 3 -схема коммутации линий переноса. Здесь обозначено: 1,2,..., m - каскады с первого по m-й; Χ, Υ, Ζ - η-разрядные слагаемые; С, С - переносы; S - суммы; БП - блок распространения переносов; БС - блок сумм; БВФ -блок вспомогательных функций. Устройство работает следующим образом. Поразрядные значения операндов Χ, Υ, Ζ, поступающие на входы разрядов слагаемых каскада (всего 3к бит), обрабатываются блоком БВФ в каждом каскаде в соответствии с СВС каскада, и на выход БВФ выдаются значения вспомогательных функций, которые вместе с двумя битами переносов Свх и С вх формируют значения сумм в блоке БС (к бит) и переносов в блоке БП (2 бита). Значения переносов на выходе данного каскада являются входными переносами для следующего каскада. Вспомогательные функции вырабатываются в каскадах одновременно, а переносы в данном каскаде формируются по мере готовности значений переносов в предыдущих каскадах; таким образом, цепи переносов образованы последовательно соединенными БП. Величина одного (Свых) или другого (С'вых) выходного бита переноса каскада может быть однозначно определена на основании значений вспомогательных функций, поступающих на вход БП. При этом блок БП на своих выводах переноса либо непосредственно генерирует биты выходного переноса, либо устанавливает связи линий переноса между выбранным вводом переноса и выводом переноса, на котором еще не сгенерирован бит. Переносы кодируются, как и в сумматоре Глассера, в соответствии с табл. 1. БС каждого каскада формирует порязрядные значения сумм по значениям тех вспомогательных функций, которые поданы на вход БС с выхода БВФ, с учетом значений входных переносов С вх и С'вх, причем і-й бит суммы имеет вес 2й. Быстродействие сумматора можно оценить по формуле: Tсм=Tподг + (n/k)Tпер, (1) где Тсм - время, необходимое для вычисления всех бит суммы и бит переноса из старшего разряда сумматора; Тподг - время определения значений вспомогательных функций с целью подготовки вычислений значений бит суммы и переноса из данного каскада; ТПер - время вычисления значений бит выходного переноса каскада; n - разрядность сумматора; k - разрядность каскада. Из формулы (1) видно, что с увеличением разрядности каскада быстродействие сумматора растет. Однако это достигается ценой возрастания сложности схемы БВФ. Функционирование каскада рассмотрим на частном, но практически важном примере сумматора, построенном на 4-разрядных каскадах суммирования трех операндов. Функционирование 4-разрядного каскада описывается табл.2, в которой представлено однозначное соответствие суммарного веса Q слагаемых каскада значениям его поразрядных бит суммы и бит выходных переносов для некоторых граничных значений Q (для остальных значений Q таблица легко восстанавливается). Эти значения сгруппированы таким образом, что при одном значении СВС рассматривается 3 варианта кодировки бит входного переноса: 00, 01,11 (см. табл. 1). СВС Q каскада выражается через составляющие его поразрядные значения весов слагаемых формулой: где ai = (0,1,2,3) - количество единиц в 1-ом разряде входного набора переменных (слагаемых) каскада; СВВ Q' определяется (С'вх и С8Х имеют одинаковый вес) в десятичной системе счисления в виде В табл. 2 записаны двоичные представления Q, т.е. где (С'выхСвых) формируется в соответствии с таблицей 1. Заполняется табл.2 для каждого Q, начиная с Q = 0 и заканчивая Qmax = 3(2k -1), по три строки соответственно трем возможным кодам для входного переноса, вычисляя О'(ю)и переводя его в двоичное представление по формуле (4). Информация, заключенная в табл. 2, является исчерпывающей при синтезе схемы каскада, однако вспомогательные функции для блоков суммы и переносов получаются по-разному. 1. Для БС табл. 2 представляет собой таблицу истинности, и логические выражения выводятся обычным образом (например, записывая ДНФ по единицам для і-го бита суммы S,), но с двумя оговорками: - Si является функцией целочисленных значений Q, что требует использования т.н. симметрических функций [Миллер Р. Теория переключательных функций. Т.2. - М.: Мир, 1971]; - для i-гo бита суммы выражение представляется в виде дизъюнкции трех составляющих (по числу возможных кодов для бит входного переноса) где ai - вспомогательные функции, зависящие от Q. 2. Для БП зависимости бита выходного переноса от бит входного переноса выводятся из сопоставления столбцов для указанных бит при данном Q. Столбец Свых (С'вых) может принимать 4 значения (т - символ транспонирования): [000]\ [001]т, [011]т, [111]т. В первом и последнем случае это означает, что независимо от значений бит входного переноса бит выходного переноса соответствует константе (о либо 1); во втором и третьем случаях имеет место соответствие значений одного из бит выходного переноса (Свых или С вых) значениям бита входного переноса (Свх или С'вх); при этом второй бит выходного переноса обязательно равен константе. Эти соответствия в виде правил приведены в последней колонке табл. 2. Таким образом, БП может быть описан следующими логическими выражениями: где b и g- вспомогательные функции, зависящие от Q. Отметим, что βο,γο - функции генерации логической 1, а β1, γ1, β1 g2 - Функции, управляющие коммутацией линий переноса, причем либо обе функции β равны 0, либо только одна из них равна 1; то же относится к функциям у. Конкретное значение Q может быть представлено поразрядно в соответствии с формулой (2) несколькими вариантами, и тогда некоторую функцию от Q можно записать в виде дизъюнкции составляющих функций для каждого варианта, причем дизъюнктивная составляющая является конъюнкцией поразрядных подфункций; последние представляют собой симметрические функции (СФ) трех одноразрядных переменных (слагаемых Хі, Yі, Zі). Все вспомогательные функции выражаются через СФ в виде дизъюнктивной нормальной формы (ДНФ); при этом учитываются как всевозможные варианты представления данного Q, так и все значения Q, от которых зависит рассматриваемая вспомогательная функция. На фиг. 3 приведена схема коммутации линий выходного переноса и линий входного переноса, включая линию, на которой генерируется константа (логическая 1). Здесь прямоугольными скобками обозначен ключ, который замыкает разрыв в линии, при α ,β и g , принимающих значение 1; крестиком обозначено место схождения линий входного переноса (включая константное значение), что соответствует логической функции ИЛИ. Если не реализуется ни одно из указанных на фиг. 3 значений Q для данного бита выходного переноса, то он принимает значение логического нуля. Описание функционирования блоков БП, БС, БВФ приводится к ДНФ с целью построения схем И-ИЛИ. Что касается исходных симметрических функций, то они могут быть реализованы, например, на 3-входовых дешифраторах и логических элементах ИЛИ. Заметим, что биты суммы для к разрядов и переносов вычисляются одновременно, что и обеспечивает повышение быстродействия сумматора относительно прототипа (см. формулу (1)).