Дадда множитель

Решеточное умножение , аналогичная концепция из десятичной математики.

Множитель Dadda является аппаратный умножитель дизайн изобретен компьютер ученого Луиджи Dadda в 1965 г. ^[1] Это похоже на Wallace мультипликатор , но он немного быстрее (для всех размеров операндов) и требует меньше ворота (для всех , кроме самых маленьких операнд размеры). ^[2]

Фактически, множители Дадды и Уоллеса имеют одинаковые три шага для двух битовых строк и длины и соответственно:${\ displaystyle w_ {1}}$${\ displaystyle w_ {2}}$${\ displaystyle \ ell _ {1}}$${\ displaystyle \ ell _ {2}}$

1. Умножение ( логическое И ) каждого бита на каждый бит дает результаты, сгруппированные по весу в столбцах.${\ displaystyle w_ {1}}$${\ displaystyle w_ {2}}$${\ displaystyle \ ell _ {1} \ cdot \ ell _ {2}}$
2. Уменьшайте количество частичных произведений путем добавления полных и половинных сумматоров до тех пор, пока у нас не останется не более двух битов каждого веса.
3. Сложите конечный результат обычным сумматором.

Как и в случае умножителя Уоллеса, произведения умножения на первом этапе имеют разные веса, отражающие величину исходных значений битов при умножении. Например, произведение бит имеет вес .${\ displaystyle a_ {n} b_ {m}}$${\ displaystyle n + m}$

В отличие от множителей Уоллеса, которые максимально уменьшают на каждом слое, множители Дадда пытаются минимизировать количество используемых вентилей, а также задержку ввода / вывода. Из-за этого умножители Дадды имеют менее затратную фазу сокращения, но конечные числа могут быть на несколько бит длиннее, что требует немного больших сумматоров.

Описание [ править ]

Пример схемы полного сумматора.

Чтобы получить более оптимальный конечный продукт, структура процесса восстановления регулируется немного более сложными правилами, чем в множителях Уоллеса.

Прогрессирование сокращения контролируется последовательностью максимальной высоты , определяемой:${\ displaystyle d_ {j}}$

${\ displaystyle d_ {1} = 2 {\ text {and}} d_ {j + 1} = \ operatorname {floor} (1.5d_ {j}).}$

Это дает такую ​​последовательность:

${\ displaystyle d_ {1} = 2, d_ {2} = 3, d_ {3} = 4, d_ {4} = 6, d_ {5} = 9, d_ {6} = 13, \ ldots}$

Начальное значение выбирается как наибольшее значение, такое, что , где и - количество битов во входном множимом и множителем. Меньшая из двух битовых длин будет максимальной высотой каждого столбца весов после первого этапа умножения. Для каждого этапа сокращения целью алгоритма является уменьшение высоты каждого столбца так, чтобы оно было меньше или равно значению . ${\ displaystyle j}$${\ displaystyle d_ {j} <min (n_ {1}, n_ {2})}$${\ displaystyle n_ {1}}$${\displaystyle n_{2}}$${\displaystyle j}$${\displaystyle d_{j}}$

Для каждого этапа от уменьшите каждый столбец, начиная с столбца с наименьшим весом, в соответствии со следующими правилами:${\displaystyle ,\ldots ,1}$${\displaystyle c_{0}}$

1. Если столбец не требует уменьшения, перейдите к столбцу${\displaystyle \operatorname {height} (c_{i})\leqslant d_{j}}$${\displaystyle c_{i+1}}$
2. Если добавить два верхних элемента в полусумматор, поместив результат в нижнюю часть столбца, а перенос в верхнюю часть столбца , затем переместитесь в столбец${\displaystyle \operatorname {height} (c_{i})=d_{j}+1}$${\displaystyle c_{i+1}}$${\displaystyle c_{i+1}}$
3. В противном случае добавьте три верхних элемента в полный сумматор, поместив результат в нижнюю часть столбца, а перенос в верхнюю часть столбца , перезапустите с шага 1${\displaystyle c_{i+1}}$${\displaystyle c_{i}}$

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

Пример редукции Дадды на множитель 8 × 8. Крайние правые - биты с меньшим весом.

Пример на соседнем изображении иллюстрирует уменьшение множителя 8 × 8, объясненное здесь.

Начальное состояние выбрано как , наибольшее значение меньше 8.${\displaystyle j=4}$${\displaystyle d_{4}=6}$

Стадия ,${\displaystyle j=4}$${\displaystyle d_{4}=6}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{5})}$ все меньше или равны шести битам по высоте, поэтому никаких изменений не вносится
• ${\displaystyle \operatorname {height} (c_{6})=d_{4}+1=7}$, поэтому применяется полусумматор, уменьшающий его до шести бит и добавляющий его бит переноса к ${\displaystyle c_{7}}$
• ${\displaystyle \operatorname {height} (c_{7})=9}$включая бит переноса из , поэтому мы применяем полный сумматор и полусумматор, чтобы уменьшить его до шести бит${\displaystyle c_{6}}$
• ${\displaystyle \operatorname {height} (c_{8})=9}$включая два бита переноса из , поэтому мы снова применяем полный сумматор и полусумматор, чтобы уменьшить его до шести бит${\displaystyle c_{7}}$
• ${\displaystyle \operatorname {height} (c_{9})=8}$включая два бита переноса из , поэтому мы применяем один полный сумматор и уменьшаем его до шести бит${\displaystyle c_{8}}$
• ${\displaystyle \operatorname {height} (c_{10}\cdots c_{14})}$ все меньше или равны шести битам в высоту, включая биты переноса, поэтому никаких изменений не производится

Стадия ,${\displaystyle j=3}$${\displaystyle d_{3}=4}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{3})}$ все меньше или равны четырем битам по высоте, поэтому никаких изменений не вносится
• ${\displaystyle \operatorname {height} (c_{4})=d_{3}+1=6}$, поэтому применяется полусумматор, уменьшающий его до четырех бит и добавляющий его бит переноса к ${\displaystyle c_{5}}$
• ${\displaystyle \operatorname {height} (c_{5})=7}$включая бит переноса из , поэтому мы применяем полный сумматор и полусумматор, чтобы уменьшить его до четырех бит${\displaystyle c_{4}}$
• ${\displaystyle \operatorname {height} (c_{6}\cdots c_{10})=8}$ включая предыдущие биты переноса, поэтому мы применяем два полных сумматора, чтобы уменьшить их до четырех бит
• ${\displaystyle \operatorname {height} (c_{11})=6}$ включая предыдущие биты переноса, поэтому мы применяем полный сумматор, чтобы уменьшить его до четырех бит
• ${\displaystyle \operatorname {height} (c_{12}\cdots c_{14})}$ все меньше или равны четырем битам по высоте, включая биты переноса, поэтому никаких изменений не производится

Стадия ,${\displaystyle j=2}$${\displaystyle d_{2}=3}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{2})}$ все меньше или равны трем битам по высоте, поэтому никаких изменений не вносится
• ${\displaystyle \operatorname {height} (c_{3})=d_{2}+1=4}$, поэтому применяется полусумматор, уменьшающий его до трех бит и добавляющий его бит переноса к ${\displaystyle c_{4}}$
• ${\displaystyle \operatorname {height} (c_{4}\cdots c_{12})=5}$ включая предыдущие биты переноса, поэтому мы применяем один полный сумматор, чтобы уменьшить их до трех бит
• ${\displaystyle \operatorname {height} (c_{13}\cdots c_{14})}$ все меньше или равны трем битам по высоте, включая биты переноса, поэтому никаких изменений не производится

Стадия ,${\displaystyle j=1}$${\displaystyle d_{1}=2}$

• ${\displaystyle \operatorname {height} (c_{0}\cdots c_{1})}$ все меньше или равны двум битам по высоте, поэтому никаких изменений не вносится
• ${\displaystyle \operatorname {height} (c_{2})=d_{1}+1=3}$, поэтому применяется полусумматор, уменьшающий его до двух бит и добавляющий его бит переноса к ${\displaystyle c_{3}}$
• ${\displaystyle \operatorname {height} (c_{3}\cdots c_{13})=4}$ включая предыдущие биты переноса, поэтому мы применяем один полный сумматор, чтобы уменьшить их до двух бит
• ${\displaystyle \operatorname {height} (c_{14})=2}$включая бит переноса из , поэтому никаких изменений не вносится${\displaystyle c_{13}}$

Добавление

На выходе последнего этапа остается 15 столбцов высотой два или меньше, которые можно передать в стандартный сумматор.

См. Также [ править ]

• Алгоритм умножения Бута
• Слитное умножение – сложение
• Дерево Уоллеса
• Алгоритм BKM для комплексных логарифмов и экспонент
• Умножение Кочанского для модульного умножения

Ссылки [ править ]

Дальнейшее чтение [ править ]

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