Арифметико-логические устройства ЭВМ, страница 6

,

например: 

(здесь используется соотношение: ),

n и k – номера разрядов числа, между которыми во всех разрядах в числе  записаны единицы. Но тогда нужно лишь множимое сдвинуть вначале на n-1 разряд, а затем на k разрядов, и вслед за этим вычесть из 1-го числа второе.

Обобщенно это приводит к такому алгоритму, подлежащему реализации в АЛУ:

Шаг 1. Просматривая множитель, начиная с младшего разряда, сдвигать содержимое сумматора (частичное произведение) вправо до появления первой единицы в множителе.

Шаг 2. На первой единице передать множимое инверсным кодом в сумматор.

Шаг 3. Сдвигать содержимое сумматора синхронно с просмотром разрядов множителя до появления первого «0».

Шаг 4. Передать на первом «0» в сумматор множимое прямым кодом и перейти к первому шагу.

Завершается алгоритм с просмотром последнего (старшего разряда) множителя.

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

первое:  – можно использовать, когда переходим от ожидаемого «0» к ожидаемой «1».

второе:  – можно использовать при переходе от ожидаемой «1» к ожидаемому «0».

Пояснение-иллюстрация:

а) ¼000100¼  Если две группы нулей разделены «1» в k-ой позиции, то вместо вычитания в k-ой позиции и сложения в k+1-ой достаточно только выполнить сложение в k-ой позиции.

б) ¼110111¼ Если две группы единиц разделены «0» в k-ой позиции, то достаточно выполнить только вычитание в  k-ой позиции.

Итак, надо знать:

1)  по каким сдвигам-ожиданиям («0» или «1») происходит просмотр множителя;

2)  содержимое следующего (соседнего старшего) разряда за анализируемым.

Первое очень просто реализовать с помощью триггера (начальная установка в «0»), а тогда тип передачи множимого на сумматор задается таблицей: