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

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

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

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

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

Для контроля передач чисел вместе с каждым числом передается и его остаток от деления на г. Дпя принятого числа заново вычисляется остаток от деления на г и сравнивается с принятым остатком.

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

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

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

Вообще достоверность контроля передач и арифметических операций тем выше, чем больше число г. Но чем больше г, тем сложнее и контрольные цепи. Поэтому в тех случаях, когда пользуются контролем по модулю, приходится выбирать некоторое компромиссное значение для величины г. Для десятичной системы, например, выбирают г равным 3, или 9, или 11, для двоичной - 3, или 5, или 7, или 15.

При выборе величины г желательно соблюдать следующее соотношение:

= -7-

где п - основание системы счисления, k,l - произвольные целые числа, по возможности невелико. Иначе говоря, = 1 (mod г). Например, для десятичной системы

3 = -iti (т. е. 10 = 1 (mod 3)),

9 = Stzl (т. е. 10 Ен 1 (mod 9)),

ll=l! li (т.е. 100= 1 (mod 11)).

Для двоичной системы о 22-1

(т. е. 4 = 1 (mod 3)), 5=? (т.е. 16= 1 (mod 5)), 7 = (т. е. 8 ЕЕ 1 (mod 7)),

15 = (т. е. 16 ЕЕ 1 (mod 15)),

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

илн на9 достаточно сложить между собой по модулю 3 {или соответственно 9) остатки от деления каждой десятичной цифры числа на 3 (на 9); при этом остаток от деления десятичной цифры на 9 равен, естественно, ей самой. Остаток от деления любого десятичного числа на 11 находится путем разбиения этого числа на пары разрядов {k - 2), вычисления остатков от деления на 11 полученных таким образом двузначных чисел и суммирования затем этих остатков по модулю И. (Например, для числа 7 839 756 840

40 = 7 (mod 11), 68 = 2 (mod 11), 75 = 9 (mod 11),

39 = 6 (mod 11), - .

78=1 (mod И), 7-f 2-f 9 + 6-Ь 1 = 25 = 3 (mod 11).

Остаток от деления 7 839 756 840 на 11 равен 3.)

Аналогичным образом остаток от деления любого двоичного числа на 3 получится разбивкой этого числа на пары двоичных разрядов и суммированием полученных двузначных чисел по модулю 3 (остаток отделения двузначного двоичного числа на 3 равен ему самому); остаток от деления двоичного числа на 7 (на 15) получится разбиением этого числа на тройки (на четверки) двоичных разрядов и суммированием полученных трехзначных (четырехзначных) двоичных чисел по модулю 7 (соответственно 15). Для вычисления остатка от деления двоичного числа на 5, нужно распределить разряды исходного числа на четверки, найти для каждого из полученных таким образом четырехзначных двоичных чисел остаток от деления на 5 и затем сложить эти остатки по модулю 5.

Иначе эти правила формулируются следующим образом:

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

2, 1, 2, 1, 2, 1;