Главная страница  Алгебраическая теория кодирования 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [ 43 ] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

*11.4..Преобразования функции /(л)

Некоторые члены алгебраического уравнения от z часто удаетс исключить с помощью подстановки вида у= (az + b)l{cz + d), г а, b, с, d GF (g). Обычно выбор подходящих элементов а, Ь, с я осуществляется путем последовательности преобразований сдви1 (у = Z - а), перехода к обратному (у = 1/z) и умножения на скг ляр {у = az). Рассмотрим, например, общее уравнение пятой степеш над полем характеристики 2

z5 + az* + fczs + cz + dz + е = 0. Обозначив оператор сдвига через А, получим

г/S + Ai/* +А*г/ + А« +

+ ау* + аА* +

+ Ьу + ЬАу + ЬАу + ЬА + + сг/2 +cAi-

+ dyi dA + + е

Полагая А = а, можно исключить член четвертого порядке а при А = c/d можно исключить член второго порядка. Вторе выбор представляется более плодотворным. Исключив член второ! порядка, можно путем перехода к обратному исключить кубическ! член. Применяя к полученному уравнению операцию линейног сдвига, можно, далее, исключить либо член четвертого порядку либо линейный член. Исключив член четвертого порядка и нормал зовав затем линейный член с помощью подходящего скалярное множителя, исходное уравнение пятой степени можно привест к виду

+ fu + g = 0.

Возникает вопрос, могут ли такие предварительные преобразоБ пия существенно упростить вычисления при определении наймов шего аффинного кратного и его корней. Так как приведенное ур пение пятой степени содержит меньше членов, чем исходное, то мо надеяться, что степень наименьшего аффинного кратного приводе ного многочлена будет равна 8, а не 16. Но, к сожалению, с помои непосредственных, хотя и громоздких вычислений можно показа! что это не так. Выбор других возможных форм редукции (исключе!

квадратного и линейного членов, или членов четвертой и второй степени, или кубического и. линейного членов) также не приводит к многочленам, аффинные кратные которых имеют степень 8. Исключение члена четвертой степени позволяет упростить аффинное кратное, но, к сожалению, это упрощение приводит к исчезновению членов младшей, а не старшей степени. Обобщение этого факта дает следующая теорема:

11.41. Теорема. Если

J{z) = z<+hz<-\ hGF{q),

- некоторый делитель аффинного многочлена А (г) над GF (д) и d не кратно р, то fjd - корень многочлена А (z).

Замечание. Здесь jjd =•- fd, где d g GF (p) ~ обратный к d mod p.

Доказательство. Множество корней многочлена А (z) включает в себя аффинное пространство, натянутое на корни г,

Г2, . . ., Га многочлена /. Так как 2 "ft = Л. то

d - d

Следовательно, fi/d ~ корень А (z). щ

2

h= 1

r-k - ri

Когда степень многочлена / не кратна р, Д может быть исключен с помощью подстановки у = z - fJd. При этом наименьшее аффинное кратное приведенного многочлена имеет корень О, а степень его равна р-. Так как для исключения Д используется очень простое преобразование, то не удивительно, что получается столь малое уменьшение степени.

С другой стороны, если степень многочлена / кратна р, то никакое преобразование сдвига не может исключить Д. Однако если удастся найти сдвиг, приводяпщй к исключению fa-x, то дальнейшее использование перехода к обратному позволяет обратить в О коэффициент Д. Успех этого преобразования гарантируется следующей теоремой:

11.42. Теорема. Если степень многочлена f (z) кратна р и fl = О, то степень наименьшего аффинного кратного многочлена / не превосходит d - 2.

Доказательство. Если 2 = О и кратно р, то

S {ri - ri) = 0 - dri = 0 и Гй = 7-1-

i= 1

- S (ri-ri).



Таким образом, аффинное пространство, натянутое на корни Tj, г, . ., Га, совпадает с аффинным пространством, натянутым на корни г. Га, . . ., Td-i- Размерность аффинного пространства, натянутого на d - 1 произвольных элементов, не превосходит d - 2, что и доказывает теорему, щ

В качестве примера использования этой теоремы рассмотрим! уравнение четвертой степени общего вида над полем характеристи-! ки 2. С помощью подходящего сдвига можно сначала исключить! линейный член уравнения, а затем с помощью перехода к обратному! привести его к стандартному виду без кубического члена. Степень наименьшего аффинного кратного такого приведенного многочлена, согласно теореме 11.42, не превосходит 2~ = 4. Это подтверж-] дается тем, что приведенный многочлен четвертой степени сам, является аффинным. i

В общем случае исключение линейного члена в произвольном! многочлене четной степени d над полем характеристики 2 сводится к решению другого алгебраического уравнения степени {d - 2)/2. Например, для исключения с помощью сдвига z = у + А линейного члена в уравнении шестой степени

z« + az + bz* + + dz + ez + f

необходимо так выбрать величину А, чтобы

а (а2)2 + с (а2) + е = 0.

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

*11.5. Подсчет корней

После вычисления А (z) - наименьшего аффинного кратно! многочлена Т{) - и определения в GF (q) его корней остается задач! определить, какие из этих корней многочлена А (z) являются корня ми многочлена 7 (z). В общем случае нет специальных правил выбора! кроме поиска среди заданных корней. Однако можно высказать пеке торые общие положения относительно числа корней многочлена / (а в поле GF (q), учитывающие только число корней многочлена А {г в поле GF (q) и общее число корней многочлена А (z). Пусть, nanpi мер,7 (z) - такоймногочлен пятой степени над полем характеристи ки 2, что степень его наименьшего аффинного кратного А (z) равет

16, а 8 корней многочлена А (z) лежат в основном поле. Сколько среди них корней многочлена / (z)? Можно предположить, что это число принимает любые значения между О и 5. Однако, согласно следующей теореме, возможными числами являются только 1 и 3.

11.51. Теорема о числе корней. Пусть / (z) - много-ч.ген без кратных корней над полем GF (q) характеристики р. Пусть Л - число корней многочлена f (z), лежащих вне GF (q), а А (z) - наименьшее аффинное кратное многочлена J{z).

Если О - корень А (z), то N = deg f. В этом случае степень .многочлена / (z) и степени всех его неприводимых делителей кратны р.

Если число различных корней многочлена А (z) в поле GF (q) положительно, то оно равно р. Число всех корней многочлена А (z) равно р+.

Если / = О, то N = 0.

Если / > 1, то N J i.

Если J = i, то числа N и р {р - \) не взаимно просты.

Если J = 2, то либо N имеет по меньшей мере один нетривиальный делитель + 1, либо N может быть предстлвлено в виде N = В Hi Сп, где В и С - положительные целые числа, а каждое из чисел п-г и п не взаимно просто с р (р - 1),

Доказательство. Если корни А (z) не лежат в GF (q), то, согласно теореме 11.41, степень каждого делителя многочлена А (z) над GF (q) кратна р. С другой стороны, если г £GF (q) - корень .многочлена А (z), то с помощью сдвига можно перевести А (z) в А (z - г) и / (z) в / (z - г). Эта операция переводит корни в GF (q) в корни в этом же поле, а корни вне поля GF (q) - в корни, также не лежащие в этом ноле. Достоинство операции сдвига состоит в том, что она преобразует аффинное пространство, натянутое на корни многочлена / (z), в линейное пространство, натянутое на корни многочлена / (z - г).

I Корни многочлена А (z - г) в GF (q) образуют линейное пространство над GF (р), и, следовательно, число таких корней равно р. Обозначим через щ, и, . . ., м/ базис этого пространства. Множество всех корней многочлена А (z) (включая и те, которые лежат в расширении поля GF (q)) также образует векторное пространство над GF (р). Множество линейно независимых элементов щ, и, ... ., Uj может быть дополнено до базиса пространства всех корней путем добавления базисных векторов v, v, . . ., Vj. Без потери общности можно полагать, что векторы ы, и, . . ., их, v, v, . . ., Vj образуют подмножество множества корней многочлена f{z - г). Пространство, натянутое на векторы щ, и, . . ., uj, v, v, ... • . ., Vj, совпадает с пространством, натянутым на корни s, s, ...



• h, ifa, . . ., tj многочлена / (z - г), где GF {qj

utiGF (q). Ясно, что если / = О, то = 0. Если / > О, то и пространство корней порождается также множеством s, Sa, .

Так как ( S + S 0 € GF {q),\

то tt£GF{q).

Таким образом, пространство, натянутое на корни многочлен (z - г), имеет базис, содержащий не более 7V - 1 элементов, лежащих вне GF (q). Следовательно, J - i или, как и утверждалось

Если / = 1, то каждый из TV элементов t, , tj предста-вим в виде ti = CiV + ui, где С; € GF (р), щ GF {q), GF (q) Переходя к сопряженным, получим tf = Сучп + i-, а это равн ti тогда и только тогда, когда i;" равно v. Таким образом, число эле ментов, сопряженных с данным корнем, равно числу сопряженн с V. Так как tj = tj, то Ciif + Ui = CjV + uj и i; = {Cj/Ct) v

4- = Cv + u. Переходя к сопряженным, получаем,

ря = Cv + (С + 1) li, и в общем случае ifl"" = + ( 2 G)u\

j=o I

Если С = 1, то р?" = г; тогда и только тогда, когда п кратно р\ В этом случае v имеет точно р сопряженных элементов. Если С Ф 1 то = г; тогда и только тогда, когда С" = 1. Так как С GF (р то С"1 = 1, и число элементов, сопряженных с v, делит число р - Предположим теперь, что / = 2 и рассмотрим сначала случа когда VI = Cvi + lii, i;4 = Cv + "2; 6 (p) и € GF [ql Обозначим через «1 число сопряженных с v-, а через щ- число сопрг женных с V2 элементов. Каждый корень многочлена f {z - г), лежащий в GF (q), представим в виде

h = CiVi + DiV2 + Щ, tf = dvf + Divf + Ui,

так что число элементов, сопряженных с ti, равно щ, если Di = равно «21 если Cj = О, и равно наименьшему общему кратному чисе щ и п, если Di и С\ отличны от нуля. Ясно, что N представил в виде Вщ + Сп для некоторых положительных чисел В и Из предыдущей части доказательства (для / = Г) видно, что каждо из чисел n-i и «2 не взаимно просто с р (р - 1).

Если не существует элементов С- GF (р) и щ GF (д), так1 что = C1V2 + Wj, то пространство, натянутое на и, . . ., и4 Vi, V2, совпадает с пространством, натянутым на щ, и, . . ., т Vi, vf. Аналогично, если не существует элементов GF

и U2 6 GF (q), таких, что i; = Cv + и, то и, и, . . ., щ, v, v§ можно выбрать в качестве базиса пространства корней многочлена А {z - г). В любом случае можно найти такой элемент v, что корни многочлена А {z - г), не лежащие в GF (q), могут быть записаны в виде

ti = CiV + Div + щ, tf.CiV+DivU-Ui.

UiGF(q), Ci, DiGF{py,

Следовательно, каждый корень многочлена f(z - r), лежащий вне GF (q), имеет столько же сопряженных, сколько и элемент v. Для каждого /

vq = Ajv + Bjv + uj, Aj, BjGFip), UjGFiq).

Пусть к обозначает число, для которого А1фО, АфО, . .., Au-i Ф О, Ak = 0. Для 2<;/ <; А выполняются равенства

v4 = Cjv4- + Djv + uj; Cj, Dj GF(p), uj£FG{g), СуфО; DJфO,

Возводя каждое из этих равенств в степень q, получаем, что

v<i<> = Cjv<i + Djv4-> + uj для всех /, 2<7<А. Если Ci=Cj для некоторых i<.j<k, то

так что

Djv"-- = Div" + Ui-Uj = Di {BkV + uu) 4 - uj.

a это противоречит предположению о том, что ф 0. Таким

образом, Ci ф Cj для 2 < i </ <А. Элементы С2, Сд, . . ., C-i выбираются среди р - 1 ненулевых элементов поля GF (р), так что 2 А; р 4- 1. Так как число сопряженных с каждым корнем, лежащим вне GF (q), кратно к, то число Л также кратно к. щ

Можно несколько усилить эту теорему, когда / = 2ир>11, так как не все значения к р + i возможны. Тщательная проверка показала, что если р = 2, 3 или 5, то все значения к допустимы, но при р = 7 значение к = 5 исключается. Эта ситуация, однако, не исключает равенств р = 7, / = 2 и = 5, так как возможно А" = 2 + 3 при = - Vi + Ui и у9 = 2i;2 + li.

Если / 3, то на нельзя наложить никаких теоретико-числовых ограничений. Как было видно при доказательстве теоремы 11.39, над полем GF (q) для каждой степени >2 существует много многочленов с линейно независимыми сопряженными элементами, т. е.

S gii" Ф О




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [ 43 ] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

0.019