Кодирование с использованием циклических кодов

Если дана /с-значная входная комбинация т (х), то п-значное кодовое слово п (х) циклического кода с порождающим полиномом g (x) можно получить двумя способами.

По первому способу исходная /с-значная комбинация, выраженная в виде полинома.

степени (к — 1), умножается на порождающий полином g (x) степени (п — к):

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

Во втором способе используется процедура деления полиномов и вычисления остатков. В соответствии с правилами деления полиномов для каждой пары полиномов С (х) и g (x) (причем g (x) & 0) существует единственная пара полиномов q (x) — частное и р (х) — остаток такие, что.

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

где q (x) — частное от деления т (х) • х^п~^к на порождающий полином g (x), а р (х) — остаток от деления. Поскольку степень g (x) равна (п — к), то степень р (х) должна быть (п — к — 1) или меньше, а сам полином р (х) будет иметь вид.

С учетом правил арифметики в GF (2) выражение ш (х) • х^п~^к = = q (x) • g (x) ® р (х) можно переписать следующим образом:

откуда видно, что полином р (х) © х^п~^к • т (х) является кратным g (x) и имеет степень л-1 или меньшую. Следовательно, он соответствует свойствам кодовых комбинаций циклических кодов и представляет собой кодовое слово кодируемой информационной последовательности т (х).

Раскрыв последнее выражение, получим.

что соответствует кодовому слову

Таким образом, кодовое слово циклического кода состоит из неизменной информационной части (к разрядов) и проверочных символов (п — к разрядов). Проверочные символы являются коэффициентами полинома р (х), т. е. остатка от деления т (х)? х^п~^к на порождающий полином д (х).

С использованием кода, задаваемого порождающим полиномом g (x) = х³+х+1, закодируем произвольную последовательность, например т = (1001).

Последовательности т = (1001) соответствует полином Умножим т (х) нах^п~^{, с}:

Разделим т (х) ? х^п~^к на порождающий полином g (x):

Остаток от деления р (х) будет равен х² + х.

Следует иметь ввиду, что в GF (2)-арифметике операция вычитания совпадает с операцией сложения по модулю 2.

Таким образом, кодовый полином, соответствующий информационной последовательности т = (1001), будет иметь следующий вид:

а соответствующее кодовое слово и = (1 001 110).