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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Работа схемы)
(Схема)
Строка 25: Строка 25:
 
Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.
 
Полные одноразрядные сумматоры обеспечивают формирование разрядов результата.
 
Разрядность результата <tex> l </tex> определяется разрядностью множителя - <tex> n </tex> и множимого - <tex> k </tex>: <tex> l=n+k </tex>
 
Разрядность результата <tex> l </tex> определяется разрядностью множителя - <tex> n </tex> и множимого - <tex> k </tex>: <tex> l=n+k </tex>
 
+
Все конъюнкторы работаю параллельно.
===== Работа схемы =====
+
Полные одноразрядные сумматоры обеспечивают поразрядное сложение результатов конъюнкций и переносов из предыдущих разрядов сумматора.
В начале первый разряд первого и первый разряд второго числа поступают на элемент "И" и результат сразу записывается в первый разряд произведения.
+
В приведенной схеме использованы четырех разрядные сумматоры с последовательным переносом.
 
+
Время выполнения операции умножения определяется временем распространения переносов до выходного разряда <tex> p8 </tex>.
Дальше второй разряд первого числа снова поступает вместе с первым разрядом второго числа на элемент И и результат уже суммируется с произведение первого разряда первого числа и второго разряда второго числа и все это записывается во второй разряд произведения.
 
 
 
И дальше все продолжается по циклу.
 
 
 
То есть все произведения разрядов первого числа на <tex> n - 1 </tex> разряд второго числа суммируются с произведением предыдущего разряда первого числа на <tex> n </tex> разряд второго числа.  И далее эта сумма так же суммируется, если только мы уже не получили нужный нам разряд произведения.
 
 
 
===== Проводники =====
 
Как мы можем видеть, <tex>y1 - y5</tex> — разряды первого числа, <tex>x1 - x4</tex> — разряды второго числа. <tex>y1 - y5</tex>  проводники идут ко всем элементам "И", а <tex>x1 - x4</tex> идут каждый только к одному из пяти разрядных сумматоров <tex>SM</tex>. А на выходе мы имеем <tex>z1 - z9</tex> — разряды конечного числа.
 
  
 
==== "Матричный умножитель" ====
 
==== "Матричный умножитель" ====

Версия 22:21, 18 января 2016

Назначение

Матричный умножитель предназначен для арифметического умножения двух двоичных чисел произвольной разрядности.

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

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

Mult bin.png

Умножение в бинарной системе счисления происходит точно так же, как в десятичной - по схеме "умножения столбиком". Если множимое - [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].

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

Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа [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].

Литература и источники

  • Е. Угрюмов "Цифровая схемотехника" 2001г.
  • Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.
  • М.И. Богданович "Цифровые интегральные микросхемы" 1996г.
  • В.Л. Шило "Популярные цифровые микросхемы" 1988г.