Метод ускоренного умножения Лемана

Метод Лемана рассмотрим в предположении, что умножение выполняется, начиная с младших разрядов множителя.

Алгоритм в данном цикле операции умножения может быть записан в следующем виде:

где - номер разряда множителя;

- цифра -го разряда множителя;

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

- знак арифметического действия.

Очевидно, что при .

Если , то производится сложение суммы частичных произведений с множимым. При производится вычитание множимого из суммы частичных произведений.

Из анализа приведенных выше выражений, описывающих алгоритм действий в данном цикле умножения, следует, что перед началом операции умножения . Это значение сохраняется до появления первой единицы в младшем разряде множителя. При появлении там единицы производится сложение множимого с предшествующей суммой частичных произведений, если в следующем по старшинству разряде множителя содержится «0», или производится вычитание множимого из предшествующей суммы частичных произведений, если в следующем по старшинству разряде множителя содержится «1», то есть .

При появлении 0 в младшем разряде множителя производится вычитание множимого из предшествующей суммы частичных произведений, если в следующем по старшинству разряде множителя содержится «1» , или производится сложение множимого с предшествующей суммой частичных произведений, если в следующем по старшинству разряде множителя содержится «0» .

Рассмотрим на конкретном примере последовательность действий в сумматоре и регистре множителя при умножении по методу Лемана.

Пусть множимое , а множитель .

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

С учетом сказанного схема выполнения конкретного примера ускоренного умножения по методу Лемана представлена ниже.

Содержимое Содержимое

регистра сумматора [C_M]

100011 10 исходное состояние 00 00000000 0

010001 11 сдвиг вправо и [C_M] 00 00000000 0

(-) + 11 01001011 1

11 01001011 1

001000 11 сдвиг вправо и [C_M] 11 10100101 1

000100 01 сдвиг вправо и [C_M] 11 11010010 1

000010 00 сдвиг вправо и [C_M] 11 11101001 0

(+) + 00 10110100 0

1 00 10011101 0

00 10011101 1

000001 00 сдвиг вправо и [C_M] 00 01001110 1

000000 10 сдвиг вправо и [C_M] 00 00100111 0

000000 01 сдвиг вправо и [C_M] 00 00010011 1

(+) + 00 10110100 0

произведение 00 11000111 1

округление 00 11001000 0

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

Анализ показывает, что при умножении по методу Лемана даже при наиболее неблагоприятном сочетании цифр разрядного множителя (101010…) количество операций суммирования равно . В среднем же количество операций суммирования равно .

Метод умножения с расшифровкой пар разрядов множителя

И запоминанием переносов

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

Рассматриваемый метод умножения заключается в следующем. В каждом цикле операции умножения выполняется поочередное сложение по модулю два суммы частичных произведений и множимого и образование поразрядных переносов, значения которых фиксируются в отдельном регистре. В результате этого формируются не полные, а поразрядные суммы частичных произведений и значения соответствующих переносов, коды которых составляют третье слагаемое в очередном цикле умножения. Поразрядное сложение по модулю два выполняется за время, меньшее, чем время, необходимое для формирования полной суммы, так как из последнего исключается время распространения переносов. Это и приводит к уменьшению общего времени, необходимого для выполнения операции умножения. При этом, однако, в заключительном цикле операции умножения требуется производить полное сложение последней поразрядной суммы частичных произведений с кодами переносов, сформированными при последнем поразрядном сложении.

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

В первом цикле умножения анализируется пара младших разрядов множителя и в зависимости от их значения (00; 01; 10; 11) формируется первое частичное произведение по изложенным в п. 2.6.3 правилам ускоренного умножения при одновременной расшифровке двух разрядов множителя. Очевидно, что в первом цикле переносы отсутствуют, то есть их коды равны нулю. Во втором цикле производится сдвиг множителя и первой суммы частичных произведений на два разряда вправо и анализируется следующая по старшинству пара разрядов множителя. Затем формируется второе частичное произведение, которое поразрядно складывается со сдвинутым на два разряда вправо первым частичным произведением. При этом формируются и фиксируются коды переносов.

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

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

Пример.

Рассмотрим пример перемножения чисел и по методу расшифровки пар разрядов множителя и запоминанием переносов. При сложении будем использовать модифицированный дополнительный код, который предпочтительнее обратного, так как в последнем циклический перенос в последующем цикле умножения может вызвать дополнительную ошибку, равную половине значения единицы младшего из сохраняемых разрядов произведения. Это может иметь место из-за потери при сдвигах того младшего разряда, в который должен был осуществляться циклический перенос при выполнении в каждом цикле полных сложений. Иллюстрирует рассматриваемый метод представленная в табл. 2.3 схема реализации операции умножения.

Данный результат умножения совпадает с полученным ранее в п. 2.6.3.

Время, необходимое для операции умножения рассмотренным методом в случае несовмещения по времени сдвига и суммирования, рассчитывается по формуле

,

а в случае совмещения сдвига и суммирования – по формуле

,

где - время поразрядного сложения по модулю два. Обычно .

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

Не нашли, что искали? Воспользуйтесь поиском по сайту: