Правильные умножители(окончание)⁠⁠

Чтобы уже закончить тему с умножителями.

Указанные в предыдущей теме(см. Решение головоломки про умножение ) умножители обеспечивают минимальное время выполнения, но к сожалению, трудно расширяемы. То есть для умножения трёхбитных чисел надо придумывать схему почти заново. Даже сами схемы выглядят как-то по кустарному – нет в них что ли симметричности и красоты.

Нужна какая-то ещё идея и такая идея есть. Всем известно устройство дешифратора. На входе оно имеет допустим два проводка, каждый из которых означает бит. На входе уже будет 4 провода, каждый из которых означает комбинацию 00, 01, 10 и 11. После того, как мы получили дешифрацию обоих множителей, нетрудно будет получить и каждый бит произведений в зависимости от множителей причём за один так.

Логическую схему дешифратора можно найти даже в Википедии . Мы её несколько оптимизируем с учётом наших идеальных устройств А и В так, чтобы всё выполнялось за один такт.

Итак логическая схема умножения двух чисел будет представлять из себя следующее

Первый такт (дешифрация)

a11=A(a0,a1)

a10=B(a1,a0)

a01=B(a0,a1)

a00 – нет отдельной линии.

Второй такт(получение результатов умножения)

с3=A(a01,b01) or A(a11,b11)

c2= A(a01,b10) or A(a10,b01) or A(a11,b10) or A(a10,b11)

c1= A(a11,b10)* or A(a10,b11)* or A(a10,b10)

c0=A(a11,b11)*

Где

* - дублирующие линии

A(x,y) - это устройство А, которое на входе получает значения x и y

or – закороченные на выходе провода. Так как мы помним, что по условия у нас 1 сильнее 0

Наглядно, на рисунке это будет выглядеть так.

Если нам надо перемножить 2 числа на 3 бита, то получим

Четыре бита

Первый такт

a11_=A(a0,a1)

a10_=B(a1,a0)

a01_=B(a0,a1)

a11=A(a2,a3)

a10=B(a3,a2)

a01=B(a2,a3)

Второй такт

a1111=A(a11_,a11)

a1110= A(a11_,a10)

…

a1100=B( a11* or a10* or a01*,a11_)

…

a0011= B( a11_* or a10_* or a01_*,a11)

Таким образом за n тактов можно дешифровать 2^n битов.

Получение же результата после дешифровки всегда занимает 1 такт.

Итого, 32 битное умножение будет занимать 6 тактов. А 64 битное – 7 тактов.

Расплатой будет конечно огромное количество элементов, поэтому увы, данную методику всё же надо сочетать с традиционной – суммированием.