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



+z + 15 =0, GF(2), я = а5 + а2+1 (5 17)

Для того чтобы формула (5.16) давала правильные результаты, Необходимо, чтобы след свободного члена D = 15 был равен нулю. Однако мы не будем рассчитывать Tr(D), а найдем величину Zi по формуле (5.16), проверив затем, является ли Zi корнем уравнения (5.17).

Воспользовавшись формулой (5.16), найдем

zi =/)2(1 +/)*) = 15 [1 + (152)1 =

= 29 (1 +29) =29(1 +23) =291(23) = 29 • 8 = 5 = (1 О О О 0),

где учтено значение модифицированного логарифма из табл. 3.6. Непосредственная подстановка подтверждает [81 Zi = 5 - корень уравнения (5.17). Второй корень находится инвертированием младшего разряда в -представлении первого корня:

Z2 = (10001)а =11.

ь ч

Пример 5.5. Предположим теперь, что г = 2. Тогда (г - 6)/4 = - 1, т. е. верхний предел i =~1 изменения / меньше нижнего / =0, следовательно,

Б . .. = О и Zi = д (см. табл. 5.1).

i е J

Для рассматриваемого поля GF(2), г = 2, имеем (г - 2)/2 = О,

1 = 2 - 1 = 3, 2" = 2 (во всех случаях вычисления выполняются по правилам обычной алгебры) и Г4 (D) = D.

Из табл. 5.1 следует, что если D = О, т. е. (D) = О, то Zi = а = О, а если D = 1, т. е. Г4 (Z)) = 1, то Zi = д = 2 = 2. При других значениях/) квадратное уравнение (5.3) нaдGF(2) корней не имеет.

Рассмотрим вариант, когда г кратно четырем. В простейших частных случаях при г, равном 4, 8 и 12 из соотношений табл. 5.1 можно получить следующие выражения для корней:

GF(24), zi =gDf +/)Р =g + [D?(l +Dl)] (5.18)

GF(28), zi =+/)p+/)i + /)12 + /)p2; GF(2*2), Zj = g + Df(Di +Dt +D\) +

+ +Di"» +/)fl3+/)/026 +£,516 +7)1032

где /)i = D + + 2 ; = 0 при Г4 (/)) = 1; если же Г4 (D) = О, то g e E GF(2 ), где I - элемент, след которого равен 1.

Так, для уравнения (5.10) cD= 6 имеем: =Z)= 6,D =Z)® = 11, Tt(D) = D + +/)4 +/)« = 6+11 + 6 + 11=0. Выберем из табл. ЗЛ4



элемент g = 4, для которого tt(g) = 1. Тогда g g = 4 + 42 = 4- (1 + + 4) = 41(4) = 4 . 15 = 3; согласно табл. 5.1 di = d-g =6 + 3 = 2, GF(2). Из формулы (5.18) следует

zi = я + Р?(1 +/)i)]* = 4+ [2(1 + 2)] =4 + 10 = 4(1 + 7) =

= 4- 14 = 2, GF(24).

Табличный метод. Предположим, что z и z" являются корнями уравнения

z +Z +/) =0, GF(g). (5.19)

Согласно теореме Виета [33] z + z"=-l,z*z"=Z). Таким образом, подбирая пары элементов заданного поля g¥{q) так, чтобы их сумма была равна -1, а для поля характеристики 2 - равна 1, можно составить таблицы, "входом" в которые являются произведения корней d = Z • Z .

Простые корни для ряда конечных полей небольших размерностей

сведены в табл. П.З. Конечно, при р = 2 в памяти достаточно хранить

лишь одно значение корня, а второе - получать путем инвертирования

младшего разряда.

Если же окажется, что соответствующего значения d в таблице нет

(на выходе запоминающего устройства, хранящего таблицу корней,

появится строго определенный фиксированный сигнал, например набор

из г нулей, но при условии, что d ф 0), то делается вывод: уравнение

(5.19) в заданном поле GF (q) решений не имеет.

Нетруддо заметить, что корни (z, z") е GF(2 ) можно рассматривать как пару (Л, l), r}xqn=l + 1,n- модифицированный логарифм; l - модифицированная функция Якоби - Зеха ~ см. § 3.3.

Например, в табл. П.З для поля GF(2®) отсутствует значение Z)= 22, следовательно, уравнение (5.11) не разрешимо над GF(2®). Для этого же поля значению d = 207 соответствуют корни z = 231 и z" = 232, полученные вьш1е другим способом.

Как уже отмечалось, в любом поле gf(q = р ) при d = о уравнение (5.3) имеет пару корней: z = О и z" = -1. Если характеристика поля р равна двум, то z = 1, в остальных случаях значение этого корня должно быть поразрядно приведено по модулю р (после соответствующего г-разрядного представления). Так, для простых полей GF( = 3), gf(q =5) соответственно получим z" = -1=2 mod 3, z" = -1=4 mod 5 и т. п.

Аналогично для поля GF( - ) имеем -1 = -(0...01) = (0... О- 1) = (0...0 V), где V =р- 1.Например,-1 =-(0001) = (0002) =

= 41, GF(3*); -1 = -(01) = (06) = 25, GF(7) - см. представления

элементов соответствующих полей на рис. 3.2.

Орбитальные представления. В табл. П.З значения параметра d

и корней z, z" квадратного уравнения (5.3) упорядочены по нараста-



нию их величин (имеется в виду упорядочение десятичных номеров элементов О, 1, 2, q - I - их модифицированных логарифмов). Однако они могут быть упорядочены и по другому принципу. Действительно, пусть Zi - корень уравнения (5.3) при данном значении D,

т. е. ZI

нения z

+ Zj + D =0. Тогда вследствие тождества (д + Ь)

а + b

раведливого для полей характеристики 2, корнем аналогичного урав-------2 + +/)2 Q jjpj свободном члене D будет z?, так как zf +

+ Zj + D = 0. (Сформулированное утверждение является частным случаем теоремы орбит - см. § 5.5.) В результате значения Пи z\ z" для полей GF(2) могут быть сгруппированы так, чтобы они образовали циклоклассы из табл. 3.14. Следовательно, табл. П.З может быть сжата. В табл. 5.2 приведены ведущие элементы Z), образующие указанные циклоклассы, и соответствующие им корни z, z"; причем для простоты опущены значения Z)=0, z=0hz" = 1. Подобные представления в работе [54] названы орбитальными.

Пример 5.6. Приведем иллюстрирующий пример для поля GF(2). В этом поле имеются три циклокласса (см. табл. 3.14) с ведущими ненулевыми элементами 1, 2 и 6, для которых след равен нулю. Параметрам D = 1, 2 и 6 (табл. П.З) соответствуют корни (6, 11), (8, 10) и (2, 5). Таким образом, орбитальные представления для поля GF(2*) расшифровываются следующим образом:

6 111

8 15 14 Г

(и);

10 4

7 13

Это означает, например, что при!) z" = 10; при Л = 2 = 3 - корни z и т. д.

2 уравнение имеет корни z = 8, 82 = 15, z" = 10 =4 GF(2)

Мы не будем здесь анализировать закономерности, связывающие величину Z), т. е. циклокласс (D, , . . ., , t> = 2 - 1, со значениями корней z\ z". Отметим лишь, что в полях GF(2) с четными числами г при D - 1, т. е. при длине циклокласса, равной 1, корни z, z" квадратного уравнения (5.3) принадлежат циклоклассам длины 2. HailMMep, из табл. 3.14 следует, что при г - 2 z\z" Е \2, з} ; при г = 4 z, z" G [б, ll} ; при г = 6 z\z" е [22, 43) ; npHr = 8z,z" 6 (зб, 17l}. Эти значения корней совпадают с величинами, представленными в табл. 5.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