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

138
???? = [
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
].
8.1.2. Особые свойства мультипликативной группы
Для мультипликативной группы
< ????;∙> вводится понятие натуральной сте- пени элемента группы
α
0
,
α, αα,…, … , α α α = α
0
,
α, α
2
,…,
α
????
, где ???? ‒ нуль или ???? ∈ ℕ.
Определение 8.3. Группа называется циклической, порожденной элемен- том α, если каждый элемент группы есть некоторая степень α
????
Теорема 8.2. Пусть
< ????;∙> ‒ группа и элемент α ∈ ???? такой, что α
????
= 1 для некоторого целого ????. Если ???? ‒ наименьшее положительное целое число такое, что α
????
= 1, то ????ǀ???? (
N
делит
????). Целое число ???? называется порядком α.
Пример 8 .9 . Задана мультипликативная группа < {1, ‒ 1, ????, ‒ ????};∙; 1>. Ка- ков порядок элемента ????? Каков порядок (‒1)? Какой элемент может быть исполь- зован в качестве α?
Решение. Находим степени элемента ????: ????
1
=
????, ????
2
= ‒1, ????
3
= ‒????, ????
4
= 1. Поря- док элемента ???? равен 4. Элемент (‒ 1) имеет порядок равный 2, т. к. (‒ 1)¹ =‒ 1, (‒
1)² = 1. Порядок элемента (‒ ????) также равен 4. Данная мультипликативная группа является циклической, порожденная элементом ????.
Определение 8.4. Группа называется бесконечной, если все натуральные степени порождающего элемента α различны, т. е. α
????
≠ α
????
при ???? ≠ ????. В этом случае говорят, что элемент α имеет бесконечный порядок.
Определение 8.5. Циклическая группа конечна и имеет порядок
????, если для
???? выполняется равенство α
????
= 1 и ???? ‒ наименьшее положительное число с таким свойством. Обозначение циклической группы будет следующим:
???? = <{α
0
= 1, α
1
, α
2
, … , α
????
};
∙>, где ???? ‒ порядок элемента α (число элементов группы).
Определение 8.6. Натуральное число
???? > 1 называется простым, если оно делится только на 1 и на себя. Натуральное число, большее 1, называется состав- ным, если оно не является простым.
Замечание. По определению целое число 1 не является ни простым, ни со- ставным. Число 2 ‒ единственное четное простое число.

139
Теорема 8.3. Всякая группа простого порядка
???? (???? ‒ простое число) явля- ется циклической. Всякая циклическая группа является абелевой, при этом
α
????
α
????
= α
????+????
,
(α
????
)
????
= α
????????
Определение 8.7. Если все элементы циклической группы ???? могут быть представлены в виде натуральных степеней некоторого элемента α ∈ ????, то такой элемент называется примитивным.
В примере 2.9 элемент
???? ‒ примитивный.
Определение 8.8. Целые числа ???? и ???? называются взаимно-простыми, если наибольший общий делитель (НОД) ???? = (????, ????) = 1.
Теорема 8.4.(Теорема Эйлера, (Леонард Эйлер (1707‒1783), швейц. мате- матик). Если α и ???? взаимно-простые числа, то
α
φ(????)
≡ 1mod ???? , где φ(????) ‒ функция Эйлера, равная количеству всех натуральных чисел мень- ших ???? и взаимно-простых с ????.
Рассмотрим примеры.
Пример 8 .10 . Пусть задано множество целых чисел ???? = {1, 2, 3, 4, 5, 6}.
Найти φ(7).
Решение. φ(7) = 6.
Пример 8 .11 . Задано множество целых чисел ???? = {1, 2, 3, 4, 5, 6, 7, 8}.
Найти φ(9).
Решение. φ(9) = 6.
Пример 8 .12 . Пусть задано множество целых чисел ???? = {1, 2, 3, 4},
φ(5) = 4. Числа 2 и 5 являются взаимно-простыми т. к.
2 4
≡ 1mod 5.
Если в циклической группе выполняется условие
φ(????) = ????, то для примитивного элемента циклической группы α справедливо
α
φ(????)
≡ 1mod ????, α
????
≡ 1. (8.1)
Но α не единственный примитивный элемент циклической группы. При- митивным всегда является элемент α
????‒1
Доказательство. Если φ(????) = ????, из (8.1) запишем

140
α
????
≡ 1mod ????. (8.2)
Умножим выражение (8.2) на элемент, обратный примитивному α:
α
????
α
−1
≡ 1α
−1
mod ????.
Преобразуя последнее выражение, получим:
α
????‒1
α
−1
≡ 1mod ????,
α
????‒1
α ≡ 1mod ????.
Из определения обратного элемента мультипликативной группы (???? ∗ ????̂ =
= ????) следует, что примитивным является элемент α
̂ = α
−1
= α
????‒1
, обратный α.
Замечание. Для циклической мультипликативной группы, числовых полей и колец обратные элементы можно найти:
1) перебором;
2) по теореме Эйлера;
3) по алгоритму Евклида.
Количество примитивных элементов определяется функцией Эйлера
φ(????‒ 1).
Пример 8 .13 . Задана мультипликативная абелева группа
???? = <{????
0
=1, ????
1
=2, ????
2
=3, ????
3
=4};∙;1>.
Построить возможные циклические группы. Определить число примитив- ных элементов.
Решение. Находим функцию Эйлера φ(5) = 4. Число примитивных элемен- тов равно φ(4) = 2. Примитивным является элемент
????
1
= 2, т. к.
2 4
= 16 ≡ 1 mod 5.
Циклическую группу образует множество { 2 0
,
2 1
, 2 2
,
2 3
}, где
2 0
= 1,
2 1
,
2 2
= 4, 2 3
= ((3)).
Примитивным будет также элемент
????
1
????−1
= 2 3
= ((3)) = ????
2
Циклическую группу образует множество { 3 0
,
3 1
, 3 2
,
3 3
}, где 3 0
= 1,
3 1
,
3 2
= ((4))4, 3 3
= ((2)).

141
Замечание. Элемент ????
3
= 4 не является примитивным элементом заданной мультипликативной группы, т. к. имеет порядок 2:
{
4 0
= 1, 4 1
,
4 2
≡ ((1))}.
8.1.3. Теорема Лагранжа
В группе множество ???? всех элементов по операции сложения образует цик- лическую аддитивную группу < {????}; +; 0 > , а элемент 1 порождает множество вида {1; 1 + 1; 1 + 1 + 1; … }. Так как число элементов в группе конечно, то в этом ряду найдется сумма ???? единиц, равная нулевому элементу группы.
Определение 8.9. Порядок каждого элемента аддитивной группы ????
????
опре- деляется по числу этих элементов в последовательности вида ????, ???? + ????, ???? + ???? +
????, … , ???? + ???? + ⋯ = 0 = ????.
П р и м е р 8 . 1 4 . Определить порядок каждого элемента аддитивной группы ???? = < {0, 1, 2, 3, 4, 5}; +; 0 > порядка 6, задаваемой таблицей Кэли (табл.
8.3).
Таблица 8 3
Таблица Кэлидля группы ???? = < {0, 1, 2, 3, 4, 5}; +; 0 >
+ 0 1 2 3 4 5 0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2 3 5 5 0 1 2 3 4
Решение. Используя определение 8.9, представим все элементы группы как:
1) 0: 0 =
????, следовательно, порядок элемента 0 равен 1;
2) 1: 1 + 1 + 1+ 1 + 1+ 1 = 6
≡ 0 mod 6, следовательно, порядок элемента 1 равен 6;
3) 2: 2 + 2 + 2 = 6
≡ 0 mod 6, порядок элемента 2 равен 3;
4) 3: 3 + 3 = 6
≡ 0 mod 6, порядок элемента 3 равен 2;
5) 4: 4 + 4 + 4 = 12
≡ 0 mod 6, порядок элемента 4 равен 3;
6) 5: 5 + 5 + 5 + 5 + 5 + 5 = 30
≡ 0 mod 6, порядок элемента 5 равен 6.
Теорема 8.5. (Теорема Лагранжа, Ж. Л. Лагранж (1736 ‒ 1813), франц. ма- тематик). Порядок любого элемента ????
????
произвольной конечной группы, а не только циклической является делителем порядка ???? группы (числа элементов группы).

142
Следствие из теоремы 8.5. Порядок каждого элемента конечной под- группы является делителем порядка группы.
8.1.4. Подгруппа
Определение 8.10. Пусть <
????; ∗> ‒ группа, а ???? ⊆ ???? ‒ подмножество, являющееся группой относительно той же групповой операции. Тогда ???? называ- ется подгруппой группы ????.
Подгруппа ???? всегда содержит нейтральный элемент группы. Для того, чтобы определить, является ли ???? подгруппой, достаточно проверить выполнение аксиом замкнутости и существования обратных элементов.
Рассмотрим примеры подгрупп.
Пример 8 .15 . Множество ???? всех четных чисел является подмножеством целых чисел ℤ = {0, ±1, ±2, …}. Тогда < ????; ± > ‒ подгруппа группы < ℤ ; ± >.
Пример 8 .16. Множество {0, 1, 2} принадлежит подмножеству целых чи- сел ℤ, но группа, задаваемая табл. 8.2, не является подгруппой группы
<
ℤ; + >, т. к. они определяются разными операциями.
Пример 8 .17 . Пусть ???? = <{0, 1, 2, 3}; +; 0> ‒ группа порядка 4, задаваемая табл. 8.4.
Таблица 8.4
Таблица Кэли для группы ???? = < {0, 1, 2, 3}; +; 0 >
+
0 1
2 3
0 0
1 2
3 1
1 2
3 0
2 2
3 0
1 3
3 0
1 2
Тогда ???? = <{0, 2}; +; 0> ‒ подгруппа группы ???? с операцией (табл. 8.5)
Таблица 8.5
Таблица Кэли для подгруппы ???? = < {0, 2}; +; 0 >
Теорема 8.6. Пусть ???? ‒ элемент порядка ???? группы ????, тогда ???? =
=< {????
1
, ????
2
, … , ????
????−1
};∙; 1 > ‒ циклическая подгруппа.
Пример 8.18 . Пусть ???? = <{1, 2, 3, 4}; ∙ ; 1> – группа, ???? = <{1, 4}; ∙ ;1> –
подмножество ???? образует циклическую подгруппу группы ????. Порядок ???? эле- мента 4 равен 2.
+
0 2
0 0
2 2
2 0

143
Следствие из теоремы 8.6. Во всякой мультипликативной группе нату- ральные степени ????
????
любого элемента
???? образуют подгруппу.
8.2. Разложение группы на смежные классы
8.2.1. Определение смежного класса по подгруппе
Для заданной конечной группы ???? и подгруппы ???? существует операция, ко- торая устанавливает взаимосвязь между ???? и ????. Эта операция называется разло- жением группы ???? на смежные классы по ????. Обозначим элементы группы ???? через
{????
1
, ????
2
, … , ????
????
}, а элементы подгруппы ???? этой группы через {ℎ
1
, ℎ
2
, … , ℎ
????
}.
Рассмотрим таблицу, построенную следующим образом (табл. 8.6):
1) запишем элементы подгруппы ???? в строку с нейтральным элементом в качестве первого элемента строки;
2) выберем произвольным способом элемент группы ????
????
, не принадлежа- щий подгруппе ????, и запишем его первым элементом второй строки;
3) просуммировав ????
????
со всеми элементами
????, получим вторую строку таб- лицы;
4) далее, выбрав произвольным способом элемент ????
????
, не принадлежащий ни первой, ни второй строке таблицы, и просуммировав его со всеми элементами
????, получим третью строку и т. д. для всех элементов группы. Построение закан- чивается тогда, когда после некоторой итерации оказывается, что каждый эле- мент группы ???? записан в некоторой ячейке таблицы.
Таблица 8.6
Таблица смежных классов
ℎ
1
= ????
ℎ
2
ℎ
3
…
ℎ
????
ℎ
1
+
????
1
ℎ
2
+
????
1
ℎ
3
+
????
1
…
ℎ
????
+
????
1
ℎ
1
+
????
2
ℎ
2
+
????
2
ℎ
3
+
????
2
…
ℎ
????
+
????
2
⋮
⋮
⋮
⋮
⋮
ℎ
1
+
????
????
ℎ
2
+
????
????
ℎ
3
+
????
????
…
ℎ
????
+
????
????
⋮
⋮
⋮
⋮
⋮
ℎ
1
+
????
????
ℎ
2
+
????
????
ℎ
3
+
????
????
…
ℎ
????
+
????
????
Построенная подобным способом построенная таблица называется табли- цей смежных классов. Строки таблицы называются смежными классами по под- группе ????. Элементы первого столбца называются образующими смежных клас- сов (лидерами смежных классов).
Пример 8 .19. Заданы группа ???? =

{0, 1, 2, 3, 4, 5}
6
; 0; +

и подгруппа
???? группы ????: ???? =

{0, 3}
6
; 0; +

. Построить таблицу смежных классов.
Решение. По определению смежного класса получим:

144
Таблица 8.7
Cмежные классы
0 3
1 4
2 5
Теорема 8.7. Каждый элемент группы принадлежит одному и только од- ному смежному классу.
Теорема используется для декодирования кодов по таблице смежных клас- сов. Декодирование основывается на анализе стандартного расположения эле- ментов таблицы.
Утверждение 8.1. Два смежных класса не пересекаются. Объединение всех смежных классов совпадает с множеством группы ????.
Для примера 8.19 справедливы выражения:
(0 + ????) ∩ (1 + ????) ∩ (2 + ????) = ∅,
(0 + ????) ∪ (1 + ????) ∪ (2 + ????) = ????, где ∩ и ∪ – соответственно операции пересечения и объединения, ∅ – пустое множество.
Следствие из теоремы 8.7. Если ???? – подгруппа конечной группы ????, то число элементов в ???? делит число элементов в ????. Доказательство следует из пря- моугольности таблицы смежных классов. Следовательно, порядок ???? равен по- рядку ????, умноженному на число смежных классов разложения ???? по ????.

145 кода ????:
{
????
????
} = ???? ∪ (????
1
+ ????) ∪ … ∪ (????
????
+ ????), (8.3) где ???? = ????
????−????
− 1 = ????
????
− 1.
8.3.1. Таблица стандартного расположения для кода
Первая строка таблицы состоит из всех кодовых слов кода ????
1
, ????
2
, … , ????
????
(включая нулевое слово). Другие строки – это смежные классы (???? + ????), т. е.
(????
1
+ ????
1
), (????
1
+ ????
2
), … , (????
1
+ ????
????
),
(????
2
+ ????
1
), (????
2
+ ????
2
), … , (????
2
+ ????
????
),
⋯
(????
????
+ ????
1
), (????
????
+ ????
2
), … , (????
????
+ ????
????
).
Напомним, что ????
????
не принадлежит коду. Стандартное расположение для кода приобретает вид, показанный в табл. 8.8.
Для ???? = 2 таблица содержит:

2
????
смежных классов (строк);

каждый смежный класс содержит 2
????
векторов;

2
????
столбцов;

2
????
∙ 2
????
= 2
????+????
= 2
????
векторов длиной
????.
Таблица 8.8
Стандартное расположение для кода
????
1
????
2
????
3
…
????
????
????
1
+
????
1
????
1
+
????
2
????
1
+
????
3
…
????
1
+
????
????
????
2
+
????
1
????
2
+
????
2
????
2
+
????
3
…
????
2
+
????
????
⋮
⋮
⋮
⋮
⋮
????
????
+
????
1
????
????
+
????
2
????
????
+
????
3
…
????
????
+
????
????
⋮
⋮
⋮
⋮
⋮
????
????
+
????
1
????
????
+
????
2
????
????
+
????
3
…
????
????
+
????
????
Например, таблица стандартного расположения для [7, 4, 3]-кода Хэм- минга имеет размеры 8

16 и содержит 2 3
∙ 2 4
=128 элементов (векторов).
Пример 8 .20 . Пусть [4, 2, 2]-код есть подгруппа некоторой двоичной группы ????
????
. Код предназначен для передачи сообщений:

146
????
0
= (00) → 0,
????
1
= (10) → 1,
????
2
= (01) → 2,
????
3
= (11) → 3.
Cообщениям
????
????
cоответствуют слова кода
????:
???? = [
0 0 0 0
1 0 1 1
0 1 0 1
1 1 1 0
]. (8.4)
Стандартное расположение элементов таблицы смежных классов кода ???? приведено в табл. 8.9.
Таблица 8.9
Стандартное расположение для [4, 2, 2]-кода
Замечание. Вектор [0001] не входит в образующие смежных классов.
Таблицы стандартного расположения для кода используются для декоди- рования помехоустойчивых кодов. Декодирование основывается на анализе стандартного расположения элементов таблицы.
8.4. Кольцо
Определение 8.12. Кольцо ‒ это алгебраическая структура или множество элементов ????, в котором определены две основные операции (сложение и умно- жение) и операция, обратная первой из них (вычитание).
В кольце должны выполняться следующие аксиомы:
‒ <????; +> ‒ абелева группа;
‒ <????; ∙> ‒ полугруппа;
‒ дистрибутивность: для любых элементов множества ???? ={ ????, ????, ???? }, ???? ⋅ (????
+
????) = ???? ⋅ ???? + ???? ⋅ ????.
Определение 8.13.Множество ???? с заданной на нем бинарной операцией и выполнением аксиом замкнутости и ассоциативности называется полугруппой.
Рассмотрим примеры полугрупп.
Пример 8 .21. <ℕ; +> ‒ аддитивная полугруппа натуральных чисел.
0000 1011 0101 1110 1000 0011 1101 0110 0100 1111 0001 1010 0010 1001 0111 1100