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

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Найти источники:  «Дерево Уоллеса»  -  новости  · газеты  · книги  · ученый  · JSTOR ( декабрь 2009 г. ) ( Узнайте, как и когда удалить это сообщение-шаблон )

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

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

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

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

1. Умножьте каждый бит одного аргумента на каждый бит другого.
2. Уменьшите количество частичных продуктов до двух с помощью слоев полных и половинных сумматоров .
3. Сгруппируйте провода по два числа и сложите их обычным сумматором. ^[3]

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

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

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

Иногда его комбинируют с кодировкой Бута . ^{[4] [5]}

Детальное объяснение

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

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

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

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

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

Пример

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

1. Сначала мы умножаем каждый бит на каждый бит:
   • вес 1 - ${\displaystyle a_{0}b_{0}}$
   • вес 2 - ,${\displaystyle a_{0}b_{1}}$${\displaystyle a_{1}b_{0}}$
   • вес 4 - , ,${\displaystyle a_{0}b_{2}}$${\displaystyle a_{1}b_{1}}$${\displaystyle a_{2}b_{0}}$
   • вес 8 - , , ,${\displaystyle a_{0}b_{3}}$${\displaystyle a_{1}b_{2}}$${\displaystyle a_{2}b_{1}}$${\displaystyle a_{3}b_{0}}$
   • вес 16 - , ,${\displaystyle a_{1}b_{3}}$${\displaystyle a_{2}b_{2}}$${\displaystyle a_{3}b_{1}}$
   • вес 32 - ,${\displaystyle a_{2}b_{3}}$${\displaystyle a_{3}b_{2}}$
   • вес 64 - ${\displaystyle 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 .