Коды, исправляющие ошибки
Содержание | Назад | Вперед | Лабораторные | О курсе

  Содержание



 

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

Из полиномиального задания циклических кодов следуют способы кодирования и декодирования при использовании таких кодов.

Кодирование. Пусть циклический (n, n-k)-код порождается многочленом g(x), который является делителем многочлена xn + 1, и степень g(x) равна k < n. Любое информационное слово a есть двоичный вектор длины n-k. Чтобы построить соответствующий кодовый вектор, достаточно представить вектор a = (an-k-1, an- k-2, ...., a0) в виде многочлена an-k-1xn-k-1+an- k-2xn- k-2+...+a0 и умножить данный многочлен на g(x). Мы получим an-k-1xn-k-1g(x)+an-k-2xn-k-2g(x)+...+a0g(x), т. е. получим двоичный вектор, который является линейной комбинацией строк порождающей матрицы с коэффициентами an-k-1, an- k-2, ...., a0.

Пример: Рассмотрим (7,4)-код, порожденный многочленом g(x) = x3 + x2 +1. Пусть информационным сообщением является вектор a = 1011, которому соответствует многочлен a(x) = x3 + x +1. Для нахождения соответствующего кодового слова перемножаем многочлены g(x) и a(x), и получаем кодовый многочлен g(xa(x) =  x6 + x5 + x4 + + x2 + x + 1.

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

Пример: Пусть (7,4)-код порожден многочленом g(x) = x3 + x2 +1 и принято слово 1110111. По принятому слову строим многочлен   x6 + x5 + x4 + x2 + x + 1, который делится на g(x). Поэтому мы делаем заключение, что при передаче ошибок не было, и переданное информационное слово есть вектор коэффициентов частного x3 + x +1 от деления многочлена x6 + x5 + x4 + x2 + x + 1 на g(x), т. е. вектор 1011.

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