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

Методы умножения двоичных беззнаковых чисел основаны на представлении произведения в виде полинома [с учетом формулы (1.4)]:

Z=X . Y=X{ S yt • 2)= 2 {X . у,) . 2 =

1=0 1=0

= 2ЧП,-2, (1.19)

где (/,е{0,1} - двоичные цифры множителя; ЧП, = ХХ Xyi - частичные произведения (4U[ - X, если t/i=l, и ЧП,= 0, если у, = 0). Заметим, что умножение ЧП/0 на степень 2 эквивалентно сдвигу множимого на i разрядов влево. Формирование произведения, согласно формуле (1.9), представляется как последовательность таких действий: 1) обнуление СЧП; 2) анализ младшего разряда, множителя: если yo-U выполняется сложение ЧПо = Х с СЧП и переход к п. 3; если уо = О, сразу переход к п. 3; 3) сдвиг множимого влево; 4) анализ очередного разряда множителя: если (/i=l, выполняется сложение ЧП, 2 с СЧП и переход к п. 5; если (/,=0, непосредственно переход к п. 5; 5) сдвиг множимого влево; 6) анализ очередного t/2 разряда множителя и т. д. После анализа старшего у„ , разряда множителя осуществляется по-, следнее сложение ЧП„ ,-2"~ с СЧП (если у„ , = 1), и процесс прекращается. Результирующая СЧП является искомой. Очевидно, что неподвижную СЧП и сдвигаемое влево на лг - 1 разряд множимое необходимо размещать в 2 п-разрядных форматах, причем операция сложения должна обрабатывать 2 «-разрядные данные..

Форматы множимого и операции сложения можно ограничить п разрядами, если изменить процедуру обработки, определяемую формулой (1.19), следующим образом:

п-I п-I

Z= 2 X . 2 у,= 2 (X ..2") . 2-« . у,=

= S 2-" •</,,

где 1/ = Х-2" - множимое, сдвинутое влево на п разрядов.

Преобразуем полученное выражение по схеме Горнера:

Z = (...((О-1-I/ уо) • 2--f 1. у,) • 2--f ...-f 1 • у„-,)• 2-.

(1.20)

Выражения в скобках в формуле (1.20) представляют собой последовательные значения СЧП,-, определяемые рекуррентной формулой

СЧП, = СЧП, ,.2- + К-1/1 ,, СЧПо = 0, /е{1, п],

(1.21)

где I/-у, = ЧП, . Заметим, что умножение СЧП на 2~ эквивалентно ее сдвигу вправо на один разряд.

В соответствии с формулами (1.20) и (1.21) процесс формирования произведения выглядит следующим образом: 1) обнуление СЧП; 2) анализ младшего разряда множителя: если (/о== 1. сложение ЧПо = Х с СЧП и переход к п. 3; если уо -О, непосредственно переход к п. 3; 3) сдвиг СЧП вправо; 4) анализ очередного разряда yi множителя и т. д. После анализа старшего разряда (/„ i множителя осуществляются последнее сложение ЧП„ 1 с СЧП (если y„ i = l) и последний сдвиг СЧП вправо, после чего процесс прекращается. Таким образом, данный процесс умножения требует для представления неподвижного множимого 1/=Х-2" п-разрядного формата (поскольку младшие п разрядов множимого равны нулю) и такого же формата для операции сложения (сложение выполняется со старшими п разрядами СЧП). Формулы (1.19) и (1.20) определяют алгоритмы умножения с младших разрядов множителя соответственно при неподвижной и подвижной СЧП.

Аналогичные формулы имеют место при умножении со старших разрядов множителя:

Z = (...«(0).2+X.y„ ,)-2+>V-y„ 2)-2+ ... Xy)2Л-Х-уо, (1.22)

СЧа = СЧП, I 2 + X • у„ ,; СЧПо = О, J е {1, п}, (1.23) 2= 2 2-(+\ V=X-2\ (1.24)

Формулы (1.22) и (1.24) получены из полинома (1.19) соответственно по схеме Горнера и перенумерацией индексов. Выражения (1.22) и (1.23) определяют процесс умножения с неподвижным «-разрядным множимым и подвижной, сдвигаемой влево 2п-разрядной СЧП. Этот процесс реализуется такой последовательностью действий: 1) обнуление СЧП; 2) сдвиг СЧП влево; 3) анализ старшего разряда множителя: если y„ i = l, выполняется сложение ЧП„ 1 = Х- t/„ i с СЧП и переход к п. 4; если О, прямой переход к п. 4; 4) сдвиг СЧП влево; 5) анализ очередного Уп-ч разряда множителя и т. д. После анализа младшего t/o разряда множителя выполняется последнее сложение ЧПо=Х-г/о с "СЧП (если г/о=1), и процесс прекращается.

Выражения (1.24) определяют процесс умножения с неподвижной СЧП и подвижным, сдвигаемым вправо 2 «-разрядным множимым. Этот процесс имеет такую последовательность действий: 1) обнуление СЧП; 2) сдвиг множимого вправо; 3) анализ старшего разряда множителя: если y„ i==l, выполняется сложение ЧП„ -2" с СЧП и переход к п. 4; если t/„ i =0, прямой переход к п. 4; 4) сдвиг множимого вправо; 5) анализ очередного разряда Уп-1 множителя и т. д. После анализа младшего разряда t/o множителя осуществляется последнее сложение ЧПо-2~ с СЧП (если уо=1), и процесс прекращается.

Рассмотренным четырем алгоритмам умножения со ответствуют четыре вычислительные схемы, используемые при разработке программ умножения (рис. 1.5): схема 1 (рис. 1.5, а) соответствует выражениям (1.20), (1.21); схема 2 (рис. 1.5, б) - формуле (1.19); схема 3 (рис. 1.5, е).- соотношениям (1.22), (1.23); схема 4 (рис. 1.5, г) -формулам (1.24). На схемах обозначены: МН - множители, ММ - множимые (с указанием в