1632
правки
Изменения
м
== Принцип работы ==
[[Файл:Матричный_умножитель_1Все конъюнкторы работают параллельно.Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex> p8 </tex>.png|420px|thumb|right]]
==== Суммирование частичных произведений ====
На этом этапе происходит сложение всех частичных произведений m. Это происходит так:
вначале мы суммируем <tex>m^{(0)}</tex> и <tex>m^{(1)}</tex>, саму сумму занесем в <tex>u^{(1)}</tex>, а переносы в <tex>v^{(1)}</tex>(в <tex>u^{(1)}</tex> и <tex>v^{(1)}</tex> будет не более n+1 битов в каждом), затем суммируем числа <tex>u^{(1)}</tex>, <tex>v^{(1)}</tex>, <tex>m^{(2)}</tex> и получаем <tex>u^{(2)}</tex>, <tex>v^{(2)}</tex>. Так суммируется <tex>u^{(i-1)}</tex>, <tex>v^{(i-1)}</tex>, <tex>m^{(i)}</tex> для всех i = 2, 3, … , n – 1. В итоге получаем два числа <tex>u^{(n-1)}</tex> и <tex>v^{(i-1)}</tex>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
rollbackEdits.php mass rollback
== Определение Принцип работы ====== Умножение в бинарной системе ====[[Файл:mult_bin.png|300px|right|thumb|''Умножение в столбик'']]
Умножение в бинарной системе счисления происходит точно так же, как в десятичной {{---}} по схеме ''умножения столбиком''. Если множимое {{---}} <tex>k</tex> разрядное, а множитель {{---}} <tex>n</tex> разрядный, то для формирования произведения требуется вычислить <tex>n</tex> частичных произведений и сложить их между собой. ===== Вычисление частичных произведений =====В бинарной системе для вычисления частичного произведения можно воспользоваться логическими элементами <tex>\&</tex> {{---}} конъюнкторами.Каждое частичное произведение <tex>(m_i)</tex> {{---}} это результат выполнения <tex>k</tex> логических операции <tex>\&</tex> ( между текущим <tex>i</tex>, где <tex>i=1..n</tex>, разрядом множителя и всеми <tex>k</tex> разрядами множимого) и сдвига результата логической операции влево на число разрядов, соответствующее весу текущего разряда множителя. Матричный умножитель вычисляет частичные произведения по формуле: <tex>m_i = 2^{i - цифровая 1} (a \& b_i), (i=1..n)</tex> ===== Суммирование частичных произведений =====На этом этапе происходит сложение всех частичных произведений <tex> m </tex>. ==== Схема ====[[Файл:Mult_3.png|700px|right|thumb|Схема матричного умножителя]]Принципиальная схемаумножителя, осуществляющяя умножение реализующая алгоритм двоичного умножения в столбик для двух четырёх {{---}} разрядных чиселприведена на рисунке. Формирование частичных произведений осуществляется посредством логических элементов <tex>\&</tex>.Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.Разрядность результата {{---}} <tex>l</tex> определяется разрядностью множителя {{---}} <tex>n</tex> и множимого {{---}} <tex>k</tex>: <tex> l=n+k </tex>.
==== Вычисление частичных произведений '''Матричный умножитель''' ====Матричный умножитель вычисляет частичные произведения Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по формуле: которым передаются разряды числа <tex>A</tex> и числа <tex>B<br/tex>. В точках пересечения этих проводников находятся логические элементы <tex>m^{(i)} = a * b_i * 2^{i}\&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
==Схемная сложность==
Частичные произведения вычисляются за <tex>n </tex> шагов, то есть имеют временную сложность O(n). Сложение с вычисление вычислением переносов включает <tex>n - 1 шагов и требует времени O(n)</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n). <br/tex>. В итоге суммарное время работы: <brtex>O(n) + O(n) + O(\log n) = O(n) <br/tex>Есть и более быстрые способы умножения двух чиселВремя работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]]как это предполагается алгоритмом, которое работает Oприведенным на первом рисунке (log nобщая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.
Особенно заметен выигрыш в быстродействии при построении многоразрядных умножителей, однако ничего не бывает бесплатно. В обмен на быстродействие придётся заплатить увеличением разрядности сумматоров, а значит сложностью схемы. Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>. == Литература См. также ==*[[Дерево Уоллеса]]*[[Двоичный каскадный сумматор]] == Источники информации ==* [http://bookfi.net/book/556972 Е. Угрюмов "Цифровая схемотехника" 2001г.] * [http://bookfi.net/book/532753 Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.] * [http://bookfi.net/book/637011 М.И. Богданович "Цифровые интегральные микросхемы" 1996г.] * [http://library.espec.ws/section6/article46.html Схема умножителя]
* ''[http://ru.wikipedia.org/wiki/Кормен Кормен Т.], [http://ru.wikipedia.org/wiki/Лейзерсон,_Чарльз_Эрик Лейзерсон Ч.], [http://ru.wikipedia.org/wiki/Ривест,_Рональд_Линн Ривест Р.]''. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
