Главная > Помехоустойчивое кодирование > Кодирование с исправлением ошибок в системах цифровой связи
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

2.2.5. Дополнительные свойства многочленов и элементов полей Галуа

Между многочленами и элементами конечных полей имеется дополнительная, еще не рассмотренная здесь связь. Эта связь позволяет глубже изучить свойства многочленов, порождающих коды. Элементы поля Галуа играют для многочленов над конечным полем ту же роль, которую комплексные числа играют для многочленов над вещественным полем. Аналогично тому как каждый многочлен с вещественными коэффициентами можно разложить на множители, допустив введение комплексных чисел, каждый многочлен с коэффициентами из конечного поля можно разложить на множители с помощью элементов из некоторого расширения этого поля. Связь между сомножителями и корнями многочленов с коэффициентами из конечного поля полностью аналогична связи между корнями и сомножителями многочленов с вещественными коэффициентами. Например, заданный многочлен может быть представлен в виде

где значений являются корнями многочлена Многочлены и элементы поля Галуа обладают рядом свойств, которые оказываются полезными при описании кодов и при построении декодеров. Перечислим эти свойства без доказательства. Каждое из свойств проиллюстрируем одним или несколькими примерами, показывающими, как его использовать.

Свойство 1. Неприводимые многочлены. Многочлен с элементами из некоторого конечного поля называется неприводимым, если его нельзя разложить на множители, используя лишь элементы этого поля. Однако этот многочлен всегда можно разложить на множители, используя элементы из некоторого

расширения. Поэтому многочлен всегда имеет корни в некотором расширении. Если неприводимый многочлен с коэффициентами из — его корень, то также будут его корнями. Кроме того, все корни могут быть найдены таким способом. Многочлен называется минимальной функцией . Если — примитивный элемент, то называется примитивным многочленом.

Пример. Многочлен неприводим над полем Элемент а из табл. 2.4 является корнем, поскольку

Используя свойство 1, получаем, что и а также должны быть корнями. самом деле,

Наоборот, если являются корнями то можно записать в виде

Свойство 2. -произвольный многочлен, коэффициенты которого лежат в то

Справедливость этого свойства вытекает, из того, что все попарные или многократные произведения в появляются с коэффициентом, который делится на значит, равен 0 в

Пример. Читатель должен «метить, что свойство 2 можно использовать для доказательства свойства 1.

Свойство 3. Сомножители Порядком элемента конечного поля называется наименьшее значение для которого По определению является корнем многочлена Если является также корнем некоторого неприводимого многочлена то должен быть делителем

Свойство 4. Поле и корни Корни многочлена совпадают с ненулевыми элементами

Пример (свойства 3 и 4). Многочлен разлагается на следующим образом:

Используя табл. показать, что корнями являются корнями и корнем является 1. Эти семь корней являются семью ненулевыми элементами

Свойство 5. Делимость на Наименьшее значение для которого произвольный многочлен без кратных корней делит совпадает с наименьшим общим кратным

порядков корней Поэтому является длиной самого короткого цикла, порожденного регистром с обратными связями, определяемыми многочленом

Пример. Порядок корней равен 7, а порядок корней равен 15. Наименьшее общее, кратное 7 и 15, равно 105. Поэтому

делит и порождает цикл длиной 105.

Свойство 6. Делимость на Многочлен делится на в том, и только в том случае, если делится на Это вытекает из того, что если корни являются также корнями то должно делиться на

Пример. Используя прямые вычисления, читатель может легко убедиться, что на делится но не делятся

<< Предыдущий параграф Следующий параграф >>
Оглавление