Def === УМНОЖИТЕЛЬ - функциональный узел, который умножает 2 числа. Умножение
Что такое умножение: a * b = a * a * a * ... * a * a * a | | +-------------------------+ b раз
Что такое умножение в двоичной системе: X * 0 = 0 X * 1 = X X * Y = X AND Y таким образом умножение в двоичной системе сводится к сдвигу и сложению: 10101 * 10111 ------------- 10101 10101 + 10101 00000 10101 ------------- 111100011
Умножение ----------------------------+ / | \ | ПАРАЛЕЛЬНЫЕ УМНОЖИТЕЛИ ПОСЛЕДОВАТЕЛЬНЫЙ Аппаратный Табличный Комбинированный УМНОЖИТЕЛЬ умножитель метод метод Время: долго быстро средне очень много Элементы: много очень много относительно мало мало Типы умножителей
Микропрограмная реализация последовательного умножителя result = 0; temp = Y; for i = 0 to N do begin if (bit(i,X) == 1) then begin result = result + temp; end; temp = SHIFT_RIGHT(temp,1); end; Последовательный умножитель
Проблема в том, что очень много сложений занимают очень много времени. Поэтому все оптимизации занимаются уменьшением числа полных сложений (когда происходит перенос).
Умножение знаковых и беззнаковых чисел различное: ab * cd ----------- 00bd БЕЗЗНАКОВЫЕ + 0ad 0cb ac ----------- ab * cd ----------- SSbd ЗНАКОВЫЕ + Sad (S = знаковое расширение частичного произведения) Scb ac ----------- Обратите внимание: младшие N байт произведения (N*N) не зависят от знака поэтому в RISC микропроцессорах обычно используют три команды для умножения: MULL Multiply Low (младшие N бит) MULHS Multiply High Signed (старшие N бит знаковое *) MULHU Multiply High Unsigned (старшие N бит беззнаковое *) Пример знакового последовательного умножителя: Знаковое и беззнаковое умножение
Один из методов заключается в вычислении произведений не побитово, а поблочно и последующего их сложения (умножение в столбик). Сокращение числа частных произведений
Значение произведения блока может быть вычислено быстрым аппаратным умножителем или табличным методом.
Умножение в столбик: +------+------+ | a | b | * +------+------+ | c | d | +------+------+ ===================================== +-------------+ | bd | +-------------+ +--------------+ | ad | + +--------------+ +--------------+ | cb | +--------------+ +--------------+ | ac | +--------------+ ===================================== +-----------------------------+ | Result | +-----------------------------+
Табличный метод: Строится ПЗУ содержащее таблицу умножения. 0 и 1 - особые случаи, их можно обработать аппаратно отдельно. Пример такой таблицы для умножителя 3x3 = > 6 (данные в таблице представленны в 16-ричной системе счистления): Можно хранить не всю таблицу а ее половину т.к. она симметрична. *|2 3 4 5 6 7 -+----------------- 2|04 06 08 0A 0C 0E 3| 09 0C 0F 12 15 4| 10 14 18 1C 5| 19 1E 23 6| 24 2A 7| 31 Время работы для 4x4 = время дешифратора(8бит) + L (транзистор) = (инвертор + 3 * И) + L (транзистор) = 5L Табличный метод умножения
Матричный (n-частичных произведений суммируются в n-каскадах) Бута (уменьшенно количество частных произведений) Уолеса (параллельное сложение частных произведений) NMM (умножение без сложения) Методы быстрого аппаратного умножения