Файл: Теория и практика помехоустойчивого.pdf

МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ,
СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ
им. проф. М. А. БОНЧ-БРУЕВИЧА»
(СПбГУТ)
С. С. Владимиров
ТЕОРИЯ И ПРАКТИКА
ПОМЕХОУСТОЙЧИВОГО
КОДИРОВАНИЯ
Математические основы
Практикум
Санкт-Петербург
2021

УДК XXX.XXX.X (XXX)
ББК XX.XXX.X xXX
В 57
Рецензент
— —
Рекомендован к печати редакционно-издательским советом СПбГУТ
В 57
Владимиров, С. С.
Теория и практика помехоустойчивого кодирования. Математические основы : практикум / С. С. Владимиров ; СПбГУТ. — СПб, 2021. — 22 с.
Призван ознакомить студентов старших курсов с математическими осно- вами теории помехоустойчивого кодирования и простыми помехоустойчивы- ми кодами. Представленный материал служит справочным и методическим по- собием при выполнении практических работ по дисциплинам «Теория и прак- тика помехоустойчивого кодирования» и «Помехоустойчивое кодирование в инфокоммуникационных системах».
Предназначен для студентов, обучающихся по направлениям 09.03.01
«Информатика и вычислительная техника» и 11.03.02 «Инфокоммуникацион- ные технологии и системы связи».
УДК XXX.XXX.X (XXX)
ББК XX.XXX.X xXX
© Владимиров С. С., 2021
© Федеральное государственное бюджетное образовательное учреждение высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича», 2021

Содержание
Практическая работа 1.
Математические основы
4
Практическая работа 2.
Двоичные поля Галуа GF(2
m
)
8
Практическая работа 3.
Алгоритмы для проведения расчетов в двоич- ных полях Галуа
............................................................................................... 12
Практическая работа 4.
Код Хэмминга
......................................................... 14
Практическая работа 5.
Изучение принципа работы кодера системати- ческого циклического кода Хэмминга
........................................................... 17
Практическая работа 6.
Изучение принципа работы декодера Меггитта для систематического циклического кода Хэмминга
................................... 19 3

Практическая работа 1
Математические основы
1.1. Цель работы
Рассмотреть на примере и получить навыки в решении задач по темам
«Двоичная алгебра», «Операции с матрицами», «Операции с полиномами»,
«Комбинаторика» в части, относящейся в вопросам помехоустойчивого ко- дирования.
1.2. Рекомендуемая литература
1. Ковриженко Г.А. Системы счисления и двоичная арифметика: От счета на пальцах до ЭВМ. К. : Рад. шк., 1984. 79 с.
2. Ланкастер П. Теория матриц: Пер. с англ. 2-е изд. М. : Наука, 1982.
272 с.
3. Винберг Э.Б. Алгебра многочленов. М. : Просвещение, 1980. 176 с.
1.3. Порядок выполнения задания
Задание выполняется каждым учащимся индивидуально. Поскольку за- дания практикума связаны с заданиями лабораторного практикума, для их выполнения рекомендуется либо использовать отдельную тетрадь, либо под- шивать листы с решением в папку.
1.3.1.
Перевести десятичное число в двоичную систему счисления и совер- шить обратное преобразование. Число задано в табл.
1.1
. Вариант выбирается по последним двум цифрам номера студенческого билета (зачетной книжки).
Таблица 1.1
Задание для перевода числа из десятичной системы счисления в двоичную
Предпосл.
Последняя цифра номера студ. билета цифра номера
1 2
3 4
5 6
7 8
9 0
1 2217 2944 2819 2289 2489 2843 2121 2851 2665 2983 2
2226 2525 2617 2713 2166 2675 2113 2138 2301 2318 3
2232 2262 2100 2619 2528 2572 2697 2672 2535 2724 4
2587 2883 2453 2305 2621 2525 2591 2158 2587 2657 5
2980 2987 2525 2180 2467 2415 2203 2866 2907 2617 6
2929 2240 2142 2809 2129 2412 2201 2853 2608 2542 7
2738 2380 2228 2570 2962 2489 2773 2526 2186 2345 8
2446 2464 2482 2826 2672 2930 2322 2611 2785 2101 9
2496 2676 2909 2687 2990 2474 2850 2312 2619 2999 0
2589 2541 2632 2857 2628 2652 2551 2937 2201 2550 4

1.3.2.
Для заданных матриц A и B осуществить следующие операции.
1. Поэлементное сложение матриц.
2. Транспонирование матрицы B.
3. Умножение матрицы A на транспонированную матрицу B.
Матрица A выбирается из табл.
1.2
по предпоследней цифре номера сту- денческого билета (зачетной книжки). Матрица B выбирается из табл.
1.3
по последней цифре номера студенческого билета (зачетной книжки).
Таблица 1.2
Матрица A. Выбирается по предпоследней цифре номера студ. билета
Цифра номера
Матрица
Цифра номера
Матрица
1


9 19 4
3 5
3 19 19 9
5 16 7


6


10 6 19 16 7
8 6
5 1
8 9
9


2


11 19 14 17 14 5
10 5
1 14 4
17


7


4 1
12 5 9
19 4
8 12 4
20 4


3


4 20 13 6
7 18 12 16 9 10 10 8


8


17 13 20 14 5
8 10 6
7 4
13 14


4


18 17 6
20 19 8
20 1
18 13 4
13


9


6 12 13 15 11 7
9 9
9 16 11 9


5


3 12 17 15 7
9 20 11 10 14 16 9


0


15 6 16 11 8
4 9
5 8
9 12 17


Таблица 1.3
Матрица B. Выбирается по последней цифре номера студ. билета
Цифра номера
Матрица
Цифра номера
Матрица
1


1 18 6
20 13 17 6
16 17 7
14 15


6


7 5
10 16 16 9
1 16 5
12 15 12


2


14 14 15 15 10 16 8
16 3
1 3
9


7


10 15 17 7
2 19 4
20 15 11 16 11


3


14 10 16 9
14 3
20 10 6
20 13 9


8


7 12 1
4 2 12 18 5 2 18 15 6


5

Продолжение табл. 1.3
Матрица B. Выбирается по последней цифре номера студ. билета
Цифра номера
Матрица
Цифра номера
Матрица
4


2 19 7
10 15 12 20 10 3
1 4
3


9


20 15 3 7
19 12 7 16 13 16 6 11


5


17 16 10 7
4 18 12 18 12 20 11 12


0


19 2 7
13 12 2 18 8
4 4
3 1


1.3.3.
Для заданных двоичных полиномов a(x) и b(x) осуществить следующие операции.
1. Сложение полиномов.
2. Произведение полиномов.
3. Деление полинома a(x) на полином b(x).
Полиномы a(x) и b(x) выбираются из табл.
1.4
. Полином a(x) по пред- последней цифре номера студенческого билета (зачетной книжки). Полином b
(x) по последней цифре номера студенческого билета (зачетной книжки).
Таблица 1.4
Полиномы a(x) и b(x)
Предп.
Полином a(x)
Посл.
Полином b(x)
цифра цифра
1
x
6
+ x
2
+ x + 1 1
x
3
+ x
2
+ 1 2
x
7
+ x
4
+ x
2 2
x
3
+ x + 1 3
x
6
+ x
5
+ x
3
+ 1 3
x
2
+ x + 1 4
x
7
+ x
3
+ x
2
+ 1 4
x
3
+ x
2 5
x
6
+ x
4
+ x
2
+ x
5
x
2
+ x
6
x
7
+ x
6
+ x + 1 6
x
3
+ x
7
x
6
+ x
3
+ x
2
+ 1 7
x
2
+ 1 8
x
7
+ x
5
+ x
4
+ x
8
x
3
+ 1 9
x
6
+ x
4
+ x
3
+ 1 9
x
4
+ x
2
+ 1 0
x
7
+ x
6
+ x + 1 0
x
4
+ x + 1 1.4. Порядок защиты практической работы
Защита работы может осуществляться одним из нижеперечисленных спо- собов или их сочетанием на усмотрение преподавателя.
1. Устный ответ по теме работы.
2. Тестирование по теме работы
3. Задача по теме работы.
6

4. Иные варианты на усмотрение преподавателя.
7

Практическая работа 2
Двоичные поля Галуа GF(2
m
)
2.1. Цель работы
Рассмотреть на примере и получить навыки в решении задач по теме
«Конечные поля Галуа» в части, относящейся в вопросам помехоустойчивого кодирования.
2.2. Рекомендуемая литература
1. Владимиров С.С. Математические основы теории помехоустойчиво- го кодирования : учебное пособие. СПб. : СПбГУТ, 2016. 96 с. ISBN:
978-5-
89160-131-4 2. Когновицкий О.С., Охорзин В.М. Теория помехоустойчивого коди- рования. Часть 1. Циклические коды : учебное пособие. СПб. : СПбГУТ, 2013.
84 с.
3. Когновицкий О.С. Основы циклических кодов. Учебное пособие. Л. :
ЛЭИС, 1990. 64 с.
4. Ковриженко Г.А. Системы счисления и двоичная арифметика: От счета на пальцах до ЭВМ. К. : Рад. шк., 1984. 79 с.
5. Ланкастер П. Теория матриц: Пер. с англ. 2-е изд. М. : Наука, 1982.
272 с.
6. Винберг Э.Б. Алгебра многочленов. М. : Просвещение, 1980. 176 с.
2.3. Порядок выполнения задания
Задание выполняется каждым учащимся индивидуально. Поскольку за- дания практикума связаны с заданиями лабораторного практикума, для их выполнения рекомендуется либо использовать отдельную тетрадь, либо под- шивать листы с решением в папку.
Все расчеты должны быть расписаны максимально подробно.
2.3.1.
Для заданного полинома p
1
(x) показать, что он не является неприводи- мым. Для этого попытаться построить соответствующее поле Галуа. Полином p
1
(x) выбирается из табл.
2.1
по предпоследней цифре номера зачетной книж- ки/студ. билета.
8

Таблица 2.1
Полином p
1
(x). Выбирается по предпоследней цифре номера студ. билета
Цифра номера
Полином
Цифра номера
Полином
1
x
4
+ x
2
+ x + 1 6
x
4
+ x
3
+ x + 1 2
x
4
+ x
3
+ x
2
+ 1 7
x
5
+ x + 1 3
x
5
+ x
2
+ x + 1 8
x
5
+ x
3
+ x + 1 4
x
5
+ x
3
+ x
2
+ 1 9
x
5
+ x
4
+ x + 1 5
x
5
+ x
4
+ x
2
+ 1 0
x
5
+ x
4
+ x
3
+ 1 2.3.2.
Для заданного образующего полинома p
2
(x) получить первые двадцать элементов конечного поля. Полином p
2
(x) выбирается из табл.
2.2
по послед- ней цифре номера зачетной книжки. Полученные элементы записать в табл.
2.3
Таблица 2.2
Полином p
2
(x). Выбирается по последней цифре номера студ. билета
Цифра номера
Полином
Цифра номера
Полином
1
x
7
+ x
3
+ x
2
+ x + 1 6
x
7
+ x
4
+ x
3
+ x
2
+ 1 2
x
7
+ x
5
+ x
2
+ x + 1 7
x
7
+ x
5
+ x
3
+ x + 1 3
x
7
+ x
5
+ x
4
+ x
3
+ 1 8
x
7
+ x
6
+ x
3
+ x + 1 4
x
7
+ x
6
+ x
4
+ x + 1 9
x
7
+ x
6
+ x
4
+ x
2
+ 1 5
x
7
+ x
6
+ x
5
+ x
2
+ 1 0
x
7
+ x
6
+ x
5
+ x
4
+ 1
Таблица 2.3
Таблица для записи элементов поля
Элемент
Полином
Двоичный вид поля a
0
+ a
1
x
+ a
2
x
2
+ ... + a
6
x
6
{a
0
a
1
a
2
a
3
a
4
a
5
a
6
}
2.3.3.
Для заданного поля Галуа (см. табл.
2.4
) осуществить расчет по задан- ной формуле. Формула берется из табл.
2.5
. Номер формулы соответству- ет предпоследней цифре зачетной книжки. Значения переменных берутся из табл.
2.6
по последней цифре номера зачетной книжки.
9

Таблица 2.4
Поле Галуа GF(2 4
). p(x) = x
4
+ x + 1.
Элемент
Полином
Двоичный вид поля a
0
+ a
1
x
+ a
2
x
2
+ a
3
x
3
{a
0
a
1
a
2
a
3
}
ε
0
= 1 1
1000
ε
x
0100
ε
2
x
2 0010
ε
3
x
3 0001
ε
4 1 + x
1100
ε
5
x
+ x
2 0110
ε
6
x
2
+ x
3 0011
ε
7 1 + x + x
3 1101
ε
8 1 + x
2 1010
ε
9
x
+ x
3 0101
ε
10 1 + x + x
2 1110
ε
11
x
+ x
2
+ x
3 0111
ε
12 1 + x + x
2
+ x
3 1111
ε
13 1 + x
2
+ x
3 1011
ε
14 1 + x
3 1001
Таблица 2.5
Формула для рассчета. По предпоследней цифре номера зачетной книжки
Цифра
Формула
Цифра
Формула
1
a
+ b c
+ ad e
6
ab a
+ c
+ d e
2
ab
+
b
+ c d
e
7
(a + c)b e
+
d c
3
ad b
+ c
+ a e
8
(a e
+ b)c +
d a
4
(a + b)c +
d e
a
9
a c
+ (b + c e
)d
5
a e
b
+ c
+ cd
0
a
+ d e
bc
+ c
10

Таблица 2.6
Переменные для рассчета. По последней цифре номера зачетной книжки
Последняя цифра номера
1 2
3 4
5 6
7 8
9 0
a
ε
12
ε
11
ε
10
ε
9
ε
8
ε
7
ε
6
ε
5
ε
4
ε
3
b
ε
2
ε
3
ε
4
ε
5
ε
7
ε
6
ε
8
ε
9
ε
10
ε
11
c
ε
14
ε
12
ε
11
ε
8
ε
6
ε
4
ε
2
ε
13
ε
11
ε
9
d
ε
3
ε
5
ε
7
ε
11
ε
9
ε
13
ε
12
ε
10
ε
8
ε
6
e
2 3
4 5
6 2
3 4
5 6
2.3.4.
Для заданного поля Галуа (см. табл.
2.4
) и элементов поля a и b най- ти характеристическую матрицу F
b и осуществить умножение элемента a на элемент b, используя матрицу F
b
. Значения элементов a и b выбираются из табл.
2.7
по предпоследней и последней цифрам номера зачетной книжки со- ответственно.
Таблица 2.7
Переменные для умножения по характеристической матрице
Предпоследняя цифра номера
1 2
3 4
5 6
7 8
9 0
a
ε
12
ε
11
ε
10
ε
9
ε
8
ε
7
ε
6
ε
5
ε
4
ε
3
Последняя цифра номера
1 2
3 4
5 6
7 8
9 0
b
ε
2
ε
3
ε
4
ε
5
ε
7
ε
6
ε
8
ε
9
ε
10
ε
11 2.4. Порядок защиты практической работы
Защита работы может осуществляться одним из нижеперечисленных спо- собов или их сочетанием на усмотрение преподавателя.
1. Устный ответ по теме работы.
2. Тестирование по теме работы
3. Задача по теме работы.
4. Иные варианты на усмотрение преподавателя.
11

Практическая работа 3
Алгоритмы для проведения расчетов в двоичных полях
Галуа
3.1. Цель работы
Рассмотреть на примере основные алгоритмы для проведения вычисле- ний в двоичных полях Галуа.
3.2. Рекомендуемая литература
1. Математические основы теории помехоустойчивого кодирования :
учебное пособие / С. С. Владимиров ; СПбГУТ. — СПб, 2016. — 96 с. — ISBN
978-5-89160-131-4.
3.3. Порядок выполнения задания
Задание выполняется каждым учащимся индивидуально. Поскольку за- дания практикума связаны с заданиями лабораторного практикума, для их выполнения рекомендуется либо использовать отдельную тетрадь, либо под- шивать листы с решением в папку.
Все расчеты должны быть расписаны максимально подробно.
3.3.1. Определение обратного элемента поля на основе расширенного алгоритма Евклида
Для заданного поля Галуа (табл.
2.4
) определить по расширенному алго- ритму Евклида (разд. 7.3.1 учебного пособия) обратный элемент для элемента поля a, указанного в табл.
3.1
Таблица 3.1
Переменные для рассчета. По номеру студента в журнале
№ вар.
a b
№ вар.
a b
№ вар.
a b
№ вар.
a b
№ вар.
a b
1
ε
1
ε
4 7
ε
7
ε
10 13
ε
13
ε
4 19
ε
5
ε
10 25
ε
11
ε
3 2
ε
2
ε
5 8
ε
8
ε
11 14
ε
14
ε
5 20
ε
6
ε
11 26
ε
12
ε
4 3
ε
3
ε
6 9
ε
9
ε
12 15
ε
1
ε
6 21
ε
7
ε
12 27
ε
13
ε
5 4
ε
4
ε
7 10
ε
10
ε
13 16
ε
2
ε
7 22
ε
8
ε
13 28
ε
14
ε
6 5
ε
5
ε
8 11
ε
11
ε
14 17
ε
3
ε
8 23
ε
9
ε
14 29
ε
1
ε
7 6
ε
6
ε
9 12
ε
12
ε
3 18
ε
4
ε
9 24
ε
10
ε
2 30
ε
2
ε
8 12

3.3.2. Умножение двух элементов поля по алгоритму
«сдвиг-со-сложением, справа-налево»
Для заданного поля Галуа (табл.
2.4
) осуществить умножение элемен- тов поля a и b (табл.
3.1
) по алгоритму «сдвиг-со-сложением, справа-налево»
(разд. 7.3.2 учебного пособия).
3.3.3. Умножение двух элементов поля по алгоритму
Карацубы–Офмана
Для заданного поля Галуа (табл.
2.4
) осуществить умножение элементов поля a и b (табл.
3.1
) по алгоритму Карацубы–Офмана (разд. 7.3.3 учебного пособия).
Важно: В результате алгоритма Карацубы–Офмана получается полином c(x), кото- рый имеет длину до 2
m
−1 двоичных элементов. Следовательно, чтобы определить элемент поля c ∈ GF(2
m
), равный a · b, необходимо привести полином c(x) по модулю образующего многочлена поля p(x).
3.3.4. Умножение двух элементов поля по алгоритму
Рейхани-Мазолеха
Для заданного поля Галуа (табл.
2.4
) осуществить умножение элементов поля a и b (табл.
3.1
) по алгоритму Рейхани-Мазолеха (разд. 7.3.4 учебного пособия).
3.4. Порядок защиты практической работы
Защита работы может осуществляться одним из нижеперечисленных спо- собов или их сочетанием на усмотрение преподавателя.
1. Устный ответ по теме работы.
2. Тестирование по теме работы
3. Задача по теме работы.
4. Иные варианты на усмотрение преподавателя.
13

Практическая работа 4
Код Хэмминга
4.1. Цель работы
Рассмотреть на примере и получить навыки в исследовании кодов Хэм- минга.
4.2. Рекомендуемая литература
1. Владимиров С.С. Математические основы теории помехоустойчиво- го кодирования : учебное пособие. СПб. : СПбГУТ, 2016. 96 с. ISBN:
978-5-
89160-131-4 2. Когновицкий О.С., Охорзин В.М. Теория помехоустойчивого коди- рования. Часть 1. Циклические коды : учебное пособие. СПб. : СПбГУТ, 2013.
84 с.
3. Когновицкий О.С. Основы циклических кодов. Учебное пособие. Л. :
ЛЭИС, 1990. 64 с.
4.3. Порядок выполнения задания
Задание выполняется каждым учащимся индивидуально. Поскольку за- дания практикума связаны с заданиями лабораторного практикума, для их выполнения рекомендуется либо использовать отдельную тетрадь, либо под- шивать листы с решением в папку.
Все расчеты должны быть расписаны максимально подробно.
4.3.1.
По заданной для (n,k) кода Хэмминга (15,11) порождающей матрице
G
(15,11)
получить проверочную матрицу H
(15,11)
G
(15,11)
=


















1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1


















14