Правильные умножители(окончание)
Чтобы уже закончить тему с умножителями.
Указанные в предыдущей теме(см. Решение головоломки про умножение ) умножители обеспечивают минимальное время выполнения, но к сожалению, трудно расширяемы. То есть для умножения трёхбитных чисел надо придумывать схему почти заново. Даже сами схемы выглядят как-то по кустарному – нет в них что ли симметричности и красоты.
Нужна какая-то ещё идея и такая идея есть. Всем известно устройство дешифратора. На входе оно имеет допустим два проводка, каждый из которых означает бит. На входе уже будет 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 тактов.
Расплатой будет конечно огромное количество элементов, поэтому увы, данную методику всё же надо сочетать с традиционной – суммированием.
