172
правки
Изменения
→Вычисление частичных произведений
== Принцип работы ==
==== Умножение в бинарной системе ====
[[Файл:mult_bin.png|180px300px|right|thumb|''Умножение в столбик'']]
Умножение в бинарной системе счисления происходит точно так же, как в десятичной {{- --}} по схеме "''умножения столбиком"''. Если множимое {{--- }} <tex>k</tex> разрядное, а множитель {{---}} <tex>n</tex> разрядный, то для формирования произведения требуется вычислить <tex>n</tex> частичных произведений и сложить их между собой.
===== Вычисление частичных произведений =====
В бинарной системе для вычисления частичного произведения можно воспользоваться логическими элементами "AND" <tex>\&</tex> {{--- }} конъюнкторами.Каждое частичное произведение (<tex>(m_i)</tex>) {{--- }} это результат выполнения <tex>k</tex> логических операции "AND" <tex>\&</tex> ( между текущим <tex>i ( </tex>, где <tex>i=1..n)</tex> , разрядом множителя и всеми <tex>k</tex> разрядами множимого) и сдвига результата логической операции влево на число разрядов, соответствующее весу текущего разряда множителя. Матричный умножитель вычисляет частичные произведения по формуле:
<tex>m_i = 2^{i - 1} (a \wedge & b_i), где (i=1..n)</tex>
===== Суммирование частичных произведений =====
==== Схема ====
[[Файл:Mult_3.png|700px|right|thumb|Схема матричного умножителя]]Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик для двух четырёх{{---}} разрядных чисел приведена на рисунке. Формирование частичных произведений осуществляется посредством логических элементов "AND"<tex>\&</tex>.
Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.
Разрядность результата {{- --}} <tex>l</tex> определяется разрядностью множителя {{- --}} <tex>n</tex> и множимого {{--- }} <tex> k</tex>:
<tex> l=n+k </tex>.
Все конъюнкторы работаю работают параллельно.
Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.
В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.
Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex> p8 </tex>.
==== "'''Матричный умножитель" ''' ====Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “И”<tex>\&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
==Схемная сложность==
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>.
== Литература и источники См. также ==* Е. Угрюмов "Цифровая схемотехника" 2001г. [[Дерево Уоллеса]]*[[Двоичный каскадный сумматор]]
== Источники информации ==* Дк[http://bookfi. Фnet/book/556972 Е. Уэйкерли Угрюмов "Проектирование цифровых устройств, том 1.Цифровая схемотехника" 2002г2001г. ]
* М[http://bookfi.Иnet/book/532753 Дк. Богданович Ф. Уэйкерли "Цифровые интегральные микросхемыПроектирование цифровых устройств, том 1." 1996г2002г. ]
* В[http://bookfi.Лnet/book/637011 М. Шило И. Богданович "Популярные цифровые Цифровые интегральные микросхемы" 1988г1996г. ]
* [http://library.espec.ws/section6/article46.html Схема умножителя]
