Выбор образующего полинома

Ясно, что полиномы кодовых слов КС(Х) должны делиться на образующий полином степени r без остат ка. Циклические коды относятся к классу линейных. Это означает, что для этих кодов существует r линейно-независимых кодовых слов и с их помощью путем суммирования в разных комбинациях можно получить все остальные разрешенные кодовые слова данного кода. Для того, чтобы все они делились на образующий полином без остатка, достаточно чтобы без остатка на него делились только r линейно независимых кодовых слов. Эти линейно-независимые кодовые слова можно получить путем r -кратного циклического сдвига вправо или влево любого из разрешенных кодовых слов.

Напомним, что сдвигу влево соответствует умножение кодового слова на X с последующим вычитанием, если в результате умножения получается полином порядка >n из результата полинома Xⁿ+1. В формульном виде вышесказанное может быть отображено следующим образом'

где В=1 если степень g(X)*Xⁱ>=n

и где В=0 если степень g(X)*Xⁱ<n

Частное g_i(X)/ g(X ) не имеет остатка, если полином (Хⁿ+1) без остатка делится на образующий полином g(X) (очевидно, первое слагаемое делится на g(X ) без остатка).

Таким образом, образующий полином g_r (X) циклического линейного кода должен делить полином Х ⁿ+1 без остатка.

Это свойство обеспечивает отсутствие остатка при делении разрешенных кодовых слов на образующий полином. Таких слов 2^k. Всего же различных кодовых слов, которые могут быть получены на выходе канала связи 2ⁿ. Среди них 2^r-1 запрещенных, т.е. полученных в результате искажения разрешенных кодовых слов помехой. Ошибка обнаруживается, если остаток от их деления на образующий полином не равен нулю. Образующий полином имеет порядок r. Максимально возможное количество ненулевых остатков равно 2^r-1. Такое количество остатков могут дать только так называемые неприводимые полиномы, т.е. полиномы, которые не делятся без остатка ни на какие другие полиномы, кроме 1 и себя самого. Таблица неприводимых полиномов от 1 до 9 порядков приводятся в литературе.

Пример таблицы неприводимых полиномов.

Степень полинома	Полином	Двоичное слово
	X+1
	X^2+X+1
	X^3+X+1
	X^3+X^2+1
	X^4+X+1
	X^4+X^3+1
	X^4+X^3+X^2+X+1
	X^9+X+1
	И еще 40 штук полиномов

Дата добавления: 2014-01-04