Коды «2 из 5» и «1 из 10» относятся к большой группе кодов «т из п», для которых характерен одинаковый вес, т. е. одинаковое число элементов в каждой ком-бинации кода. В табл. 3.6 представлены количества возможных комбинаций некоторых кодов из п». Число этих комбинаций определяется из соотношения

ml (п -т)!

(3.2)

3.3. ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК В КОДАХ

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

На рис. 3.1а представлен простой пример трехэлементного дво-ичйого-кода с максимальным числом 2 = 8 комбинаций и с пол-

<<1

ООО I

001 010

011 100 101 110

too т

ооф,---low

ООО 1 011 2 110 3

101 и

oooi-----

Рис. 3.1. а) Трехэлементный двоичный код с полным использованием всех комбинаций; б) с неполным использованием всех комбинаций ,

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

На рис. 3.1а представлена геометрическая модель кода. Отдельным вершинам куба соответствуют комбинации кода, причем таким образом, что соседние комбинации отличаются друг от друга только в одной позиции. Например, комбинации 001 и 011 отличаются второй цифрой, комбинации 011 и 111 - третьей и т. д. Расстояние между любыми комбинациями равно числу ребер между вершинами куба, соответствующими этим комбинациям. Например, между комбинациями 100 и 011 расстояние с?=3, между комбинациями 101и011с?=2 и т. п. С точки зрения обнаружения

ошибок, однако, решающим является минимальное расстояние (шаг) кода, которое в данном случае равно 1.

На рис. 3.16 приведен пример трехэлементного кода, в котором используются только четыре комбинации из максимального числа 2=8 комбинаций. В этом случае минимальное кодовое расстояние d=2 и ошибку в коде можно обнаружить. Рассмотрим, например, передачу информации, которой соответствует комбинация ООО. Если появится одна ошибка, например, во второй позиции, то вместо комбинации ООО будет принята комбинация 010, которой не соответствует ни одна из используемых комбинаций кода, т. е. ошибку можно легко обнаружить. То же самое справедливо для случая одиночной ошибки в позиции любой комбинации кода, т. е. в кодах с минимальным расстоянием d=2 можно надежно обнаружить одиночную ошибку. Из представленных выше это, например, коды «2 из 5», «1 из 10» и биквинарный код. Вообще можно сказать что в коде.с минимальным расстоянием d можно обнаружить ошибки d-1 или меньшей кратности.

Коды с минимальным расстоянием d=\, у которых нельзя определить ошибку, можно преобразовать путем добавления избыточной информации так, чтобы получилось хотя бы минимальное расстояние d=2, при котором можно надежно обнаружить одиночную ошибку.

На практике чаще всего используется принцип четности. Принцип ясен из табл. 3.7. К соответствующей комбинации добавляется один бит четности 1 или О так, чтобы результирующее количество единиц в комбинации было четное, или, наоборот, выбирается такое значение этого бита, 1 или О, чтобы результирующее количество единиц в комбинации было нечетное. Четность числа N в ф-ле (2.1) можно выразить следующим соотношением:

P{N) = PimoAm 0<Р{М)<т. (3.3)

Величина т обычно выбирается так, чтобы она была равна ооновэиию Z, что означает добавление одного бита к соответствующей комбинации. В двоичной системе 2=2 и Рг = 0 или 1, т. е. справедливо

P(iV) = 2Pimod2=p„ep„ ,e . . .архФро- (3.4)

Например, для =1101 четность равна РС ) = 1ф1фОф1 = 1.

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

Нечетность

Четность

0010

0111

о 1 о

1 1 1

оно оно

0111

о 1 1

0010 1

оно о

0111 1

§ 1

1 оно 1

1 оно &

1 0111 1

о 1 1

четность новая столбцов четность

исправление:

1110

ошибки . 1100 ИМ

0010

новая четность

1110

ttt 3

ошибки

быть обеспечено двукратной записью соответствующей комбин.я-ции, т. е. записью одной комбинации двумя запоминающими устройствами.

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

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