Теория информации и надежная связь - Галлагер Р.
Скачать (прямая ссылка):
Многочлены
Выражение вида fnDn + /„-jD"-1 + ... + /о, обозначаемое через /(D), называется многочленом над GF (q) степени п, если коэффициенты /п, ..., /о являются элементами GF (q) и если первый коэффициент /пненулевой. Удобно считать, что коэффициент /*, связанный с многочленом я-го порядка, определен для всех i ^ 0, но удовлетворяет соотношению ft = 0 для i > п. Поэтому можно рассматривать многочлен
231
над GF (q) как способ представления бесконечной последовательности элементов поля /0, когда лишь конечное число членов последова-
тельности отлично от нуля. Степенью многочлена в этом случае является наибольшее число п, для которого fn =?0. В частном случае 0-много-члена, fn = 0 для всех п>0, условимся считать, что 0-многочлен имеет степень 0.
Символ D в многочлене / (D) называется неопределенным. Его нельзя интерпретировать как переменную или неизвестный элемент поля, во-первых, потому, что в дальнейшем мы иногда будем подставлять в качестве D элемент, не принадлежащий первоначальному полю, и, во-вторых, потому, что чаще интерес будет представлять последовательность коэффициентов, определяемая многочленом, а не многочлен как функция. Во всяком случае, после того как будут определены правила обращения с многочленами, вопрос о том, что такое неопределенная, исчезнет сам по себе.
Назовем два многочлена равными, если каждый из них соответствует одной и той же последовательности коэффициентов. Например, пусть / (D) = D3 + D2 + D и g (D) — D — два многочлена над полем по модулю 2 (условимся при записи многочленов опускать слагаемые, коэффициенты при которых равны 0, и записывать 1D1 как!)1')- В силу нашего определения, эти многочлены не равны. Вместе с тем, если подставить вместо D элементы поля 0 и 1, то получим, что / (0) = = 0, / (1) = 1 и g (0) = 0, g (1) = 1. Поэтому, если рассматривать f (D) и g (D) как функции переменной, определенной в поле по модулю
2, то они будут равны, хотя при рассмотрении их в виде многочленов они не равны.
Сумма двух многочленов над данным полем есть многочлен над тем же полем, определяемый по известному правилу
f{D) + g (D) = 2 (ft + 8l) DK (6.4.7)
i = 0
Степень / (D) + g (D) равна максимальному n, для которого fn + + gn Ф 0 и, следовательно, не превосходит наибольшей среди степеней / (D) и g (D). Например, над полем по модулю 2
(D2 + D + 1) + (D2 + 1) = (1 © 1) D2 + D + (1 © 1) = D.
Произведение двух многочленов над данным полем есть многочлен над тем же полем, определяемый соотношением
f(D)g(D) = 1l(t hgi.i)D‘. (6.4.8)
i \/= о /
Непосредственно используя (6.4.8),’можно показать, чтодля?(?>) = 0 / (D)0 = 0 для всех / (D). (6.4.9)
Кроме того,
/ (D) ¦g (D) ф 0 для / (Р) Ф 0, g (D) Ф 0. (6.4.10)
Чтобы убедиться в этом, предположим, что / (D) имеет степень я, /„ ф 0 и g (D) имеет степень т, gm Ф 0. Тогда из (6.4.8) следует, что
232
/ (D)g (D) имеет степень n + m и первое слагаемое этого многочлена равно f„gmDn+m.
Умножение многочлена / (D) над некоторым полем на элемент а этого поля определяется соотношением
af(D)=S(aft)D‘.
i
Аналогично, отрицательный многочлен для данного многочлена определяется как
i
Легко убедиться, что множество многочленов над полем образует абелеву группу по сложению. Также можно показать, что для умножения многочленов выполняются и ассоциативный и коммутативный законы и что справедлив дистрибутивный закон
[/ (D) + g (?>)] h (D) = f (D)h (D)+g( D)h (D).
Однако множество многочленов над полем не образует поле из-за отсутствия обратных по умножению элементов. Последнее служит примером того, что теорема 6.4.1 становится неверной без ограничения конечными множествами.
Сформулируем некоторые элементарные свойства многочленов, которые будут полезны в дальнейшем:
-[/ (D)g (?>)] = [-/ (?>)] g(D)=f (D) l-g (?>)], (6.4.11)
/ (D)g (D) = f (D)h (D) => g (D) = h (P) для f (D) Ф 0. (6.4.12)
Доказательства (6.4.11) и (6.4.12) аналогичны доказательствам (6.4.4) и (6.4.5).
Хотя, вообще говоря, нельзя делить один многочлен на другой и получить многочлен — частное, деление все же может производиться, если при этом допускается остаток.
Теорема 6.4.2. (Алгоритм Евклида деления многочленов.) Пусть / (D) и g (D) — многочлены над GF (q) и пусть g (D) имеет степень, не меньшую 1. Тогда существуют единственные многочлены h (D) и г (D) над GF (q), для которых
f(D)=g(D)h(D) + r(D), (6.4.13)
где степень г (D) меньше, чем степень g (D).
Доказательство. Покажем сначала, как найти h (D) и г (D), удовлетворяющие (6.4.13), а затем докажем, что это решение единственное. Пусть / (D) имеет степень п и пусть g (D) имеет степень т. Если п < т, то положим h (D) = 0, г (D) = / (D). Если п ^ т, произведем деление / (D) на g (D) по тому же правилу, по которому производится деление многочленов в обычном поле действительных чисел, а затем положим h (D) равным частному от деления, г (D) — остатку. Это означает, что первое слагаемое h (D) равно fngm~1Dn~m. Это первое слагаемое, умноженное на g(D), вычитается из / (D), и следующее слагаемое h (D) находится путем деления на g (D) этого остатка. Когда остаток
