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

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

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

Фактически, множители Дадды и Уоллеса имеют одинаковые три шага для двух битовых строк. и длины и соответственно:

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

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

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

Описание

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

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

Ход сокращения контролируется последовательностью максимальной высоты. , определяется:

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

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

Для каждого этапа от , уменьшите каждый столбец, начиная с столбца с наименьшим весом, согласно этим правилам:

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

Пример алгоритма

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

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

Исходное состояние выбран как , наибольшее значение меньше 8.

Этап ,

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

Этап ,

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

Этап ,

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

Этап ,

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

Добавление

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

Смотрите также

Рекомендации

  1. ^ Дадда, Луиджи (Май 1965 г.). «Некоторые схемы параллельных умножителей». Alta Frequenza. 34 (5): 349–356.
  2. ^ Townsend, Whitney J .; Swartzlander, Jr., Earl E .; Авраам, Джейкоб А. (Декабрь 2003 г.) [2003-08-06]. «Сравнение задержек множителя Дадды и Уоллеса» (PDF). Расширенные алгоритмы, архитектуры и реализации SPIE XIII. Международное общество. Дои:10.1117/12.507012. В архиве (PDF) из оригинала на 2018-07-16. Получено 2018-07-16.

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