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

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

с методом последовательного преобразования множителя, изложенным в 4.2.2 *).

В схему преобразования по-прежнему будут поступать каждый раз три разряда непреобразованного множителя: очередной разряд, соседний справа (младший) и соседний слева (старший); предыдущий разряд преобразованного множителя, который использовался в правиле преобразования, приведенном на стр. 371, здесь нам не потребуется. Правило преобразования по существу останется точно таким же, как прежде, однако мы дополним его одной важной деталью: если очередная цифра преобразованного множителя есть -f-1 или - 1 или если очередная цифра непреобразованного множителя совпадает с соседней слева его цифрой, то сдвиг вправо в регистрах/4 и В будем производить сразу на два разряда. В обоих этих случаях следующая цифра преобразованного множителя должна получиться нулем; следовательно, ни суммирования, ни вычитания в следующем цикле умножения все равно не было бы, и этот цикл умножения можно просто опустить. Это мы и делаем, производя сдвиг множителя и суммы частичных произведений на 2 разряда. Зато когда после очередного сдвига (на 1 или на 2 разряда) в схему преобразования поступает очередная тройка разрядов множителя, то уже заранее известно, что предыдущая цифра преобразованного множителя была нулем; поэтому, собственно, и можно не запоминать предыдущую цифру преобразованного множителя и не принимать ее во внимание при преобразовании очередного разряда.

С учетом указанных дополнений правило умножения можно свести в таблицу 4-2.

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

*) Описываемый ниже метод в литературе, по-видимому, не был описан. Преимущества его перед другими способами использования дополнительных цепей сдвига весьма значительны - ср. со способом, опи-санньм в предыдущей работе автора ( laquo;Арифметические устройства электронных цифровых машин raquo;, Физматгиз, 1958, стр. 128-130).

Таблица 4-2

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

множителя

множителя находится цифра несуществующего разряда) вероятность каждой из комбинаций ООО, 010, 100 и 110 равна вероятности остальных комбинаций равны нулю. Затем от цикла к циклу вероятности постепенно изменяются. Обозначим через Ро предел, к которому стремится вероятность комбинации ООО, через р - предел вероятности комбинации 001 и т. д.

Теперь обратим внимание на то, что после комбинаций ООО, 001 и 010 в результате очередного сдвига на краю регистра с равными вероятностями могут получаться комбинации ООО, 010, 100 и ПО; после комбинации 011 с равными вероятностями получаются либо 101, либо 001; после комбинации 100 с равными вероятностями получаются либо 010, либо ПО; после комбинаций 101, ПО и 111 с равными вероятностями появляются комбинации 001, либо ОН, либо 101, либо 111. Поэтому

Ро =-(P0+Pl+P2 gt;,

Р2 = -(РО + Pi +.Р2) + уР4, Рз =--(Р5+Рб + Р7),

Pi = J{P0 + Pl + Р2),

P5 = у Рз + -(Рб + Рб + Pv),

Рб= (Ро + Pi + Рг) + Y Р*

Р7={Р5 + Р6 + Р,).

Кроме ТОГО, конечно,

Ро +РХ +Р2~+/8 +Р4 +Р5 +Рб +Р7 = 1-

Решая совместно эти уравнения, найдем

Ро = Рз = Р4 = Рт = Vio,

Pi = Рг = Рв = Рб = /ао-

Теперь можно найти, на сколько разрядов в среднем производится сдвиг. Поскольку сдвиг на 1 разряд выполняется в комбинациях ОП и 100, суммарная вероятность которых равна рд -Ь Р4 = /в, а сдвиг на 2 разряда - во всех остальных комбинациях с вероятностью то в сред-

1 4 С1

нем сдвиг выполняется на -1 -j--2 = ~ разряда. Таким

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

Далее можно заметить, что в некотором цикле умножения суммирование или вычитание выполняется только в комбинациях 001,010, 101 и ПО, суммарная вероятность которых равна Pi -f Рг -Ь Р5 + Ре = Так как на каждый разряд множителя приходится в среднем Ve цикла умножения, то среднее количество суммирований-вычитаний,

3 5 1

приходящееся на 1 разряд множителя, равно г - п = й- Как

О У о

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

Если по-прежнему считать, что такт суммирования Тд вдвое длиннее, чем такт сдвига Тс, то среднее время