Умножение с хранением переносов

Время, затрачиваемое на сложение двоичных чисел, состоит из времени, необходимого для поразрядного сложе­ния, и времени на формирование переноса

t_сл = t_Å + t_пер.

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

Пример: Мн = 0,1011

Мт= 0,1101

0,0000

0,0000 регистр переносов

⁺ 0,1011 = Мн b₄

0,1011

0,0000 регистр переносов

0, 0 101 1 2^-1

⁺ 0,0000 = Мн b₃

0,0101 1

0,0000 регистр переносов

0, 0 010 11 2^-1

⁺ 0,1011 = Мн b₂

0,1001 11

0,0010 регистр переносов

0, 0 100 111 2^-1

⁺ 0,1011 = Мн b₁

1,0001 111

0, 1 000 1111 2^-1

 

Умножение на два разряда множителя одновременно

Разбиение множителя на группы длиной k разрядов означает переход к новой системе счисления с основанием 2^k. Если при этом удается сократить количество элементарных действий, выполняемых при умножении (сложение и сдвиги), то сокращается время умножения. Остановимся более подробно на умножении на два разряда множителя за один такт (k=2). Это связано с анализом пар разрядов множителя.

Возможны четыре случая сочетания разрядов множителя: 00, 01, 10, 11. Умножение на каждую из пар разрядов множителя должно выполняться за один такт автоматного времени, то есть в каждом такте умножения должно выполняться не более одного сложения. Рассмотрим умножение на эти пары на примере алгоритма А.

В случае пары 00 необходимо выполнить только сдвиг частичной суммы на два разряда - 2^-2.

Для пары 01 выполняется добавление множимого в сумматор с последующим сдвигом суммы на два разряда - 2^-2.

При наличии пары 10 возможны следующие варианты действий:

a) 2^-2, то есть в этом случае происходят два сложения, что противоречит требованию;

б) 2^-2, в этом случае требуется дополнительный регистр для хранения удвоенного Мн;

в) 2^-2, что соответствует добавлению к частичной сумме сдвинутого на один разряд влево множимого;

г) 2^-1, то есть частичная сумма сдвигается на один разряд вправо до и после добавления к ней множимого.

При умножении на пару 11 (к частичной сумме необходимо добавить утроенное множимое) ее можно представить в виде

11 = (2² - 1)

Мн ∙ 11= Мн∙(2² - 1) = Мн∙2²- Мн, то есть в текущем такте к частичной сумме добавляется множимое, взятое со знаком минус. Добавление Мн∙2² реализуется путем увеличения на единицу следующей старшей пары разрядов.

В табл.1 представлены правила преобразования множителя для системы (0,1,1).

Таблица 1

Анализируемая пара разрядов Мт	Перенос из предыдущей пары	Преобразованная пара
11
10

Пример: Мн = 0101

Мт = 11000111

Мт^п = 0101001001

Умножение будем осуществлять согласно алгоритму А.

[- Мн]_доп = 1.1011

2 Мн = 0.1010

0.0000

⁺ 1.1011 = -Mн

1.1011

1. 11 10 11 ∙ 2^-2

⁺ 0.1010 = 2Mн

0.1000 11

0. 00 10 0011 ∙ 2^-2

0. 00 00 100011 ∙ 2^-2 ( ∙ 2^-4)

⁺ 1.1011 =-Mн

1.1011 100011

1. 11 10 11100011 ∙ 2^-2

⁺ 0.0101 = Mн

0.0011 11100011

0. 00 00 1111100011 ∙ 2^-2

Время умножения на два разряда множителя одновременно

Появление любой из рассматриваемых пар множителей равновероятно. Следовательно, время умножения на два разряда множителя может быть выражено следующим соотношением: = (n/2 + 1) [0,75∙(t_сл + t_сдв) + (0,25∙t_сдв], где n – количество разрядов множителя.

 

Умножение на четыре разряда одновременно

В этом случае с помощью приема, аналогичного приему, использованному в случае умножения на два разряда одновременно, можно рассматривать сразу тетраду двоичных разрядов. Может быть выведено общее правило сокращенного умножения:

1. Если цифра множителя b_i-1 < r/2, то + , где = Мн b_i.

2. Если цифра множителя b_i-1 ³ r/2, то + , где = [Мн (r - b_i)]_доп.

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

Пример: Мн = 011

Мт = С49

Мт^п = 1457

Можно заранее заготовить кратные множители: Мн, 2Мн, 4Мн, поместив их в дополнительные регистры. Это позволит сократить время, необходимое для формирования частичного произведения , равного от нуля до семи множимых.

[+7Мн]_доп = 0.10101 [+5Мн]_доп= 0.01111 [+4Мн]_доп= 0.01100

[-7Мн]_доп = 1.01011 [-4Мн]_доп = 1.10100

0.00000

⁺ 1.01011 = -7Mн

1.01011

1. 1111 0 1011 ∙ 2^-4

⁺ 0.01111 = +5Mн

0.01101 1011

0. 0000 0 1101 1011 ∙ 2^-4

⁺ 1.10100 =-4Mн

1.10100 1101 1011

1. 1111 1 0100 1101 1011 ∙ 2^--4

⁺ 0.00011 = +Mн

0.00010 0100 1101 1011

0. 0000 00010 0100 1101 1011 ∙ 2^--4 = Мн∙Мт