Файл: Каган Б.М. Цифровые вычислительные машины и системы учеб. пособие.pdf

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

Данный метод умножения требует корректировки ре­ зультата, если старшая пара разрядов множителя 11 или 10 и есть дополнительная единица от предыдущей па­ ры (что сигнализируется единичным состоянием тригге­ ра запоминания Тааті). В этом случае к полученному про­ изведению должно быть добавлено множимое.

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

Подобным же образом можно организовать умноже­ ние с обработкой за шаг трех разрядов множителя. Пра­ вила для обработки троек разрядов множителя приведе­ ны в табл. 5-3.

Необходимые для реализации умножения на три раз­ ряда множителя удвоенное и учетверенное множимые могут быть получены сдвигом множимого в регистре или переключением разрядов на входе сумматора. Утроен­ ное множимое должно быть сформировано до выполне­ ния умножения и храниться в отдельном регистре.

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

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

340

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

Рассмотрим этот способ на примере умножения с об­ работкой за шаг двух разрядов множителя.

Условимся, что мы производим умножение начиная со старших разрядов множителя, т. е. рассматриваем множитель слева направо. Предположим, что при иссле­ довании первой пары мы предусматриваем следующие действия. Если встречается пара 00 или 10, т. е. правый разряд пары 0, то мы производим такие же действия, как и в предыдущем способе: или ничего не прибавляем к сумме частичных произведений, или прибавляем удвоенное множимое. В случае, если встретилась пара 01 или 11, будем прибавлять к сумме частичных произ­ ведений множимое, умноженное на число, которое на 1 больше, чем данная пара (т. е. прибавлять удвоенное или учетверенное множимое).

Тогда сумма частичных произведений в случае пар 00 и 10 будет правильна, а в случае пар 01 и 11 она бу-

341

дет неправильна и должна быть скорректирована на следующем шаге. После обработки очередной пары разрядов множителя сумма частичных произведений должна быть сдвинута на два разряда влево, что равно­ значно увеличению ее в 4 раза. Следовательно, в случае обработки пары 01 или 11 сумма частичных произведе­ ний перед обработкой следующей пары будет больше истинной на учетверенное множимое. Поэтому если правый разряд предыдущей пары был 1, то для коррек­ ции суммы частичных произведений действие при обра­ ботке данной пары должно учитывать необходимость вы­ читания учетверенного множимого.

В случае обработки пары 00 из суммы частичных произведений должно быть вычтено учетверенное мно­ жимое. Для пары 10 из суммы частичных произведений должно быть вычтено удвоенное множимое. Для пары 01 также должно быть вычтено удвоенное множимое. Для пары 11 сумма частичных произведений не изме­ няется.

Правила для обработки пар разрядов множителя с учетом младшего разряда предыдущей пары могут быть сведены в табл. 5-4.

Описанный алгоритм ускорения умножения был предложен Мак-Сорли [Л. 108]. Схема, реализующая алгоритм Мак-Сорли для умножения с обработкой за шаг двух разрядов множителя начиная со старших его разрядов, показана на рис. 5-16.

Регистр множителя содержит дополнительный стар­ ший разряд Гдоп, который перед началом умножения

342

сбрасывается. В ходе выполнения умножения в Тдоп хра­ нится младший разряд комбинации, обработанной на предыдущем шаге.

Из табл. 5-4 видно, что для выполнения умножения необходимы удвоенное и учетверенное множимые. По­ этому перед началом умножения в регистр множимого

Рис. 5-16. Схема умножения на 2 разряда множителя, начиная со старших, по алго­ ритму Мак-Сорли.

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

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

343

управляются двумя старшими разрядами и дополнитель­ ным разрядом Тдоп регистра множителя. После обработ­ ки каждой пары разрядов регистра множителя его со­ держимое и содержимое сумматора частичных произве­ дений сдвигаются на два разряда влево. Алгоритм Мак-Сорли с успехом может быть применен и при умно­ жении начиная с младших разрядов множителя.

Следует отметить, что, если множитель оканчивается на 1, то, как в случае умножения начиная со старших разрядов множителя, так и в случае умножения начиная с младших разрядов необходимо после получения ре­ зультата вычесть из него множимое.

Аналогичным образом можно организовать и умно­ жение с обработкой за шаг трех разрядов множителя.

Порядок действия при разных комбинациях разрядов в тройках и младшего разряда соседней старшей тройки множителя приведен в табл. 5-5.

Т а б л и ц а 5-5

Для выполнения умножения с обработкой за шаг трех разрядов множителя необходимы числа с крат­ ностью множимому 2, 4, 6 и 8. Числа с кратностью мно­ жимому 2, 4 и 8 могут быть легко получены сдвигом его на 1,2 или 3 разряда влево. Число с кратностью множи­ мому 6 можно получить, складывая двойное и учетверен-

344

ное множимые и помещая результат для хранения в от­ дельный регистр.

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

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

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

В табл. 5-6, 5-7 показан порядок действия при асин­ хронном умножении с исследованием на каждом шаге трех разрядов множителя, который использует только множимые, кратные степени двух.

Таблица 5-6 относится к методу умножения, при ко­ тором на каждом шаге умножения исследуется комби­ нация очередных трех разрядов множителя и дополни­ тельная единица, появляющаяся при обработке преды­ дущей комбинации. Таблица 5-7 относится к методу умножения начиная с младших разрядов множителя, ис­ пользующему алгоритм Мак-Сорли, при котором на каждом шаге умножения исследуются данная комбина­ ция и младший разряд соседней, более старшей комби­ нации.

В зависимости от соотношения затрат оборудования для хранения чисел, кратных множимому, переключения входов сумматора и введения дополнительных цепей сдвига могут быть использованы те или иные методы ускорения умножения [Л. 34].

345