Дерево Уоллеса

4-слойное сокращение Уоллеса матрицы частичного произведения 8x8 с использованием 15 полусумматоров (две точки) и 38 полных сумматоров (три точки). Точки в каждом столбце — это биты одинакового веса.

Множитель Уоллеса — это аппаратная реализация двоичного умножителя , цифровой схемы, которая умножает два целых числа. Он использует набор полных и половинных сумматоров ( дерево Уоллеса или сокращение Уоллеса ) для поэтапного суммирования частичных произведений, пока не останется два числа. Множители Уоллеса максимально сокращают на каждом уровне, тогда как множители Дадды пытаются минимизировать необходимое количество вентилей, откладывая сокращение на верхние уровни.

Множители Уоллеса были изобретены австралийским ученым-компьютерщиком Крисом Уоллесом в 1964 году.

Дерево Уоллеса состоит из трех ступеней:

1. Умножьте каждый бит одного из аргументов на каждый бит другого.
2. Уменьшите количество частичных произведений до двух, используя слои полных и половинных сумматоров .
3. Сгруппируйте провода в два числа и сложите их обычным сумматором.

По сравнению с простым добавлением частичных произведений с помощью обычных сумматоров преимуществом дерева Уоллеса является его более высокая скорость. Он имеет $O(\log n)$ редукционные слои, но каждый слой имеет только $O(1)$ задержка распространения. Простое добавление частичных продуктов потребовало бы $O(\log ^{2}n)$ время. Поскольку изготовление частичных продуктов $O(1)$ и последнее дополнение $O(\log n)$, общее умножение $O(\log n)$, не намного медленнее, чем сложение. С точки зрения теории сложности алгоритм дерева Уоллеса помещает умножение в класс NC. ¹ . Недостатком дерева Уоллеса по сравнению с простым сложением частичных произведений является гораздо большее количество элементов.

Эти вычисления учитывают только задержки на воротах и ​​не учитывают задержки по проводу, которые также могут быть очень существенными.

Дерево Уоллеса также может быть представлено деревом сумматоров 3/2 или 4/2.

Иногда его комбинируют с кодировкой Booth .

Подробное объяснение

Дерево Уоллеса — это вариант длинного умножения . Первый шаг — умножить каждую цифру (каждый бит) одного фактора на каждую цифру другого. Каждый из этих частичных продуктов имеет вес, равный произведению его факторов. Конечный продукт рассчитывается по взвешенной сумме всех этих частичных продуктов.

Первый шаг, как было сказано выше, состоит в умножении каждого бита одного числа на каждый бит другого, что выполняется как простой логический элемент И, в результате чего получается $n^{2}$ биты; частичное произведение битов $a_{m}$ к $b_{n}$ имеет вес $2^{(m+n)}$

На втором этапе полученные биты сводятся к двум числам; это осуществляется следующим образом: Если есть три или более проводов одинакового веса, добавьте следующий слой:

• Возьмите любые три провода с одинаковыми весами и введите их в полный сумматор . Результатом будет выходной провод одинакового веса и выходной провод с более высоким весом для каждых трех входных проводов.
• Если остались два провода одинаковой массы, введите их в полусумматор .
• Если остался только один провод, подключите его к следующему слою.

На третьем и последнем этапе два полученных числа подаются в сумматор, в результате чего получается конечный продукт.

Пример

$n=4$, умножение $a_{3}a_{2}a_{1}a_{0}$ к $b_{3}b_{2}b_{1}b_{0}$:

1. Сначала мы умножаем каждый бит на каждый бит:
   • вес 1 – $a_{0}b_{0}$
   • вес 2 – $a_{0}b_{1}$, $a_{1}b_{0}$
   • вес 4 – $a_{0}b_{2}$, $a_{1}b_{1}$, $a_{2}b_{0}$
   • вес 8 – $a_{0}b_{3}$, $a_{1}b_{2}$, $a_{2}b_{1}$, $a_{3}b_{0}$
   • вес 16 – $a_{1}b_{3}$, $a_{2}b_{2}$, $a_{3}b_{1}$
   • вес 32 – $a_{2}b_{3}$, $a_{3}b_{2}$
   • вес 64 – $a_{3}b_{3}$
2. Слой уменьшения 1:
   • Пропустите единственный провод веса 1, на выходе: 1 провод веса 1.
   • Добавьте полусумматор для веса 2, выходы: 1 провод веса-2, 1 провод веса-4.
   • Добавьте полный сумматор для веса 4, выходы: 1 провод веса-4, 1 провод веса-8.
   • Добавьте полный сумматор для веса 8 и пропустите через него оставшийся провод, выведите: 2 провода веса-8, 1 провод веса-16.
   • Добавьте полный сумматор для веса 16, выходы: 1 провод веса-16, 1 провод веса-32.
   • Добавьте полусумматор для веса 32, выходы: 1 провод веса-32, 1 провод веса-64.
   • Пропустите единственный провод веса 64, на выходе: 1 провод веса 64.
3. Провода на выходе восстановительного слоя 1:
   • вес 1 – 1
   • вес 2 – 1
   • вес 4 – 2
   • вес 8 – 3
   • вес 16 – 2
   • вес 32 – 2
   • вес 64 – 2
4. Слой уменьшения 2:
   • Добавьте полный сумматор для веса 8 и половинные суммы для весов 4, 16, 32, 64.
5. Выходы:
   • вес 1 – 1
   • вес 2 – 1
   • вес 4 – 1
   • вес 8 – 2
   • вес 16 – 2
   • вес 32 – 2
   • вес 64 – 2
   • вес 128 – 1
6. Сгруппируйте провода в пару целых чисел и сумматор для их сложения.

См. также

• Древесные люди

Дальнейшее чтение

• Савард, Джон Дж. Г. (2018) [2006]. «Продвинутые арифметические методы» . четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.

Внешние ссылки

• Общая реализация множителя дерева Уоллеса на языке VHDL .