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

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.7.5. Защита двоичных кодов десятичных цифр. Если десятичная цифра кодируется при помощи нескольких двоичных цифр, то для защиты двоичных кодов от помех можно применить обычные методы, изложенные выше. Например, при использовании 4-разрядного двоичного кода для представления десятичных цифр можно добавить 5-й - контрольный - разряд, осуществить контроль по четности и таким образом обнаруживать одиночные ошибки.

Однако для этого случая известны и другие, более выгодные методы построения помехозапщщенных кодов.

В разделе 1.6 упоминался код едва из пяти raquo; (табл. 1-6 на стр. 96, столбед laquo;б raquo;). Легко видеть, что этот код, содержащий также 5 двоичных разрядов на одну десятич- ную цифру, позволяет обнаруживать, кроме всех одиночных ошибок, 40% двойных и 4-кратных ошибок, все 3-кратные и 5-кратные ошибки. Признаком ошибки при этом будет являться изменение количества единиц в группе из пяти двоичных разрядов. О других полезных свойствах этого кода сказано в разделе 1.6.3.

В разделе 1.6.2 рассмотрен другой 5-разрядный код десятичных цифр, позволяющий обнаруживать одиночные ошибки - код laquo;За + 2 raquo;. Возможность обнаружения одиночных ошибок вытекает из того, что расстояние между двумя ближайшими из используемых комбинаций равно двум единицам, т. е. что любые две допустимые комбинации различаются не менее чем в двух разрядах. Последнее легко проверить непосредственным сравнением изображений десятичных цифр в этом коде (см. стр. 94). Наряду с этим код laquo;За + 2 raquo; позволяет удобно выполнять арифметические операции над десятичными числами, о чем говорилось в свое время.

Чтобы имелась возможность не только обнаруживать, но и исправлять одиночные ошибки либо обнаруживать двойные ошибки, необходимо обеспечить расстояние между двумя ближайшими комбинациями минимум в три единицы. Как видно из таблицы 1-7 (стр. 101), для этого на. каждые 4 двоичных разряда информации нужно иметь по меньшей мере 3 контрольных разряда, т. е. изображать каждую десятичную цифру с помощью 7 двоичных разрядов. Можно, однако, показать, что среди 7-разрядных

двоичных кодов десятичных цифр, обеспечивающих минимальное расстояние в 3 единицы, нет таких кодов, которые в отношении выполнения арифметических операций были бы аналогичны коду laquo;За + 2 raquo;. Зато существует один 8-разрядный код такого типа - код laquo;27а + 6 raquo;*).

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

- максимальная вероятность обнаружения одиночных ошибок;

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

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

Если мы пользуемся, например, кодом laquo;8, 4, 2, 1 raquo;, то все эти показатели оказываются очень плохими. Вероятность обнаружения одиночных ошибок оказывается равной всего 25%. Скажем, при передаче десятичной цифры laquo;О raquo; (ОООО) ни одна из четырех возможных одиночных ошибок не обнаруживается (вместо ОООО принимаются комбинации 1000, 0100, 0010 или 0001, каждая из которых является допустимой); при передаче кода laquo;9 raquo; (1001) одиночные ошибки в первом или четвертом разрядах не обнаруживаются (потому что при этом получаются допустимые комбинации 0001 или 1000), а одиночные ошибки во втором или третьем разрядах можно обнаружить (так как комбинации 1101 и 1011 недопустимы) и т. д. Наибольшее отклонение в значении десятичной цифры при необнаруживаемых одиночных ошибках может быть равно восьми (например, если при передаче цифры laquo;О raquo; [ОООО] произойдет ошибка в старшем двоичном разряде, то будет принята

*) Diamond J. М., Checking Codes for Digital Computers. Proc. IRE, 1955, 43, -N 4 (стр. 487-488).

**) К a u t z W. H., Optimized Data Encoding for Digital Computers, Conv. Rec. IRE, 1954, Part. 4 - Electronic Computer and Information Theory (стр. 47-57).

8 Щ

ODoMz-

----1

,6 oil

---1-

------\----

ItlDl

00Ц,/ mo]

цифра laquo;8 raquo; [1000]). Среднее значение таких отклонений, как нетрудно подсчитать, равно трем.

Можно показать, что наилучшим с точки зрения указанных критериев является код, приведенный в столбце laquo;г raquo; таблицы 1-6 (см. стр. 96). На рис. 1-7 приведена графическая интерпретация этого кода, причем условная развертка 4-мерного куба выполнена в соответствии с рис.

1-4 на стр. 109. Из рисун-/00/j 10/1 1010У ка видно, что допустимые комбинации выбраны по возможности так, чтобы расстояние между ними было не меньше двух единиц (если бы использовалось не 10, а 8 комбинаций, то можно было бы не задействовать комбинации 0111 и 1101, соответствую шие цифрам laquo;3 raquo; и laquo;6 raquo;, и тогда это условие выполнялось бы для всех случаев). В некоторых местах, однако, приходится все-таки использовать комбинации, находящиеся друг от друга на расстоянии в одну единицу; следовательно, не все одиночные ошибки будут обнаруживаться. Но в этих случаях близким комбинациям поставлены в соответствие близкие по значению десятичные цифры.

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

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

Рис. 1-7. Графическое представление оптимального (с точки зрения защиты от помех) 4-разрядного двоичного кода десятичных цифр.