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

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-8

Изображение чисел or О до 15 в самокоррекгирующемся коде, рассчитанном на исправление одиночных ошибок

ла. Когда в принятом коде производится контроль по четности внутри контрольных групп, случай двойной ошибки ничем внешне не отличается от случая одиночной ошибки; при этом вырабатывается некий номер разряда, в котором якобы имеется ошибка, но не имеющий на самом деле никакого отношения к тем разрядам, где ошибка действительно произошла *). Исправление кода по общему правилу не только не улучшило бы, но даже ухудшило бы дело.

.Если бы, скажем, в рассмотренном выше примере при передаче кода числа 9 (т. е. кода 1001100) ошибка произо-

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

шла не только в5-м, но и в 7-м разряде, то был бы принят код 0011100. Количество единиц в 1-й контрольной группе четно, во 2-й нечетно, в 3-й четно. Внешне дело выглядит так, как будто произошла ошибка при передаче 2-го разряда (так как (010)2 = (2)io). Однако исправление 2-го разряда дало бы код 0011110 - еще более далекий от правильного, чем принятый.

Можно построить и такой код, который обнаруживал бы двойные ошибки и исправлял одиночные. Для этого к самокорректирующемуся коду, рассчитанному на исправление одиночных ошибок, нужно приписать еще один контрольный разряд (разряд двойного контроля). Полноеколи-чество разрядов кода при этом будет равно т + k +1, те ffl - количество разрядов информации, k определяется по таблице 1-7. Цифра в разряде двойного контроля устанавливается такой, чтобы общее количество единиц во всех т + k + I разрядах кода было четным. Этот разряд не включается в общую нумерацию разрядов и не входит ни в одну контрольную группу.

После приема кода контроль по четности будет производиться раздельно по контрольньш группам и для всего кода в целом. При этом могут быть следующие случаи:

(1) в принятом коде в целом и по всем контрольным группам количество единиц четно;

(2) в принятом коде в целом количество единиц нечетно, но во всех контрольных группах количество единиц четно;

(3) Б принятом кодев целом и-в некоторых из контрольных групп количество единиц нечетно;

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

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

Пример такого кода приведен в таблице 1-8, где колонка laquo;Д. К. raquo; дает цифры разряда двойного контроля.

Увеличивая дальше количество контрольных разрядов, можно было бы построить коды, рассчитанные на исправление двойных ошибок, на исправление двойных ошибок и обнаружение тройных и т. д. Однако методы построения этих кодов не вполне разработаны.

1.7.2. Геометрическая интерпретация. Иногда полезно геометрическое представление кодов Хемминга и других помехозаищщенных кодов.

Каждый разряд п-разрядного двоичного числа можно поставить в соответствие с одной из координат в п-мерном

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

На рис. 1-1 показан такой куб в 3-мерном пространстве. Считается, что ось z соответствует первому справа разряду кода, ось г/ -второму разряду, ось X-третьему. Восемь вершин куба соответствуют восьми различным комбинациям цифр, возможным в трех двоичных разрядах.

Расстоянием между двумя верпшнами называется минимальное количество ребер, которые нужно пройти, чтобы попасть из одной вершины в другую. Например, на рис. 1-1 расстояние от вершины ООО до вершины 001 равно одной единице, расстояние от вершины ООО до вершины 011 равно двум единицам, а до вершины 111 -трем. Расстояние между двумя комбинациями цифр равно фактически количеству разрядов, в которых эти комбинации различны.

Если при передаче кодов допускаются все 2 комбинаций, которые могут быть в п двоичных разрядах, то мини-

Рис. 1-1. Единичный 3-мерный куб, соответствующий 3-раз-рядшыу двоичному коду.