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

  Содержание



 

2.2. Описание циклического кода с помощью полиномов

Алгебраическое описание циклического кода дается следующей теоремой.

Теорема 2.2. В алгебре классов вычетов по модулю многочлена xn+1 подпространство V является циклическим тогда и только тогда, когда V содержит все классы вычетов, представители которых кратны некоторому многочлену g(x). Более того, многочлен g(x) является делителем многочлена xn+1.

Доказательство. Достаточность. Пусть g(x) - многочлен степени меньше n, и V содержит все двоичные наборы, соответствующие классам вычетов по модулю xn+1, представители которых кратны многочлену g(x). Рассмотрим произвольный вектор v Î V. Пусть двоичный вектор соответствует классу с представителем s(x), который делится на g(x). Тогда, согласно теореме 2.1, циклический сдвиг вектора v соответствует классу с представителем [xs(x)]. Так как многочлен xs(x) также делится на g(x), то циклический сдвиг вектора v принадлежит коду V, т. е. V - циклическое подпространство.

Необходимость. Пусть V - циклическое подпространство, и g(x) -многочлен наименьшей степени, такой, что двоичный вектор, соответствующий классу вычетов [g(x)] принадлежит коду V. Рассмотрим произвольный двоичный вектор v Î V, который соответствует классу вычетов с представителем s(x).

Многочлен s(x) можно разделить на многочлен g(x) таким образом, что степень остатка меньше степени многочлена, т. е. s(x) = q(x) g(x) + r(x), где 0 ≤ deg r(x) < deg g(x). Так как циклический код V является линейным, то двоичный вектор, соответствующий классу вычетов [q(x)g(x)] принадлежит коду V, и, следовательно, двоичный вектор, соответствующий классу вычетов [r(x)] также принадлежит коду V. Так как g(x) - многочлен наименьшей степени с таким свойством, то deg r(x) = 0, т. е. многочлен s(x) делится на g(x). Поскольку двоичный вектор 0...0, соответствующий классу вычетов [xn+1] = [0], принадлежит любому линейному коду, то на g(x) делится и многочлен xn+1.

Таким образом, любой циклический код задается некоторым многочленом g(x), на который делится многочлен xn+1. Многочлен g(x) называется порождающим многочленом циклического кода.

Пример: Рассмотрим циклический код длины 7. Многочлен  x7 + 1 можно разложить на неприводимые многочлены следующим образом: x7 + 1 = (x + 1)(x3 + x2 +1)(x3 + x +1). Согласно предыдущей теореме, все циклические коды исчерпываются кодами, порожденным многочленами (x + 1)(x3 + x2 +1), (x + 1)(x3 + x +1),  (x3 + x2 +1)(x3 + x +1), (x + 1), (x3 + x2 +1), (x3 + x +1).

Рассмотрим код, порожденный многочленом g(x) = x3 + x2 +1. Существует ровно 24 различных многочленов степени меньше 4, которые при умножении на многочлен g(x) дают многочлен степени меньше 7. Перепишем эти многочлены: {0, g(x), xg(x), (x+1)g(x), x2g(x), (x2+1)g(x), (x2+x)g(x), (x2+x+1)g(x), x3g(x), (x3+1)g(x), (x3+x)g(x), (x3+x+1)g(x), (x3+x2)g(x), (x3+x2+1)g(x), (x3+x2+x)g(x), (x3+x2+x+1)g(x)}, и соответственно, циклический код, порожденный многочленом g(x), есть код V = {0000000, 0001101, 0011010, 0010111, 0110100, 0111001, 0101110, 0100011, 1101000, 1100101, 1110010, 1111111, 1011100, 1010001, 1000110, 1001011}. 

Можно показать, что циклический код V Í Bn, B = {0,1}, порожденный многочленом g(x) степени k < n имеет размерность (n - k). Для этого достаточно рассмотреть двоичные векторы, которые соответствуют классам вычетов [g(x)], [xg(x)], ...,             [xn-k-1g(x)]. Эти векторы являются линейно независимыми, так как любая их линейная комбинация с коэффициентами из поля {0,1}, в которой хотя бы один их коэффициентов не равен 0, определяет многочлен степени меньше n, который по этой причине не может делиться на многочлен xn+1, и следовательно, любая линейная комбинация [g(x)], [xg(x)], ..., [xn-k-1g(x)] с коэффициентами из поля {0,1}, в которой хотя бы один их коэффициентов не равен 0, не равна [0] = [xn+1].

Таким образом, многочлен g(x) степени k < n, который является делителем многочлена xn + 1, порождает циклический (n, n-k)-код. В порождающую матрицу этого кода можно записать векторы, соответствующие классам [g(x)], [xg(x)], ..., [xn-k-1g(x)].

Пример: Действительно, код, рассмотренный в предыдущем примере, имеет базисные векторы 0001101, 0011010, 0110100, 1101000, соответствующие классам вычетов [g(x)], [xg(x)], [x2g(x)], [x3g(x)], т. е. имеет размерность 4. Порождающая матрица имеет вид:

.

Для задания проверочной матрицы циклического кода V, порожденного многочленом g(x), используется частное h(x) = (xn+1)/g(x) от деления многочлена xn+1 на многочлен g(x). Строится порождающая матрица для кода, порожденного многочленом h(x), и ее вектор-строки записываются в обратном порядке. Полученная матрица и будет проверочной матрицей для исходного кода V.

Пример: Для циклического (7,4)-кода, порожденного многочленом g(x) =  x3 + x2 +1, h(x) = (x7+1)/g(x) = x4 + x3 + x2 +1. Порождающая матрица для кода, порожденного многочленом h(x), имеет вид:

.

Переписываем ее строки в обратном порядке и получаем проверочную матрицу циклического кода, порожденного многочленом x3 + x2 +1:

.