1632
правки
Изменения
м
== Принцип работы ==
[[Файл:Матричный_умножитель_2Все конъюнкторы работают параллельно.Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <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|Схема матричного умножителя]]Принципиальная схемаумножителя, осуществляющяя умножение реализующая алгоритм двоичного умножения в столбик для двух четырёх {{---}} разрядных чисел c помощью суммированияприведена на рисунке. Формирование частичных произведений осуществляется посредством логических элементов <tex>\&</tex>.Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.Разрядность результата {{---}} <tex>l</tex> определяется разрядностью множителя {{---}} <tex>n</tex> и множимого {{---}} <tex>k</tex>: <tex> l=n+k </tex>.
==== Вычисление частичных произведений '''Матричный умножитель''' ====Матричный умножитель вычисляет частичные произведения Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по формуле: которым передаются разряды числа <tex>A</tex> и числа <brtex>B</tex>. В точках пересечения этих проводников находятся логические элементы <tex>m_i = 2^{i} a b_i\&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
==Схемная сложность==
Частичные произведения вычисляются за ''<tex>n'' </tex> шагов. Сложение с вычисление вычислением переносов включает ''<tex>n - 1'' </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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
