Умножение двоичных чисел

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

умножение начиная с младших разрядов множителя:

умножение начиная со старших разрядов множителя:

При «ручном» методе в обоих случаях умножение сводится к последовательному поразрядному умножению множимого на цифры множителя и накоплению (суммированию) получаемых частичных произведений. При этом операциями сложения могут управлять разряды множителя: если в i-м разряде множителя находится единица, то к сумме частичных произведений добавляется множимое с соответствующим сдвигом на i — 1 разряд (вправо или влево в зависимости от принятого способа выполнения операции умножения); если в i-м разряде множителя нуль, то множимое не прибавляется.

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

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

Знак произведения формируется по известному правилу: (+)•(+) = (+); (+)•(-) = (-); (-)•(+) = (-); (—)•(—) = (+). В ЭВМ, как было указано в § 2.3, знак «—» числа кодируется единицей, а «+» — нулем, но правило формирования знака сохраняется. Операция, которую реализует ЭВМ для определения знака произведения, называется суммой по модулю два и обозначается : ; ; ; .

Существует четыре метода умножения. Рассмотрим наиболее распространенный метод умножения целых чи­сел, начиная с младшего разряда со сдвигом суммы частичных про­изведений вправо при неподвижном множимом (рис. 7.4).

Операция умножения состоит из п или п —1 циклов (п —1 —чис­ло цифровых разрядов множителя). В каждом цикле анализиру­ется очередная цифра множителя, и если это 1, то к сумме частич­ных произведений прибавляется множимое; если 0 — прибавления множимого не происходит. Цикл завершается сдвигом суммы час­тичных произведений относитель­но неподвижного множителя (если не выполняется умножение на знаковый разряд).

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

Схема АЛУ для умножения n-разрядных положительных двоич­ных чисел приведена на рис. 7.5. В состав АЛУ входят входной ре­гистр множимого Рг1, регистры множителя Рг2 и Рг2’ на которых с помощью специально организованной передачи цепи сдвига впра­во Рг2^/ = П(1)Рг2 и передачи Рг2=Рг2' выполняется сдвиг мно­жителя вправо, сумматор СМ для образования суммы частичных произведений, входной РгВ и выходной РгСМ регистры сумматора, на которых соответственно хранится текущее значение и образует­ся новое значение суммы частичных произведений и окончательное произведение.

Первоначаль­но в Pг1 поступает множимое. Регистр РгВ, хранящий сумму час­тичных произведений, устанавливается в нулевое состояние, а в счетчик циклов СчЦ за­носится число обрабаты­ваемых цифровых разря­дов. Затем в Рг2 поступает множитель. На этом завершается процедура началь­ных установок и начина­ется процесс вычисления сумм частичных произве­дений.

В зависимости от зна­чений (0 или 1) младшего разряда множителя к час­тичному произведению прибавляется либо 0, либо х, для чего регистру РгА сумматора присваивается соответствующее значе­ние. Полученная сумма умножается на 2^-1 путем передачи кода с выхода сумматора на РгСМ со сдвигом на один разряд вправо. Одновременно множитель подготавлива­ется к перемещению в Рг2 так, чтобы на месте анализируемого младше­го разряда в Рг2 оказался следующий разряд множителя. Для этого содержимое регистра Рг2 передается в регистр Рг2' со сдвигом вправо на один раз­ряд.

Разряд 0 регистра Рг2’ при этом остается свободным и в него заносится младший разряд суммы, выходящий при сдвиге за пре­делы регистра РгСМ (Рг2'[0]: = СМ[п —1]. В следующем такте завершается сдвиг множителя путем занесения содержи­мого регистра Рг2' в регистр Рг2 и в регистре РгВ образуется сдвинутая сумма частичных произведений.

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

Задание:

Составить алгоритм выполнения операции умножения целых положительных чисел.

Порядок выполнения работы:

1. Зарисовать схему АЛУ.
2. Разработать алгоритм, опираясь на схему и описание работы.
3. Внести изменения в алгоритм умножения для одной из трех схем умножения:

Схема 1

Схема 2

Схема 3

Контрольные вопросы:

1. Какие виды АЛУ вы знаете?
2. Перечислите основные методы ускорения умножения
3. Как реализуется операция умножения в АЛУ?