Помехоустойчивое кодирование

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

 

 

1. Общие принципы использования избыточности.

2. Связь корректирующей способности кода с кодовым расстоянием..

3. Блочные коды.

4. Введение в циклические коды.

5. Выбор образующего многочлена по заданному объему кода и заданной корректирующей способности.

 

 

Блочные коды.

 

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

Исходя из неравенства 2 ^k -1≥ Q (нулевая комбинация часто не используется, так как не меняет состояния канала связи), определяем число информационных разрядов k, необходимое для передачи заданного числа команд обычным двоичным кодом.

Каждой из 2 ^k - 1 ненулевых комбинаций k -разрядного безызбыточного кода нам необходимо поставить в соответствие комбинацию из n символов. Значения символов в n -k проверочных разрядах такой комбинации устанавливаются в результате суммирования по модулю 2 значений символов в определенных информационных разрядах.

Поскольку множество 2 ^k комбинаций информационных символов (включая нулевую) образует подгруппу группы всех n-разрядных комбинаций, то и множество 2 ^k n -разрядных комбинаций, полученных по указанному правилу, тоже является подгруппой группы n -разрядных кодовых комбинаций. Это множество разрешенных кодовых комбинаций и будет групповым кодом.

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

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

Ясно, что из общего числа 2 ⁿ -1 возможных ошибок групповой код может исправить всего 2 ^{n - k} -1 разновидностей ошибок по числу смежных классов.

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

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

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

 

ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ

 

 

1. Общие принципы использования избыточности.

2. Связь корректирующей способности кода с кодовым расстоянием..

3. Блочные коды.

4. Введение в циклические коды.

5. Выбор образующего многочлена по заданному объему кода и заданной корректирующей способности.