Главная Помехоустойчивое кодирование



что и" = 6, которому соответствуют корни и, 12, 15. Так как£= 11 = = 6, то и корни являются соответствующими квадратами: 11 = 6, 12 =8, 15 = 14, GF(2).

Другие универсальные методы, пригодные для решения уравнений произвольных степеней, изложены в § 5.5.

5.3. УРАВНЕНИЯ ЧЕТВЕРТОЙ СТЕПЕНИ

Приведение к каноническому виду. В произвольном уравнении четвертой степени

(5.40)

с помощью подстановки х = у AjA можно исключить кубический член, сведя уравнение (5.40) к виду

у" •ау Ьус = О, (5.41)

где а = (86 - ЪА)1\ b = (А ~ 4АВ + 8С)/8; с= (256/)- 64ЛС + + 16АВ- ЗЛ)/256.

Коэффициент при квадратном члене обращается в единицу при замене у = z\fa в уравнении (5.41). В результате получается уравнение

(5.42)

z* + + 1Z + 11 = О,

где 11\ = b\fala\ - cja}.

Переход от уравнения (5.40) к уравнению (5.42) возможен в любом поле. Однако в поле характеристики 2 подстановка х = у - А\4 невозможна и используется подстановка

ху (С/А)1, АФО, которая приводит к уравнению аэу" + агУ + ai + до = О,

гдедз =-0+ (BQIA + (С/АУ; аг = В(AQ 1, ai = А, ао = 1.

(5.43)

(5.44)

замечание. преобразование (5.43) невозможно при А = 0. может оказаться, что и 5 = о, т. е. + 0 ;с + е =0. такое уравнение с помощью подстановки х = = 2в (естественно, если извлекается кубический корень из в; в противном случае исходное уравнение не имеет четырех Неравных корней) приводится к виду

+ Z + = о, где = е6~. при л = о, 5 о преобразование (5.43) также невозможно, но в нем и Нет необходимости, так как в этом случае уравнение (5.40) уже представлено в форме (5.44).

если окажется, что дз = о, то исходное уравнение (5.40) содержит двукратный коренк в этом можно убедиться, например, выразив коэффициенты уравнения (5 40) согласно теореме виета через корни Хь хг, з, х этого уравнения и подставив значения коэффициентов в формулу для Д3. после преобразований



получим дз = (xi + хг) (xi + хз) (xi + х4) (х + хз) (хг + х4) (Хз +х4), и, следовательно, из условия Дз = о вытекает равенство хотя бы одной пары корней уравнения (5.40).

Далее, при условии Ф О Ф Ог положим = 2(2/3)*. Тогда получим

+z +£iz +£"2 = О,

где El = ai{ajaiy\ Ег = aja

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

Подставим в уравнение (5.40)

x =Az -у В/А,

(5.45)

(5.46)

Тогда после преобразований получим каноническое уравнение без квадратного члена:

г"* +z +MZ +1=0,

(5.47)

fji= (В уСА)1А; v= (В"" -уАСВ уАП)1А, (5.48)

Табличный метод. Канонические уравнения (5.45) и (5.47) содержат по два параметра, так что таблицы корней этих уравнений должны содержать по два адресных входа. Вычисление параметров, а также восстановление л: по z для уравнения (5.47) проще, чем для уравнения (5.45). Поэтому целесообразно протабулировать значения корней именно канонического уравнения (5.47).

Неравные корни уравнения z* + z + = О, а также уравнения (5.47) для ряда конечных полей GF(2) небольших размерностей представлены в табл. 5.4 и П.5. Значения = О для простоты исключены, так как в этом случае появляется нулевой корень, а степень уравнения уменьшается на единицу, т. е, дело по-существу, сводится к решению кубического уравнения z + z +д = 0 (см. § 5.2).

В табл. 5.5 приведены примеры решения уравнений четвертой степени для различных полей. Из трех значений (2, 23, 44} GGF(2*), возможных для корня в строке г = 6 выбрано значение 2.

Орбитальные представления. Таблицу корней уравнения (5.47) можно сжать точно так же, как и соответствующие таблицы корней квадратного и кубического уравнений, переходя к орбитальным представлениям. Для полей небольших размерностей такие представления даны в табл. 5.6.

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



таблица 5.4

Простые корни уравнения четвертой степени z +z + tp

над полем GF(2), л = 3... 6

tttf

Четырех неравных корней нет

GF(2"*), я= а** +а+ 1

GF(2=),=a + a + l

Четырех неравных корней нет

Орбиты.

+ а+ 1

Разобьем полином четвертой степени на два квадратных полинома-сомножителя [54]:

(5.49)

Примеры решения уравнения x** + Лх + Вх + Сх + D = О

над полем GF( 2), л =3...6

таблица 5.5

Коэффициенты

Параметры

Корни по табл. ns или по табл. 5.4

Корни

х"

х"

3 13

7 13

26 2

23 2

22 2

10 20

12 0

егыр

26 ex рг

13НЫХ

29 ; корне

:Й в ПС

»ле (

18 JF(2

;) и.

1 1



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 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94


0.014