Файл: Контрольная работа Математические методы теории сетей связи.pdf
ВУЗ: Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича
Категория: Методичка
Дисциплина: Сети связи
Добавлен: 25.10.2018
Просмотров: 3998
Скачиваний: 34
Для остальных последовательностей приведем ортогональные после-
довательности без пояснений (проверить самостоятельно):
100 – 000, 001, 010, 011.
101 – 000, 010, 101, 111.
110 – 000, 001, 110, 111.
111 – 000, 011, 101, 110.
Отметим, что двоичные последовательности с четным числом единиц
(в рассмотренном примере – 000, 011, 101 и 110) являются самоортого-
нальными.
1.15. Задана совокупность двоичных последовательностей длины 3:
000, 001, 010, 011. Показать, что данная совокупность является подгруппой
всех возможных двоичных последовательностей длины 3. Найти совокуп-
ность двоичных последовательностей, ортогональных заданной. Показать,
что найденная совокупность также является подгруппой всех двоичных по-
следовательностей длины 3. Найти базисы заданной совокупности и орто-
гональной ей. Показать, что произведение найденных базисов по правилам
умножения матриц дает чисто нулевую матрицу.
Решение
1. Для того чтобы показать, что совокупность 000, 001, 010, 011 явля-
ется подгруппой всех восьми двоичных последовательностей длины 3, не-
обходимо установить, что эта совокупность удовлетворяет групповым ак-
сиомам. Проверка выполнения групповых аксиом сводится к проверке
замкнутости элементов совокупности по операции поразрядного сложения
по mod 2 при наличии среди элементов совокупности нулевой последова-
тельности.
Легко убедиться, что и то, и другое имеет место; при этом порядок
подгруппы равен 4, т. е. делит порядок группы.
2. Ортогональными к заданным последовательностям являются после-
довательности 000 и 100, которые также образуют подгруппу размерности
2 всех двоичных последовательностей длины 3.
3. Базис последовательностей 000, 001, 010, 011 представляется мат-
рицей:
1
0
0
0
1
0
.
Действительно, все последовательности заданной совокупности могут
быть получены как линейная комбинация строк базисной матрицы:
W= с
1
(010) + с
2
(001), где с
i
– элементы GF(2).
4. Базис совокупности ортогональных последовательностей представ-
ляется матрицей:
0
0
1
.
5. Умножение матриц
1
0
0
0
1
0
и
0
0
1
возможно только в том слу-
чае, когда одна из них транспонирована:
1
0
0
0
1
0
×
0
0
1
или
0
0
1
×
1
0
0
1
0
0
.
Выполнить умножение матриц самостоятельно и убедиться в ортого-
нальности рассмотренных подгрупп.
1.16. Используя таблицы сложения и умножения для полей GF(2) и
GF(3), приведенные в 1.13, определить, чему равны суммы и произведения
пар чисел 1 и 2, 2 и 3, 3 и 4, 4 и 5, 5 и 6, 6 и 7 по mod 2 и по mod 3.
1.17. Показать, что пространство строк матрицы
1
0
0
0
1
0
содержит
последовательности 000, 001, 010, 011.
2. Кольца многочленов и поля Галуа
Идеал кольца и классы вычетов кольца целых чисел – по модулю m и
многочленов – по модулю многочлена f(х).
Размерность идеала кольца классов вычетов многочленов по модулю
многочлена f(х)=g(х)h(х), где f(х) имеет степень n, g(х) – степень n–k,
h(х) – степень k.
Простые и расширенные поля Галуа, подполя
.
Циклическая группа расширенного поля Галуа, порядок элементов по-
ля (группы), число элементов некоторого порядка.
Примитивные элементы поля и примитивные многочлены.
Литература: см. 1.3 и 1.4.
Цель. Изучить структуру числовых колец и колец многочленов, спосо-
бы формирования идеалов колец, связь между кольцами классов вычетов
многочленов и конечными полями. Получить навыки формирования идеа-
лов заданного порядка.
Контрольные вопросы
2.1. Над полем GF(2) заданы многочлены p
1
(х)=х
3
+1 и p
2
(х)=х
4
+х
3
+х+1:
a) найти наибольший общий делитель этих многочленов HOД [p
1
(х),
p
2
(х)] (указание: использовать алгоритм Евклида);
б) найти многочлены A(x) и B(x), удовлетворяющие равенству:
HOД [p
1
(х), p
2
(х)] = A(x) p
1
(х)+ B(x) p
2
(х).
2.2. Сколько различных многочленов второй степени вида х
2
+ax+b, где
a и b – элементы GF(2) имеется над полем GF(2)?
2.3. Сколько различных многочленов вида (x–α)(x–β), где α и β не рав-
ны 0, имеется над полем GF(2
4
), сколько из них неприводимых над этим
полем? Сколько из них неприводимо над полем GF(2)?
2.4. Используя алгоритм Евклида, найти HOД (1573,308) и целые чис-
ла A и B, удовлетворяющие равенству HOД (1573,308) = 1573A+308B.
2.5. Доказать, что в кольце целых чисел по модулю 15 многочлен
p(х)=х
2
–1 имеет более двух корней, а в поле GF(2
3
) – один. Чему равно зна-
чение этих корней?
2.6. Сколько различных многочленов над GF(2) делят многочлен х
6
–1?
2.7. Построить поле GF(5), выписав для него таблицы сложения и ум-
ножения. Определить порядок ненулевых элементов поля.
2.8. Определить возможные порядки ненулевых элементов GF(7).
Сколько элементов каждого порядка имеется? Указать порядок каждого
ненулевого элемента из этого поля.
2.9. Вычислить 3
100
(mod 5).
2.10. Доказать, что многочлен х
2
+x+1 неприводим над GF(2). В каком
поле корни этого многочлена являются примитивными элементами? По-
строить это поле.
2.11. Доказать, что многочлен х
3
+x+1 неприводим над GF(2). В каком
поле корни этого многочлена являются примитивными элементами? По-
строить это поле.
2.12. Сколько примитивных элементов имеет поле GF(2
3
)? Корнями
каких многочленов они являются?
2.13. Построить поле GF(2
4
):
a) по модулю многочлена π(x)=1+ х+x
4
;
б) по модулю многочлена π(x)=1+ х
3
+x
4
;
в) каков порядок корней этих многочленов?
г) каков порядок остальных ненулевых элементов GF(2
4
)?
д) каким многочленом (указать степень) принадлежат в качестве
корней ненулевые элементы GF(2
4
) из п. б?
2.14. Показать, что поле GF(2
2
) является подполем GF(2
4
).
2.15. Какие подполя содержит GF(2
8
)?
2.16. Сколько идеалов существует в кольце многочленов по модулю
многочлена f(х) над полем GF(2), если идеалы образуют все многочлены,
кратные каждому неприводимому сомножителю многочлена f(х)? Какова
размерность идеалов:
а) f(x) = x
3
+1;
б) f(x) = x
7
+1.
Примеры решения задач и дополнительные задачи
2.17
.
Показать, что для p = 4 поле целых чисел GF(p) не существует.
Решение
Элементы GF(4): {0}, {1}, {2}, {3}.
Составим таблицы сложения и умножения:
+
0
1
2
3
×
0
1
2
3
0
1
2
3
0
1
2
3
1
2
3
0
2
3
0
1
3
0
1
2
0
1
2
3
0
0
0
0
0
1
2
3
0
2
0
2
0
3
2
1
Из анализа таблиц сложения и умножения делаем выводы:
1) по операции сложения существует единичный элемент 0 и для каж-
дого элемента поля есть обратный: для 0 – это 0, для 1 – это 3, для 2 – это 2,
для 3 – это 1;
2) по операции умножения существует единичный элемент 1, а обрат-
ные элементы существуют для 1 – это 1, и для 3 – это 3, но для элемента 2
обратного элемента не существует.
Общий вывод: для целых чисел простое поле GF(4) не существует.
2.18. Что называют примитивным элементом поля?
Что является примитивным элементом поля:
а) GF(2),
б) GF(3),
в) GF(5)?
Ответ: Примитивным элементом поля называют ненулевой элемент по-
ля, последовательные степени которого дают все ненулевые элементы поля.
Обозначим примитивный элемент поля через α.
а) для GF(2) α=1;
б) для GF(3) α=2; остальные ненулевые элементы GF(3): α
2
=1; α
3
=2;
в) для GF(5) α=2; остальные ненулевые элементы GF(5): α
2
=4; α
3
=3; α
4
=1.
2.19. Что называют порядком поля? Группы?
Ответ: Порядком поля (группы) называют число элементов поля
(группы).
2.20. Чему равен порядок поля:
а) GF(2)?
б) GF(3)?
в) GF(5)?
г) GF(p)?
Ответ: а) 2; б) 3; в) 5; г) p.
2.21. Построить поле GF(2
2
).
Решение
Поле – кольцо классов вычетов многочленов по модулю неприводимо-
го примитивного многочлена, т. е. такого неприводимого многочлена, кор-
ни которого являются примитивными элементами поля. Для поля GF(2
m
)
это должен быть неприводимый многочлен над полем GF(2) степени m,
принадлежащий максимальному показателю, т. е. e = 2
m
– 1.
В рассматриваемом случае e = 3, т. е. это должен быть неприводимый
многочлен 2-й степени, входящий в разложение двучлена х
3
+1 и не входя-
щий в разложение двучлена меньшей степени. Этим свойством обладает
единственный многочлен х
2
+х+1, так как х
3
+1= (х+1)(х
2
+х+1). Все корни
х
3
+1 являются ненулевыми элементами поля GF(2
2
): α
0
, α
1
, α
2
. При этом
α
0
=1 есть корень х+1, а α и α
2
– корни х
2
+х+1.
Для получения их в двоичном представлении необходимо разделить α
i
,
где i=1,2, на многочлен π(α)=1+α+α
2
, по модулю которого строится поле, и
взять в качестве α
i
остаток от деления α
i
на π(α), тогда получим:
α
0
=1 = 10,
α
1
= α = 01,
α
2
=1 + α = 11.
Таким образом, последовательность степеней корня многочлена
х
2
+х+1 образует мультипликативную группу GF(2
2
). Если к этим элементам
добавить 0=00, то получим все элементы поля GF(2
2
)=GF(4).
2.22. Доказать, что последовательность чисел 0=00, 1=10, α=01, α
2
=11
образует поле GF(2
2
).
Решение
Необходимо проверить наличие единичных элементов по операциям
сложения и умножения и обратных элементов по этим операциям для всех
элементов поля, так как ассоциативность, коммутативность и дистрибутив-
ность выполняются при введении операций над элементами поля как над
двоичными векторами.
+
0
1
α
α
2
×
0
1
α
α
2
0
1
α
α
2
0
1
α
α
2
1
0
α
2
α
α
α
2
0
1
α
2
α
1
0
0
1
α
α
2
0
0
0
0
0
1
α
α
2
0
α
α
2
1
0
α
2
1
α
Таблица сложения проверяется сложением соответствующих векторов,
а таблица умножения строится с учетом двух соотношений: π(α)=1+α+α
2
=0
и α
3
=1 (см. пояснения к решению задачи 2.17).
Из анализа таблиц вытекает, что в поле существует единичный эле-
мент по сложению «0» и единичный элемент по умножению «1». Эти два