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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вычисление частичных произведений)
Строка 1: Строка 1:
 
== Определение ==
 
== Определение ==
 +
[[Файл:Рисунок2.png|420px|thumb|right]]
  
 
Матричный умножитель - цифровая схема, осуществляющяя умножение двух чисел.
 
Матричный умножитель - цифровая схема, осуществляющяя умножение двух чисел.
Строка 8: Строка 9:
 
Матричный умножитель вычисляет частичные произведения по формуле: <br>
 
Матричный умножитель вычисляет частичные произведения по формуле: <br>
 
<math>m^{(i)} = a * b_i * 2^{i}</math>
 
<math>m^{(i)} = a * b_i * 2^{i}</math>
[[Файл:Матричный_умножитель_1.png|200px|thumb|right]]
 
  
 
==== Суммирование частичных произведений ====
 
==== Суммирование частичных произведений ====

Версия 08:43, 15 октября 2010

Определение

Рисунок2.png

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

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

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

Матричный умножитель вычисляет частичные произведения по формуле:
[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).
В итоге суммарное время работы:
O(n) + O(n) + O(log n) = O(n)
Есть и более быстрые способы умножения двух чисел, например умножение с помощью дерева Уоллеса, которое работает O(log n).