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И”.
==== Работа схемы ====
===== Этап 1 =====
Сумматор, выполненный на микросхеме <tex>D6</tex>, суммирует первое и второе частные произведения. При этом младший разряд первого частного произведения не нуждается в суммировании. Поэтому он подаётся на выход умножителя непосредственно (разряд <tex>M0</tex>).
===== Завершение =====
Точно таким же образом осуществляется суммирование третьего и четвёртого частного произведения. Это суммирование выполняют микросхемы <tex>D4</tex> и <tex>D2</tex> соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.
==== "Матричный умножитель" ====
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “2И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
Конкретно по нашей схеме:
Скорость работы схемы, приведенной на схеме определяется максимальным временем распространения сигнала. Это цепь <tex>D7, D6, D4, D2</tex>.
Если сумматоры частных произведений останутся той же разрядностиЕсть и более быстрые способы умножения двух чисел, что и ранеенапример умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], то разрядность сумматоров пар частичных произведений должна быть увеличена на единицукоторое работает <tex>O(\log n)</tex>. == См.также ==*[[Дерево Уоллеса]]*[[Двоичный каскадный сумматор]]
Разрядность сумматоров четвёрок частичных произведений будет на два разряда больше разрядности сумматоров частичных произведений и т== Источники информации ==* [http://bookfi.дnet/book/556972 Е.Угрюмов "Цифровая схемотехника" 2001г.]
Есть и более быстрые способы умножения двух чисел, например умножение с помощью * [[дерево Уоллеса|дерева Уоллеса]]http://bookfi.net/book/532753 Дк. Ф. Уэйкерли "Проектирование цифровых устройств, которое работает <tex>O(\log n)</tex>том 1." 2002г.]
== Литература ==* Е[http://bookfi. Угрюмов net/book/637011 М.И. Богданович "Цифровая схемотехникаЦифровые интегральные микросхемы" 2001г1996г. ]
* В.Л. Шило "Популярные цифровые микросхемы" 1988г. [[Категория: Дискретная математика и алгоритмы]]
* ''[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
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> l=n+k </tex>.
Все конъюнкторы работают параллельно.Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex> p8 </tex>. ===== Этап 2 ='''Матричный умножитель''' ====Второе частное произведение должно быть сдвинуто Если внимательно посмотреть на один разрядсхему '''матричного умножителя''' (англ. Это осуществляется тем''binary multiplier''), то можно увидеть, что младший разряд выходного она образует матрицу, сформированную проводниками, по которым передаются разряды числа сумматора <tex>D6A</tex> соединяется со вторым разрядом произведения (и числа <tex>M1B</tex>). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов В точках пересечения этих проводников находятся логические элементы <tex>A\&</tex> соединяется с первым разрядом частного произведения, первый разряд группы входов <tex>A</tex> соединяется со вторым разрядом частного произведения, и так же третий, четвертый и старший. Однако старший разряд группы входов <tex>A</tex> не с чем соединять! ВспомнимИменно по этой причине умножители, что если добавить к числу слева нольреализованные по данной схеме, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемыполучили название матричных умножителей.
==Схемная сложность==
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.
<tex>O(n) + O(n) + O(\log n) = O(n) </tex>
Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.
Особенно заметен выигрыш в быстродействии при построении многоразрядных умножителей, однако ничего не бывает бесплатно. В обмен на быстродействие придётся заплатить увеличением разрядности сумматоров, а значит сложностью схемы.
* Дк[http://library. Фespec. Уэйкерли "Проектирование цифровых устройств, том 1." 2002гws/section6/article46. html Схема умножителя]
* ''[http://ru.wikipedia.org/wiki/Кормен Кормен Т.], [http://ru.wikipedia.org/wiki/Лейзерсон,_Чарльз_Эрик Лейзерсон Ч.], [http://ru.wikipedia.org/wiki/Ривест,_Рональд_Линн Ривест Р.]''. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.И: МЦНМО, 2000. Богданович "Цифровые интегральные микросхемы" 1996г— 960 с. — ISBN 5-900916-37-5
