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



4)ормула (3.14) дает элемент, принадлежащий множеству К. Такие элементы определяются соотношением

Ь = Т/+ l,moda& , где ; = ОЛ,..., " 1.

(3-15)

Подставляя это выражение b в числитель дроби (3.14), найдем при О одно из значений корня:

(3.16)

О, 1,. ., , - 1; v-/t].

для каждого /

Остальным значениям корня соответствуют такие величины / в формуле (3.14), при которых аь / нацело делится на Т. Такими будут i ~ (Т/7?)г 1, где ii = О, 1, 2,. . . , - 1. Учитьшая это соотношение для i и переобозначая ii как г, окончательно получим следующее выражение для значений корня степени Т > О из элемента b (3.15) :

/ + 1 + v/,

(3.17)

где / = О, 1,. . , , - I; / = О, 1,. . . , 7? - 1.

Например, при Т = 12, = 2* имеем X = - 1 = 15, т? = НОД (Э£ , Т) = 3, = X /т? = 5, / = О, 1,. .., 4; / = О, 1, 2, так что для элементов Ь = Т/ + 1 находим следующие значения корня а = \/:

(3.18)

Та же самая совокупность значений корня а формируется и при

других степенях Т, таких, что НОД («, , Т) = 3, т. е. при Т, равном

3, 6, 9. Но конкретные значения а соответствуют разным величинам

аргумента Ь: например, Д Е [ 2, 7, 12) для -Т, -/То, /lY -

см. табл. 3.3.

Представим соотношения (3.15) и (3.17) в показательной форме, также используемой далее:

значение аргумента Ь Е /С, из которого может быть извлечен корень степени Т при НОД ( , Т) 1,

b - а

; = О, 1,.. . , - 1;

(3.19)

значение корня а ЕК

О, 1,.

т?- 1,

(3.20)



где а - примитивный элемент циклической группы; =11,2,..., =

1} ; z = /7?; 7? = НОД («, ,Т). Рассмотрим для примера извлечение кубического корня при = 2;

г - атуральное число.

Докажем вспомогательное утверждение. Если г - число четное, то q - \ н- це о дг литя на 3, а если нечетное - не делится.

Оценим остаток rest от деления 2 на 3, где к~ произвольное нату-алыюе число. Для каждой пары двоек rest (2-2) : 3 = 1. Поэтому

2 ~ 1 mod 3 при четных к\ 2 = 2 mod 3 при нечетных к.

Следовательно, при г - 2к всегда

{2 " 1) = {2 - 1) (2 + 1) = О mod 3,

так как либо первый, либо второй сомножитель кратен трем. При нечетных г всегда rest (2 - 1) : 3 = 1 0.

Пусть необходимо вычислить где =1,2, =

= 2 " l) . Если г нечетно, то т? = НОД (X , 3) = 1, так как ае, на Т = 3 нацело не делится. В результате а = Е К для любых причем значение а единственно и может быть найдено по формуле (3.14). Если же г ~ четное число, то т? - НОД (дб , 3) 1 и извлечение кубического корня возможно лишь из элементов Ь, удовлетворяющих соотношению (3-15) япя аналогичному соотношению (3.19). При этом корень имеет три значения, определяемых формулами (3,17) или

(3.20).

В заключение напомним, что квадратный корень всегда извлекается из любого элементах поля GF(2) и принимает единственное значение а G К, совпадающее с л: - г5(х - 1) + 1 - X г, где т5 = 2 ~, а г подбирается так, чтобы \/х~ = X G А.

3.3. ОПЕРАЦИИ НАД РАСШИРЕННЫМИ ПОЛЯМИ

ГАЛУА ХАРАКТЕРИСТИКИ 2

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

Наибольшее распространение получили следующие способы представления элементов поля характеристики 2: в виде десятичных номеров-чисел /V (модифицированных логарифмов Log), степеней а примитивного элемента а, логарифмов log (а) по основанию а, функций



Якоби- Зеха (обычных и модифицированных), двоичных векторов и полиномов, разложения по нормальному базису и др. [35, 36].

В табл. 3.4 .. . 3.6 приведены перечисленные варианты представлений для полей GF(2) небольших размерностей г = 2 ... 5.

Условно можно выделить два вида представлений

в полярных

или в прямоугольных координатах. В таблицах к полярным координатам отнесены степенное и родственные ему различные логарифмические представления, а к прямоугольным - тесно связанные друг с другом полиномиальное и векторное представления.

Связь степенного и логарифмического представлений не требует особого комментария. Достаточно отметить, что логарифмы берутся по основанию а, поэтому они равны степени элемента а. (Бесконечные степени и логарифмы, конечно же, используются просто лишь как символы.)

Ненулевые элементы поля образуют циклическую группу порядка 2 - 1 (мультипликативную группу). Подобные группы были рассмот-

Представленияполя 0¥{2),х = х + 1, г = 2, 3

Таблица 3.4

Канонический базис

Нормальный базис

(примитивный)

Полярные координаты

Прямоугольные координаты

Поляр-

Прямо-

Деся-

Степень

Логарифм

loga

Функ1щн Зеха

-------1

Двоич-

Полином

ные коор-

угольные

тичный номер

Обычные Log

Модифицированные L

ный вектор

2 1 0

а а а

1 - г- 1 . .

i - 0

динаты

координаты

4 2 1

7 7 7

11), 7-

of" а

хл- 1

3,сз= (ОН), у =

0 0 1

1 1 1

0 1 0

1 1 0

1 0 0 0 1 1

х х+ 1

1 0 1 0 0 1

1 1 0

х л- X

0 1 1

1 1 1

1 0 1

+ x+ 1

1 0 0 0 1 0



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