Умножение двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика

Пусть сомножителями X и Y являются s-битные целые числа без знака:

Где - (Х) - множимое, (Y) - множитель, (Z) - произведение. Тогда:

Z = X - Y. (4.2)

Где:

;

.

Представим множитель Y в развернутой форме:

. (4.3)

Тогда:

(4.4)

Произведение множимого на один бит множителя называется частичным произведением. Полное произведение числа представляет собой сумму (s) частичных произведений (ЧП). При умножении вручную существует два способа:

    - Способ № 1, начиная с младшей цифры множителя и сдвиг частичных произведений влево; - Способ № 2, начиная со старшей цифры множителя и сдвиг частичных произведений вправо. Например. Необходимо перемножить два беззнаковых числа (7-3=21). Для удобства возьмем длину разрядной сетки равную четырем битам. Правило умножения вручную заключается в следующем: - шаг 1. Анализируется младший (правый) бит множителя, если младшая цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого, если младшая цифра множителя равна (0), то в сумму частичных произведений записываются все (0); - шаг 2. Анализируется следующий после младшего бит множителя, если цифра множителя равна (1), то в сумму частичных произведений записываются все биты множимого сдвинутые на один разряд влево, если цифра множителя равна (0), то в сумму частичных произведений записываются все (0), сдвинутые на один разряд влево; - шаг 3. Шаги (1) и (2) повторяются до тех пор, пока не будут проанализированы все цифры множителя; - шаг4. Производится сложение всех сумм частичных произведений. Полученная сумма и будет равна произведению множимого на множитель.

Итак: необходимо перемножить два беззнаковых числа (7-3=21)

Где: (7) - множимое;

    (3) - множитель; (21) - произведение.

Необходимо вычислить сумму частичных произведений - (ЧП), а следовательно и произведение.

Способ №1

Десятичное

Число

Двоичное

Число

Комментарии

7(10)

0111(2)

Множимое

3(10)

0011(2)

Множитель

4321

Номера цифр множителя

0111

1Ое - ЧП

0111

2Ое - ЧП

0000

3Ое - ЧП

0000

4Ое - ЧП

21(10) 0010101(2)

Сумма ЧП - произведение

Способ №2

Десятичное

Число

Двоичное

Число

Комментарии

7(10)

0111(2)

Множимое

3(10)

0011(2)

Множитель

1234

Номера цифр множителя

0000

1Ое - ЧП

0000

2Ое - ЧП

0111

3Ое - ЧП

0111

4Ое - ЧП

21(10) 0010101(2)

Сумма ЧП - произведение

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

Длина произведения s-битных сомножителей равна 2s бит:

(4.5)

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

(4.6)

Умножение реализуется циклическим процессом, на каждом шаге которого:

    - анализируется очередной бит множителя; - в зависимости от его значения происходит (yI=1) или нет (yI=0) прибавление множимого к предыдущей сумме частичных произведений; - производится изменение взаимного положения множимого (X) и суммы частичных произведений с учетом веса (2I).

Таким образом, умножение в двоичной системе счисления естественным образом сводится к двум операциям -- сложению и сдвигу чисел.

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

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

схемы выполнения операции умножения двоичных беззнаковых чисел

Рисунок 4.8 -- Схемы выполнения операции умножения двоичных беззнаковых чисел

Соответственно, при умножении старшими разрядами вперед должен анализироваться старший разряд множителя.

Схема 1

. (4.7)

. (4.8)

Время выполнения операции умножения:

(4.9)

Где (tС) -- время, затрачиваемое на выполнение операции сдвига на один разряд;

(t+) -- время, затрачиваемое на выполнение операции сложения.

Схема 2

. (4.10)

(4.11)

. (4.12)

Схема 3

. (4.13)

. (4.14)

. (4.15)

Схема 4

. (4.16)

. (4.17)

. (4.18)

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

Алгоритм №1. Алгоритм умножения младшими разрядами вперед, со сдвигом суммы ЧП вправо.

    1. Исходное значение суммы (ЧП) принимается равным (0), счетчику тактов - (Сч. Т) присваивается значение, равное числу разрядов множителя. 2. Анализируется младшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по старшим разрядам; если (0) -- прибавление не производится. 3. Производится сдвиг множителя и суммы ЧП вправо на (1) разряд. Содержимое (Сч. Т) уменьшается на (1). 4. Анализируется содержимое (Сч. Т). Если оно не равно (0), то переход к (п.2), иначе -- (п.5). 5. Умножение закончено, младшая часть произведения находится на месте множителя, а старшая -- на месте суммы (ЧП). Например: необходимо перемножить два беззнаковых числа (7-3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 - множимое, Y = 3 - множитель, Z = 21 - произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т. е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.1.

Таблица 4.1 - Алгоритм умножения со сдвигом вправо двоичных беззнаковых чисел

Регистр (В)

Множимое X

Регистр (С)

Множитель Y

Регистр (А)

Произведение Z

Счетчик тактов (Сч. Т)

Комментарии

0

1

1

1

0

0

1

1

00000000

4

0111

Множимое

01110000

1Я СЧП

0

0

1

00111000

3

1ЫЙСдвиг СЧП

0111

Множимое

10101000

2Я СЧП

0

0

01010100

2

2 ОЙСдвиг СЧП

0

00101010

1

3 ИЙСдвиг СЧП

00010101

0

4ЫЙСдвиг СЧП

СТОП

Алгоритм №2. Алгоритм умножения старшими разрядами вперед, со сдвигом суммы ЧП влево.

    1. Исходное значение суммы (ЧП) принимается равным (0), (Сч. Т) присваивается значение, равное числу разрядов множителя. 2. Производится сдвиг суммы (ЧП) влево на (1) разряд. 3. Анализируется старшая разрядная цифра множителя. Если она равна (1), то к сумме (ЧП) прибавляется множимое, совмещенное по младшим разрядам; если (0) -- прибавление не производится. 4. Производится сдвиг множителя влево на (1) разряд. Содержимое (Сч. Т) уменьшается на (1). 5. Анализируется содержимое (Сч. Т). Если оно не равно (0), то переход к (п.2), иначе -- (п.6). 6. Умножение закончено, произведения находится на месте суммы (ЧП), которая имеет удвоенную разрядность. Например: необходимо перемножить два беззнаковых числа (7-3=21). Для удобства возьмем длину разрядной сетки равную четырем битам, а именно: Х = 7 - множимое, Y = 3 - множитель, Z = 21 - произведение. Если (X) и (Y) равняется четырем битам, то как было отмечено выше (Z) должно быть восьмиразрядным значением, т. е длина разрядной сетки произведения в два раза больше множимого и множителя. Алгоритм умножения приведен в табл. 4.2.

Таблица 4.2 - Алгоритм умножения со сдвигом влево двоичных беззнаковых чисел

Регистр (В)

Множимое X

Регистр (С)

Множитель Y

Регистр (А)

Произведение Z

Счетчик тактов (Сч. Т)

Комментарии

0

1

1

1

0

0

1

1

00000000

4

00000000

1ЫЙСдвиг СЧП

0

1

1

00000000

3

2 ОЙСдвиг СЧП

00000000

3 ИЙСдвиг СЧП

1

1

00000000

2

4ЫЙСдвиг СЧП

00000000

5ЫЙСдвиг СЧП

0111

Множимое

00000111

1Я СЧП

1

1

00001110

6ОЙ сдвиг СЧП

0111

Множимое

00010101

0

2Я СЧП

СТОП

Похожие статьи




Умножение двоичных беззнаковых чисел в компьютерных системах - Компьютерная арифметика

Предыдущая | Следующая