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

  Содержание



 

7. Описание циклических кодов посредством корней в расширении поля

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

Пусть  m ≥ 2 и n = 2m - 1. Рассмотрим поле Галуа GF(2m) с 2m элементами. Известно, что мультипликативная группа поля, которую образуют все ненулевые элементы поля с операцией умножения, является циклической. Таким образом, в поле существует примитивный элемент a, т. е. такой элемент a, что любой ненулевой элемент b можно представить как степень элемента a, т. е. b = ar. Рассмотрим циклический (n, k)-код, порожденный многочленом g(x), который имеет корни g1, ..., gr в поле GF(2m). Известно, что g1, ..., gr будут корнями любого многочлена, который делится на многочлен g(x). С другой стороны, если g(x) является многочленом минимальной степени, корнями которого являются элементы g1, ..., gr, то всякий многочлен, корнями которого являются g1, ..., gr, делится на g(x). Следовательно, множество кодовых слов можно описать как множество всех многочленов, корнями которых являются g1, ..., gr.

Таким образом, многочлен an-1xn-1+an-2xn-2+...+a0 является кодовым, если и только если

an-1g1n-1 + an-2g1n-2 + ... + a0 = 0,

...

an-1gr n-1 + an-2gr n-2 + ... + a0 = 0.

Последние соотношения можно рассматривать как операцию умножения кодового слова на проверочную матрицу, которая состоит из степеней элементов g1, ..., gr. Условие того, что многочлен c(x) соответствует кодовому слову, превращается в систему равенств c(g1) = ... = c(gr) = 0. Таким образом, проверочная матрица кода будет состоять из степеней элементов g1, ..., gr:


В качестве примера рассмотрим проверочную матрицу циклического (7,4) - кода, порожденного многочленом g(x) = x3 + x + 1:

.

Переходя в расширение поля, эту матрицу можно записать более компактно. Столбцы матрицы Н можно отождествить с элементами поля GF(8), которое можно построить как алгебру классов вычетов по модулю многочлена z3 + z + 1. В многочленах, представляющих элементы поля, используем элементы первой строки матрицы в качестве коэффициентов при z2, второй - в качестве коэффициентов при z1, a третьей - в качестве коэффициентов при z0. Тогда, используя для построения поля GF(8) многочлен p(z) = z3 + z + 1 и выбирая класс [z] с представителем z в качестве примитивного элемента α, можно переписать матрицу Н в виде

Н = [α 6 α 5 α 4 α 3 α 2 α  α0].

Над расширением поля GF(8) проверочная матрица оказалась (1×7)-матрицей. Используя эту матрицу, кодовое слово можно определить как двоичный вектор c такой, что в расширении поля GF(8) он дает нулевое произведение cНT:

cНT = 0

или

.

Таким образом, если рассмотреть соответствующий кодовый многочлен

,

то α должно быть корнем этого многочлена.

Мы далее предполагаем, что m ≥ 2, n = 2m - 1, g1, ..., gr - ненулевые элементы поля GF(2m) и проверочная матрица представляется в виде, где

Заменяя каждый элемент поля GF(2m) коэффициентами представляющего его многочлена над GF(2), эту матрицу можно записать в виде булевой проверочной матрицы с n столбцами и rm строками. Для циклических кодов, однако, предпочтительнее работать в поле GF(2m).

Рассматриваемый код определяется как множество многочленов  степени не выше n - 1, таких, что для всех j = 1, ..., r выполняется равенство cj) = 0.

Таким образом, мы перешли от матричного описания линейных кодов к описанию циклических кодов, проверочная матрица которых представляется как матрица в расширении поля Галуа. Такое представление циклических кодов облегчает поиск хороших кодов и разработку кодеров и декодеров.