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

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.

Таблица 1-7

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

Имея т + k разрядов, самокорректирующийся код можно построить следующим образом.

Присвоим каждому из разрядов свой номер - от 1 до {т + k); запишем эти номера по двоичной системе. Поскольку 2* gt;-т + fe, каждый номер можно представить, очевидно, -разрядным двоичным числом. Для определенности будем полагать, что при записи номеров разрядов по двоичной системе использован позиционный способ изображения чисел с естественными весами разрядов; вообще это условие не является необходимым.

Предположим далее, что все т + k разрядов кода разбиты на контрольные группы (которые частично перекрываются), причем так, что единицы в двоичном представлении номера разряда указывают на его принадлежность к определенным контрольным группам. Например, разряд № 5 принадлежит к 1-й и 3-й контрольным группам, потому что в двоичном представлении его номера

(5)io = (...000101)2

1-й и 3-й разряды содержат единицы; разряд № 7 принадлежит 1-й, 2-й и 3-й контрольным группам, потому что в

двоичном представлении его номера (7)io = (...0111)2

содержатся единицы в 1-м, 2-м и 3-м разрядах и т. д.

Среди т + k разрядов кода при этом имеется k разрядов, каждый из которых принадлежит только к одной контрольной группе. Это разряды, номера которых являются целыми степенями двойки и потому в двоичном представлении содержат по одной единице: разряд № 1, принадлежащий только к 1-й контрольной группе (потому что его номер по двоичной системе имеет вид ...000001), разряд № 2, принадлежащий только ко 2-й контрольной группе (так как (2)io = (...000010)2), разряд 2--\ принадлежащий только к k-w контрольной группе. Эти k разрядов мы и будем считать контрольными. Остальные т разрядов, каждый из которых принадлежит по меньшей мере к двум контрольным группам, будут основньми разрядами числа (информационными разрядами).

При этом в каждой из k контрольных групп будем иметь по одному контрольному разряду. Например, в 1-ю контрольную группу входят все разряды, номера которых в двоичном представлении содержат единицу младшего разряда: 1-й, 3-й,5-й, 7-й и т. д.; из них контрольным является 1-й. Во 2-ю контрольную группу входят все разряды, номера которых в двоичном представлении содержат единицу 2-го разряда: 2-й, 3-й, 6-й, 7-й и т. д.; из них контрольным является 2-й.

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

Таким образом формируется код числа.

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

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

Пример. Пусть должны передаваться 4-раз рядные двоичные числа - от ОООО до ПИ (т. е. от О до 15 по десятичной системе). Для построения самокорректирующегося кода, рассчитанного на исправление одиночных ошибок, необходимо добавить 3 контрольных разряда (см. таблицу 1-7: при m = 4, А== 3). Введем общую нумерацию для разрядов кода - от № 1 до № 7. Согласно сказанному выше, в 1-ю контрольную группу включим 1-й, 3-й, 5-й, 7-й разряды, во вторую - 2-й, 3-й, 6-й и 7-й разряды, в третью - 4-й, 5-й, 6-й и 7-й разряды. Контрольными разрядами будем считать 1-й, 2-й и 4-й. Само число разместим в 3-м, 5-м, 6-м и 7-м разрядах. Установив цифры в контрольных разрядах так, чтобы количество единиц в каждой контрольной группе было четным, получим такие изображения чисел, как показано в таблице 1-8. (В столбце laquo;Д. К. raquo; приведены цифры 8-го разряда - разряда laquo;двойного контроля raquo;- для кода, который рассматривается позже. Пока на этот столбец не нужно обращать внимания.)

Предположим теперь для примера, что при передаче изображения числа 9 (т. е. кода 1001100) произошла ошибка в 5-м разряде, так что был принят код 1011100. Произведя в принятом коде контроль по четности внутри контрольных групп, мы обнаружили бы, что количество единиц нечетно в 1-й и 3-й контрольной группах и четно во 2-й контрольной группе. Это указывает, во-первых, на наличие ошибки и, во-вторых, означает, что номер ошибочно принятого разряда в двоичном представлении содержит единицу на первом и на третьем местах и нуль - на втором месте. Иначе говоря, номер разряда, в котором произошла ошибка, равен 5 (так как (101)2 = (5)io)- Заменив в 5-м разряде принятую цифру на противоположную, получим правильный код.

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