Научная литература
booksshare.net -> Добавить материал -> Физика -> Галлагер Р. -> "Теория информации и надежная связь" -> 115

Теория информации и надежная связь - Галлагер Р.

Галлагер Р. Теория информации и надежная связь — М.: Советское радио, 1974. — 738 c.
Скачать (прямая ссылка): teoriyainformacii1974.pdf
Предыдущая << 1 .. 109 110 111 112 113 114 < 115 > 116 117 118 119 120 121 .. 355 >> Следующая


233
будет иметь степень, меньшую, чем степень g (D), он выбирается в качестве г (D). В качестве примера рассмотрим случай, когда g (D) = = ?>2 + ?> + 1 и / (D) = ?>3 + D + 1 являются многочленами над полем по модулю 2:

1__________

Z)2 + D+1)D3_|_

D3 + D2 + D D2 +1 ?>2 + ?> + 1 D

В этом примере h (D) = D + 1 и r (D) = D.

Теперь предположим, что существуют два решения (6.4.13), задаваемые h (?>), г (D) и h' (?>), г' (D), Тогда

g (D)h (D) + г (D)=g (.D)h' (D) + / (D), (6.4.14)

g (D) [h (D) - h' (D)] = r' (D) - r (D). (6.4.15)

Теперь заметим, что г' (D) — г (D) имеет степень, меньшую, чем степень g (D), и поэтому h (D) —h' (D) = 0. Но отсюда следует, что г' (D) — г (D) = 0, что завершает доказательство единственности решения. !

В дальнейшем при операциях над конечными полями нас часто будет интересовать не столько частное h (D), сколько остаток г (?>) в (6.4.13). По аналогии с арифметическими действиями по модулю простого числа назовем вычетом многочлена f(D) по модулю многочлена

g(D) остаток от деления / (D) на g (?>); будем обозначать его через

Rg(D) Г/ (?>)]:

Rg(D) f/Р)1 = r (D); r (D) определяется (6.4.13). (6.4.16)

Алгоритм Евклида деления многочленов можно использовать для исследования существования делителей и корней многочлена над GF (q). Многочлен g(D) является множителем (или делителем) другого многочлена / (D), если существует многочлен h (D) над рассматриваемым полем, удовлетворяющий соотношению

f(D)=g (D)h(D). (6.4.17)

Другими словами, / (D) делится на g (D), если при использовании алгоритма Евклида (6.4.13) получим г (D) = 0. Многочлен / (D) называется приводимым, если существуют два многочлена g (D). и h (D) над рассматриваемым полем, каждый из которых имеет степень, не меньшую 1, удовлетворяющие (6.4.17). Многочлен называется неприводимым, если он не является приводимым.

Часто бывает полезно разлагать многочлен на неприводимые множители. При этом всегда существует некоторая доля неопределенности, поскольку при разложении всегда можно умножить один из сомножителей на произвольный элемент поля, а другой сомножитель — на обратный ему элемент поля, не изменяя при этом произведение. Норми-

234
рованным многочленом называется многочлен, у которого старший ненулевой коэффициент равен 1; можно избежать указанной выше неопределенности, если при разложении многочлена всегда представлять его в виде произведения элемента поля и нормированных неприводимых множителей.

Теорема 6.4.3. (Единственность разложения.) Многочлен / (D) над заданным полем единственным образом представляется в виде произведения элемента поля и нормированных неприводимых многочленов над данным полем, каждый из которых имеет степень, не меньшую 1.

Доказательство. Ясно, что входящий в разложение элемент поля единствен и равен /п, где п — степень многочлена / (D). Поэтому можно ограничиться рассмотрением нормированных многочленов. Предположим, что теорема неверна и существует некоторый нормированный многочлен / (D) наименьшей степени, который может быть разложен двумя способами:

Gl (D)a3 (D) ...ak (D) = b± (D)... bj (D), (6.4.18)

где многочлены ak (D) и bj (D) нормированные и неприводимые.

Каждый из многочленов ah (D) должен отличаться от каждого из bj (D); в противном случае должен существовать нормированный многочлен, степень которого меньше, чем степень /(D), допускающий два различных разложения. Без ограничения общности допустим, что степень b± (D) не выше степени а± (D). Тогда получим

аг (D) = bx (D)h (D) + г (D), (6.4.19)

где г (D) имеет степень, меньшую,чем степень &i(D), и меньшую, чем ai(D). Подставляя (6.4.19) в (6.4.18), получаем

r (D) а2 (D)... ak (D) = Ьг(D)\b2 (D)... bj(D) — h(D)a2(D)... ah(D)].

Разложив г (D) на множители и умножив произведение на элемент поля таким образом, чтобы нормировать множители, получим два разложения нормированного многочлена, имеющего степень, меньшую, чем степень f (D), причем левое разложение на неприводимые множители не содержит в качестве множителя неприводимый многочлен Ьг (D)JПолученное противоречие доказывает справедливость теоремы. |

• Элемент а из поля называется корнем многочлена / (D) над этим полем, если f(a) — 0.

Теорема 6.4.4. Элемент а, принадлежащий полю, является корнем ненулевого многочлена/(D) над этим полем тогда и только тогда, когда (D — а) является делителем /(D). Кроме того, если/ (D) имеет степень п, то число элементов поля, являющихся корнями / (D), не превосходит п.

Доказательство. Согласно алгоритму Евклида имеем

/ (D) = (D - a)h (?>) + г (D).

(6.4.20
Предыдущая << 1 .. 109 110 111 112 113 114 < 115 > 116 117 118 119 120 121 .. 355 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed