Однотактный умножитель двоичных чисел

 

Изобретение относится к вычислительной технике и может быть использовано при построении быстродействующих умножителей для арифметических устройств ЭВМ и специализированных вычислительных устройств. Цель изобретения - повышение быстродействия. Цель достигается за счет построения умножителя на основе однослойного преобразователя N_vaz -разрядного кода в (1+/log₂N_vaz/_целое) -рядный код и (1+/log₂N_vaz/_целое) -входового многоразрядного параллельного сумматора с одновременно-групповыми переносами. Преобразователь выполнен на разнотипных многовходовых одноразрядных сумматорах. Между разрядами как преобразователя, так и параллельного сумматора распространяется многоразрядный перенос. 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 N_var-разрядного кода в n-рядный код, блок 5 суммирования, узел 6 формирования окончательного результата, входы множителя 7 и множимого 8, выходы 9 результата. Преобразователь 4 N_var-разрядного кода в n-рядный код является однослойным и содержит в каждом разряде N_var-входовойОС. Преобразователь 4 имеет в своем составе один слой (линейку) N-входовых ОС следующих типов: 2, 3, . . , N-1, N-, N-1, . . . , трех-, двухвходовые ОС. На выходах каждого N-входового ОС вырабатываются сумма С и [log₂ N_var] _целое- разрядный перенос. В частности, для фиг. 2 имеют место [log₂32] _целое = 5, [log₂31] _целое = 4, [log₂30] _целое = 4, т. е. пяти- и четырехразрядные переносы, разряды которых обозначены П1, П2, П3, П4, П5.

На фиг. 2 (для N = 32) представлены четыре центральных сумматора из линейки: два 31-входовых (31 ОС) 10, один 32-входовый (32 ОС) 11 и один 30-входовый (30 ОС) 12.

Блок 5 суммирования состоит из n-входовых ППС 13, каждый разряд которых (фиг. 3) содержит n_var-входовый ОС 14 (n_var = 2, 3, 4, 5), два узла 15, 16 формирования одновременных переносов и сумматор 17 по модулю два, входы 18 ППС 13, выходы 19 суммы ППС 13, входы 20 и выходы 21 переносов ППС 13. Узел формирования одновременных переносов состоит из элементов И и ИЛИ, на входы которых поступают сигналы согласно следующим логическим выражениям, где (для пятивходового четырехразрядного сумматора) ⁱФП1(ⁱФП2) - выходы узлов 15 (16) для i-го разряда; ⁱC, ⁱПj, ⁱППj - выходы суммы и переносов соответственно для j-го разряда n_var-входового ОС 14; , , - значения переносов из предыдущей четверки разрядов (в следующую четверку разрядов) сумматора.

¹ФП1 = (¹ПП1 ) v ¹П1 v (¹ПП1 ); ²ФП1 = (²ПП1 ¹ПП1 ) v (²ПП1 ¹П1) v (²ПП1 ) v ²П1v (²ПП1 ¹ПП1 ) ; ¹ФП2 = (¹ПП2 ) v ¹П2 v (¹П1 ) v (¹ПП2 ); ²ФП2 = (²ПП2 ПП1 ) v (²ПП2 ¹П1) v (²ПП2 ) v (²П1 ¹ПП2 ) v (²1П ¹П2) v v (²П1 П1 ) v ²П2 v (²ПП2 ¹ПП1 ) v (²П1 ¹ПП2 ); ³ФП1 = (³ПП1 ²ПП1 ¹ПП1 ) v (³ПП1 ²ПП1 ¹П1) v (³ПП1 ²ПП1 ) v (³ПП1 ²П1) v v (³ПП1 ПП2 ) v(³ПП1 П1 ) v ³П1 v (³ПП1 ²ПП1 ¹ПП1 ) v (³ПП1 ¹ПП2 ); ³ФП2 = (³ПП2 ²ПП1 ¹ПП1 ) v (³ПП2 ²ПП1 ¹П1) v (³ПП2 ²ПП1
) v
v(³ПП2 ¹ПП2 ) v (³ПП2 П1) v (³ПП2 ПП2 ) v (³ПП2П2) v (³ПП2 П1 ) v ³П2 v
v(³П1 ПП2 ПП1 ) v (³П1 ²ПП2 П1) v (³П1 ПП2 ) v(³П1
²П2) v (³П1 ²П1 ¹ПП2 ) v
v (³П1 ²П1 П2) v (³П1 П1 П1 ) v (³ПП2 ПП1ПП1 ) v
v( ³П1 ПП2 ПП1 ) v (³П1 П1 ПП2 );
⁴ФП1 = (⁴ПП1 ³ПП1 ²ПП1 ¹ПП1 ) v(⁴ПП1 ³ПП1 ²ПП1 ¹П1) v (⁴ПП1 ³ПП1 ²ПП1 ) v
v (⁴ПП1 ³ПП1 ²П1) v (⁴ПП1 ³ПП1 ¹ПП2 ) v (⁴ПП1 ³ПП1 П2) v (⁴ПП1 ³ПП1 ¹П1 ) v
v (⁴ПП1 ³П1) v(⁴ПП1 ²ПП2 ПП1 ) v (⁴ПП1 ²ПП2 П1) v (⁴ПП1 ²ПП2 ) v
v(⁴ПП1 ²П2) v(⁴ПП1 ²П1 ¹ПП2 ) v (⁴ПП1 ²П1 П2) v (⁴ПП1 ²П1 П1 ) v ⁴П1 v
v(⁴ПП1ПП1 ²ПП1 ¹ПП1 ) v(⁴ПП1 ³ПП1 ¹ПП2 ) v
v(⁴ПП1 ²ПП2 ¹ПП1 ) v (⁴ПП1 ²П1 ¹ПП2 );
⁴ФП2 = (⁴ПП2 ³ПП1 ²ПП1 ¹ПП1 ) v (⁴ПП2 ³ПП1 ²ПП1 П1) v (⁴ПП2 ³ПП1 ²ПП1 ) v
v (⁴ПП2 ПП1 ²П1) v (⁴ПП2 ³ПП1 ПП2 ) v (⁴ПП2 ³ПП1 ²ПП1 ) v (⁴ПП2 ПП1 П2) v
v (⁴ПП2 ³ПП1 П1 ) v (⁴ПП2 ³П1) v (⁴ПП2 ПП2ПП1 ) v (⁴ПП2 ПП2 ¹П1)v
v (⁴ПП2 ²ПП2 ) v (⁴ПП2 ²П1 ¹ПП2 ) v (⁴ПП2П2) v (⁴ПП2 ²П1 П2) v
v (⁴ПП2 П1 П1 ) v (⁴П1 ³ПП2 ²ПП1 ) v ⁴П2 v (⁴П1 ПП2
²ПП1 ¹П1) v
v (⁴П1 ³ПП2 ²ПП1 ) v (⁴П1 ³ПП2 ²П1) v (⁴П1ПП2 ПП2 ) v ⁴П1 ³ПП2 П2 V (⁴П1 ³ПП2 П1 )V(⁴П1 ³П2) V (⁴П1 ³П1 ²ПП2 ¹ПП1 )V V( ⁴П1 ³П1 ²ПП2 ¹ П1) (⁴ П1 ³П1 ²П1 П2) (⁴ П1 ³П1 ²П1 П1 )
(⁴ПП2 ³ПП1 ¹ПП2 ) V (⁴ПП2 ²ПП2 ¹ПП1 ) V (⁴ПП2 ³П1 ²ПП2 ) V
V (⁴П1 ³ПП2 ¹ПП1 ) V (⁴П1 ³ПП2 ¹ПП2 ) V (⁴П1 ³П1 ²ПП2 ¹ПП1 ) .

Пятивходовый ОС (5ОС) построен (фиг. 4) на основе двух быстродействующих двухвходовых ОС (2 ОС), одного элемента И-НЕ избыточной матицы трехвходовых элементов И.

С целью увеличения быстродействия 2 ОС выполнен на элементах И, ИЛИ-НЕ и двух элементах запрета. Выходы 2 ОС отражают количество единиц на входном двухразрядном двоичном числе: & ₂⁰ - ноль, & ₂¹ - одну (сумма), & ₂² - две (перенос). Здесь & _jⁱ - обозначает совпадение количества i единиц на входе из j возможных. Логические выражения их имеют вид:
& ^o₂ = ; & ¹₂ = xx₂, & ²₂ = x₁x₂.
Выходы 5 ОС различаются двух типов. При соединении 5 ОС в дальнейшем SМУК используются выходы 5 ОС первого типа (на фиг. 5 не показаны): & , & , & , & , & , & , обозначающие соответствующее количество единиц на пяти входах. Для 5, 4 ППС используются выходы 5 ОС второго типа (см. фиг. 4): сумма С, первый П1 и второй П2 разряды переноса, подготовка первого ПП1 и второго ПП2 разрядов переноса. При этом: C = & ¹₅& ³₅; П1 = & ²₅& ³₅; П2 = & ⁵₅; ПП1 = & ¹₅& ⁵₅; ПП2 = & ³₅. Значения & _jⁱ на выходе 5 ОС получаются в соответствии со значениями ^к& _jⁱ на выходе SМУК (для К = 1, 2):
& ⁰₅ = (¹& ⁰₂²& ⁰₂& ⁰₁);
& ¹₅ = (¹& ¹₂²& ⁰₂& ⁰₁)(¹& ⁰₂²& ¹₂& ⁰₁)(¹& ⁰₂²& ⁰₂& ¹₁);
& ⁰₁)(¹& ¹₂²& ¹₂& ⁰₁);
;
;
.

Тридцатидвухвходовый ОС (32 ОС 11) построен (фиг. 5) на основе шестнадцати 2 ОС с помощью попарного объединения их выходов, на SМУК, выходы которых попарно соединены со следующим каскадом сумматоров SМУК и т. д. Все SМУК представляют собой матрицы двухвходовых элементов И. Два 2 ОС и SМУК, соединенные вместе, представляют собой четырехвходовый ОС (4 ОС). Аналогично соединение двух 4 ОС и следующего в каскаде SМУК представляет собой восьмивходовый ОС (8 ОС). Соединение двух 8 ОС и следующего SМУК образует шестнадцативходовый ОС (16 ОС). Выходы двух 16 ОС поступают на входы SМУК, на выходах которого с помощью элементов ИЛИ образуются выходные сигналы С, П1, П2, П3, П4, П5, которые необходимо иметь для преобразователя. Логические выражения этих сигналов имеют вид & ³₃₂& ⁵₃₂& ⁷₃₂& ⁹₃₂& ¹¹₃₂& ¹³₃₂& ¹⁵₃₂& ¹⁷₃₂& ¹⁹₃₂& ²¹₃₂& ²³₃₂& ²⁵₃₂& ²⁷₃₂;
& ⁶₃₂& ⁷₃₂& ¹⁰₃₂& ¹¹₃₂& ¹⁴₃₂& ¹⁵₃₂& ¹⁸₃₂& ¹⁹₃₂& ²²₃₂& ²³₃₂& ²⁶₃₂;
& ⁶₃₂& ⁷₃₂& ¹²₃₂& ¹³₃₂& ¹⁴₃₂& ¹⁵₃₂& ²⁰₃₂& ²¹₃₂& ²²₃₂& ²³₃₂& ²⁸₃₂;
& ¹¹₃₂& ¹²₃₂& ¹³₃₂& ¹⁴₃₂& ¹⁵₃₂& ²⁴₃₂& ²⁵₃₂& ²⁶₃₂& ²⁷₃₂;
& ¹⁸₃₂& ¹⁹₃₂& ²⁰₃₂& ²¹₃₂& ²²₃₂& ²³₃₂& ²⁴₃₂& ²⁵₃₂& ²⁶₃₂& ²⁷₃₂& ²⁸₃₂;
П5 = & ³²₃₂.

В связи с увеличением нагрузки на элементы при возрастании числа входов ОС в схему вводятся дополнительные разветвители в виде элементов-повторителей (фиг. 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, с выходов которых с задержкой все частичные произведения одновременно поступают со сдвигом на входы N_var-входовых ОС преобразователя 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 появляется результат умножения.

Формула изобретения

ОДНОТАКТНЫЙ УМНОЖИТЕЛЬ ДВОИЧНЫХ ЧИСЕЛ, содержащий M-разрядные регистры множимого и множителя (m - разрядность сомножителей), матрицу из m m элементов И, (2m - 1)-разрядный преобразователь N_var-разрядного кода в n-разрядный код (n < N_var, n= 1+] log₂N_var[, N_var-двоичный непозиционный варьируемый для разных разрядов код), блок суммирования и узел формирования окончательного результата, выход которого соединен с выходом результата умножителя, входы множимого и множителя умножителя соединены соответственно с информационными входами регистров множимого и множителя, выход i-го разряда регистра множителя соединен соответственно с первыми входами элементов И i-й строки матрицы (i= 1, . . . , m), выход j-го разряда регистра множимого соединен соответственно с вторыми входами элементов И j-го столбца матрицы, (j= 1, . . . m) выходы всех элементов И матрицы соединены с соответствующими входами разрядов со сдвигом на один разряд влево (2m-1) -разрядного преобразователя N_var-разрядного кода в n-рядный код, отличающийся тем, что, с целью повышения быстродействия, (2m-1)-разрядный преобразователь N_var-разрядного кода в n-рядный код в каждом разряде содержит N_var-входовой одноразрядный сумматор, блок суммирования состоит из n-входовых параллельно-параллельных сумматоров, каждый разряд которых содержит n_var-входовой одноразрядовый сумматор (n_var= 2,3,4,5,6), два узла формирования одновременных переносов и сумматор по модулю два, причем выход суммы N_var-входового одноразрядного сумматора ni-го разряда (2m-1)разрядного преобразователя N_var-разрядного кода в n-рядный код соединен соответственно с первым входом n_var-входового одноразрядного сумматора i-го разряда n-входового параллельно-параллельного сумматора (i= 1, . . . 2, m-1), выходы переносов N_{va r}-входовых одноразрядных сумматоров i-го разряда (2m-1)-разрядного преобразователя N_var-разрядного кода в n-рядный соединены с соответствующими n-1 входами n_var-входового одноразрядного сумматора (i+1)-го разряда n-входового параллельно-параллельного сумматора, а в n-входовом параллельно-параллельном сумматоре выходы преносов n_varвходовых одноразрядных сумматоров соединены с входами первого и второго узлов формирования одновременных переносов соответствующих разрядов, выходы первого и второго узлов формирования одновременных переносов i-го разряда соединены соответственно с первым и вторым входами сумматора по модулю два (i+1)-го и (i+2)-го разрядов, выход суммы n_var-входового одноразрядного сумматора i-го разряда соединен соответственно с третьим входом сумматора по модулю два i-го разряда, выход которого соединен с выходом суммы i-го разряда n-входового параллельно-параллельного сумматора, первый, второй и третий выходы переносов каждого 4i-го разряда которого соединены соответственно с выходами первого и второго узлов формирования одновременных переносов каждого 4i-го разряда и выходом второго узла формирования каждого (4i-1)-го разряда, а узел формирования окончательного результата содержит N_max/8-1 групп из шести элементов ИЛИ, N_max/8-1 групп из трех элементов И, (N_max/8)-ю группу из трех элементов ИЛИ и N_max/8 16-разрядных схем формирования одновременно-групповых переносов и суммы, причем каждая 16-разрядная схема формирования одновременно-групповых переносов и суммы, кроме первой схемы, содержит пять групп из четырех элементов И каждая и два элемента И, а первая схема содержит пять групп по три элемента И в каждой, первые входы элементов ИЛИ j-й группы (j= 1, . . . , N_max/8) соединены соответственно с первым, вторым и третьим выходами переносов каждого 4i-го разряда n-входового параллельно-параллельного сумматора, а вторые входы - с выходами четвертых элементов И третьей, четвертой и пятой групп j-й 16-разрядной схемы формирования одновременно-групповых переносов и суммы, третьи входы элементов ИЛИ l-й группы (l= 2, . . . , N_max/8-1) соединены с выходами элементов И (l-1)-й группы, первый, второй и третий входы переносов каждого (4i+1)-го разряда n-входового параллельно-параллельного сумматора соединены соответственно с выходами первого, второго и третьего элементов ИЛИ p-й группы (p= 1, . . . , N_max/8-1), выходы четвертого, пятого и шестого элементов ИЛИ p-й группы соединены с соответствующими входами каждого из элементов И третьей, четвертой и пятой групп (p+1)-й 16-разрядной схемы формирования одновременно-групповых переносов и суммы и первыми входами элементов И p-й группы, вторые входы которых соединены с выходами первого и второго элементов И (p+1)-й 16-разрядной схемы формирования одновременно-групповых переносов и суммы, выходы суммы с первого по четвертый каждых четырех разрядов n-входового параллельно-параллельного сумматора соединены с выходами соответствующих разрядов результата умножителя, выходы элементов ИЛИ (N_max/8)-й группы и элементов И (N_max/8-1)-й группы соединены с выходом переполнения умножителя, а в каждой 16-разрядной схеме формирования одновременно-групповых переносов и суммы, кроме первой схемы, выходы суммы с первого по четвертый K-го n-входового четырехразрядного параллельно-параллельного сумматора (K= 1,2,3,4) соединены с соответствующими входами K-го элемента И первой группы, выход которого соединен с соответствующими входами K-х элементов третьей и четвертой групп и соответствующим входом первого элемента И, выходы суммы с первого по третий K-го n-входового четырехразрядного параллельно-параллельного сумматора соединены с соответствующими входами K-го элемента И второй группы, выход которого соединен с соответствующими входом K-го элемента И пятой группы и соответствующим входом второго элемента И, выходы t-х элементов И третьей, четвертой и пятой групп (t= 1,2,3) соединены соответственно с первым, вторым и третьим входами переноса (t+1)го n-входового четырехразрядного параллельно-параллельного сумматора, первый, второй и третий выходы переноса t-го n-входового четырехразрядного параллельно-параллельного сумматора соединены с входами соответствующих элементов И третьей, четвертой и пятой групп, а в первой 16-разрядной схеме формирования одновременно-групповых переносов и суммы выходы суммы с первого по четвертый b-го n-входового четырехразрядного параллельно-параллельного сумматора (b= 2,3,4) соединены с соответствующими входами (b-1)-го элемента И первой группы, выход которого соединен с соответствующими входами (b-1)-х элементов И третьей и четвертой групп, выходы суммы с первого по третий b-го n-входового четырехразрядного параллельно-параллельного сумматора соединены с соответствующими входами (b-1)-го элемента И второй группы, выход которого соединен с соответствующим входом (b-1)-го элемента И пятой группы, первый, второй и третий выходы переноса t-го n-входового четырехразрядного параллельно-параллельного сумматора соединены с входами соответствующих элементов И третьей, четвертой и пятой групп, выходы первых и вторых элементов И третьей, четвертой и пятой групп соединены соответственно с первым, вторым и третьим входами переноса третьего и четвертого n-входовых четырехразрядных параллельно-параллельных сумматоров.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8