Однотактный умножитель двоичных чисел
Изобретение относится к вычислительной технике и может быть использовано при построении быстродействующих умножителей для арифметических устройств ЭВМ и специализированных вычислительных устройств. Цель изобретения - повышение быстродействия. Цель достигается за счет построения умножителя на основе однослойного преобразователя Nvaz -разрядного кода в (1+/log2Nvaz/целое) -рядный код и (1+/log2Nvaz/целое) -входового многоразрядного параллельного сумматора с одновременно-групповыми переносами. Преобразователь выполнен на разнотипных многовходовых одноразрядных сумматорах. Между разрядами как преобразователя, так и параллельного сумматора распространяется многоразрядный перенос. 8 ил.
Изобретение относится к вычислительной технике и может использоваться при построении быстродействующих умножителей для арифметических устройств ЭВМ и специализированных вычислительных устройств.
Цель изобретения - повышение быстродействия. На фиг. 1 представлена функциональная схема умножителя; на фиг. 2 - функциональная схема центральных (i+1)-го, i-го, (i-1)-го разрядов преобразователя для N = 32; на фиг. 3 - функциональная схема пятивходового четырехразрядного параллельно-параллельного сумматора (5, 4 ППС) с одновременными переносами; на фиг. 4 - функциональная схема пятивходового одноразрядного сумматора (ОС); на фиг. 5 - функциональная схема 32-входового ОС; на фиг. 6 - функциональная схема сумматора унитарных кодов (SМУК); на фиг. 7 - функциональная схема узла формирования окончательного результата (для N = 64); на фиг. 8 - временные диаграммы функционирования умножителя. Однотактный умножитель (фиг. 1) содержит регистры множителя 1 и множимого 2, матрицу 3 из m x m элементов И, (2m-1)-рарядный преобразователь 4 Nvar-разрядного кода в n-рядный код, блок 5 суммирования, узел 6 формирования окончательного результата, входы множителя 7 и множимого 8, выходы 9 результата. Преобразователь 4 Nvar-разрядного кода в n-рядный код является однослойным и содержит в каждом разряде Nvar-входовойОС. Преобразователь 4 имеет в своем составе один слой (линейку) N-входовых ОС следующих типов: 2, 3, . . , N-1, N-, N-1, . . . , трех-, двухвходовые ОС. На выходах каждого N-входового ОС вырабатываются сумма С и [log2 Nvar] целое- разрядный перенос. В частности, для фиг. 2 имеют место [log232] целое = 5, [log231] целое = 4, [log230] целое = 4, т. е. пяти- и четырехразрядные переносы, разряды которых обозначены П1, П2, П3, П4, П5. На фиг. 2 (для N = 32) представлены четыре центральных сумматора из линейки: два 31-входовых (31 ОС) 10, один 32-входовый (32 ОС) 11 и один 30-входовый (30 ОС) 12. Блок 5 суммирования состоит из n-входовых ППС 13, каждый разряд которых (фиг. 3) содержит nvar-входовый ОС 14 (nvar = 2, 3, 4, 5), два узла 15, 16 формирования одновременных переносов и сумматор 17 по модулю два, входы 18 ППС 13, выходы 19 суммы ППС 13, входы 20 и выходы 21 переносов ППС 13. Узел формирования одновременных переносов состоит из элементов И и ИЛИ, на входы которых поступают сигналы согласно следующим логическим выражениям, где (для пятивходового четырехразрядного сумматора) iФП1(iФП2) - выходы узлов 15 (16) для i-го разряда; iC, iПj, iППj - выходы суммы и переносов соответственно для j-го разряда nvar-входового ОС 14; , , - значения переносов из предыдущей четверки разрядов (в следующую четверку разрядов) сумматора. 1ФП1 = (1ПП1 ) v 1П1 v (1ПП1 ); 2ФП1 = (2ПП1 1ПП1 ) v (2ПП1 1П1) v (2ПП1 ) v 2П1v (2ПП1 1ПП1 ) ; 1ФП2 = (1ПП2 ) v 1П2 v (1П1 ) v (1ПП2 ); 2ФП2 = (2ПП2 ПП1 ) v (2ПП2 1П1) v (2ПП2 ) v (2П1 1ПП2 ) v (21П 1П2) v v (2П1 П1 ) v 2П2 v (2ПП2 1ПП1 ) v (2П1 1ПП2 ); 3ФП1 = (3ПП1 2ПП1 1ПП1 ) v (3ПП1 2ПП1 1П1) v (3ПП1 2ПП1 ) v (3ПП1 2П1) v v (3ПП1 ПП2 ) v(3ПП1 П1 ) v 3П1 v (3ПП1 2ПП1 1ПП1 ) v (3ПП1 1ПП2 ); 3ФП2 = (3ПП2 2ПП1 1ПП1 ) v (3ПП2 2ПП1 1П1) v (3ПП2 2ПП1) v
v(3ПП2 1ПП2 ) v (3ПП2 П1) v (3ПП2 ПП2 ) v (3ПП2П2) v (3ПП2 П1 ) v 3П2 v
v(3П1 ПП2 ПП1 ) v (3П1 2ПП2 П1) v (3П1 ПП2 ) v(3П1
2П2) v (3П1 2П1 1ПП2 ) v
v (3П1 2П1 П2) v (3П1 П1 П1 ) v (3ПП2 ПП1ПП1 ) v
v( 3П1 ПП2 ПП1 ) v (3П1 П1 ПП2 );
4ФП1 = (4ПП1 3ПП1 2ПП1 1ПП1 ) v(4ПП1 3ПП1 2ПП1 1П1) v (4ПП1 3ПП1 2ПП1 ) v
v (4ПП1 3ПП1 2П1) v (4ПП1 3ПП1 1ПП2 ) v (4ПП1 3ПП1 П2) v (4ПП1 3ПП1 1П1 ) v
v (4ПП1 3П1) v(4ПП1 2ПП2 ПП1 ) v (4ПП1 2ПП2 П1) v (4ПП1 2ПП2 ) v
v(4ПП1 2П2) v(4ПП1 2П1 1ПП2 ) v (4ПП1 2П1 П2) v (4ПП1 2П1 П1 ) v 4П1 v
v(4ПП1ПП1 2ПП1 1ПП1 ) v(4ПП1 3ПП1 1ПП2 ) v
v(4ПП1 2ПП2 1ПП1 ) v (4ПП1 2П1 1ПП2 );
4ФП2 = (4ПП2 3ПП1 2ПП1 1ПП1 ) v (4ПП2 3ПП1 2ПП1 П1) v (4ПП2 3ПП1 2ПП1 ) v
v (4ПП2 ПП1 2П1) v (4ПП2 3ПП1 ПП2 ) v (4ПП2 3ПП1 2ПП1 ) v (4ПП2 ПП1 П2) v
v (4ПП2 3ПП1 П1 ) v (4ПП2 3П1) v (4ПП2 ПП2ПП1 ) v (4ПП2 ПП2 1П1)v
v (4ПП2 2ПП2 ) v (4ПП2 2П1 1ПП2 ) v (4ПП2П2) v (4ПП2 2П1 П2) v
v (4ПП2 П1 П1 ) v (4П1 3ПП2 2ПП1 ) v 4П2 v (4П1 ПП2
2ПП1 1П1) v
v (4П1 3ПП2 2ПП1 ) v (4П1 3ПП2 2П1) v (4П1ПП2 ПП2 ) v 4П1 3ПП2 П2 V (4П1 3ПП2 П1 )V(4П1 3П2) V (4П1 3П1 2ПП2 1ПП1 )V V( 4П1 3П1 2ПП2 1 П1) (4 П1 3П1 2П1 П2) (4 П1 3П1 2П1 П1 )
(4ПП2 3ПП1 1ПП2 ) V (4ПП2 2ПП2 1ПП1 ) V (4ПП2 3П1 2ПП2 ) V
V (4П1 3ПП2 1ПП1 ) V (4П1 3ПП2 1ПП2 ) V (4П1 3П1 2ПП2 1ПП1 ) . Пятивходовый ОС (5ОС) построен (фиг. 4) на основе двух быстродействующих двухвходовых ОС (2 ОС), одного элемента И-НЕ избыточной матицы трехвходовых элементов И. С целью увеличения быстродействия 2 ОС выполнен на элементах И, ИЛИ-НЕ и двух элементах запрета. Выходы 2 ОС отражают количество единиц на входном двухразрядном двоичном числе: & 20 - ноль, & 21 - одну (сумма), & 22 - две (перенос). Здесь & ji - обозначает совпадение количества i единиц на входе из j возможных. Логические выражения их имеют вид:
& o2 = ; & 12 = xx2, & 22 = x1x2.
Выходы 5 ОС различаются двух типов. При соединении 5 ОС в дальнейшем SМУК используются выходы 5 ОС первого типа (на фиг. 5 не показаны): & , & , & , & , & , & , обозначающие соответствующее количество единиц на пяти входах. Для 5, 4 ППС используются выходы 5 ОС второго типа (см. фиг. 4): сумма С, первый П1 и второй П2 разряды переноса, подготовка первого ПП1 и второго ПП2 разрядов переноса. При этом: C = & 15& 35; П1 = & 25& 35; П2 = & 55; ПП1 = & 15& 55; ПП2 = & 35. Значения & ji на выходе 5 ОС получаются в соответствии со значениями к& ji на выходе SМУК (для К = 1, 2):
& 05 = (1& 022& 02& 01);
& 15 = (1& 122& 02& 01)(1& 022& 12& 01)(1& 022& 02& 11);
& 01)(1& 122& 12& 01);
;
;
. Тридцатидвухвходовый ОС (32 ОС 11) построен (фиг. 5) на основе шестнадцати 2 ОС с помощью попарного объединения их выходов, на SМУК, выходы которых попарно соединены со следующим каскадом сумматоров SМУК и т. д. Все SМУК представляют собой матрицы двухвходовых элементов И. Два 2 ОС и SМУК, соединенные вместе, представляют собой четырехвходовый ОС (4 ОС). Аналогично соединение двух 4 ОС и следующего в каскаде SМУК представляет собой восьмивходовый ОС (8 ОС). Соединение двух 8 ОС и следующего SМУК образует шестнадцативходовый ОС (16 ОС). Выходы двух 16 ОС поступают на входы SМУК, на выходах которого с помощью элементов ИЛИ образуются выходные сигналы С, П1, П2, П3, П4, П5, которые необходимо иметь для преобразователя. Логические выражения этих сигналов имеют вид & 332& 532& 732& 932& 1132& 1332& 1532& 1732& 1932& 2132& 2332& 2532& 2732;
& 632& 732& 1032& 1132& 1432& 1532& 1832& 1932& 2232& 2332& 2632;
& 632& 732& 1232& 1332& 1432& 1532& 2032& 2132& 2232& 2332& 2832;
& 1132& 1232& 1332& 1432& 1532& 2432& 2532& 2632& 2732;
& 1832& 1932& 2032& 2132& 2232& 2332& 2432& 2532& 2632& 2732& 2832;
П5 = & 3232. В связи с увеличением нагрузки на элементы при возрастании числа входов ОС в схему вводятся дополнительные разветвители в виде элементов-повторителей (фиг. 6). Кроме того, элементы матрицы SМУК (фиг. 6), как и элементы матрицы любого выходного сумматора 5 SМУК в многовходовом ОС выполнены на основе трехвходовых элементов И, при этом третий вход этих элементов И соединяется с входом синхронизирующего импульса - СИ 2 (фиг. 8). Вход СИ 2 необходим для того, чтобы со всех N-входовых ОС преобразователя осуществить синхронный выбор результата преобразования на параллельный сумматор. Узел 6 формирования окончательного результата (фиг. 7) (для N = 64) содержит четыре 6-разрядных схем 22 формирования одновременно-групповых переносов и суммы, группу из трех элементов ИЛИ 23, пять групп элементов И 24, 25, 26, 27, 28 в 16-разрядной схеме 22, три группы из трех элементов И 29, два элемента И 30, 31 в 16-разрядной схеме 22i (i = 1, 2, 3), три группы из шести элементов ИЛИ 32. Результат с выхода 9 устройства считывается по тактовому импульсу СИ1 (фиг. 8). Устройство работает следующим образом. По синхроимпульсу СИ1 (см. фиг. 8) с задержкой на ( - среднее время срабатывания простого логического элемента) информация с регистров множителя 1 и множимого 2 поступает параллельным кодом на вход элементов И матрицы 3, с выходов которых с задержкой все частичные произведения одновременно поступают со сдвигом на входы Nvar-входовых ОС преобразователя 4 кодов. Выходные сигналы суммы и разрядов переноса ОС в каждом разряде преобразователя 4 кодов поступают с задержкой 5 (для N = 32) по синхроимпульсу СИ2 на входы входовых ОС 14 блока 5 суммирования (причем n << N), представляющих собой входы многоразрядного сумматора с одновременно-групповыми переносами. ОС 14 разбиты на четырехразрядные группы, внутри каждой из которых с помощью узлов 15, 16 формирования одновременных переносов вырабатываются сигнал 19 сумм в данных четырех разрядах и три сигнала 21 переноса , , , в среднюю, более старшую группу из четырех разрядов. Выходы 19 сумм из каждой четырехразрядной группы (см. фиг. 7) поступают на входы схем формирования одновременных переносов между четырьмя четырехразрядными группами. Выходы сигналов одновременно-групповых переносов из каждой группы 22 поступают через входы первых трех элементов ИЛИ 32 на первые входы трех элементов И 29 в этой группе разрядов, обеспечивающих формирование одновременно-групповых переносов между группами 22. На вторые входы этих трех элементов И 29 через элементы И 30, 31 поступают сигналы с выходов каждых пяти элементов И 24, 25, 26, 27, 28 из каждой группы разрядов внутри группы 22. Через время, равное 12 (см. фиг. 8), обусловленное задержкой всех групп 22 (для N = 32), на выходах 9 появляется результат умножения.
Формула изобретения
РИСУНКИ
Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8