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



Следовательно, условия (5.29) явно недостаточно для того, чтобы все три корня уравнения (5.26) принадлежали тому же полю, что и коэффициенты этого уравнения. Возможен вариант, при котором все три корня уравнения лежат в некотором расширении исходного поля GF(2). Причем в настоящее время не известны простые приемы, позволяющие указать требуемое расширение [53, 54].

Итак, неравенство (5.28) позволяет исключить из рассмотрения уравнения, у которых нет трех разных корней. Так, уравнение + z + + 2 = 0, GF(2*) не имеет трех неравных корней, поскольку Тг (!/£") = = 1 Тг(1) = 0. Действительно, полином z + z +2 можно фактооизо-

вать (разложить на множители) следующим образом: + z + 2 = = (z + 4)(z + 4z + 14), при этом Tr(Z)= 14/4) =Tr(8) = 1,GF(2). В соответствии с утверждением 5.1 квадратное уравнение z + 4z +

+ 14 = О Неразрешимо над полем GF(2*). В результате исходное кубическое уравнение имеет всего лишь один корень z - 4 е GF(2), а два

других кошя лежат в некотором распшрении поля GF (2**).

В работе [51] найдено следующее необходимое и достаточное условие принадлежности всех трех корней кубического уравнения (5.26)

пoлюGF(2):

(5.30)

где полиномырхрг, . . ,рг вычисляются рекуррентно согласно соотношениям

рг=е; р2=е; i>, +£-2" (5.31)

т. e.i3 =/2 +£ pi; Л= ia +"/2 ит. д.

Проиллюстрируем применение формул (5.30) и (5.31) на примере. Пример 5.8. Пусть уравнение (5.26) задано над полем GF(2 ), г = 4 и £ = 8 либо е = в.в первом случае

рэ =£ + ££ = 8 + 8 = 8 + 7 = 7- (1+2) = 7- 5 = 11;

4 =е + ер = 8 + 15 • 11 = 8 + 1090, GF(2),

Во втором ~

is = 6 + 6 =6 + 1 = 11; 4 = 6 + 6 - И = 6+ 6 = 0, GF(2).

Следовательно, при £ = 8 у уравнения (5.26) нет корней, а при £ = 6 ~ ровно три корня.

Сведение канонического кубического уравнения к квадратному.

Напомним, что нас интересуют только неравные корни уравнения (5.26), причем все лежащие в том же самом заданном поле GF(2), что и его коэффициенты.

Введем новую переменную z = м + 1/м; тогда уравнение (5.26) преобразуется к виду



+£« + 1= 0.

Обозначив = V, т. е. м =vv7сведем последнее уравнение к иско-

мому квадратному уравнению +£v + 1 = 0, GF(2).

(5.32)

Уравнение (5.32) может быть решено одним из приемов, изложенных в § 5.1. Например, заменяя переменную v = Ew, приходим к каноническому уравнению типа (5.3):

+ w +i) =0, = l/£ GF(2). (5.33)

Как отмечалось в § 5.1, условие Tr(Z)) = О является необходимым и достаточным для разрешимости подобных квадратных уравнений над GF(2). Так как (Ха,-) = Ха/, GF(2), то Тг(1/£) = Тг(1/£), и указанное условие разрешимости можно записать в форме

Tr(Z)) =Тг(1/£) =Тг(1/£) =0. (5.34)

Рассмотрим два типа полей GF((7 - 2 ) ~ при четном и нечетном г. Если г - нечетное число, то Тг(1) = 1 и условия (5.29) и (5.34) становятся противоречивыми. Другими словами, если выполнено равенство (5.29) - необходимое условие для того, чтобы все три корня уравнения (5.26) лежали в поле GF(2 ), т. е. если Тг(1/£) = 1, то квадратное уравнение (5.32) заведомо не разрешимо надполем GF(2 ). Следовательно, уравнение (5.32) имеет корни только в расширенном поле GF(2 ) [51]. Как в этом случае действовать далее при отыскании корней кубического уравнения (5.26), будет пояснено ниже на примере.

Предположим, что г ~ четное число, тогда Тг(1) = О и условия (5.29) и (5.34) совпадают, так что квадратное уравнение (5.33) разрешимо и имеет пару корней в исходном поле GF(2 ).

Покажем, как в данном случае можно найти KOpin кубического уравнения (5.26) по корням Vi,V2 квадратного уравнения (5.32).

Так как ViVi = 1 является произведением корней Vi, г2 и равно свободному члену в уравнении (5.32), то

Vi + 1/Vi = V2 + I/V2 И VHv/ =/4 V]/.

Поэтому для восстановления корней z\ z" и z" канонического уравнения (5.26) достаточно использовать лишь одно из значений: Vi

или V2-

В конце § 3.2 было установлено, что при четных г для некоторых элементов поля GF(2) существует точно три значения кубического корня, а для остальных - не существует ни одного. Пусть

{и\и\ы"] GGF(2).



Тогда = м + l/u; z" = и" + z" = w"+ - искомые

корни уравнения (5.26), по которым нетрудно найти корни уравнений (5.23), (5.20), учитывая зависимости (5.25). Если же окажется, что в поле GF(2*) не существует кубического корня из Vi (или, что то же самое, - из v2), то уравнения (5.20), (5.23) и (5.26) не имеют трех разных корней в этом поле.

Пример 5.9. Поясним изложенный метод на конкретном примере. Задавшись тремя значениями: Xi = 4, Х2 = 2, х = 6, составим кубическое уравнение (х + 4) (х + 2) (х + 6) =0 над полем GF(2). После очевидных преобразований получим (с учетом табл. 3.5) следующее уравнение, принимаемое за исходное:

л: + 7л: + 10л:+10 = 0, GF(2), (5.35)

т. е. Л = 7; б =С = 10.

Как было показано вьдне, подстановка типа х = а zyJA + в =

= а + z\fa приводит заданное уравнение к каноническому виду (5.26), где Е определяется формулой (5.27).

В данном случае л: = 7 + 5z, £ = 11. Так какТг(1) = 0 = Тг(1/£) = = Тг(6), GF(2), то необходимое условие (5.29) возможности существования трех разных корней у уравнения (5.26) соблюдаются.

Очередная подстановка z = -V-/v = -ew +"-£vv дает квадратное уравнение (5.33), где d = 1/ = 11. Из табл. П.З выбираем один из корней, соответствующих параметру Z) = 11 GF(2), например w = 3. Тогда

i;=£w= 13; ы =е [5, 10, 15; z = (м+ 1/м) G (l4, 6, s} ; а =б =9; =5;

y--zsfa е (З, 10, 12} ; л: = (Л +>) G [4, 6,2} ,

что совпадает с заданным набором значений корней.

Пример 5,10. Проиллюстрируем теперь метод решения кубического уравнения при нечетном г. Примем (l, 2, 3) G GF(2) и составим уравнение

3 +6л: +7л: + 4 = 0, Л = 6, 6=7, С = 4, GF(2), (5.36)

которое, как и в предыдущем примере, приведем к каноническим (кубическому и квадратному) уравнениям:

+z +£" = 0; + w + /) =0, = 1. (5.37)

Из табл. П.З следует, что квадратное уравнение при Z) = 1 не имеет решений в поле GF(2). Поэтому будем рассматривать это квадратное уравнение над расширенным полем GF(22* == 2*). Из той же таблицы



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.058