Порождающий полином

Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней, т. е. такой многочлен делится только на самого себя или на единицу и не делится ни на какой другой многочлен. На такой многочлен делится без остатка двучлен xⁿ + 1. Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

Возвращаясь к определению циклического кода и учитывая запись операций циклического сдвига кодовых комбинаций, можно записать порождающую матрицу циклического кода в следующем виде:

где p(x) — исходная кодовая комбинация, на базе которой получены все остальные (m − 1) базовые комбинации, C_i = 0 или C_i = 1 («0», если результирующая степень полинома p(x) · xⁱ не превосходит (n − 1), «1», если превосходит).

Комбинация p(x) называется порождающей (порождающей, генераторной) комбинацией. Для построения циклического кода достаточно верно выбрать p(x). Затем все остальные кодовые комбинации получаются такими же, как и в групповом коде.

Порождающий полином должен удовлетворять следующим требованиям:

1. p(x) должен быть ненулевым;

2. вес p(x) не должен быть меньше минимального кодового расстояния: v(p(x)) ≥ d_min;

3. p(x) должен иметь максимальную степень k (k — число избыточных элементов в коде);

4. p(x) должен быть делителем полинома (xⁿ − 1).

Выполнение условия 4 приводит к тому, что все рабочие кодовые комбинации циклического кода приобретают свойство делимости наp(x) без остатка. Учитывая это, можно дать другое определение циклического кода. Циклический код — код, все рабочие комбинации которого делятся на порождающий без остатка.

Для определения степени порождающего полинома можно воспользоваться выражением r ≥ log₂(n+1), где n — размер передаваемого пакета за раз, т. е. длина строящегося циклического кода.

Примеры порождающих полиномов, можно найти [5] в таблице: