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

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.4. Более сложные коды - даже такие, как коды Хемминга для исправления одиночных ошибок - почти никогда не применяются и, как считают, особого эффекта не могут дать.

1.7.4. Ортотронный контроль*). Пусть имеем т-разряд-ное двоичное число или, может быть, несколько чисел, содержащих всего т двоичных разрядов. Разобьем все имеющиеся разряды на s равных групп, по г двоичных разрядов в каждой группе {т = rs). Наименьшая избыточность кода получится при г s lAm. Запишем далее число (набор чисел) в виде прямоугольной таблицы из s строк и г столбцов - в соответствии с разбивкой имею-1Щ1Хся разрядов на группы. Добавим по одному контрольному разряду к каждой из s строк и к каждому из г столбцов. Цифры контрольных разрядов выбираются так, чтобы количество единиц в каждой строке и в каждом столбце было, скажем, четным.

Если при передаче числа исказится цифра в каком-нибудь разряде, то это будет обнаружено контролем по

*) По поводу происхождения термина laquo;ортотронный raquo; (англ. - orthotronic) в литературе имеются противоречивые сведения. Скорее всего это слово означает контроль по взаимно перпендикулярным (ортогональным) направлениям.

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

Пример. Пусть имеем 30-разрядные двоичные числа, которые разбиваются на 6 групп, по 5 разрядов в каждой группе (т = 30, s = 6, г = 5). Количество контрольных разрядов при этом равно 5 + /=П. Например, двоичное число

П101 10101 10110 00011 10000 01110

должно быть записано в виде

11101 10101

00011 10000 01110

(контрольные разряды строк)

О 1 1

(контроль- 00011 ные разряды столбцов)

Если при передаче кода произойдет ошибка, например, в двенадцатом слева разряде (вместо laquo;О raquo; будет принято laquo;1 raquo;), то принятый код будет иметь вид

00011

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

Избыточность рассматриваемого кода больше, чем избыточность кода Хемминга, позволяющего исправлять одиночные ошибки: для кода Хемминга при т разрядах информации количество k контрольных разрядов должно быть не меньше logg (сл. 1.7.1), для рассматривае-

мого кода - не меньше, чем 2Ytn. Зато и операции кодирования и исправления ошибок здесь проще.

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

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

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