Файл: прикладная теория информации.pdf

147
Пример 8.22. Пусть ???? ‒ это конечный набор символов (алфавит). Напри- мер, ???? ‒ множество символов белорусского алфавита, или ???? – двоичное множе- ство {0, 1}. Слово символов из множества имеет вид ????₁, ????₂, …, ????
????
, где
????
????
∈ ????. Пусть ???? обозначает множество слов алфавита ????. Введем бинарную опе- рацию ○, называемую конкатенацией над ???? следующим образом: если ????₁, ????₂, …, ????
????
и ????₁, ????₂, …, ????
????
∈ ????, то ????₁, ????₂, …, ????
????
○????₁, ????₂, …, ????
????
= ????₁, ????₂,
…, ????
????
, ????₁, ????₂, …, ????
????
Например, если ???? = {0, 1}, то 11011 ○ 1010110 = 110111010110.
Пусть ????₁, ????₂, …, ????
????
, ????₁, ????₂, …, ????
????
и ????₁, ????₂, …, ????
????
∈ ????. Тогда (????₁, ????₂, …, ????
????
○
????₁, ????₂, …, ????
????
) ○ ○ (????₁, ????₂, … , ????
????
) = (
????₁, ????₂, …, ????
????
????₁, ????₂, …, ????
????
) ○ ????₁, ????₂, …, ????
????
=
????₁,
????₂, …, ????
????
, ????₁, ????₂, …, ????
????
????₁, ????₂, …, ????
????
. Бинарная операция конкатенации ассоциа- тивна на множестве ???? и это множество вместе с операцией конкатенации обра- зует полугруппу.
Кольцо можно определить и так: кольцо ???? является группой относительно операции сложения и полугруппой относительно операции умножения. В кольце для операции умножения могут не выполняться аксиомы существования нейтрального и обратного элементов группы.
Рассмотрим примеры колец.
Пример 8 .23. Все действительные числа ℝ образуют кольцо относи- тельно операций сложения и умножения.
Пример 8 .2 4. Алгебраическая система целых чисел < ????; +;⋅>.
Пример 8.2 5. Множество квадратных матриц размером ???? × ????. Нейтраль- ным элементом относительно операции умножения в кольце матриц является единичная матрица.
Пример 8 .26. Кольцо целых чисел ℤ по модулю ????. Например, ???? = 14.
Тогда система < {0, 1, 2, … , 13}; +;⋅; 0; 1 > ‒ кольцо, в котором для элемента 2 не существует обратного элемента, т. к. 2 ⋅ 2
−1
≠ 1 mod 14.
8.4.1. Идеал кольца
Определение 8.14. Пусть ???? ‒ кольцо, а ????
′
есть подкольцо ‒ подмножество множества ????. Подкольцо ????
′
определяется операциями кольца.
Рассмотрим примеры подколец.
Пример 8. 27. Целые числа ℤ образуют подкольцо кольца рациональных чисел
{ℤ = 0, ±1, ±2, … , }; +;⋅; 0; 1 >.
Пример 8. 28. Рациональные числа образуют подкольцо кольца действи- тельных чисел ℝ.
Пример 8 .29. Действительные числа ℝ образуют подкольцо кольца ком- плексных чисел.
Пример 8 .30. Множество квадратных матриц размером ???? × ???? c целыми значениями элементов образуют подкольцо кольца матриц размером ???? × ????

148 с рациональными элементами.
Определение 8.15. Подмножество ???? элементов кольца ???? называется идеа- лом в ????, если выполняются следующие условия:
‒ ???? является подкольцом кольца ????, т. е. для любого множества {????, ????} ∈ ???? выполняется (???? + ????) ∈ ???? и ???? ⋅???? ∈ ????;
‒ для любого элемента ???? ∈ ???? и любого элемента ???? ∈ ???? произведения ???? ⋅ ???? и
???? ⋅ ???? принадлежат ????.
8.4.2. Главный идеал
Определение 8.16. Пусть ???? ‒ коммутативное кольцо. Идеал ???? кольца ???? называется главным идеалом, порожденным элементом ???? (обозначается < ???? >), если ???? состоит из всех произведений ???? на элементы кольца ????, т. е.
???? = < ???? > = { ???? ∙????: ???? ∈ ????}.
Теорема 8.9. Совокупность целых чисел ℤ образует главный идеал тогда и только тогда, когда она состоит из всех чисел, кратных некоторому числу.
Пример 8 .31 . Множество целых чисел ℤ = {0, 1, 2, 3}
4
является коммута- тивным кольцом с единицей. Найти главный идеал кольца ℤ.
Решение. Если ???? ‒ минимальное целое число из ????, то по определению иде- ала ???? = ????·????. Выберем в качестве ???? = 2, т. е. ???? = < 2 >. Тогда элементы множества всех чисел, кратных ????, запишем в виде ???? = < 2 >:
0
⋅ 2 = 0; 1 ⋅ 2 = 2; 2 ⋅ 2 = ((0))
4
; 3 ⋅ 2 = ((2))
4
Тогда главный идеал есть ???? = < 2 > = {0, 2}.
Пример 8 .32 . Задано кольцо целых чисел ℤ. Построить главный идеал, порожденный целым числом 8.
Решение. < 8 > = {8????: ???? ∈ ℤ} = {…, – 48, – 40, ‒ 32, ‒ 24, ‒ 16, ‒ 8, 0, 8, 16,
24, 32, 40, 48,…}.
Замечание. Если имеются главные идеалы < ???? > и < ???? > целых чисел ℤ, то их пересечение < ???? > ∩ < ???? > является наименьшим общим кратным
(HOK (????, ????)) чисел ???? и ????, т. е.
< ???? > ∩ < ???? > = < HOK (????, ????) >.
8.4.3. Кольцо полиномов
Рассмотрим кольцо вида ????
????
=
????(????)
????
????
‒1
, состоящее из класса вычетов кольца полиномов ????(????) по модулю полинома ????
????
‒ 1.

149
Определение 8.17. Идеалом ????
????
кольца ????
????
называется линейное подмноже- ство полиномов от ???? такое, что если ????(????) ∈ ????
????
, то ????(????) ⋅ ????(????) ∈ ????
????
для всех
????(????)
∈ ????
????
Пример 8.33 . Пусть ???? = 3. Подмножество полиномов вида ????
????
= {0, (1 +
+
????), (???? + ????
2
), (1 + ????
2
)} есть идеал в ????
3
. Действительно:
‒ подмножество замкнуто относительно сложения (линейно). Например, (1
+
????) + (1 + ????
2
) = (
???? + ????
2
)mod (????
3
‒ 1);
‒ выполняется условие ????(????) ⋅ ????(????) ∈ ????
????
. Например,
????
2
(1 + ????
2
) = ????
2
+
+????
4
≡ (???? + ????
2
)mod (????
3
‒ 1).
8.5. Конечные поля
Определение 8.18. Полем называется коммутативное кольцо с единицей, каждый элемент которого имеет обратный элемент относительно умножения.
Определение 8.19. Поле ‒ это множество элементов, над которыми заданы две бинарные операции (сложение, умножение) и для них существуют обратные операции (кроме деления на ноль), причем умножение дистрибутивно относи- тельно сложения, т. е.
(
???? + ????)???? = ????
c
+
????????, ????(???? + ????) = ???????? + ????
b
Поле ‒ это алгебра <{????}; +; ⋅; ‒ ;:; 0; 1>.
Рассмотрим примеры полей.
Пример 8 .34 . Множество рациональных чисел.
Пример 8 .35 . Множество действительных чисел ℝ.
Пример 8 .36. Множество чисел с ???? элементами, где ???? ‒ простое число.
При построении кодов различного назначения наибольший интерес пред- ставляют конечные алгебры ‒ поля Галуа (Galois Feld – ????????). Эта алгебра названа в честь французкого математика Эвариса Галуа (1811 ‒ 1832).
Конечные поля ????????(????
????
) имеют порядок поля ????
????
, где простое число ???? ‒ это характеристика поля, натуральное число ???? ‒ размерность поля. Порядок поля
????????(????
????
) равен числу элементов поля.
Определение 8.20. Поле ????????(????) называется подполем поля ????????(????
????
)
, если оно содержится в поле ????????(????
????
) и имеет те же операции. Поле ????????(????
????
) называется расширением поля ????????(????) (простого поля).
Например, поле из двух элементов ????????(2) ‒ простое поле порядка 2, а
????????(2 7
) = ????????(128) ‒ его расширение; поле действительных чисел ℝ является расширением поля рациональных чисел.
Замечания:
1. Алгебра (школьная) рациональных чисел ‒ это пример бесконечного поля.

150 2. Целые числа
ℤ бесконечных множеств не образуют поле (результат опе- рации деления двух целых чисел не обязательно является целым числом).
3. При
???? = 1 имеем простое поле ????????(????) с модулярными операциями сло- жения и умножения, т. е. операциями по mod ????.
Для каждого простого ???? существует только одно поле, т. е. правила сложе- ния и умножения, удовлетворяющие всем нужным аксиомам, можно задать только одним способом. Для заданного простого поля ???? элементами поля являются числа 0, 1, …, (???? ‒ 1).
Наименьшее число элементов, образующих поле, равно 2. Это является следствием того, что для каждой операции (сложения и умножения) может быть только один нейтральные элемент.
8.6. Представление элементов конечного поля Галуа
????????(????
????
)
Удобное описание многих вычислительных алгоритмов, процессов поме- хоустойчивого и криптографического кодирования и декодирования реализуется с помощью степенного, полиномиального, векторного и логарифмического представления элементов расширенного поля Галуа.
Элементы поля ????????(????
????
) могут интерпретироваться как класс вычетов по- линомов от ???? c коэффициентами из ????????(????) по модулю неприводимого над полем
????????(????) полинома степени ????.
8.6.1. Арифметика полей Галуа
Пример 8 .37 . Определить основные операции в поле неприводимого над полем ????????(2) полинома ????(????) = 1 + ???? + ????
2
, ???? = 2.
Рещение. Операция сложения в поле ????????(2 2
), элементы которого записы- ваются в виде полиномов, задается в виде табл. 8.10.
Таблица 8.10
Операция сложения в поле полиномов
+
0 1
????
1 +
????
0 0
1
????
1 +
????
1 1
0 1 +
????
????
????
????
1 +
????
0 1
1 +
????
1 +
????
????
1 0
Записывая коэффициенты полиномов над полем ????????(2), получим следую- щее соответствие между полиномами и двоичными векторами (табл. 8.10

151
Таблица 8.11
Полиномы и векторы
Таблица Кэли в поле ????????(2 2
), элементы которого записываются в виде дво- ичных чисел, имеет вид, представленный в табл. 8.1
Таблица 8.12
Операция сложения в поле двоичных чисел
Аналогично построим таблицы умножения элементов поля ????????(2 2
). Опе- рация умножения в поле ????????(2 2
), элементы которого записываются в виде поли- номов, задается в виде табл. 8.13.
Таблица 8.13
Операция умножения в поле полиномов
Таблица умножения, представленная двоичными векторами, имеет вид, представленный в табл. 8.14
Таблица 8.14
Операция умножения в поле двоичных чисел
0 0 0 1
1 0
????
0 1 1 +
????
1 1
+
0 0 1 0 0 1 1 1 0 0 0 0 1 0 0 1 1 1 1 0 1 0 0 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 1 0 0 0
×
0 1
????
1 +
????
0 0
0 0
0 1
0 1
????
1 + ????
????
0
????
1 +
????
1 1 +
????
0 1 + ????
1
????
×
0 0 1 0 0 1
1 1
0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 1 1 0 1 0 0 0 1 1 1
1 0
1 1 0 0 1 1 1 0 0 1

152
Например, элемент таблицы 10 с координатами (01, 11) получен следую- щим образом:
1. Воспользуемся обычным умножением в «столбик» со старшим разрядом числа слева:
1 0 1 1 1 0 1 0 1 1 0 2. Результат умножения приведем по модулю полинома ????(????) (вектора ‒ ко- эффициентов ????(????)):
1 1 0|1 1 1 1 1 1 1 0 0 1
3. Для записи двоичного числа со старшим разрядом числа справа выпол- ним инверсию:
0 0 1|1 0 0.
Получим вектор 1 0.
Теорема 8.10. В расширенном поле ????????(????
????
) полиномов существует при- митивный элемент α порядка (????
????
‒ 1), т. е.
α
(????
????
‒1)
= 1.
Каждый элемент β поля ????????(????
????
) может быть представлен как некоторая степень, т. е. β = α
????
Определение 8.21. Неприводимый над полем ????????(????) полином степени ???? называется примитивным, если его корнем является примитивный элемент α поля ????????(????
????
).
Пример 8 .38 . Полином ????(????) = 1 + ???? + ????
2
неприводим над полем
????????(2).
Этот полином примитивный, т. к. примитивный элемент α поля ????????(????
????
) является корнем полинома ????(????). Действительно,
????
2
≡ (1 + ????) mod(1 + ???? + ????
2
).
Тогда
????(α) = 1 + α + α
2
= 1 + α + 1 + α = 0.
В табл. 8.15 приведены четыре формы представления элементов поля
????????(2 2
). Поле образовано полиномами над полем ????????(2) по модулю неприводи- мого полинома ????(????) = 1 + ???? + ????
2
Порядок элемента α равен 3, т. к.α
(2 2
‒1)
= α
3
≡ 1 mod(1 + α + α
2
).

153
Таблица 8.15
Формы представления элементов поля ????????(2 2
)
Используя разные формы элементов поля можно эффективно производить алгебраические операции в поле ????????(????
????
):
1. Умножение с представлением элементов β поля ????????(????
????
) в виде степеней примитивного элемента α выполняется следующим образом:
β
1
· β
2
= α
????
· α
????
= α
????+????
= ((α
Rest[
????+????
????
]
)), где Res???? [
????+????
????
] ‒ остаток от деления (???? + ????) на порядок ???? примитивного элемента
α поля ????????(????
????
).
Например, используя таблицу 8.15, имеем
α
2
· α
2
= α
4
≡ α
1
mod 3.
2. Деление на элемент поля
Теорема 8.11. Если полином ????(????) степени ???? неприводим над полем
????????(????), то каждый ненулевой полином ????(α) степени не более (???? ‒ 1) имеет един- ственный обратный полином ????(α)
−1
такой, что
????(α) · ????(α)
−1
≡ 1mod ????(α).
Нахождение обратных элементов легко выполнить, если воспользоваться представлением элементов поля в виде степеней примитивного элемента или ло- гарифмов.
Пусть ???? = ????(α) ‒ произвольный элемент поля ????????(????
????
) c коэффициентами из поля ????????(????), т. е.
???? = ????(α) = ????
0
+ ????
1
α + ????
2
α
2
+ ⋯ + ????
????‒1
α
????‒1
Требуется разделить элемент ???? на элемент поля
В виде сте- пени прими- тивного эле- мента
В виде по- линома
В виде дво- ичного числа
В виде ло- гарифма
‒
0 0 0
‒
α
0 1
1 0 0
α
1
α
0 1 1
α
2 1 +
α
1 1 2
α
3
= ????
0 1
1 0 0

154
???? = ????
0
+ ????
1
α
1
+????
2
α
2
+ ⋯ +????
????−1
α
????−1
Для того чтобы найти ???? ????
⁄
, вычислим обратный элемент ????
−1
= 1 ????
⁄
, а затем представим ???? ????
⁄ как
???? ????
⁄ = c·1 ????
⁄ .
Пример8 .39 . Поле образовано полиномами над полем ????????(2) по модулю неприводимого полинома ????(????) = 1 + ???? + ????
2
. Вычислить α (1
⁄
+ α).
Решение. Полиному (1+ α) соответствует α
2
. Тогда
α (1
⁄
+ α) =
α
α
2
= α
−1
= α
3
α
−1
= α
2
= ((1 + α)).
Пример 8 .40. Поле образовано полиномами над полем ????????(2) по модулю неприводимого полинома ????(????) = 1 + ???? + ????
3
. Вычислить √110.
Решение. Вектору (110) соответствует элемент поля α
3
. Квадратный ко- рень √α
3
= √1α
3
= √α
7
α
3
=
√α
10
=
α
5
= ((111)).
8.7. Векторные пространства и подпространства
Определение 8.22. Векторное пространство ???? над полем ???? – это алгебраи- ческая система, удовлетворяющая следующим аксиомам:
1.
???? является аддитивной группой.
2. Для любых двух элементов ???? ∈ ????и ???? ∈ ???? определено произведение ????????.
3. Выполняется аксиома ассоциативности для всех элементов ????, ???? ∈ ????
????(???? + ????) = ???????? + ????????.
4. Если ???? ∈ ????и ????, ???? ∈ ????, то (с + ????)???? = ???????? + ????????.
5. Если
???? ∈ ????и ????, ???? ∈ ????, то (с????)???? = ????(????????).
6.
1 ∙ ???? = ????, где 1 – нейтральный элемент поля.
Определение 8.23. Подмножество ???? векторного пространства ????, удовле- творяющее условиям:
– если ????
1
, ????
2
∈ ????, то ????
1
+ ????
2
∈ ????;
– для ???? ∈ ???? и ???? ∈ ????, ???????? ∈ ????.
Замечание. Кодовые векторы избыточного кода определяют подпростран- ство векторного пространства.

155