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



Таблица 5.2

Орбитальные представления параметра D и корией z , z уравнения

+ z +D=0 над полем GFCZ), г = 2... 9

12 19

246 241



18 22 32 38 46 54 56 58 60 62 64 74 86 88 92 94 104 108 120 124 126 128 192 256

60 71 177 260 107 61 195 144 210 405 224

147 196 204

166 42 138 273 173 136 49 199 310 294

470 463 367 290 451 505 373 426 362 169 352 439 402 396 438

53 478 347 459 500

78 441 394 474

+ + 1,

Пример 5.7. Решим над полем GF(2®), я(х) уравнение (5.1) с параметрами (3.25) . .. (3.27). Представим заданное уравнение в приведенной форме: 115 (V + 182л: + 30 = 0). Полагая х = = 182z, перейдем к уравнению (5.3) с параметром = 178, которому в табл. П.З соответствуют корни 75 и 104. Но мы хотим продемонстрировать использование орбитального метода. Значения Z) = 178 G GF(2*)

в табл. 5.2 нет. Образуем элементы из циклокласса, содержащего D. Имеем: 178 = 142; 178* = 142 = 199; 178« = 199 = 142: 178* = = 142 = 28. Значение Z) = 28 есть в табл. 5.2; ему соответствуют величины z = 119hz" = 165.

Вычисляя значения для 119*** и 165***, учтем следующее. Так как

= 8,тоа*/* =

для поля GF (X ) = а при Ь = 2, т. е. а

а при г



= а Следовательно, 119 = 237; 119"* = 218; 119 = 180; 119** = = 104 = Zi; 165 =74; 165 = 147; 165» =38; 165** =75=2.

Возвращаясь к исходной переменной х, найдем искомые корни: Xi = 182 Zi = 30; Х2 = 182 Z2 = 1. Проверка: (х + 30) (д: + 1) = = л: + (1 +30)л:+30. Из табл. П. 1 находим 30) = 182.

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

5.2. КУБИЧЕСКИЕ УРАВНЕНИЯ

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

зх +2: +1 +0 = О, аэфо

х +ах +iBx + C=0,

гдеЛ=у12Мз; b~ailas\ сао/а. С помощью замены переменной

х-у-а/з

уравнение (5.20) приводится к виду [33]

(5.20)

(5.21)

У+ (б~ ~А)у-(с А- 1аВ)=0, (5.22)

3 27 3

т. е.

у -ау ь=0.

(5.23)

Данное преобразование справедливо для любого поля, характеристика которого отлична от трех, иначе подстановка (5.21) не имеет смысла, так как 3 = 0 mod 3.

При а ф о новая подстановка у = \/a~z сводит уравнение (5.23) к каноническому виду:

(5.24)

z +Z +£" = 0, e = b/a; а=в ai Ь = С+(23)/27- {ав)/3.

Если же а = О, то уравнение (5.23) имеет три равных корня: 2,э = Ь , при условии, что данный кубический корень существует, например, для поля комплексных чисел.

Нас интересуют кубические уравнения над полями характеристики 2. Для таких полей ~Л=Л,3 = 1,2 = 0 mod 2, поэтому из соотношений (5.21) .. . (5.24) следует 202



= уУА, аВ уА, ь=С-уАВ, +а> + Ь=0,

, ,-1 } (5.25)

y-\Jaz приа =90, т. е. x,= z\/B +Л;

+ Z +£ = 0, GF(2),

(5.26)

Eblal = (C + 6)/v(J+7v (5.27)

Заметим, что подстановка х ~ {А y/W)zi + GF(2 ) приводит уравнение (5.20) к иной канонической форме z? + + £ = О с одним параметром Е, также определяемым соотношением (5.27). Однако далее мы будем работать с формой (5.26), так как Zi = z + 1.

Если £ = О, то уравнение (5.26) имеет один нулевой корень и два

равных корня -уЧ . Так как коэффициент при z в левой части уравнения (5.26) равен нулю, то по теореме Виета сумма корней также равна нулю. Поэтому кубическое уравнение (5.26) над полем GF (2) не может содержать точно два корня в этом поле [54]. Таким образом, возможны следующие варианты: уравнение (5.26) имеет в заданном поле GF(2) либо все три корня, либо только один корень, либо вообще не имеет корней.

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

Следующее утверждение [51] позволяет "отсекать" нерабочие варианты, когда кубическое уравнение соответствует более чем трем ошибкам.

Утверждение 5.2. Кубическое уравнение (5.26) имеет единственное решение z G GF (2 ) тогда и только тогда, когда

Тг(1/£) ?Тг(1).

Следствие. Равенство Тг(1/£) ф Тг(1)

(5.28)

(5.29)

является необходимым условием для того, чтобы все три корня уравнения (5.26) лежали в поле GF(2).

Подчеркнем особо, что равенство (5.29) является лишь необходимым (но далеко не достаточным!) условием. Например, из табл. 3.14

видно, что npnG (l, 6 = 1/11, 8 1/9, 11 = 1/6, 12 = 1/5, 14= 1/3, 15 = l/l] выполняются равенства Тг(1/£) = О = Тг(1), GF(2*). Однако лишь при Е = в и Е = И уравнение (5.26) имеет в поле GF(2) три различных корня - (11, 12, 15) и (6, 8, 14), в то время как при Е G G \l, 8, 12, 14, 15} ~ не имеют ни одного. В сказанном можно убедиться хотя бы прямым перебором всех 16 элементов поля GF(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.0113