Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 34

Под вычитанием ( a - b ) понимается  a + ( - b );под делением

( a / b ) понимается (b^-1)*a.

Широко известны следующие примеры полей:

1) R : множество вещественных чисел;

2) C : множество комплексных чисел;

3) Q : множество рациональных чисел;

Все эти поля содержат бесконечное множество элементов.Мы интересуемся полями с конечным числом элементов.

Поле с q элементами,если оно существует,называется конечным полем или ПОЛЕМ ГАЛУА и обозначается через GF (q).

Что представляет собой наименьшее поле? Оно обязательно содержит нулевой элемент и единичный элемент.На самом деле этого уже достаточно при следующих таблицах сложения и умножения:

+│0 1      *│0 1

─┼───      ─┼───

0│0 1      0│0 0

1│1 0      1│0 1

Это поле GF(2),с которым мы будем иметь дело.

ОПРЕДЕЛЕНИЕ.Пусть F - некоторое поле.Подмножество в F называется

ПОДПОЛЕМ,если оно само является полем относительно наследуемых из F

операций сложения и умножения.В этом случае исходное поле F называется РАСШИРЕНИЕМ ПОЛЯ.

МНОГОЧЛЕНОМ ( ПОЛИНОМОМ ) над полем GF(q) называется математическое выражение

f(X) = fn-1 * X^(n-1) + fn-2 * X^(n-2) +...+ f1 * X + f0, где символ X называют НЕОПРЕДЕЛЁННОЙ (фиктивной)переменной,коэффициенты fn-1,...,f0 принадлежат полю GF(q),а индексы и показатели степеней являются целыми числами.

НУЛЕВЫМ ПОЛИНОМОМ называется полином f(X) = 0.

ПРИВЕДЕННЫМ ПОЛИНОМОМ называется полином,старший коэффициент fn-1

которого равен 1.

СТЕПЕНЬЮ ненулевого полинома f(X) назыается индекс старшего коэффициента fn-1;степень номинала f(X) обозначается через deg f(X).

НЕПРИВОДИМЫМИ назыаются полиномы,которые не могут быть представлены в виде произведения полиномов низших степеней с коэффициентами из того же поля.

Приведённые неприводимые полиномы называются ПРОСТЫМИ.

Для произвольного приведённого полинома p(X) ненулевой степени над полем F КОЛЬЦОМ ПОЛИНОМОВ ПО МОДУЛЮ P(X) называется множество всех полиномов над F,степень которых не превосходит степени полинома

p(X),с операциями сложения и умножения полиномов по модулю p(X).

Кольцо полиномов по модулю приведённого полинома p(X) является полем тогда и только тогда,когда полином p(X) прост.

В качестве примера построим поле GF(4) по полю GF(2),используя полином p(X) = X^2 + X + 1 .

Этот полином неприводим.Элементы поля задаются полиномами {0,1,X,

X+1}.Кроме того они могут быть представлены в другом обозначении:

Полиномильное    Двоичное     Десятичное    Степенное обозначение     обозначение   обозначение   обозначение

0               00            0             0

1               01            1            X^0

X               10            2            X^1

X+1              11            3            X^2

Арифметические таблицы (сложения и умножения) будут иметь вид:

+ │ 0    1    X    X+1              * │ 0    1    X    X+1

───┼───────────────────             ───┼───────────────────

0 │ 0    1    X    X+1              0 │ 0    0    0    0

1 │ 1    0    X+1  X                1 │ 0    1    X    X+1

X │ X    X+1  0    1                X │ 0    X    X+1  1

X+1│ X+1  X    1    0               X+1│ 0    X+1  1    X

Элемент B называется КОРНЕМ полинома p(X) или КОРНЕМ уравнения

p(X) = 0,если p(B) = 0.

Полином не обязательно имеет корни в своём собственном поле.

ОПРЕДЕЛЕНИЕ.ПРИМИТИВНЫМ ЭЛЕМЕНТОМ поля GF(q) называется такой элемент a,что ве элементы поля,за исключением нуля,могут быть представлены в виде степени элемента а.

Например,в поле GF(5) 2^1 = 2, 2^2 = 4, 2^3 = 3, 2^4 = 1,так что

2 является примитивым элементом поля GF(5).

ОПРЕДЕЛЕНИЕ.ПРИМИТИВНЫМ ПОЛИНОМОМ p(X) над полем GF(q) называется простой полином над FG(q),такой,что в расшрении поляБпотроенном по модулю p(X),соответствующий полиному X элемент является ПРИМИТИВНЫМ.

ОПРЕДЕЛЕНИЕ.Пусть GF(q) - некоторое поле,пусть GF(Q) - расширение поля GF(q),и пусть В - элемент GF(Q).простой многочлен f(X) наименьшей степени над GF(q),для которого f(B) = 0,называется МИНИМАЛЬНЫМ

ПОЛИНОМОМ элемента В над GF(q).

Примитивные и минимальные полиномы определяют с помощью таблиц.