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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 96 промежуточных версий 9 участников)
Строка 1: Строка 1:
== Определение ==
+
== Принцип работы ==
 +
==== Умножение в бинарной системе ====
 +
[[Файл: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>.
  
== Принцип работы ==
 
  
[[Файл:Матричный_умножитель_1.png|420px|thumb|right]]
+
Все конъюнкторы работают параллельно.
 +
Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.
 +
В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.
 +
Время выполнения операции умножения определяется временем распространения переносов до  выходного разряда <tex> p8 </tex>.
  
==== Вычисление частичных произведений ====
+
==== '''Матричный умножитель''' ====
Матричный умножитель вычисляет частичные произведения по формуле: <br>
+
Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы <tex>\&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
<tex>m^{(i)} = a * b_i * 2^{i}</tex>
 
  
==== Суммирование частичных произведений ====
 
На этом этапе происходит сложение всех частичных произведений 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>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
 
 
==Схемная сложность==
 
==Схемная сложность==
Частичные произведения вычисляются за n шагов, то есть имеют временную сложность O(n). Сложение с вычисление переносов включает n - 1 шагов и требует времени O(n). Последнее сложение можно выполнить за O(log n). <br>
+
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.
В итоге суммарное время работы: <br>
+
 
O(n) + O(n) + O(log n) = O(n) <br>
+
В итоге суммарное время работы:
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает O(log n).
+
 
 +
<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.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
 
* ''[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
 +
 +
[[Категория: Дискретная математика и алгоритмы]]
 +
 +
[[Категория: Схемы из функциональных элементов ]]

Текущая версия на 19:27, 4 сентября 2022

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

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

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

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

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

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

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

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

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

Схема

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

Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик для двух четырёх — разрядных чисел приведена на рисунке. Формирование частичных произведений осуществляется посредством логических элементов [math]\&[/math]. Полные одноразрядные сумматоры обеспечивают формирование разрядов результата. Разрядность результата — [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]\&[/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].

См. также

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