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

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

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

[0] [0]. 101111100110011101 [0]

дало бы

[0] 1 . oioOOOTOlOTOlOOlOl [0],

независимо от того, откуда начинается преобразование - от старших или от младших разрядов.

Количество положительных и отрицательных единиц в преобразованном множителе здесь получилось равным восьми - таким же, как в примере на стр. 370. Однако в среднем этот метод, как мы сейчас увидим, более эффективен.

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

Для подсчета среднего количества тактов суммирования-вычитания обозначим через р/ вероятность того, что 1-й разряд преобразованного множителя содержит цифру -(-1 или -1; нумерация разрядов здесь начинается от младшего или от старшего из значащих разрядов - в зависимости от того, от какого разряда начинается преобразование множителя, т. е. от какого разряда начинается процесс вьшолнения умножения. Очевидно, что pi =V2, так как предыдущая цифра преобразованного множителя не существует (всегда laquo;О raquo;), а вероятность несовпадения двух соседних цифр непреобразованного множителя равна Уг. Поскольку вероятность того, что {i - 1)-я цифра преобразованного множителя есть О, равна 1- p/ i, то

Pi = -0 - Pi-i)-

В частности, Рг =У4. Рз =/е, Pt =Vie, - В пределе lim p,- = -l-(i lim р;),

г - raquo; ОО г - raquo; со

откуда

hm Pi = Vs-

г-CO

Таким образом, при достаточно большом количестве разрядов в множителе среднее количество суммирований или вычитаний, приходящееся на один разряд множителя, равно примерно Уз =0,333... Как мы увидим в 4.2.4, это - наилучший результат, который может быть получен при использовании логических методов ускорения умножения.

В осуществлении метод последовательных преобразований ненамного сложнее, чем метод группировки разрядов множителя, эффективность же его выше. Однако метод группировки разрядов, рассмотренный в п. 2 deg;, представляет определенный интерес как с теоретической точки зрения (см. 4.2.4), так и в качестве основы для некоторых аппаратных методов ускорения умножения (см. 4.3).

Как мы уже говорили, все логические методы ускорения умножения в двоичной системе фактически сводятся к преобразованию множителя в такую форму, когда для каждого разряда допустимыми цифрами являются -I, Он 4-1. Если следовать формально первому определению основания системы счисления, приведенному в 1.2.1 (стр. 15), то мы должныбыли бы утверждать, что множитель преобразуется из двоичной системы счисления в троичную, поскольку для каждого разряда теперь допустимы не два, а три различных символа. Здесь мы впервые сталкиваемся с ситуацией, когда общепринятое определение основания системы счисления оказывается неудобным и когда лучше пользоваться вторым определением раздела 1.2.1 (стр. 16). С точки зрения второго определения, поскольку цифры -I, О, -1-1 неравновероятны и поскольку общее количество инфэрмации, содержащееся в т разрядах преобразованного множителя, такое же,как и вт двоичных разрядах непреобразованного множителя, форма представления множителя остается по-прежнему двоичной.

Аналогичное положение возникает также при использовании логических методов ускорения умножения в системе счисления с основаниемп gt;2 (раздел 4.2.3), неко-торыхаппаратных методов ускорения умножения (раздел 4.3), использовании избыточных цифр частного для ускорения деления (раздел 5.1.3)и т. д.

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

Однако при п gt;. 2 имеется весьма простой метод, для которого нет аналога в чисто двоичной системе, позволяющий сократить среднее количество суммирований еще примерно вдвое. Им является метод перехода к симметричному диапазону цифр.

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

0,1,2,...,(п-1),

в такую форму, где используются: для нечетного п цифры

п - 1 п - Ъ . Р1 , , п - Ъ raquo; - 1

2 2

для четного п цифры

.Hni 1 о 4-1 -

п - 2 n - i 10 4-1 raquo;- 2

Для четного п иногда допускают и цифру - /г и цифру /а; если это так, то преобразование множителя становится неоднозначным.

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

(а) если данная цифра множителя больше или равна /а. то вычесть из нее величину п;