Матричный умножитель — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Назначение)
("Матричный умножитель")
Строка 30: Строка 30:
 
Время выполнения операции умножения определяется временем распространения переносов до  выходного разряда <tex> p8 </tex>.
 
Время выполнения операции умножения определяется временем распространения переносов до  выходного разряда <tex> p8 </tex>.
  
==== "Матричный умножитель" ====
+
==== '''Матричный умножитель - Binary multiplier''' ====
 
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
 
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
 +
 
==Схемная сложность==
 
==Схемная сложность==
 
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.  
 
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.  

Версия 01:10, 19 января 2016

Принцип работы

Умножение в бинарной системе

Умножение в столбик

Умножение в бинарной системе счисления происходит точно так же, как в десятичной - по схеме "умножения столбиком". Если множимое - [math]k[/math] разрядное, а множитель -[math]n[/math] разрядный, то для формирования произведения требуется вычислить [math]n[/math] частичных произведений и сложить их между собой.

Вычисление частичных произведений

В бинарной системе для вычисления частичного произведения можно воспользоваться логическими элементами "AND" - конъюнкторами. Каждое частичное произведение ([math]m_i[/math]) - это результат выполнения [math]k[/math] логических операции "AND" ( между текущим [math]i ( i=1..n)[/math] разрядом множителя и всеми [math]k[/math] разрядами множимого) и сдвига результата логической операции влево на число разрядов, соответствующее весу текущего разряда множителя. Матричный умножитель вычисляет частичные произведения по формуле:

[math]m_i = 2^{i - 1} (a \wedge b_i), где i=1..n[/math]

Суммирование частичных произведений

На этом этапе происходит сложение всех частичных произведений [math] m [/math].

Схема

Схема матричного умножителя

Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик для двух четырёх-разрядных чисел приведена на рисунке. Формирование частичных произведений осуществляется посредством логических элементов "AND". Полные одноразрядные сумматоры обеспечивают формирование разрядов результата. Разрядность результата -[math]l[/math] определяется разрядностью множителя-[math]n[/math] и множимого-[math]k[/math]:

[math] l=n+k [/math].


Все конъюнкторы работают параллельно. Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора. В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом. Время выполнения операции умножения определяется временем распространения переносов до выходного разряда [math] p8 [/math].

Матричный умножитель - Binary multiplier

Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа [math]A[/math] и числа [math]B[/math]. В точках пересечения этих проводников находятся логические элементы “И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.

Схемная сложность

Частичные произведения вычисляются за [math]n[/math] шагов. Сложение с вычислением переносов включает [math]n - 1[/math] шаг. Последнее сложение можно выполнить за [math]O(\log n)[/math].

В итоге суммарное время работы:

[math]O(n) + O(n) + O(\log n) = O(n) [/math]

Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.

Особенно заметен выигрыш в быстродействии при построении многоразрядных умножителей, однако ничего не бывает бесплатно. В обмен на быстродействие придётся заплатить увеличением разрядности сумматоров, а значит сложностью схемы.

Есть и более быстрые способы умножения двух чисел, например умножение с помощью дерева Уоллеса, которое работает [math]O(\log n)[/math].

Источники информации


См так же

--Kirill Antonov 23:55, 18 января 2016 (GST)