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

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

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

V =   p(x) p(x) · xC2 (xn − 1) p(x) · x2C3 (xn − 1) … p(x) · xm−1Cm (xn − 1)   ,

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

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

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

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

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

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

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

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

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

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

 

 

r, степень полинома P(x), порождающий полином
100101, 111101, 110111
1000011, 1100111
10001001, 10001111, 10011101
111100111, 100011101, 101100011







Дата добавления: 2015-04-10; просмотров: 1203; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2022 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.004 сек.