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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 67 промежуточных версий 5 участников)
Строка 1: Строка 1:
== Определение ==
 
 
Матричный умножитель {{---}} цифровая [[Реализация булевой функции схемой из функциональных элементов|схема]], осуществляющая умножение двух чисел c помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
 
 
 
== Принцип работы ==
 
== Принцип работы ==
 
==== Умножение в бинарной системе ====
 
==== Умножение в бинарной системе ====
[[Файл:Двоумн.gif|90px|left]]
+
[[Файл:mult_bin.png|300px|right|thumb|''Умножение в столбик'']]
[[Файл:Матричный_умножитель_2.PNG|420px|thumb|right]]
+
 
Умножение в бинарной системе счисления происходит точно так же, как в десятичной.
+
Умножение в бинарной системе счисления происходит точно так же, как в десятичной {{---}}  по схеме ''умножения столбиком''.  
Для формирования произведения требуется вычислить <tex>n</tex> (где <tex>n</tex> — количество разрядов в числах) частичных произведений. Примечательно то, что в бинарной арифметике следует умножать только числа <tex>1</tex> и <tex>0</tex>. Это означает, что нужно прибавлять к сумме остальных частичных произведений либо множитель, либо ноль. Таким образом, для формирования частичного произведения можно воспользоваться логическими элементами “И”.
+
Если множимое {{---}} <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_i = 2^{i} a b_i</tex>
+
===== Суммирование частичных произведений =====
==== Суммирование частичных произведений ====
+
На этом этапе происходит сложение всех частичных произведений <tex> m </tex>.
На этом этапе происходит сложение всех частичных произведений <tex> m </tex>. В большинстве современных систем это происходит с помощью [[Дерево Уоллеса|дерева Уоллеса]].
 
  
 
==== Схема ====
 
==== Схема ====
[[Файл:Mul_2.jpg?|right|Схема матричного умножителя]]
+
[[Файл:Mult_3.png|700px|right|thumb|Схема матричного умножителя]]
Далее будем рассматривать умножение пяти разрядного и четырех разрядного чисел. Соответственно нам понадобится три пяти разрядных сумматора.
+
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик для двух четырёх {{---}} разрядных чисел приведена на рисунке.  
 
+
Формирование частичных произведений осуществляется посредством логических элементов <tex>\&</tex>.
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляется посредством логических элементов “И”.
+
Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.
 
+
Разрядность результата {{---}} <tex>l</tex> определяется разрядностью множителя {{---}} <tex>n</tex> и множимого {{---}} <tex>k</tex>:
Помимо этого, рассматриваемая схема содержит шесть дополнительных двухвходовых элементов "исключающее ИЛИ" и два дополнительных входа <tex> u1, u2 </tex>. При этом в рабочем режиме на входы <tex> c, u1, u2, p1, p2, p3 </tex> подаются сигналы логического "0".
 
 
 
Это нужно для работы теста проверяющего неисправности. Но это не относится к этой теме.
 
===== Работа схемы =====
 
Схема работает по достаточно простому принципу.
 
  
В начале первый разряд первого и первый разряд второго числа поступают на элемент "И" и результат сразу записывается в первый разряд произведения.
+
<tex> l=n+k </tex>.
  
Дальше второй разряд первого числа снова поступает вместе с первым разрядом второго числа на элемент И и результат уже суммируется с произведение первого разряда первого числа и второго разряда второго числа и все это записывается во второй разряд произведения.
 
  
И дальше все продолжается по циклу.
+
Все конъюнкторы работают параллельно.
 +
Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.
 +
В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.
 +
Время выполнения операции умножения определяется временем распространения переносов до  выходного разряда <tex> p8 </tex>.
  
То есть все произведения разрядов первого числа на <tex> n - 1 </tex> разряд второго числа суммируются с произведением предыдущего разряда первого числа на <tex> n </tex> разряд второго числа.  И далее эта сумма так же суммируется, если только мы уже не получили нужный нам разряд произведения.
+
==== '''Матричный умножитель''' ====
===== Проводники =====
+
Если внимательно посмотреть на схему '''матричного умножителя''' (англ. ''binary multiplier''), то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы <tex>\&</tex>. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
Как мы можем видеть, <tex>y1 - y5</tex> — разряды первого числа, <tex>x1 - x4</tex> — разряды второго числа. <tex>y1 - y5</tex> проводники идут ко всем элементам "И", а <tex>x1 - x4</tex> идут каждый только к одному из пяти разрядных сумматоров <tex>SM</tex>. А на выходе мы имеем  <tex>z1 - z9</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>.  
Строка 56: Строка 46:
 
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>.
 
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает <tex>O(\log n)</tex>.
  
== Литература и источники ==
+
== См. также ==
* Е. Угрюмов "Цифровая схемотехника" 2001г.
+
*[[Дерево Уоллеса]]
 +
*[[Двоичный каскадный сумматор]]
  
* Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.  
+
== Источники информации ==
 +
* [http://bookfi.net/book/556972  Е. Угрюмов "Цифровая схемотехника" 2001г.]
  
* М.И. Богданович "Цифровые интегральные микросхемы" 1996г.  
+
* [http://bookfi.net/book/532753  Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.]
  
* В.Л. Шило "Популярные цифровые микросхемы" 1988г.  
+
* [http://bookfi.net/book/637011 М.И. Богданович "Цифровые интегральные микросхемы" 1996г.]
  
 
* [http://library.espec.ws/section6/article46.html Схема умножителя]
 
* [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].

См. также

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