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

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

основной принцип, известный из ручного умножения. На изображении показан ручной пример умножения 345 (вверху) на 12 (сбоку).

Пример редукции на множитель 8х8.

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

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

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

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

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

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

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

Подробное объяснение [ править ]

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

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

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

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

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

Пример [ править ]

${\ 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 .