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

Материал из Викиконспекты
Версия от 02:32, 16 января 2011; 192.168.0.2 (обсуждение) (Схемная сложность)
Перейти к: навигация, поиск

Определение

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

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

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

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

Матричный умножитель вычисляет частичные произведения по формуле:
[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).

Литература