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

Определение

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

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

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

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

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р.. Алгоритмы: построение и анализ = Introduction to Algorithms / Пер. с англ. под ред. А. Шеня. — М.: МЦНМО, 2000. — 960 с. — ISBN 5-900916-37-5