Глава 3. ИЗБЫТОЧНЫЕ КОДЫ И ПРИНЦИПЫ ИСПОЛЬЗОВАНИЯ ИЗБЫТОЧНОСТИ

3.1. Общие положения

Одним из наиболее важных требований, предъявляемых к системам передачи информации, является обеспечение высокой достоверности принимаемых сообщений.

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

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

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

Пример. Для передачи информации используются следующие кодовые комбинации, различающиеся не менее чем двумя разрядами: Пусть при передаче комбинации (например, произошла одиночная ошибка, в результате чего исказился первый разряд и принята комбинация 1011. Эта комбинация является запрещенной, что свидетельствует о наличии в ней ошибки. При выборе разрешенных комбинаций, отличающихся четырьмя разрядами 1100 и 0011, легко убедиться, что в этом случае обнаруживаются одно-, дву- и трехкратные ошибки и не обнаруживается лишь четырехкратная ошибка.

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

Следовательно, не все искажения могут быть обнаружены. Доля обнаруживаемых ошибочных комбинаций

Для использования данного кода в качестве исправляющего множество запрещенных кодовых комбинаций разбивается на непересекающихся подмножеств

Каждое из подмножеств ставится в соответствие одной из разрешенных комбинаций. Если принятая запрещенная, комбинация принадлежит подмножеству считается, что передана комбинация (рис. 14).

Рис. 14. Возможные трансформации разрешенных кодовых комбинаций.

Ошибка будет исправлена в тех случаях, когда полученная комбинация действительно образовалась из комбинации Таким образом ошибка исправляется в случаях. Доля исправляемых ошибочных комбинаций

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

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

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

При кодировании к каждой последовательности из информационных символов добавляется один символ (0 или 1) такой, чтобы

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

Большинство разработанных кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек (пакетов) ошибок.