172
правки
Изменения
→Вычисление частичных произведений
== Принцип работы ==
==== Умножение в бинарной системе ====
[[Файл:mult_bin.png|180px300px|right|thumb|''Умножение в столбик'']]
Умножение в бинарной системе счисления происходит точно так же, как в десятичной {{---}} по схеме ''умножения столбиком''.
===== Вычисление частичных произведений =====
В бинарной системе для вычисления частичного произведения можно воспользоваться логическими элементами <tex>\wedge&</tex> {{---}} конъюнкторами.Каждое частичное произведение (<tex>(m_i)</tex>) {{---}} это результат выполнения <tex>k</tex> логических операции <tex>\wedge&</tex> ( между текущим <tex>i ( </tex>, где <tex>i=1..n)</tex> , разрядом множителя и всеми <tex>k</tex> разрядами множимого) и сдвига результата логической операции влево на число разрядов, соответствующее весу текущего разряда множителя. Матричный умножитель вычисляет частичные произведения по формуле:
<tex>m_i = 2^{i - 1} (a \wedge & b_i), </tex> <tex>(i=1..n)</tex>
===== Суммирование частичных произведений =====
[[Файл:Mult_3.png|700px|right|thumb|Схема матричного умножителя]]
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик для двух четырёх {{---}} разрядных чисел приведена на рисунке.
Формирование частичных произведений осуществляется посредством логических элементов <tex>\wedge&</tex>.
Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.
Разрядность результата {{---}} <tex>l</tex> определяется разрядностью множителя {{---}} <tex>n</tex> и множимого {{---}} <tex>k</tex>:
Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex> p8 </tex>.
==== '''Матричный умножитель {{---}} Binary multiplier''' ====Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы <tex>\wedge&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
==Схемная сложность==
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>.
== См . также ==
*[[Дерево Уоллеса]]
*[[Двоичный каскадный сумматор]]
