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

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, мог бы дать лучший результат, чем данный способ, а в среднем они одинаковы.

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

3 deg;. Наиболее эффективным из логических методов ускорения является последовательное преобразование цифр множителя *).

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

Правило преобразования множителя сформулируем одинаково как для умножения от младших разрядов, так и для умножения от старших разрядов:

- если данная цифра непреобразован-J ного множителя не совпадает с соседней справа

его цифрой, соседняя слева цифра есть О и предыдущая цифра преобразованного множителя есть О, то данный разряд преобразованного множителя должен содержать +1;

*) В литературе этот метод известен также под названием усовершенствованного метода Booth и Booth. Впервые он опубликован в работе Lehman М.,- Short-cut Multiplication and Division in Automatic Digital Computers, sept. 1957, v. EC-6, No 3, справедливее было бы, вероятно, называть его методом Lehman. В настоящей книге метод обобщается на случай умножения от старших разрядов. В несколько иной формулировке этот метод имеется также в работе А. Т. Кухарчу-каи Н. М. Проценко (см. сноску на стр. 369).

- если данная цифра непреобразованного множителя не совпадает с соседней справа его цифрой, соседняя слева цифра есть 1 и предыдущая цифра преобразованного множителя есть О, то данный разряд преобразованного множителя должен содержать -1;

- если данная цифра непреобразованно-г о множителя совпадает с соседней справа его цифрой или если предыдущая цифра преобразованного множителя не является нулем, то данный разряд в преобразованном множителе есть 0.

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

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

Действительно. Предположим, что умножение ведется от младших разрядов. Справа от младшего разряда множителя всегда предполагается нуль. Если далее младшие разряды множителя тоже содержат серию нулей, то в соответствующих разрядах преобразованного множителя будут получаться нули:

исходный множитель ... 00 ... О [0]

преобразованный множитель ... 00... О ,

потому что каждый раз цифра данного разряда совпадает с цифрой соседнего справа разряда.

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

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

исходный множитель ... 0100 .. .

преобразованный множитель ... 0100 .. .

Во втором случае:

исходный множитель ... 1100 .. .

преобразованный множитель .. . OlOO . .,

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

исходный множитель ...0011 ... 11011 ... 110 ,..

преобразованный множитель ... 0100... 00100.. . ОТО ...

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

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

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