10
правок
Изменения
Нет описания правки
== Определение ==
Матричный умножитель - цифровая схема, осуществляющяя умножение двух чиселc помощью суммирования.
== Принцип работы ==
[[Файл:Матричный_умножитель_1Матричный_умножитель_2.pngPNG|420px|thumb|right]]
==== Вычисление частичных произведений ====
Матричный умножитель вычисляет частичные произведения по формуле: <br>
<tex>mm_i = 2^{(i)} = a * b_i * 2^{i}</tex>
==== Суммирование частичных произведений ====
На этом этапе происходит сложение всех частичных произведений m. Это происходит так:
вначале мы суммируем <tex>m^{(0)}m_0</tex> и <tex>m^{(1)}m_1</tex>, саму сумму занесем в <tex>u^{(1)}u_1</tex>, а переносы в <tex>v^{(1)}v_1</tex>(в <tex>u^{(1)}u_1</tex> и <tex>v^{(1)}v_1</tex> будет не более n+1 битов в каждом), затем суммируем числа <tex>u^{(1)}u_1</tex>, <tex>v^{(1)}v_1</tex>, <tex>m^{(2)}m_2</tex> и получаем <tex>u^{(2)}u_2</tex>, <tex>v^{(2)}v_2</tex>. Так суммируется <tex>u^u_{(i-1)}</tex>, <tex>v^v_{(i-1)}</tex>, <tex>m^{(i)}m_i</tex> для всех i = 2, 3, … , n – 1. В итоге получаем два числа <tex>u^u_{(n-1)}</tex> и <tex>v^v_{(i-1)}</tex>, которые складываем с помощью [[двоичный каскадный сумматор|двоичного каскадного сумматора]].
==Схемная сложность==
Частичные произведения вычисляются за ''n'' шагов. Сложение с вычисление переносов включает ''n - 1'' шаг. Последнее сложение можно выполнить за ''O(log n)''. <br>
