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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Схемная сложность)
Строка 11: Строка 11:
  
 
==== Вычисление частичных произведений ====
 
==== Вычисление частичных произведений ====
Для формирования частичного произведения, кроме операции умножения на один разряд, требуется осуществлять его сдвиг влево на число разрядов, соответствующее весу разряда множителя. Сдвиг можно осуществить простым соединением соответствующих разрядов частичных произведений к необходимым разрядам двоичного сумматора.<br>
+
Для формирования частичного произведения, кроме операции умножения на один разряд, требуется осуществлять его сдвиг влево на число разрядов, соответствующее весу разряда множителя. Сдвиг можно осуществить простым соединением соответствующих разрядов частичных произведений к необходимым разрядам двоичного сумматора.
Матричный умножитель вычисляет частичные произведения по формуле: <br>
+
 
 +
Матричный умножитель вычисляет частичные произведения по формуле:  
 +
 
 
<tex>m_i = 2^{i} a b_i</tex>
 
<tex>m_i = 2^{i} a b_i</tex>
 
==== Суммирование частичных произведений ====
 
==== Суммирование частичных произведений ====
Строка 19: Строка 21:
 
==== Схема ====
 
==== Схема ====
 
[[Файл:Mul_2.jpg‎|right|Схема матричного умножителя]]
 
[[Файл:Mul_2.jpg‎|right|Схема матричного умножителя]]
Далее будем рассматривать умножение четырехразрядных чисел. Соответственно нам понадобится три четырёхразрядных сумматора. <br>
+
Далее будем рассматривать умножение четырехразрядных чисел. Соответственно нам понадобится три четырёхразрядных сумматора.  
 +
 
 
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляют микросхемы <tex>D1, D3, D5, D7 </tex>. В этих микросхемах содержится сразу четыре логических элемента “2И”.
 
Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляют микросхемы <tex>D1, D3, D5, D7 </tex>. В этих микросхемах содержится сразу четыре логических элемента “2И”.
 
==== Работа схемы ====
 
==== Работа схемы ====
 
===== Этап 1 =====
 
===== Этап 1 =====
Сумматор, выполненный на микросхеме <tex>D6</tex>, суммирует первое и второе частные произведения. При этом младший разряд первого частного произведения не нуждается в суммировании. Поэтому он подаётся на выход умножителя непосредственно (разряд <tex>M0</tex>). <br>
+
Сумматор, выполненный на микросхеме <tex>D6</tex>, суммирует первое и второе частные произведения. При этом младший разряд первого частного произведения не нуждается в суммировании. Поэтому он подаётся на выход умножителя непосредственно (разряд <tex>M0</tex>).
 +
 
 
===== Этап 2 =====
 
===== Этап 2 =====
Второе частное произведение должно быть сдвинуто на один разряд. Это осуществляется тем, что младший разряд выходного числа сумматора <tex>D6</tex> соединяется со вторым разрядом произведения (<tex>M1</tex>). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов <tex>A</tex>  соединяется с первым разрядом частного произведения, первый разряд группы входов <tex>A</tex> соединяется со вторым разрядом частного произведения, и так же третий, четвертый и старший. Однако старший разряд группы входов <tex>A</tex>  не с чем соединять! Вспомним, что если добавить к числу слева ноль, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемы. <br>
+
Второе частное произведение должно быть сдвинуто на один разряд. Это осуществляется тем, что младший разряд выходного числа сумматора <tex>D6</tex> соединяется со вторым разрядом произведения (<tex>M1</tex>). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов <tex>A</tex>  соединяется с первым разрядом частного произведения, первый разряд группы входов <tex>A</tex> соединяется со вторым разрядом частного произведения, и так же третий, четвертый и старший. Однако старший разряд группы входов <tex>A</tex>  не с чем соединять! Вспомним, что если добавить к числу слева ноль, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемы.  
 +
 
 
===== Завершение =====
 
===== Завершение =====
 
Точно таким же образом осуществляется суммирование третьего и четвёртого частного произведения. Это суммирование выполняют микросхемы <tex>D4</tex> и <tex>D2</tex> соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.
 
Точно таким же образом осуществляется суммирование третьего и четвёртого частного произведения. Это суммирование выполняют микросхемы <tex>D4</tex> и <tex>D2</tex> соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.
Строка 31: Строка 36:
 
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “2И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
 
Если внимательно посмотреть на схему умножителя, то можно увидеть, что она образует матрицу, сформированную проводниками, по которым передаются разряды числа <tex>A</tex> и числа <tex>B</tex>. В точках пересечения этих проводников находятся логические элементы “2И”. Именно по этой причине умножители, реализованные по данной схеме, получили название матричных умножителей.
 
==Схемная сложность==
 
==Схемная сложность==
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>. <br>
+
Частичные произведения вычисляются за <tex>n</tex> шагов. Сложение с вычислением переносов включает <tex>n - 1</tex> шаг. Последнее сложение можно выполнить за <tex>O(\log n)</tex>.  
В итоге суммарное время работы: <br>
+
 
<tex>O(n) + O(n) + O(\log n) = O(n) </tex> <br>
+
В итоге суммарное время работы:
Конкретно по нашей схеме: <br>
+
 
Скорость работы схемы, приведенной на схеме определяется максимальным временем распространения сигнала. Это цепь <tex>D7, D6, D4, D2</tex>. <br>
+
<tex>O(n) + O(n) + O(\log n) = O(n) </tex>  
 +
 
 +
Конкретно по нашей схеме:  
 +
 
 +
Скорость работы схемы, приведенной на схеме определяется максимальным временем распространения сигнала. Это цепь <tex>D7, D6, D4, D2</tex>.  
 +
 
 
Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.
 
Время работы схемы можно сократить, если сумматоры располагать не последовательно друг за другом, как это предполагается алгоритмом, приведенным на первом рисунке (общая схема), а суммировать частичные произведения попарно, затем суммировать пары частичных произведений и т.д. В этом случае время выполнения операции умножения значительно сократится.
  
Строка 47: Строка 57:
  
 
== Литература ==
 
== Литература ==
* Е. Угрюмов "Цифровая схемотехника" 2001г. <br>
+
* Е. Угрюмов "Цифровая схемотехника" 2001г.  
* Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г. <br>
+
 
* М.И. Богданович "Цифровые интегральные микросхемы" 1996г. <br>
+
* Дк. Ф. Уэйкерли "Проектирование цифровых устройств, том 1." 2002г.  
* В.Л. Шило "Популярные цифровые микросхемы" 1988г. <br>
+
 
 +
* М.И. Богданович "Цифровые интегральные микросхемы" 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
 
* ''[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

Версия 23:18, 5 ноября 2011

Определение

Матричный умножитель — цифровая схема, осуществляющая умножение двух чисел c помощью двоичного каскадного сумматора.

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

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

Двоумн.gif
Матричный умножитель 2.PNG

Умножение в бинарной системе счисления происходит точно так же, как в десятичной. Для формирования произведения требуется вычислить [math]n[/math] (где [math]n[/math] — количество разрядов в числах) частичных произведений. Примечательно то, что в бинарной арифметике следует умножать только числа [math]1[/math] и [math]0[/math]. Это означает, что нужно прибавлять к сумме остальных частичных произведений либо множитель, либо ноль. Таким образом, для формирования частичного произведения можно воспользоваться логическими элементами “2И”.

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

Для формирования частичного произведения, кроме операции умножения на один разряд, требуется осуществлять его сдвиг влево на число разрядов, соответствующее весу разряда множителя. Сдвиг можно осуществить простым соединением соответствующих разрядов частичных произведений к необходимым разрядам двоичного сумматора.

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

[math]m_i = 2^{i} a b_i[/math]

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

На этом этапе происходит сложение всех частичных произведений m. Во всех современных системах это происходит с помощью дерева Уоллеса.

Схема

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

Далее будем рассматривать умножение четырехразрядных чисел. Соответственно нам понадобится три четырёхразрядных сумматора.

Принципиальная схема умножителя, реализующая алгоритм двоичного умножения в столбик, приведена на схеме. Формирование частичных произведений в этой схеме осуществляют микросхемы [math]D1, D3, D5, D7 [/math]. В этих микросхемах содержится сразу четыре логических элемента “2И”.

Работа схемы

Этап 1

Сумматор, выполненный на микросхеме [math]D6[/math], суммирует первое и второе частные произведения. При этом младший разряд первого частного произведения не нуждается в суммировании. Поэтому он подаётся на выход умножителя непосредственно (разряд [math]M0[/math]).

Этап 2

Второе частное произведение должно быть сдвинуто на один разряд. Это осуществляется тем, что младший разряд выходного числа сумматора [math]D6[/math] соединяется со вторым разрядом произведения ([math]M1[/math]). Но тогда первое частное произведение необходимо сдвинуть на один разряд по отношению ко второму частному произведению! Это выполняется тем, что младший разряд группы входов [math]A[/math] соединяется с первым разрядом частного произведения, первый разряд группы входов [math]A[/math] соединяется со вторым разрядом частного произведения, и так же третий, четвертый и старший. Однако старший разряд группы входов [math]A[/math] не с чем соединять! Вспомним, что если добавить к числу слева ноль, то значение числа не изменится, поэтому мы можем этот разряд соединить с общим проводом схемы.

Завершение

Точно таким же образом осуществляется суммирование третьего и четвёртого частного произведения. Это суммирование выполняют микросхемы [math]D4[/math] и [math]D2[/math] соответственно. Отличие заключается только в том, что здесь не нужно задумываться о старшем разряде предыдущей суммы, ведь предыдущая микросхема сумматора формирует сигнал переноса.

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

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

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

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

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

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

Конкретно по нашей схеме:

Скорость работы схемы, приведенной на схеме определяется максимальным временем распространения сигнала. Это цепь [math]D7, D6, D4, D2[/math].

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

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

Если сумматоры частных произведений останутся той же разрядности, что и ранее, то разрядность сумматоров пар частичных произведений должна быть увеличена на единицу.

Разрядность сумматоров четвёрок частичных произведений будет на два разряда больше разрядности сумматоров частичных произведений и т.д.

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

Литература

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