Файл: Контрольная работа Математические методы теории сетей связи.pdf
ВУЗ: Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича
Категория: Методичка
Дисциплина: Сети связи
Добавлен: 25.10.2018
Просмотров: 3999
Скачиваний: 34
элемента образуют простое поле GF(2), т. е. в состав расширенного поля в
качестве подполя входит простое поле.
Для каждого элемента поля существует обратный элемент. По операции
сложения обратными элементами являются те, на пересечении которых в
таблице сложения располагаются «0», а по операции умножения обратными
элементами являются ненулевые элементы, на пересечении которых в таб-
лице умножения располагаются «1». Сравните с решением задачи 2.17.
2.23. Построить поле GF(2
3
).
Решение
Для построения поля GF(2
3
) необходимо знать примитивный много-
член 3-й степени. Таких многочленов известно два: х
3
+х+1 и х
3
+х
2
+1.
Построим поле по модулю каждого из этих многочленов:
π
1
(α)=α
3
+α+1
π
2
(α)=α
3
+α
2
+1
α
1
= α =010
α
2
= α
2
=001
α
3
=1+α =110
α
4
= α+α
2
=011
α
5
=1+α+α
2
=111
α
6
=1 +α
2
=101
α
7
=1 =100
α
1
= α =010
α
2
= α
2
=001
α
3
=1 +α
2
=101
α
4
=1+α+α
2
=111
α
5
=1+α =110
α
6
= α+α
2
=011
α
7
=1 =100
Получили два различных представления ненулевых элементов GF(2
3
);
дополним каждое из них нулевым элементом 0=(000). Получим два пред-
ставления GF(2
3
). Для первого из них первообразным корнем является ко-
рень π
1
(α), а для второго − π
2
(α).
2.24. Построить поле GF(2
4
) на основе мультипликативной группы
порядка 2
4
−1. Проверить прямой подстановкой справедливость распреде-
ления элементов поля GF(2
4
) в качестве корней по неприводимым много-
членам, входящим в разложение х
15
+1.
Решить самостоятельно (использовать материалы см. 2.1).
2.25. Построить поле GF(2
5
) по модулю π(α)=1+α
2
+α
5
.
Решить самостоятельно.
2.26. Найти наибольший общий делитель (НОД) чисел 186 и 66, т. е.
НОД(186,66) =?
Решение
Воспользуемся алгоритмом Евклида и найдем:
1-й шаг:186−2·66=54,
2-й шаг: 66−1·54=12,
3-й шаг: 54−4·12=6,
4-й шаг: 12−2·6=0.
Итак, НОД(186,66)=6.
Представим полученный результат в виде: fa+gb = d,
где a=186, b=66, d=6.
В этих целях преобразуем полученные выше равенства.
Значение для 54 из 1-го шага подставим в равенство 2-го шага:
−186+3·66 =12.
Подставляя значения для 54 и 12 в равенство 3-го шага, получаем
5·186 −14·66 = 6, что соответствует искомому.
Сделаем еще одно преобразование: найденные значения для 6 и 12
подставим в равенство 4-го шага: −11·186+31·66=0.
Анализируя полученные равенства, приходим к выводу, что алгоритм
Евклида пошагово находит значение f и g, т. е. процесс решения задачи на-
хождения НОД сводится к преобразованию выражения f
i
a+g
i
b=d
i
в fa+gb=d.
При этом значения f
i
, g
i
и d
i
зависят от их значений на двух предыду-
щих шагах алгоритма. Найдем общие выражения для значений f
i
, g
i
, d
i
.
Для этого перепишем последовательно найденные равенства, допол-
нив их двумя формальными равенствами в качестве исходных:
1·186+0·66=186,
0·186+1·66=66,
1·186−2·66=54,
−1·186+3·66=12,
5·186-14·66=6,
−11·186+31·66=0.
Определим q
i
=[d
i–2
/d
i–1
], где [ ] означает целую часть дроби d
i–2
/d
i–1
.
Теперь общее выражение для f
i
, g
i
и d
i
может быть представлено в сле-
дующем виде: E
i
=E
i–2
− q
i
E
i–1
.
Для подтверждения этого представим процесс нахождения
НОД(186,66) в виде таблицы.
Шаг i
f
i
g
i
d
i
q
i
f
i
·a+g
i
·b=d
i
−1
1
0
186
–
1·186 + 0·66 = 186
0
0
1
66
–
0·186 + 1·66 = 66
1
1
−2
54
[186/66]=2
1·186 − 2·66 = 54
2
−1
3
12
[66/54]=1
−1·186 + 3·66 = 12
3
5
−14
6
[54/12]=4
5·186 − 14·66 = 6
4
−11
31
0
[12/6]=2
−11·186 + 31·66 = 0
Выполненные преобразования используются при быстром декодирова-
нии кодов БЧХ для решения ключевого уравнения по алгоритму Евклида.
2.27. Вычислить 2
19
(mod 5).
Число 2 является примитивным элементом поля GF(5) и 2
4
=1. Число 2
19
может быть представлено: 2
19
=2
4·4
·2
3
(mod 5)=1
4
·2
3
(mod 5)=2
3
(mod 5) =3.
Ответ: 2
19
(mod 5) =3.
3. Теорема Ферма и циклотомические классы
Теорема Ферма.
Признаки делимости двучленов.
Корни неприводимых многочленов и циклотомические классы много-
членов вида х
n
– 1 для случаев:
а) n = p
m
–1;
б) n – любое целое число.
Степени неприводимых многочленов в разложении х
n
–1 на неприво-
димые сомножители.
Минимальные и двойственные многочлены.
Литература: см. 2.1–2.3.
Цель. Научиться вычислять число неприводимых сомножителей мно-
гочленов вида х
n
–1, их степени и последовательности их корней. Получить
навыки в формировании циклотомических классов, определении показате-
лей, которым принадлежат неприводимые многочлены, представлении их
корней в виде элементов расширенного поля Галуа.
Контрольные вопросы
3.1. Перечислить все многочлены степени n над полем GF(2), предста-
вить их в виде неприводимых сомножителей и определить показатели, к
которым эти многочлены принадлежат в следующих случаях:
a) n=2, б) n=3, в) n=4, г) n=5.
3.2. Определить показатели, которым принадлежат следующие много-
члены над полем GF(2):
а) х
8
+ х
7
+ х
5
+ х
4
+ х
3
+ х+1,
б) х
7
+ х
3
+ х+1,
в) х
6
+ х
5
+ х
4
+ х
3
+ х
2
+ х+1
и указать их неприводимые сомножители.
3.3. Определить число и степени неприводимых сомножителей много-
членов над полем GF(2):
х
8
+1, х
9
+1, х
10
+1, х
11
+1, х
1
2
+1, х
13
+1, х
14
+1, х
15
+1, х
16
+1, х
17
+1, х
18
+1,
х
19
+1, х
20
+1, х
21
+1, х
22
+1, х
23
+1.
3.4. Определить все неприводимые сомножители следующих двучле-
нов:
а) х
30
+1,
б) х
31
+1,
в) х
32
+1.
3.5. Используя результат решения задачи 2.13, а, прямым умножением
показать, что многочлены из примера п. 2.1 равны: f
1
(x)=х
4
+х+1=
(х+α)(х+α
2
)(х+α
4
)(х+α
8
) и f
2
(x) = х
4
+
х
3
+1= (х+α
7
)(х+α
11
)(х+α
13
)(х+α
14
).
3.6. Найти двойственные многочлены для следующих многочленов:
х
2
+х+1, х
3
+х+1, х
5
+х+1, х
6
+х
3
+1, х
9
+х
4
+1.
Примеры решения задач и дополнительные задачи
3.6. Доказать, что многочлен х
2
+х+1 неприводим над полем GF(2).
Решение
Для доказательства достаточно показать, что данный многочлен не
имеет сомножителей, содержащих х в первой степени, т. е. что х или х+1 не
делят многочлен x
2
+x+1 в двоичном поле.
Этот результат может быть получен тремя способами.
1. Непосредственным делением – предоставляется выполнить читателю.
2. Подстановкой корней х и х+1 в многочлен х
2
+х+1.
Действительно: корень х равен 0, корень х+1 равен 1.
Проверяем: f(x=0)=0
2
+0+1=1, т. е. 0 не является корнем х
2
+х+1,
f(x=1)=1
2
+1+1=1, т. е. 1 также не является корнем х
2
+х+1.
3. Определением, к какому показателю принадлежит х
2
+х+1, т. е. оп-
ределением, какой порядок имеют его корни. Для этого представляем
х
2
+х+1=0, откуда х
2
=х+1. Умножаем обе части равенства на х: х
3
=х
2
+х, но
х
2
=х+1, значит х
3
=х+1+х=1. Следовательно, корни х
2
+х+1 являются и кор-
нями х
3
+1, т. е. х
2
+х+1 принадлежит показателю 3.
Этот результат не является неожиданным, так как многочлен вида
х
n
+x
n–1
+x
n–2
+…+x+1, содержащий все степени х от n до 0 в качестве сла-
гаемых, является сомножителем двучлена вида х
n+1
+1 наряду с сомножите-
лем х+1.
Кроме того, применение функции Эйлера позволяет определить число
корней х
3
+1, имеющих порядок 3: φ(3)=2. Значит, из трех корней х
3
+1 два
корня имеют порядок 3, а это корни именно многочлена х
2
+х+1, так как по-
рядок корня многочлена х+1 равен 1.
3.7. Найти корни многочлена х
2
+х+1.
Решение
Решение предыдущей задачи показало, что х
2
+х+1 входит в разложе-
ние х
3
+1. По теореме Ферма корни х
3
+1 являются элементами поля GF(2
2
).
Найдем циклотомический класс по модулю 3: С
1(3)
=
{
1,2}.
Следовательно, х
2
+х+1 имеет корнями элементы α и α
2
поля GF(2
2
).
Напомним состав поля GF(2) по модулю π(α)=1+α+α
2
:
0=00, 1= α
0
=10= α
3
, α
1
=01, α
2
=11.
Таким образом, корнями f(x)= х
2
+х+1 являются последовательности 01
и 11.
Действительно: 11+01+10 = 00, т. е. f(x=α) = 0 и 01+11+10=00, т. е.
f(x=α
2
)=0.
3.8. Построить многочлен f(x) второй степени над полем GF(2), корня-
ми которого являются элементы α
1
=10 и α
2
=11 поля GF(2
2
).
Решение
В соответствии с теоремой Безу: f(x) = (x+α
1
)(x+α
2
) = x
2
+α
2
x+α
1
x+α
3
=
= x
2
+(α
1
+α
2
)x+α
3
=x
2
+x+1, так как α
1
+α
2
= (01)+(11)=(10)=α
0
=1, α
3
=1 (см.
предыдущую задачу и таблицы задачи 2.22).
Тот же самый результат можно получить используя формулы Виета, в
соответствии с которыми для нормированного многочлена 2-й степени
f(x) = f
2
х
2
+f
1
х+f
0
над полем GF(2) справедливо: f
2
=1, f
1
= α
1
+α
2
=1, f
0
= α
1
α
2
=1.
Обратить внимание на то, что многочлен, неприводимый над полем
GF(2), разлагается на сомножители над полем GF(
2
2
), т. е. над полем своих
корней.
3.9. Найти все неприводимые многочлены степени 3 над полем GF(2).
Решение
Перечислим все многочлены степени 3 с коэффициентами из двоично-
го поля: х
3
+х
2
+х+1, х
3
+х
2
+х, х
3
+х
2
+1, х
3
+х+1, х
3
+1, х
3
+х, х
3
+х
2
, х
3
.
Второй и четыре последних многочлена явно не могут быть неприво-
димыми, так как имеют известные сомножители. Осталось проверить пер-
вый, третий и четвертый многочлены. Для проверки достаточно убедиться,
что проверяемый многочлен не имеет в качестве сомножителя х+1, т. е. «1»
не должна быть корнем проверяемого многочлена. Непосредственной под-
становкой проверяем.
Для х
3
+х
2
+х+1: 1
3
+1
2
+1+1=0, т. е. этот многочлен имеет сомножителем
х+1, и, действительно, х
3
+х
2
+х+1=(х+1)(х
2
+1)=(х+1)
3
.
Для х
3
+х
2
+1: 1
3
+1
2
+1=1.
Для х
3
+х+1: 1
3
+1+1=1.
Многочлен третей степени может содержать в качестве сомножителей
только многочлены 1-й или 2-й и 1-й степеней, поэтому делаем вывод, что
многочлены х
3
+х
2
+1 и х
3
+х+1 являются неприводимыми.