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

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 видно, например, что 7-разрядный код Хемминга с исправлением одиночных ошибок может содержать 4 разряда информации, а его избыточность равна 3 двоичньш разрядам (т = 4, k = 3, т + k = 7)..

Именно такой величина избыточности должна была бы получиться, если бы мы предположили, что вероятность приема сообщения без ошибок равна р*) = Vs. вероятность приема сообщения с одиночной ошибкой в каком-либо t-M разряде (i = 1, 2,..., 7) тоже равна р() = Vs. а случаи приема сообщений с ошибками более чем в одном разряде невероятны. Согласно сказанному выше потеря информации при этом была бы равна

Ну (х) = - S Р log2 Р laquo; = - logs Vs.

Т. е. 3 двоичным разрядам. Код Хемминга идеально соответствует такому предположению: он содержит ровно 3 избыточных разряда и с полной достоверностью исправляет все одиночные ошибки. Однако само предположение не выдерживает критики. Если случаи приема сообщения без ошибок и приема сообщения с одиночной ошибкой в каком-либо t-M разряде равновероятны, то это означает, что вообще вероятность ошибки при приеме каждого из двоичных разрядов р должна быть весьма велика*): из равенства (1 - рУ = (1 - рУр вытекает р = Va. Но тогда, конечно, нельзя пренебрегать возможностью одновременных ошибок в двух, трех и более разрядах. При р = V2 их суммарная вероятность равна Vie-

Коды Хемминга, исправляющие одиночные ошибки, в действительности применяются, конечно, для намного меньших уровней помех - когда двойными, тройными ИТ. д. ошибками можно на самом деле пренебречь. Но тогда и избыточность кода может быть много меньшей. Мы сильно завысили ее потому, что при построении кода несоразмерно преувеличили роль одиночных ошибок. В то же время, допустив такую большую избыточность, мы не получили никаких возможностей для исправления двойных, тройных и т. д. ошибок.

*) Ошибки в различных разрядах считаются независимыми.

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

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

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

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

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

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

В вьмислительной машине канал связи как таковой отсутствует. Те laquo;помехи raquo;, с которыми нам приходится иметь дело, представляют собой в сущности сбои в работе (неправильные срабатывания) цифровых элементов, элементов запоминания, элементов формирования сигналов и логических элементов машины.

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

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

Таким образом, оценка тех или иных кодов с точки зрения вычислительной техники непременно должна включать оценку слоотости операций кодирования и декодирования. Задача здесь состоит не в том, чтобы получить код с минимальной избыточностью, а в том, чтобы минимизировать общий объем оборудования (включая и оборудование кодирования и декодирования чисел) или, возможно.