Динамо-машины  Обратные коды 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 [ 119 ] 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189

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

..11 = 1..00-..01.

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

00- если данная пара разрядов содержит цифры 00 и из предыдущей пары единица не передается;

01- если данная пара содержит цифры 01 и из предыдущей пары единица не передается или если данная пара разрядов содержит 00 и передается единица из предыдущей пары разрядов;

10- если данная пара содержит 10 и нет единицы из предыдущей пары или если данная пара содержит - 01 и есть единица из предыдущей пары разрядов;

И-если данная пара разрядов содержит 11 и нет единицы из предыдущей пары или если данная пара содержит 10 и есть единица из предыдущей пары; 1..00 - если данная пара разрядов содержит цифры 11 и единица передается из предыдущей пары разрядов.

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

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

Операции, которые мы здесь выполняем, заключают в себе преобразование множителя в такую форму, когда наряду с цифрами 0 1 допускается также цифра -1 (ее мы будем обозначать 1). Цифра О в множителе соответствует отсутствию суммирований или вычитаний, цифра 1-

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

Изображения чисел в этой форме неоднозначны. Фактически все логические методы ускорения двоичного умножения, которые мы будем рассматривать дальше, сводятся к различным способам преобразования множителя в указанную форму. Тот или иной способ тем более эффективен, чем больше в преобразованном множителе среднее количество нулей и меньше среднее количество положительных и отрицательных единиц, т. е. чем меньше в среднем требуется тактов суммирования или вычитания; важно также, каково максимальное количество тактов суммирования вычитания, которое может встретиться при выполнении умножения.

Для оценки эффективности описанного выше метода группировки разрядов по парам заметим прежде всего, что- при любой комбинации цифр слагаемых в течение пары циклов умножения может быть не более одного суммирования или вычитания. Таким образом, теперь в х у д ш е м случае приходится половина такта суммирования или вычитания на каждый разряд множителя - вдвое меньше, чем при отсутствии группировки пар разрядов (теперь laquo;худшими raquo; являются случаи умножения на 01...010101 или на 10... 101010, в то время как при отсутствии группировки разрядов по парам laquo;худшим raquo; был случай умножения на 11...111111).

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

00, 01, 10 и 11 равновероятны (вероятность появления любой из них равна V4). Для любой последующей пары разрядов вероятность появления каждой из комбинаций

01, 10 и 11 равна V4, для комбинаций же 00 и 1. .00 их вероятности в сумме равны V4. (Если вероятность передачи единицы в данную пару разрядов обозначить через р,

то вероятность комбинации 00 равна (1-р)-;, а вероятность комбинации 1. .00 - р , что в сумме дает V4; вероятность появления любой другой из комбинаций - скажем.

комбинации 01 - равна (1 - р) 4 + Р = 4~-)

Поскольку в комбинациях 01, 10 и И требуется по одному такту суммирования или вычитания в течение ближайшей пары циклов умножения, а в комбинациях 00 и 1..00- ни одного такта, то в среднем на пару циклов умножения будет приходиться по % такта суммирования-вычитания. На каждый разряд множителя будет приходиться, таким образом, в среднем /g (или 0,375) такта суммирования-вычитания вместо 0,5 такта, которые мы имели без группировки.

Пример. Пусть множитель первоначально имеет вид

0.101111100110011101.

Действуя описанным методом, получим (в круглых скобках указаны цифры, переносимые из одной пары разрядов в другую)

(группировка раз-о 10 II И 10 01 10 01 II 01 рядов по парам) + (0)

+ (0) 10

+ (0)

+ (0) 10

+ (0)

+(1)

1 . .00

(преобразован- 1j

ный мнoжитeль)-f (1)

1 -Oi 00 ol 10 01 10 10 ОГ 01

Вместо 12 единиц в исходном представлении множителя получаем 9 положительных и отрицательных единиц в преобразованном множителе.