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

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

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

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

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

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

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

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

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

Зная можно вычислить

Разложение Число способов

Вычисление

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