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

Определение

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

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

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

Матричный умножитель вычисляет частичные произведения по формуле:
[math]m_i = 2^{i} a b_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