Определение необходимого количества избыточных символов

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

Разложим группу 2n всех n-разрядных комбинаций на смежные классы по подгруппе 2k разрешенных n-разрядных кодовых комбинаций, проверочные разряды в которых еще не заполнены. Помимо самой подгруппы кода в разложении насчитывается 2(nk) – 1 смежных классов. Элементы каждого класса представляют собой суммы по модулю 2 комбинаций кода и образующих элементов данного класса. Если за образующие элементы каждого класса принять те наиболее вероятные для заданного канала связи вектора ошибок, которые должны быть исправлены, то в каждом смежном классе сгруппируются кодовые комбинации, получающиеся в результате воздействия на все разрешенные комбинации определенного вектора ошибки. Для исправления любой полученной на выходе канала связи кодовой комбинации теперь достаточно определить, к какому классу смежности она относится. Складывая ее затем (по модулю 2) с образующим элементом этого смежного класса, получаем истинную комбинацию кода.

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

Каждый символ опознавателя определяют в результате проверки на приемной стороне справедливости одного из равенств, которые мы составим для определения значений проверочных символов при кодировании. Ранее указывалось, что в двоичном линейном коде значения проверочных символов подбирают так, чтобы сумма по модулю 2 всех символов (включая проверочный), входящих в каждое из равенств, равнялась нулю. В таком случае число единиц среди этих символов четное. Поэтому операции определения символов опознавателя называют проверками на четность. При отсутствии ошибок в результате всех проверок на четность образуется опознаватель, состоящий из одних нулей. http://peredacha-informacii.ru/ Если проверочное равенство не удовлетворяется, то в соответствующем разряде опознавателя появляется единица. Исправление ошибок возможно лишь при наличии взаимно однозначного соответствия между множеством опознавателей и множеством смежных классов, а следовательно, и множеством подлежащих исправлению векторов ошибок. Таким образом, количество подлежащих исправлению ошибок является определяющим для выбора числа избыточных символов nk. Их должно быть достаточно для того, чтобы обеспечить необходимое число опознавателей.

Если, например, необходимо исправить все одиночные независимые ошибки, то исправлению подлежат n ошибок:

Определение необходимого количества избыточных символов

Тип ошибки можно обозначить так:

1. Пачка не более 2-х символов:

  • ...010.. – одиночная ошибка;
  • ...0110... – двойная смежная ошибка.

2. Пачка не более 3-х символов:

  • ...010... – одиночная ошибка;
  • ...0110... – двойная независимая ошибка;
  • ...01110... – тройная смежная ошибка или пачка из 3-х символов;
  • ...01010... – двойная ошибка в пачке из 3-х символов.

Различных ненулевых опознавателей для исправления одиночных ошибок должно быть не менее n. Необходимое число проверочных разрядов, следовательно, должно определяться из соотношения:

2nk – 1 ≥ n.

Если необходимо исправить не только все единичные, но и все двойные независимые ошибки, соответствующее неравенство принимает вид:

2nk – 1 ≥ C1n + C2n.

Для исправления двойных смежных ошибок и пачек ошибок (не более 3-х символов) неравенство имеет вид:

Определение необходимого количества избыточных символов

В общем случае для исправления всех независимых ошибок кратности до s включительно получаем:

2nk – 1 ≥ C1n + C2n + ... + Csn.

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