1632
правки
Изменения
м
== Определение ==
Матричный умножитель {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая умножение двух чисел c помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
Матричный умножитель вычисляет частичные произведения по формуле: <tex>m_i = 2^{i - 1} (a \& b_i), (i=1..n)</tex>
<tex>m_i = 2^{i} a b_i</tex>==== Суммирование частичных произведений =====На этом этапе происходит сложение всех частичных произведений <tex> m. В большинстве современных систем это происходит с помощью [[Дерево Уоллеса|дерева Уоллеса]]</tex>.
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляют микросхемы <tex>D1, D3, D5, D7 </tex>. В этих микросхемах содержится сразу четыре логических элемента “2И”.==== Работа схемы =======l== Этап 1 =====Сумматор, выполненный на микросхеме <tex>D6</tex>, суммирует первое и второе частные произведения. При этом младший разряд первого частного произведения не нуждается в суммировании. Поэтому он подаётся на выход умножителя непосредственно (разряд <tex>M0n+k </tex>).
===== Этап 2 =====
Второе частное произведение должно быть сдвинуто на один разряд. Это осуществляется тем, что младший разряд выходного числа сумматора <tex>D6</tex> соединяется со вторым разрядом произведения (<tex>M1</tex>). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов <tex>A</tex> соединяется с первым разрядом частного произведения, первый разряд группы входов <tex>A</tex> соединяется со вторым разрядом частного произведения, и так же третий, четвертый и старший. Однако старший разряд группы входов <tex>A</tex> не с чем соединять! Вспомним, что если добавить к числу слева ноль, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемы.
===== Завершение =====Все конъюнкторы работают параллельно.Точно таким же образом осуществляется суммирование третьего Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и четвёртого частного произведенияпереносов из предыдущих разрядов сумматора.В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом. Это суммирование выполняют микросхемы Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex>D4p8 </tex> и <tex>D2</tex> соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.
==== "Матричный умножитель" ====
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “2И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
Конкретно по нашей схеме:
Скорость работы схемы, приведенной на рисунке определяется глубиной этой схемы. Это цепь <tex>D7, D6, D4, D2</tex>.
rollbackEdits.php mass rollback
== Принцип работы ==
==== Умножение в бинарной системе ====
[[Файл:Двоумнmult_bin.gifpng|90px300px|left]][[Файл:Матричный_умножитель_2.PNG|420pxright|thumb|right''Умножение в столбик'']] Умножение в бинарной системе счисления происходит точно так же, как в десятичной{{---}} по схеме ''умножения столбиком''.Для формирования произведения требуется вычислить Если множимое {{---}} <tex>nk</tex> (где разрядное, а множитель {{---}} <tex>n</tex> — количество разрядов в числах) частичных произведений. Примечательно разрядный, то, что в бинарной арифметике следует умножать только числа для формирования произведения требуется вычислить <tex>1</tex> и <tex>0n</tex>. Это означает, что нужно прибавлять к сумме остальных частичных произведений либо множитель, либо ноль. Таким образом, для формирования частичного произведения можно воспользоваться логическими элементами “2И”и сложить их между собой.
===== Вычисление частичных произведений =====Для формирования В бинарной системе для вычисления частичного произведенияможно воспользоваться логическими элементами <tex>\&</tex> {{---}} конъюнкторами.Каждое частичное произведение <tex>(m_i)</tex> {{---}} это результат выполнения <tex>k</tex> логических операции <tex>\&</tex> ( между текущим <tex>i</tex>, кроме где <tex>i=1..n</tex>, разрядом множителя и всеми <tex>k</tex> разрядами множимого) и сдвига результата логической операции умножения на один разряд, требуется осуществлять его сдвиг влево на число разрядов, соответствующее весу текущего разряда множителя. Сдвиг можно осуществить простым соединением соответствующих разрядов частичных произведений к необходимым разрядам двоичного сумматора.Матричный умножитель вычисляет частичные произведения по формуле:
==== Схема ====
[[Файл:Mul_2Mult_3.jpgpng|700px|right|thumb|Схема матричного умножителя]]Далее будем рассматривать умножение четырехразрядных Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик для двух четырёх {{---}} разрядных чиселприведена на рисунке. Соответственно нам понадобится три четырёхразрядных сумматораФормирование частичных произведений осуществляется посредством логических элементов <tex>\&</tex>. Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.Разрядность результата {{---}} <tex>l</tex> определяется разрядностью множителя {{---}} <tex>n</tex> и множимого {{---}} <tex>k</tex>:
===== Проводники ='''Матричный умножитель''' ====Как мы можем видеть у нас Если внимательно посмотреть на схеме <tex>8</tex> входов и <tex>8</tex> выходов. Как мы можем видеть, <tex>a0 - a3</tex> - это разряды первого числа, <tex>b0 - b3</tex> - это разряды второго числасхему '''матричного умножителя''' (англ. <tex>a2, b2, a3, b3</tex> проводники идут ко всем микросхемам (<tex>D1, D3, D5, D7 </tex>''binary multiplier''), а <tex>a0то можно увидеть, b0что она образует матрицу, a1, b1</tex> идут каждый только к одной микросхемесформированную проводниками, по которым передаются разряды числа <tex>a0A</tex> к и числа <tex>D7B</tex>, . В точках пересечения этих проводников находятся логические элементы <tex>b0</tex> к <tex>D5\&</tex>. Именно по этой причине умножители, <tex>a1</tex> к <tex>D3</tex>реализованные по данной схеме, <tex>b1</tex> к <tex>D1</tex>. А на выходе мы имеем <tex>p0 - p7</tex> - это разряды конечного числаполучили название матричных умножителей.
==Схемная сложность==
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.
<tex>O(n) + O(n) + O(\log n) = O(n) </tex>
Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <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. Шило "Популярные цифровые микросхемы" 1988г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
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Схемы из функциональных элементов ]]
