Главная страница  |  Описание сайта  |  Контакты
ОДНОТАКТНЫЙ УМНОЖИТЕЛЬ ДВОИЧНЫХ ЧИСЕЛ
ОДНОТАКТНЫЙ УМНОЖИТЕЛЬ ДВОИЧНЫХ ЧИСЕЛ

ОДНОТАКТНЫЙ УМНОЖИТЕЛЬ ДВОИЧНЫХ ЧИСЕЛ

Патент Российской Федерации
Суть изобретения: Изобретение относится к вычислительной технике и может быть использовано при построении быстродействующих умножителей для арифметических устройств ЭВМ и специализированных вычислительных устройств. Цель изобретения - повышение быстродействия. Цель достигается за счет построения умножителя на основе однослойного преобразователя Nvaz -разрядного кода в (1+/log2Nvaz/целое) -рядный код и (1+/log2Nvaz/целое) -входового многоразрядного параллельного сумматора с одновременно-групповыми переносами. Преобразователь выполнен на разнотипных многовходовых одноразрядных сумматорах. Между разрядами как преобразователя, так и параллельного сумматора распространяется многоразрядный перенос. 8 ил.
Поиск по сайту

1. С помощью поисковых систем

   С помощью Google:    

   С помощью Яндекс:  

2. Экспресс-поиск по номеру патента


введите номер патента (7 цифр)

3. По номеру патента и году публикации

2000000 ... 2099999   (1994-1997 гг.)

2100000 ... 2199999   (1997-2003 гг.)
Номер патента: 2012039
Класс(ы) патента: G06F7/52
Номер заявки: 4616622/24
Дата подачи заявки: 06.12.1988
Дата публикации: 30.04.1994
Заявитель(и): Пензенский научно-исследовательский электротехнический институт
Автор(ы): Чижухин Г.Н.
Патентообладатель(и): Пензенский научно-исследовательский электротехнический институт
Описание изобретения: Изобретение относится к вычислительной технике и может использоваться при построении быстродействующих умножителей для арифметических устройств ЭВМ и специализированных вычислительных устройств.
Цель изобретения - повышение быстродействия.
На фиг. 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 (2 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 появляется результат умножения.
Формула изобретения: ОДНОТАКТНЫЙ УМНОЖИТЕЛЬ ДВОИЧНЫХ ЧИСЕЛ, содержащий M-разрядные регистры множимого и множителя (m - разрядность сомножителей), матрицу из m · m элементов И, (2m - 1)-разрядный преобразователь Nvar-разрядного кода в n-разрядный код (n < Nvar, n= 1+] log2Nvar[, Nvar-двоичный непозиционный варьируемый для разных разрядов код), блок суммирования и узел формирования окончательного результата, выход которого соединен с выходом результата умножителя, входы множимого и множителя умножителя соединены соответственно с информационными входами регистров множимого и множителя, выход i-го разряда регистра множителя соединен соответственно с первыми входами элементов И i-й строки матрицы (i= 1, . . . , m), выход j-го разряда регистра множимого соединен соответственно с вторыми входами элементов И j-го столбца матрицы, (j= 1, . . . m) выходы всех элементов И матрицы соединены с соответствующими входами разрядов со сдвигом на один разряд влево (2m-1) -разрядного преобразователя Nvar-разрядного кода в n-рядный код, отличающийся тем, что, с целью повышения быстродействия, (2m-1)-разрядный преобразователь Nvar-разрядного кода в n-рядный код в каждом разряде содержит Nvar-входовой одноразрядный сумматор, блок суммирования состоит из n-входовых параллельно-параллельных сумматоров, каждый разряд которых содержит nvar-входовой одноразрядовый сумматор (nvar= 2,3,4,5,6), два узла формирования одновременных переносов и сумматор по модулю два, причем выход суммы Nvar-входового одноразрядного сумматора ni-го разряда (2m-1)разрядного преобразователя Nvar-разрядного кода в n-рядный код соединен соответственно с первым входом nvar-входового одноразрядного сумматора i-го разряда n-входового параллельно-параллельного сумматора (i= 1, . . . 2, m-1), выходы переносов Nva r-входовых одноразрядных сумматоров i-го разряда (2m-1)-разрядного преобразователя Nvar-разрядного кода в n-рядный соединены с соответствующими n-1 входами nvar-входового одноразрядного сумматора (i+1)-го разряда n-входового параллельно-параллельного сумматора, а в n-входовом параллельно-параллельном сумматоре выходы преносов nvarвходовых одноразрядных сумматоров соединены с входами первого и второго узлов формирования одновременных переносов соответствующих разрядов, выходы первого и второго узлов формирования одновременных переносов i-го разряда соединены соответственно с первым и вторым входами сумматора по модулю два (i+1)-го и (i+2)-го разрядов, выход суммы nvar-входового одноразрядного сумматора i-го разряда соединен соответственно с третьим входом сумматора по модулю два i-го разряда, выход которого соединен с выходом суммы i-го разряда n-входового параллельно-параллельного сумматора, первый, второй и третий выходы переносов каждого 4i-го разряда которого соединены соответственно с выходами первого и второго узлов формирования одновременных переносов каждого 4i-го разряда и выходом второго узла формирования каждого (4i-1)-го разряда, а узел формирования окончательного результата содержит Nmax/8-1 групп из шести элементов ИЛИ, Nmax/8-1 групп из трех элементов И, (Nmax/8)-ю группу из трех элементов ИЛИ и Nmax/8 16-разрядных схем формирования одновременно-групповых переносов и суммы, причем каждая 16-разрядная схема формирования одновременно-групповых переносов и суммы, кроме первой схемы, содержит пять групп из четырех элементов И каждая и два элемента И, а первая схема содержит пять групп по три элемента И в каждой, первые входы элементов ИЛИ j-й группы (j= 1, . . . , Nmax/8) соединены соответственно с первым, вторым и третьим выходами переносов каждого 4i-го разряда n-входового параллельно-параллельного сумматора, а вторые входы - с выходами четвертых элементов И третьей, четвертой и пятой групп j-й 16-разрядной схемы формирования одновременно-групповых переносов и суммы, третьи входы элементов ИЛИ l-й группы (l= 2, . . . , Nmax/8-1) соединены с выходами элементов И (l-1)-й группы, первый, второй и третий входы переносов каждого (4i+1)-го разряда n-входового параллельно-параллельного сумматора соединены соответственно с выходами первого, второго и третьего элементов ИЛИ p-й группы (p= 1, . . . , Nmax/8-1), выходы четвертого, пятого и шестого элементов ИЛИ p-й группы соединены с соответствующими входами каждого из элементов И третьей, четвертой и пятой групп (p+1)-й 16-разрядной схемы формирования одновременно-групповых переносов и суммы и первыми входами элементов И p-й группы, вторые входы которых соединены с выходами первого и второго элементов И (p+1)-й 16-разрядной схемы формирования одновременно-групповых переносов и суммы, выходы суммы с первого по четвертый каждых четырех разрядов n-входового параллельно-параллельного сумматора соединены с выходами соответствующих разрядов результата умножителя, выходы элементов ИЛИ (Nmax/8)-й группы и элементов И (Nmax/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-входовых четырехразрядных параллельно-параллельных сумматоров.