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

Если дана /с-значная входная комбинация т(х), то п-значное кодовое слово п(х) циклического кода с порождающим полиномом 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) = х3+х+1, закодируем произвольную последовательность, например т = (1001).

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

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

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

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

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >