35
правок
Изменения
→Дерево Уоллеса
чисел (как в [[Матричный умножитель|матричном умножителе]]).
Однако, в отличие от [[Матричный умножитель|матричного умножителя]], дерево Уоллеса складывает все числа не последовательно, а с помощью специального элемента(назовём его <tex>3\to2</tex>), преобразующего <tex>3 </tex> числа <tex>x</tex>, <tex>y</tex> и <tex> z </tex> в числа <tex>a</tex> и <tex>b</tex> такие, что <tex>x + y + z = a + b</tex>.
С помощью этого элемента на каждом шаге производятся следующие операции:
# Берутся тройки чисел <tex>(x_1, x_2, x_3)</tex>, <tex>(x_4, x_5, x_6)</tex>, <tex>\ldots</tex>
# Для каждой тройки применяется элемент <tex>3\to2</tex>.
# Повторяются пункты 1 и 2 пока не осталось <tex>2 </tex> числа.# Оставшиеся <tex>2 </tex> числа складываются с помощью [[Двоичный каскадный сумматор|двоичного каскадного сумматора]].
На выходе имеем число, которое равно сумме чисел на всех входах.
