Порождающий полином циклического кода

Важным свойствам циклических кодов является то, что все разрешенные кодовые слова - полиномы кратны одному фиксированному полиному g(х), который называется порождающим (генерирующим, образующим) полиномом. При делении на порождающий полином запрещенных кодовых комбинаций всегда образуется остаток R(х), отличный от нуля. Именно эта особенность циклических кодов используется при кодировании и декодировании. Старшая степень порождающего полинома всегда равна числу проверочных символов кода: r=n-k. В общем случае порождающий полином имеет вид:

(21)

где g_r,…, g₀ - коэффициенты формальной переменной " х ", могут быть равны “1” или “0”

В теории кодирования показано, что старшую степень полинома g(х) следует выбирать равной

r=lt_исп, (22)

где l определяется условием 2 ^l = n+1.,

Пример 11 Определить количество проверочных символов r для циклического кода с числом информационных символов k=20 и кратностью исправляемых ошибок t_исп=2.

Учитывая условие (22), определим методом подбора приемлемое значение l. Примем l=3. Тогда n=2^l-1=2³-1=7, что меньше k=20. Следовательно, необходимо увеличить l. При l=4 также получаем n‹k. Возьмем l=5. Тогда n=2^l-1=2⁵-1=31; r=lt_исп=5∙2=10. В результате получаем код (31;21) с n=31, k=n-r=21 и r=10. Этот код обеспечивает кодовое расстояние d₀≥2t_исп+1=5.

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

а) полиномы g(х) должны быть неприводимыми т.е. не делиться ни на какой другой полином;

б) двучлен вида (хⁿ+1) должен делиться на g(х) без остатка (имеется в виду обычная операция деления). Такие полиномы найдены с помощью ЭВМ и приведены в специальных таблицах.

Примечание: Как исключение, в качестве порождающего допускается использовать полином вида х⁵+х⁴+х²+1, не удовлетворяющий вышеприведенным условиям (Гост 17422-82 Системы передачи данных. Скорости передачи данных и основные параметры помехоустойчивых циклических кодов.)

Дата добавления: 2015-08-13