Page 36 - ЭВМ

2) логические методы (ЛМ).
АМ и ЛМ требуют дополнительного оборудования. При исполь-
зовании ЛМ дополнительное оборудование не зависит от длины n со-
множителя, а при АМ – зависит.

Рассмотрим логические методы. Из предыдущего известно, что
на каждом шаге умножения прибавление к промежуточному резуль-
тату множимого происходит при единичном значении текущего раз-
ряда множителя [2].
Полагая появление 0 или 1 в множителе равновероятным, полу-
чим, что в среднем число сложений равно n/2.
Метод Лемана позволяет уменьшить общее время за счет
уменьшения числа необходимых сложений.

Идея метода Лемана состоит в следующем:
1. В множителе можно всегда выделить единичные и нулевые
чередующиеся последовательности, например (01100011110). Оче-
видно, что при обычном умножении, например по второму способу,
правая единичная последовательность требует четырех прибавлений
множимого. Однако значение этой последовательности можно рас-
сматривать как (10000 – 1). Используя это соображение, следует при

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

множителя, а группы разрядов.
Пусть b j – j-й разряд множителя: …b 3, b 2, b 1, где b 1 – младший
разряд множителя.
Введем переменные:
0, не надо выполнять действие «+» или «–» на i шаге умножения,
d i = 1, надо выполнять действие «+» и «–» на i шаге умножения,

0, надо выполнять операцию «+», если d i = 1,
S i = 1, надо выполнять операцию «–», если d i = 1.
d = i (b ⊕ i b i+ 1 ) d i− 1
⋅
S = i b i+ 1 d ⋅ i
Например:

36