Быстрые умножители.

Пусть требуется вычислить произведение двух целых положительных чисел

Тогда произведение можно представить в виде

Величины называются частичными произведениями. Число частичных произведений равно числу разрядов множителя Рассмотренный выше матричный умножитель (рис. 6.132) и производит вычисление таких частичных произведений с совмещением операции их суммирования в каждой ступени вычисления

Выражение для можно преобразовать к виду:

на основании элементарного соотношения

используемого для нечетных значений Все частичные произведения

(кликните для просмотра скана)

имеют одинаковую структуру, а их число уменьшилось вдвое по сравнению с числом частичных произведений при использовании рассмотренного преобразования в каждой ступени вычисления частичного произведения производится умножение сразу на два разряда множителя У. Такой метод вычисления произведения называется модифицированным алгоритмом Бута. Легко показать, что алгоритм Бута справедлив и для умножения двоичных чисел, представленных в дополнительном коде, причем произведение выдается также в дополнительном коде.

Покажем, что частичные произведения достаточно просто реализуются с помощью КС. Не теряя общности, можно положить тогда функционирование КС будет описываться выражением:

Так как или 1, то величина в скобках может принимать значения от -2 до +2, т.е. число Пусть . Это означает, что множимое X следует сдвинуть на один разряд влево, а результат необходимо представить в дополнительном коде для выполнения суммирования частичных произведений. Дополнительный код частичного произведения в этом случае При этом возникает задача расширения разрядной сетки частичных произведений до разрядной сетки всего произведения которое имеет большее число разрядов по сравнению с младшим частичным произведением.

Пример 1:

Пример 2:

Таблица 6.27. (см. скан) Быстрый умножитель разряда

Рис. 6.135

Табл. 6.27 задает функционирование -разрядного быстрого умножителя, где обратный код числа Функция введена для расширения разрядной сетки частичных произведений, а функция со предназначена для преобразования обратного кода в дополнительный.

Из диаграмм Вейча (рис. 6.135; составленным по табл. 6.27, видно, что

а функции минимизации не поддаются, т.е.

Функции несложно представить в форме

где По этим функциям может быть построена КС, реализующая быстрый умножитель разряда.

На рис. 6.136 показаны ИС:

Рис. 6.136

Рис. 6.137

555ИП8 - быстрый умножитель разряда, построенный в соответствии с (6.60) и (6.61);

531ИК1 - быстрый умножитель разряда с сумматором частичных произведений.

Умножитель содержит пять асинхронных потенциальных -триггеров для фиксации функций где Схема разрядов показана на рис. 6.137. Если то осуществляется прямая передача значений на выходы Фиксация значений в триггерах используется для построения быстрых конвейерных умножителей (см. § 6.14). Таким образом, может использоваться для проектирования как конвейерных, так и обычных -разрядных быстрых умножителей.

На рис. 6.138 показана схема быстрого умножителя разряда. Четыре формируют два частичных произведения с весами разрядов от 2° до 29 и от 22 до 211 (сигналы необходимы для преобразования обратного кода в дополнительный). Константы единица с весами 28, 29 и 211 добавляются для правильного суммирования частичных произведений в дополнительном коде с расширением разрядной сетки. Так как частичные произведения представляются в дополнительном коде, то и сомножители должны подаваться на умножитель в дополнительном коде. Понятно, что произведение будет также представлено в

(кликните для просмотра скана)

дополнительном коде. Если знаковые разряды сомножителей, то — знаковые разряды произведения произведение положительное, произведение отрицательное).

В табл. 6.28 указано число разрядов частичных произведений, имеющих одинаковый вес Из табл. 6.28 видно, что даже два частичных произведения не могут быть просуммированы с помощью -разрядного двоичного сумматора. Поэтому производится предварительное суммирование разрядов частичных произведений с помощью одноразрядных сумматоров (например, После того, как таким способом будет получено не более, чем по два разряда с весами, большими 2°, суммирование сформированных двоичных чисел выполняется на -разрядном сумматоре, построенном, например, на трех Схема суммирования разрядов частичных произведений с помощью одноразрядных сумматоров называется деревом Уоллеса [9] (в данном случае имеется только основание дерева из-за малого числа частичных произведений).

Таблица 6.28. (см. скан) Число разрядов частичных произведений

Аналогично схеме на рис. 6.138 может быть построена схема быстрого умножителя при любом числеп и разрядов сомножителей. При этом следует пользоваться правилом: две константы единица с весами и добавляются к первому (младшему) частичному произведению, а к остальным частичным произведениям — только по одной константе единица с весами

На основе рассмотренного выше принципа быстрого умножения (на два разряда множителя) построена и схема (рис. 6.136), которая одновременно выполняет и суммирование частичных произведений. Схема, вычисляющая частичные произведения разряда, описывается табл. 6.29. Функции и

Таблица 6.29. (см. скан) Вычисление частичных произведений

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

Выходы разрядов суммы частичных произведений описываются выражениями:

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

На рис. 6.139 показана схема быстрого умножителя разрядов, выполненная на шести Сомножители, как и в схеме на рис. 6.138, подаются в дополнительном коде знаковые разряды), и результат произведения выдается в дополнительном коде произведение положительное, произведение отрицательное). При умножении и m-разрядных отрицательных чисел максимальной величины (), модуль которых равен и при получаются значения: что при использовании в качестве знакового разряда только дает правильный результат умножения.