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

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

различных вариантов построения кода laquo;два из пяти raquo;. Столько же возможно кодов laquo;три из пяти raquo;.

Коды laquo;два из пяти raquo; и laquo;три из пяти raquo; дают также возможность обнаруживать наиболее вероятные ошибки при передаче чисел (о чем говорится в разделе 1.7).

Очень интересными свойствами обладает код, приведенный в столбце laquo;в raquo; таблицы 1-6. Если двоичные цифры обозначить соответственно w, х, у, z, как сделано в таблице, то для любой десятичной цифры комбинация z, w, х, у дает младшую цифру произведения на 3, комбинация х, у, г, W - младшую цифру произведения на 7, комбинация у, г, W, X - младшую цифру произведения на 9. Таким образом, младший разряд произведения десятичной цифры на 3, на 7 или на 9 может быть получен круговой перестановкой двоичных цифр.

Возьмем, например, десятичную цифру 2; ее изображение имеет вид ООН; выполнив перестановку w, х, у, z~z, W, X, у, получим 1001, что является изображением цифры 6 (2 X 3 = 6); перестановка w, х, у, z

X, у, z,wp,aeT комбинацию 0110, представляющую цифру 4 (младший разряд произведения 2X7== 14); перестановка W, x,y,z- у, Z, W, X дает 1100, т. е. цифру 8 (младший разряд произведения 2 X 9 = 18).

Приведенный код заимствован из книги laquo;Синтез электронных вычислительных и управляющих схем raquo; (пе-рев. с англ. под ред. В. И. Шестакова, ИЛ, 1953). Не видно, однако, каким образом он был найден.

В столбцах laquo;п gt;и laquo;д raquo;таблицы 1-6 приведены еще два двоичных кода для десятичных цифр. Эти коды мы рассмотрим, в разделах 1.7.5 и 1.8.1; здесь же никаких пояснений к ним-приводить не будем. Читатель может сделать попытку самостоятельно догадаться, какими полезными свойствами обладают эти коды.

Построение кода laquo;5, 4, 2, 1 raquo;, приведенного в столбце laquo;е raquo; таблицы 1-6, очевидно. Интересно, что десятичные числа, записанные в этом коде, можно рассматривать как двоично-пятеричные; при этом три младших двоичных разряда каждой десятичной тетрады изображали бы один пятеричный разряд, старшая двоичная цифра соответствовала бы двоичному разряду. Код этот имеет некоторые достоинства при выполнении арифметических операций.

1.7. Помехозащищенные коды

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

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

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

1.7.1. Коды Хемминга. Коды Хемминга - наиболее известные и, вероятно, первые*)из самоконтролирующихся и самокорректирующихся кодов. Построены они применительно к двоичной системе счисления.

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

*) См. Hamming R. W. Error correcting and error detecting codes. Bell Syst. Techn. J., 1950, 2.

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

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

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

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

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

2* gt; А + m + 1

k gt; loga ik + m+ 1), где т - количество основных двоичных разрядов числа. Минимальные значения k при заданных значениях т, пай-