Глава 3

Число неприводимых -ичных многочленов заданной степени

Мы видели, что можно построить БЧХ-код с блоковой длиной 2™ - 1 и исправлением двух ошибок, если известен неприводимый двоичный многочлен степени т.

Априори нет никаких гарантий существования неприводимых двоичных многочленов произвольной заданной степени. Возможным методом доказательства существования неприводимых двоичных многочленов любой степени т является вывод точной формулы для числа 1т таких многочленов, которая покажет, что > О для любого натурального числа т. Хотя такое решение может показаться неоправданно сложным, результаты искупают все усилия, тем более, что методы рассуждений оказываются также полезными в следующих параграфах.

3.1. Грубый подход к решению

Рассмотрим сначала грубые методы перечисления неприводимых двоичных многочленов заданной степени. Очевидно, существуют] два неприводимых многочлена степени 1: х и ж + 1. Существуют* четыре двоичных многочлена степени 2, три из которых разлагаются; на множители. Полный их список имеет вид

х = х\

х +]. = {х + i)\ Х + X = X {х + \), -(- X + 1 неприводим.

Имеются восемь двоичных многочленов степени 3 и в обще* случае 2 двоичных многочленов степени d, соответствующих двум! возможным выборам значений каждого из коэффициентов /о,

d-i *

/j, . . ., fd-i "В выражении / (х) = (З/г*) + Восемь многочленов третьей степени разлагаются на множители следующим! образом:

х» =-х»,

х» -1-1 = (х-Ь1)(х2 + х--1),

х +х =x(x-fl)2, х* 4-Х + 1 ненриводим, хЗ + х2 =х{х + \),

x-j-x --1 неприводим,

XJX-X =х(х2 + Х-1-1),

хЗ + х2 + х-1-1=(х + 1)з.

Среди восьми многочленов третьей степени два распадаются в произведение квадратного и линейного множителей, четыре - в произведение трех линейных множителей, а остальные два являются неприводимыми. В общем случае, полагая А; = О, 1, 2, . . ., п в выражении

(3.11)

/(х) = х(х-Ь1)"Л

получаем {п -f- 1) двоичных многочленов степени п, распадающихся в произведение п линейных множителей.

Обозначим через число неприводимых двоичных многочленов степени т. Тогда /х = 2, /3 = 1, /д = 2. Подсчитаем теперь /4, не выписывая все 16 двоичных многочленов степени 4. Многочлен четвертой степени может быть представлен в виде произведения лшогочленов третьей и первой степени /дД = 4 различными способами, а в виде произведения двух неприводимых квадратных многочленов 1\ = \ способами. Он может распадаться в произведение квадратного и двух линейных множителей; разложение осуществляется однозначно при различных линейных множителях и IJi = 2 способами при повторении одного и того же линейного множителя - всего 3 способами. Наконец, возможны пять способов разложения в произведение четырех линейных сомножителей. Подытожим эти возможности в следующем виде:

/4 = 2* - 13 = 3.

82 Гл. 3. Число неприводимых q-ичных многочленов заданной степени Зная /4, можно вычислить 1:

Разло:жение

Число способов

/5 = 2» - 26 = 6. Вычисление 1:

Рааложение

Число способов

/в = 26 - 55 = 9.

Если проявить достаточную настойчивость и внимание, то можно подсчитать /7, /g, . . . .К счастью, большинства из этих вычислений! можно избежать, если использовать более тонкую схему счета, известную под названием метода производящих функций.

3.2.*Производяш,ие функции

Если имеется последовательность Aq, Ат, А, . . ., то производящую функцию, соответствующую этой последовательности, можно; определить как формальный степенной ряд

АI могут быть рациональными числами или элементами любого поля.

оо оо

Две производящие функции А (£) = AiZ ъ. В (z) = 2 -г* называются равными, если 4; = Б; для всех i. При более слабом допущении, что Ai = Bi для i = О, 1, . . ., А; - 1, мы говорим, что А {z) = В (z) mod z".

Сумма или разность двух производящих функций определяется равенством

S {Ai ± Bi) z\

а произведение задается формулой

A{z)B(z).

- S Z{AjBij)z\

г=0 j=0

Будем говорить, что С (z) = А (z)/B (z) тогда и только тогда, когда С (z) В (z) = А (z). Отношение двух производящих функций, если оно существует, всегда единственно,, так как если D (z) В (z) = = C{z)B (z), то О = Z) (z) 5 (z) - С (г) В (z) = [D (z) - С (z)] В (z) и, как мы предлагаем проверить читателю, либо В (z) = О, либо D (z) = С (z). Если Ад = О, то В (z) А (z) = О mod z при любом В (z) и уравнение В (z) А (z) = i не разрешимо относительно В (z). Однако если А,, Ф О, то

A{z)

A(z)

Следовательно,

00 00

= 3[-ЗЙ)Т

со оо

Таким образом, производящая функция А (z) имеет мультипликативную обратную тогда и только тогда, когда Ад Ф 0.

Назовем А (z) четной производящей функцией, если Ai = О для всех нечетных i, и нечетной производящей функцией, если Ai = О для всех четных i. Сумма или разность двух четных производящих функций дают четную функцию, а сумма или разность двух нечетных производящих функций - нечетную функцию. Произве-

Гл. 3. Число неприводимых q-ичных многочленов заданной степени

3.2. Производящие функции

дение двух четных или двух нечетных производящих функций - четная функция, произведение четной функции на нечетную - нечетная функция. Мультипликативно обратная к четной производящей функции (если она существует) - четная функция. Произвольная производящая функция может быть записана как сумма четной

н нечетной производящих функций: А {z) = А {z) -f- А (г). Мы используем значки « и для обозначения соответственно четной н нечетной функций. Отметим графическое сходство этих знаков с четной косинусоидальной и нечетной синусоидальной функциями i).

Важно подчеркнуть, что перечисленные свойства производящих функций никак не зависят от сходимости или расходимости ряда

при некоторых значениях г. Например, при At = i\ этот ряд

расходится для всех ненулевых комплексных значений z. Далее, коэффициенты At не обязательно должны быть действительными или комплексными числами. Производящие функции можно строить над любым полем.

Для заданной производящей функции

можно определить ее формальную производную

А (z) = S nAnZ-K

3.21. Теорема.

Если

с (z) = (г) 5 (z) = 2 ( 2 AkBn-k) z",

n=0 ft=0

с (z) = 2 n ( 2 4ft5„ ft) z"-i =%[{k + n-k) ABn-k] z-- -

n=l k=0 n=i h=0

= 2 [2 Л:Л5„ , ,, 1,+ 2(n-fc)4ftB„ ftb"-i =

n=l ft=0 ft=0

=.Aiz)B{z) + A(z)B (z).

С помощью индукции этот результат может быть распространен! до известной формулы производной произведения нескольких npo-J изводящих функций.

Во избежание недоразумений читатель не должен путать / (г), нечетную часть / (z), с J (z), взаимным многочленом для / (z).

[ПЧ2)]= 2М"()Г

4=1 i=l ij

3.22. Следствие.

[ П "

rf.i.(.) Й

Таким образом, для формальной производной выполняются свойства обычной производной. Единственное отличие состоит в том, что формальная производная не связана с операцией предельного перехода.

Формальная производная применима также к производящим функциям, которые являются обычными многочленами. Это позволяет сформулировать следующий результат.

3.23. Теорема. Неприводимый многочлен g (z) с ненулевой производной g (z) ) является делителем многочлена / (z) кратности >1 тогда и только тогда, когда g (z) делит (/ (z), / (z)), к. о. д. / (2) и Г (Z).

Доказательство. Пусть g (z) - неприводимый делитель / (2), так что fiz) = g (z) h (z). Тогда / (z) = g (z) h (z) + g (z) h (z). Если многочлен g (z) делит / (z), то он также делит g (z) k (z). Ho deg g (z) < deg g (z) и поэтому g (z) не может делить g (z). Значит, g (z) делит h (z). Таким образом, g (z) является делителем / (z) кратности >-l тогда и только тогда, когда он делит / (z) и / (z), т. е. тогда и только тогда, когда g (z) делит н. о. д. / (z) и / (z). щ

Эта теорема справедлива для всех полей. Пусть, например, / (х) - двоичный многочлен + х* + -\- х. Тогда

/ {х) = + x + х-" X, f (х) = 5х* + Ах + 2х + i и (х), Г (х)) = х + i{x + 1)2.

x* + i,

При этом разложение / (х) на неприводимые множители[имеет вид fix) =х{х + 1)2 {х + х + 1).

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