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

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 разрядах. При этом допустимы всего 2 - комбинаций: в основных п - 1 разрядах возможны любые комбинации, а цифра контрольного разряда по какому-либо правилу однозначно связана с цифрами остальных разрядов. Из 2 вершин п-мерного куба задействована только половина (2 -i), остальным не соответствуют какие-нибудь используемые комбинации. Есть надежда так расставить используемые вершины, чтобы минимальное расстояние между ними было равно двум единицам. Одиночная ошибка при передаче кода сдвинет соответствующую комбинацию на одну единицу; таким образом мы попадем в вершину куба, которая не соответствует никакой из допустимых комбинаций. Это и будет являться признаком одиночной ошибки.

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

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

Расстояние между двумя ближайшими допустимыми комбинациями теперь равно двум единицам. Следовательно, одиночная ошибка, которая сдвигает комбинацию на расстояние 1, может быть обнаружена. Однако при этом ее

нельзя исправить, потому что каждая неотмеченная вершина куба отстоит на равные расстояния от трех отмеченных вершин. Если, скажем, принята комбинация 111, то нельзя выяснить, почему это произошло: вследствие ошибки в 1-м справа разряде при передаче комбинации 110,

(OOf)

ООО)

(ГШ)

(OOf) (Off:

Рис, 1-2. Расположыие допустимых комОинацнй: а) в коде, рассчитанном ка обнаружение одиночных ошибок; б) в коде, рассчитанном па исправление одиночных ошибок или на обнаружение одиночных и двойных ошибок.

или вследствие ошибки во 2-м разряде при передаче комбинации 101, или вследствие ошибки в 3-м разряде при передаче комбинации 011; нет, следовательно, способа исправить допущенную ошибку.

Чтобы одиночные сшибки можно было не только обнаруживать, но и исправлять, расстояние между допустимыми комбинациями должно быть не меньше трех единиц. Такой код для п - Ъ иллюстрируется рис. 1-2, б. В случае одиночной ошибки получается комбинация, соответствующая неотмеченной вершине, но она находится laquo;ближе raquo; к одной из отмеченных вершин, чем к другим; последнее обстоятельство и позволяет исправлять одиночные ошибки.

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

Продолжив это рассуждение дальше, можно утверждать, что для исправления одиночных и обнаружения двой-

ных ошибок или для обнаружения одиночных, двойных и тройных ошибок необходим код с минимальным расстоянием между допустимыми комбинациями в 4 единицы, для исправления двойных ошибок (или для обнаружения всех ошибок вплоть до четырехкратных) минимальное расстояние должно быть 5 единиц и т. д. К этим критериям мы вернемся еще в 1.7.3.

Приведенная геометрическая интерпретация дает возможность получить наглядное пространственное изображение кода только в очень ограниченных случаях - для п = 2 и п = 3. Впрочем, вместо п-мерного куба для графического изображения кода можно воспользоваться сеткой, имеющей 2 узлов, каждый из которых соединен с п другими узлами. Пример такой сетки для п = 3 показан на рис. 1-3. Для случаев п = 4 и п = 5 сетку можно

Рис. 1-3. Сетка для графического изображения 3-разрядного кода.

1100\

010$.

1001 т/ юю

Рис. 1-4. Условная развертка и-мерного куба (и=4 и и=5).

изобразить в виде условной развертки п-мерного куба, как показано на рис. 1-4. Пунктирными линиями на этом рисунке показаны места, где должна laquo;сшиваться raquo; развертка;