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



найдем wi = 22 G GF(2*). Далее вычислима = l/Ewy G ( 8, 29, 5o} G G GF(2*). Вернуться к исходному полю GF( = 2) и одновременно рассчитать корни кубического уравнения (5.37) можно с помощью следующего, правда, несколько искусственного, приема:

1) использовать формулу z = [м + 1/и]~ = ul{u + 1), GF(2*);

2) привести результат по модулю q - 1=7. Таким образом получаем:

1) 1 = 8/(8 + 1) = 19; Z2 = 29/(29 + 1) = 10; = 50/(50 + 1) = =t37, GF(2*);

2) zi = 19 = 5; z2 = 10 = 3; z3 = 37 = 2 mod 7.

Наконец, с помощью перехода х - А z\JВ + Л = 6 + 3z найдем множество {2, 1, з] корней уравнения (5.36), совпадающее с заданным.

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

Табличный метод Каноническое уравнение (5.26) третьей степени содержит всего один параметр Е. Следовательно, как и для квадратных уравнений, можно составить таблицы некратных корней уравнения (5.26) в функции от единственного параметра. И в данном случае лишь некоторым из величин Е соответствуют точно три неравные kopin в поле GF(2 ) для указанного кубического уравнения. Количество Му "рабочих" значений Е может быть рассчитано по рекуррентной формуле

М;. =2М 1+m(r), Ml = О,

где т{г) - функция нечетности, i.t.mij) =0 при четных г иm(г) = = 1 - при нечетных.

В частности, имеем - О, М- - Х.М = 2, М5 = 5,71/ = 10,717 = = 21,8 = 42, М9 = 85.

Простые корни уравнения (5.26) для ряда конечных полей GF(2 ) небольших размерностей сведены в табл. П.4. Адресным "входом" в эту таблицу является параметр Е, Конечно, в памяти достаточно хранить лишь пару корней z\ z", а третий - определять из соотношения z" = z + z", так как сумма всех трех корней равна нулю - коэффициенту при отсутствующем члене z в уравнении (5.26).

Факторизация кубического полинома. Объем памяти, хранящей значения корней, можно существенно сократить, если оставить в таблице лишь один корень. Пусть zj - корень уравнения (5.26),т. е. zf + zi = Тогда кубический полином из левой части указанного уравнения факторизуется следующим образом [54]:

z + z + £ = z + z + z? +Zi = (z + zi) (z + zjz + z + 1). (5.38)

Корни полинома второй степени в последнем соотношении находятся с помощью метода, изложенного в § 5.1:



1) с помощью замены переменной z = zg получают каноническое (относительно g) уравнение g + + Z) = О, где Л = 1 + z ;

2) по параметру D находят, например, из табл. П.З корни g и g"

(или один из них) ;

3) искомые kojffiehz, z" полинома второй степени восстанавливают

исходя из соотношения z ~Zig.

Таким образом, [zi, z2 - zg, z3 = zi (g + 1)} - и есть полнее множество корней уравнения (5.26).

Пример 5.11. Вновь рассмотрим для примера уравнение (5.35) или соответствующее ему при х = 7 + 5z каноническое уравнение z + z + + 11 = О, GF(2*). Из табл. П.4 для поля GF(2*) по Е = 11 находим z = 6, z" = 8, z" - 14. Пусть известен лишь один из этих корней, например zi = z = 6. Факторизация кубического полинома дает

z + z + 11 = (z + 6) (z + 6z + 6),

где учтено, что z? + 1 = 6 + 1 = И, GF(2*).

С помощью подстановки z = 6g перейдем к каноническому квадратному уравнению g + + Z)=0, где Z) = И G GF(2*). Используя табл. П.З, для поля GF(2*) npuD= 11 можно определить корни полиномов над полем GF(2*):

канонического квадратного g + + 11= (+3)( + 9);

вспомогательного квадратного z + 6z + 6 = (z + 8) (г + 14), так как zi 3 = 8; zi 9 = 14;

канонического кубического z + z + £ = (z + 6) (z + 8) (z + 14) ;

исходного кубического + 7x + lOx + 10 = (x+ 6) (x+ 2) (x+ 4), где учтено, что x = 7 + 5z, т. е. 7 + 5 • 6 = 6; 7 + 5-8=2; 7 + 5*14 = 4, GF(2).

Орбитальные представления. Как и для квадратных уравнений, можно сжать таблицы корней кубических уравнений, перейдя к орбитальным представлениям. Напомним, что условие (5.29) для следов, не исключает возможности существования у канонического уравнения (5.26) трех неравных корней. Выбирая из табл. 3.14 ведущие элементы 1/, удовлетворяющие указанному условию следов, можно составить таблицу орбит. Однако некоторым из этих орбит могут соответствовать и неразрешимые над полем GF(2 ) уравнения.

Другой подход основан на связи параметров Е и D ~ свободных членов в канонических формах соответственно кубического (5.26)

и квадратного (5.3) уравнений. Выше было показано, что Я = zf + z aZ) = 1 + z7. Исключаяzi, выразим параметре через!):

£=Z)/(1 +D)/

(5.39)

Заметим, что ПФ1, так как z фQ

Итак, в предположении, что Тг(1/£) = Тг(1), а уравнение (5.26) имеет корень zi G GF(2 ), мы установили, что пара оставшихся нерав-



ных корней кубического уравнения, совпадает с корнями квадратного полинома в последних скобках выражения (5.38). При этом параметры е и d оказываются связанными соотношением (5.39). Подставляя в формулу (5,39) значения Z)h3 табл. П.З или из сжатой табл. 5.2, можно получить значения для параметра е, собранные в табл. П.4 и в сжатой

абл. 5.3. В этих же таблицах приведены соответствующие значения ]:орней. Важно подчеркнуть, что ведущие элементы d циклоклассов, собранные в табл. 5.2, не обязательно отображаются формулой (5.39) также в ведущие элементы е циклоклассов. Однако для удобства использования в табл. 5.3 орбитальные представления приведены к ведущим элементами соответствующих циклоклассов.

В заключение поясним, как пользоваться табл. П.4 и 5.3. В предыдущем примере мы имели параметр е = ii g GF(2). Из табл. П.4 для поля GF(2 ) сразу найдем три уже известных корня, образующих множество ( 6, 8, 14} . Если бы в этой таблице значения е -11 не оказалось, то это означало бы, что уравнение + z + £- О не имеет трех

неравных корней в поле GF(2).

В сжатой табл. 5.3, содержащей лишь орбитальные представления, значения е = ii нет; однако это значение лежит в том же циклоклассе,

таблица 5.s

Орбитальные представления параметра е и корней z , z , z уравиения +z +е = О над полем GF(2), г = 3... 9

2 31

102 87

64 86 92 128

34 171 106 174

57 188 116

230 239 127 237



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