10
правок
Изменения
Новая страница: «== Определение == Матричный умножитель - цифровая схема, осуществляющяя умножение двух чис…»
== Определение ==
Матричный умножитель - цифровая схема, осуществляющяя умножение двух чисел.
== Принцип работы ==
==== Вычисление частичных произведений ====
Матричный умножитель вычисляет частичные произведения по формуле: <br>
<math>m^{(i)} = a * b_i * 2^{i}</math>
==== Суммирование частичных произведений ====
На этом этапе происходит сложение всех частичных произведений m. Это происходит так:
вначале мы суммируем <math>m^{(0)}</math> и <math>m^{(1)}</math>, саму сумму занесем в <math>u^{(1)}</math>, а переносы в <math>v^{(1)}</math>(в <math>u^{(1)}</math> и <math>v^{(1)}</math> будет не более n+1 битов в каждом), затем суммируем числа <math>u^{(1)}</math>, <math>v^{(1)}</math>, <math>m^{(2)}</math> и получаем <math>u^{(2)}</math>, <math>v^{(2)}</math>. Так суммируется <math>u^{(i-1)}</math>, <math>v^{(i-1)}</math>, <math>m^{(i)}</math> для всех i = 2, 3, … , n – 1. В итоге получаем два числа <math>u^{(n-1)}</math> и <math>v^{(i-1)}</math>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
==Схемная сложность==
Частичные произведения вычисляются за n шагов, то есть имеют временную сложность O(n). Сложение с вычисление переносов включает n - 1 шагов и требут времени O(n). Последнее сложение можно выполнить за O(log n). <br>
В итоге суммарное время работы: <br>
O(n) + O(n) + O(log n) = O(n) <br>
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает O(log n).
Матричный умножитель - цифровая схема, осуществляющяя умножение двух чисел.
== Принцип работы ==
==== Вычисление частичных произведений ====
Матричный умножитель вычисляет частичные произведения по формуле: <br>
<math>m^{(i)} = a * b_i * 2^{i}</math>
==== Суммирование частичных произведений ====
На этом этапе происходит сложение всех частичных произведений m. Это происходит так:
вначале мы суммируем <math>m^{(0)}</math> и <math>m^{(1)}</math>, саму сумму занесем в <math>u^{(1)}</math>, а переносы в <math>v^{(1)}</math>(в <math>u^{(1)}</math> и <math>v^{(1)}</math> будет не более n+1 битов в каждом), затем суммируем числа <math>u^{(1)}</math>, <math>v^{(1)}</math>, <math>m^{(2)}</math> и получаем <math>u^{(2)}</math>, <math>v^{(2)}</math>. Так суммируется <math>u^{(i-1)}</math>, <math>v^{(i-1)}</math>, <math>m^{(i)}</math> для всех i = 2, 3, … , n – 1. В итоге получаем два числа <math>u^{(n-1)}</math> и <math>v^{(i-1)}</math>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
==Схемная сложность==
Частичные произведения вычисляются за n шагов, то есть имеют временную сложность O(n). Сложение с вычисление переносов включает n - 1 шагов и требут времени O(n). Последнее сложение можно выполнить за O(log n). <br>
В итоге суммарное время работы: <br>
O(n) + O(n) + O(log n) = O(n) <br>
Есть и более быстрые способы умножения двух чисел, например умножение с помощью [[дерево Уоллеса|дерева Уоллеса]], которое работает O(log n).
