Метод умножения с расшифровкой пар разрядов множителя

И запоминанием переносов

Этот метод относится к аппаратно-логическим методам ускоренного выполнения операции умножения и его целесообразно использовать в ЭВМ, в состав арифметического устройства которых входит комбинационный сумматор параллельного действия и регистры сдвига. Для реализации данного метода в состав арифметического устройства вводятся дополнительный регистр и вентили для хранения сдвигов и передачи переносов.

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

Укрупненно алгоритм выполнения операции умножения с расшифровкой пар разрядов множителя и запоминанием переносов можно описать следующим образом.

В первом цикле умножения анализируется пара младших разрядов множителя и в зависимости от их значения (00; 01; 10; 11) формируется первое частичное произведение по изложенным в п. 2.6.3 правилам ускоренного умножения при одновременной расшифровке двух разрядов множителя. Очевидно, что в первом цикле переносы отсутствуют, то есть их коды равны нулю. Во втором цикле производится сдвиг множителя и первой суммы частичных произведений на два разряда вправо и анализируется следующая по старшинству пара разрядов множителя. Затем формируется второе частичное произведение, которое поразрядно складывается со сдвинутым на два разряда вправо первым частичным произведением. При этом формируются и фиксируются коды переносов.

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

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

 

Пример.

Рассмотрим пример перемножения чисел и по методу расшифровки пар разрядов множителя и запоминанием переносов. При сложении будем использовать модифицированный дополнительный код, который предпочтительнее обратного, так как в последнем циклический перенос в последующем цикле умножения может вызвать дополнительную ошибку, равную половине значения единицы младшего из сохраняемых разрядов произведения. Это может иметь место из-за потери при сдвигах того младшего разряда, в который должен был осуществляться циклический перенос при выполнении в каждом цикле полных сложений. Иллюстрирует рассматриваемый метод представленная в табл. 2.3 схема реализации операции умножения.

Данный результат умножения совпадает с полученным ранее в п. 2.6.3.

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

,

а в случае совмещения сдвига и суммирования – по формуле

,

где - время поразрядного сложения по модулю два. Обычно .

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