Файл: Контрольная работа Математические методы теории сетей связи.pdf
ВУЗ: Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича
Категория: Методичка
Дисциплина: Сети связи
Добавлен: 25.10.2018
Просмотров: 3972
Скачиваний: 34
Ко всему они являются двойственными, поскольку
х
3
(х
–3
+х
–1
+1)=
= 1+х
2
+х
3
.
3.10. Определить, к какому показателю принадлежат многочлены
х
3
+х+1 и х
3
+х
2
+1.
Решение
По своей степени эти многочлены могут входить в разложение дву-
члена х
3
2
1
+1=х
7
+1. Достаточно проверить принадлежность к показателю
7 одного из них, например, х
3
+х+1.
Полагаем х
3
=х+1:
х
4
=х
2
+х
х
5
=х
3
+х
2
=х
2
+х+1
х
6
=х
3
+х
2
+х=х
2
+1
х
7
=х
3
+х=х+1+х=1.
Этим доказана принадлежность х
3
+х+1 и х
3
+х
2
+1 к показателю 7. А это
в свою очередь означает, что корни этих многочленов примитивные. Дей-
ствительно, найдем функцию Эйлера от числа 7: φ(7)=6, т. е. среди ненуле-
вых элементов поля GF(2
3
) шесть элементов являются примитивными – это
все ненулевые элементы, исключая α
0
=1, а именно: α
1
, α
2
, α
3
, α
4
, α
5
, α
6
. Они
распределяются по двум циклотомическим классам: С
1(7)
=
{
1,2,4},
С
3(7)
=
{
3,6,5}.
При этом α
1
, α
2
и α
4
– корни х
3
+х+1, а α
3
, α
5
, α
6
– корни х
3
+х
2
+1. Про-
верить это можно прямой подстановкой.
3.11. Проверить применением теоремы Безу справедливость найден-
ных в п. 2.1 неприводимых сомножителей х
15
+1. Использовать результаты
решения задач 2.13 и 2.24.
3.12. Определить, является ли многочлен х
5
+х+1 неприводимым над
полем GF(2).
Решение
Для решения этой задачи достаточно проверить имеет ли многочлен
х
5
+х+1 в качестве сомножителей неприводимые
многочлены первой и вто-
рой степени, т. е. х+1 и х
2
+х+1.
Многочлен х+1 имеет корнем «1». Подставим х=1 в х
5
+х+1, получаем
х
5
+х+1=1
5
+1+1=1, т. е. х+1 не делит х
5
+х+1.
Для корней х
2
+х+1 справедливо х
2
+х+1=0 или х
2
=х+1. Подставляем это
значение
в
х
5
+х+1:
х(х+1)(х+1)+х+1=х(х
2
+1)+х+1=х
3
+х+х+1=х
3
+1=
= (х+1)(х
2
+х+1)=0, т. е. корни х
2
+х+1 являются и корнями х
5
+х+1.
Значит, х
5
+х+1 имеет одним из своих сомножителей х
2
+х+1. Выполняя
деление х
5
+х+1 на х
2
+х+1, находим х
5
+х+1=(х
2
+х+1)(х
3
+х
2
+1).
Ответ: Многочлен х
5
+х+1 не является неприводимым над полем GF(2).
3.13. Проверить делимость многочлена х
5
+х+1 на многочлен х
3
+х
2
+1.
Решить самостоятельно методом проверки общих корней.
3.14. Найти все неприводимые многочлены пятой степени над полем
GF(2).
Рекомендации по решению
1) выписать все двоичные приведенные многочлены 5-й степени с ко-
эффициентом 1 при х
0
;
2) определить методом проверки общих корней делимость рассматри-
ваемых многочленов на многочлены х+1 и х
2
+х+1 и выявить неприводимые;
3) правильность решения проверить по приложению.
3.15. Найти последовательности корней неприводимых двоичных мно-
гочленов 5-й степени из предыдущей задачи.
Рекомендации по решению
1) построить циклотомические классы по модулю 2
5
–1=31. Поскольку
31 – простое число, все ненулевые элементы поля GF(2
5
), являющиеся ис-
комыми корнями, имеют порядок 31,
и их число равно 30, т. е. всего суще-
ствует 6 неприводимых двоичных многочленов 5-й степени, а следователь-
но, и 6 циклотомических классов по модулю 31. Все эти многочлены явля-
ются примитивными;
2) по составу циклотомических классов найти пары двойственных
многочленов;
3) используя результаты решения задач 2.25 и 3.14, установить соот-
ветствие между найденными неприводимыми многочленами и последова-
тельностями их корней;
4) правильность решения проверить по приложению.
4. Разложение х
n
–1 на неприводимые сомножители
Методика определения неприводимых сомножителей двучленов вида x
n
–1.
Методика определения порядка корней сомножителей двучленов вида x
n
–1.
Методика использования таблиц неприводимых многочленов для на-
хождения неприводимых сомножителей двучленов вида x
n
–1 по их корням.
Решение задач по разложению двучленов x
n
–1 на неприводимые со-
множители с использованием таблиц неприводимых многочленов.
Литература: см. 2.4.
Цель. Привить студентам навыки нахождения неприводимых сомно-
жителей двучленов вида x
n
–1, определения значения и порядка корней
многочленов.
Контрольные вопросы
4.1. Найти все неприводимые сомножители двучленов следующих
степеней: 23, 51, 73, 85, 127.
4.2. Указать, какие из найденных в п. 4.1 многочленов являются при-
митивными (см. [1] и приложение).
4.3. Определить максимальную степень неприводимых в двоичном по-
ле многочленов в разложении двучленов степеней 255 и 511. Каким показа-
телям принадлежат эти многочлены?
4.4. Написать в общепринятом виде многочлены, заданные в двоично-
восьмеричном представлении: 7, 13, 23, 45, 103, 211, 435, 1021, 2011, 4005.
4.5. Написать в двоично-восьмеричном представлении многочлены,
найденные в п. 4.1.
Примеры решения задач и дополнительные задачи
4.6. Определить степени, число и вид неприводимых над GF(2) много-
членов, входящих в разложение двучленов х
127
+1 и х
255
+1.
Решение
1. Многочлен х
127
+1 = х
7
2
1
+1. Поскольку 7 – простое число, в раз-
ложение на неприводимые сомножители х
127
+1 над GF(2) входят только
х+1 и неприводимые многочлены 7-й степени. Их число равно
(127)
126
18
7
7
.
Все эти 18 многочленов принадлежат показателю 127. Из приложения
найдем вид девяти неприводимых двоичных многочленов степени 7 в дво-
ично-восьмеричном представлении: 211, 217, 235, 367, 277, 325, 203, 313,
345. Дополнив эти многочлены двойственными им 221, 361, 271, 357, 375,
253, 301, 323, 247, завершаем решение первой части задачи.
2. Многочлен х
255
+1=х
8
2
1
+1. Поскольку 8 делится на числа 2 и 4, в
разложение х
255
+1 на неприводимые сомножители входят, кроме неприво-
димых многочленов 8-й степени, неприводимые многочлены 4-й и 2-й сте-
пеней. Определим число многочленов каждой из этих степеней, входящих
в разложение х
255
+1.
Для этого представим 255 в виде простых сомножителей: 255=3·5·17.
Это значит, что х
255
+1 делят х
3
+1, х
5
+1, х
15
+1, х
17
+1, х
51
+1 и х
85
+1. Из этого
делаем вывод, что в разложение х
255
+1 входят некоторые неприводимые
многочлены, не принадлежащие показателю 255:
х+1 – принадлежит показателю 1,
х
2
+х+1 – принадлежит показателю 3,
х
4
+х
3
+х
2
+х+1 – принадлежит показателю 5,
х
4
+х+1, х
4
+х
3
+1 – принадлежат показателю 15,
два многочлена 8-й степени, принадлежащие показателю 17:
17
16
2
8
8
,
четыре многочлена 8-й степени, принадлежащие показателю 51:
51
32
4,
8
8
восемь многочленов 8-й степени, принадлежащие показателю 85:
85
64
8.
8
8
Кроме того, в разложение х
255
+1 входят
(255)
128
16
8
8
многочле-
нов 8-й степени, принадлежащих показателю 255. Многочлены 8-й степени
найдем из приложения. Для этого необходимо определить образующие со-
ответствующих циклотомических классов.
Значения образующих:
- для многочленов, принадлежащих к показателю 17: s =
255
15;
17
это-
му числу соответствует многочлен 15 727 D: х
8
+х
7
+х
6
+х
4
+х
2
+х+1. Это само-
двойственный многочлен. Значит, должен быть еще один многочлен, при-
надлежащий показателю 17; таковым является многочлен 45 471 А:
х
8
+х
5
+х
4
+х
3
+1 также самодвойственный;
- для многочленов, принадлежащих показателю 51, числа s равны 5 и 25.
Это многочлены 5 763 D: х
8
+х
7
+х
6
+х
5
+х
4
+х+1 и х
8
+х
7
+х
4
+х
3
+х
2
+х+1 и
25 433 В: х
8
+х
4
+х
3
+х+1 и х
8
+х
7
+х
5
+х
4
+1;
- для многочленов, принадлежащих к показателю 85, числа s=3, 9, 21 и 27.
Вид многочленов 8-й степени, принадлежащих к показателям 85 и 255,
предлагается найти самостоятельно.
4.7. Найти неприводимые многочлены степени 9, принадлежащие по-
казателю, меньшему 511.
Решение
Число 511 можно представить в виде 511=7×73. Из этого следует, что
многочлены 9-й степени могут принадлежать помимо показателя 511 к по-
казателю 73.
Число неприводимых многочленов 9-й степени, принадлежащих пока-
зателю 73:
73
72
8.
9
9
Образующие циклотомических классов, соответствующих корням
этих многочленов, составляют числа, кратные j = 7.
Из приложения находим, что им соответствуют следующие многочле-
ны 9-й степени:
7 1231 А и двойственный многочлен 1145,
21 1027 А и двойственный многочлен 1641,
35 1401 С и двойственный многочлен 1003,
77 1511 С и двойственный многочлен 1113.
Записать эти многочлены в обычном виде предлагается самостоятельно.
5. Декодер Меггита
Структурная схема декодера Меггита.
Алгоритм исправления ошибки по методу Меггита.
Расчет комбинации, на которую настраивается дешифратор.
Расчет эффективности исправления ошибок в канале с группировани-
ем ошибок.
Оценка выигрыша от декорреляции ошибок.
Литература: [6].
Цель. Изучить принцип построения и алгоритм работы декодера Мег-
гита для циклических кодов, исправляющих однократную ошибку. При-
вить студентам навыки вычисления значения синдрома ошибки, соответст-
вующего моменту исправления ошибки.
Контрольные вопросы
5.1. Нарисовать схему декодера Меггита для исправления однократ-
ных ошибок укороченными циклическими кодами Хемминга:
а) (10,5) с g(x) = 1+x
2
+x
5
;
б) (11,5) c g(x) = 1+x+x
6
;
в) (12,5) c g(x) = 1+x+x
7
.
5.2. Для каждого кода из предыдущей задачи определить комбинацию,
на которую должен быть настроен дешифратор, и показать по тактам рабо-
ту синдромного регистра при выводе информационных разрядов принятой
комбинации из буферного регистра, начиная с того момента, когда в нем
сформировался синдром, до момента исправления ошибки. Считать, что
ошибка произошла в символе кодовой комбинации, соответствующем ко-
эффициенту при x
7
.
Примеры решения задач и дополнительные задачи
5.3. Построить
порождающую и проверочную матрицы укороченного
циклического кода (10,5) с порождающим многочленом g(x) = 1+ х
2
+ х
5
.
Решение