Соловьева Ф.И. Введение в теорию кодирования
Подождите немного. Документ загружается.
Оглавление
Введение 3
Основные понятия и определения . . . . . . . . . . . . . . . . . . . . . . . . 5
Двоичный симметричный канал связи . . . . . . . . . . . . . . . . . . . . . 7
1 Линейные коды 9
1.1. Линейные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2. Границы объемов кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.3. Код Хэмминга и его свойства . . . . . . . . . . . . . . . . . . . . . . . 14
1.3.1. Определение кода Хэмминга . . . . . . . . . . . . . . . . . . . . 14
1.3.2. Примеры кодов Хэмминга длины 7 . . . . . . . . . . . . . . . . . 15
1.3.3. Декодирование кода Хэмминга . . . . . . . . . . . . . . . . . . . 15
1.4. Способы построения новых кодов . . . . . . . . . . . . . . . . . . . . . 16
1.5. Теорема Глаголева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2 Декодирование 20
2.1. Декодирование двоичных кодов . . . . . . . . . . . . . . . . . . . . . . 20
2.2. Декодирование линейных кодов . . . . . . . . . . . . . . . . . . . . . . 21
2.2.1. Стандартное расположение. Синдром . . . . . . . . . . . . . . . 21
2.2.2. Свойства синдрома . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3. Вероятность ошибки декодирования . . . . . . . . . . . . . . . . . . . . 25
3 Теорема Шеннона 28
3.1. Необходимые понятия . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2. Свойства энтропии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.3. Необходимые комбинаторно-вероятностные
утверждения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.4. Доказательство теоремы Шеннона . . . . . . . . . . . . . . . . . . . . 33
4 Свитчинговые методы 36
4.1. Коды Васильева . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.2. Конструкция Моллара . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3. Общая идея метода свитчинга . . . . . . . . . . . . . . . . . . . . . . . 40
4.4. Некоторые свойства совершенных кодов . . . . . . . . . . . . . . . . . 41
4.4.1. Дистанционная инвариантность . . . . . . . . . . . . . . . . . . 41
4.4.2. О существовании совершенных кодов . . . . . . . . . . . . . . . 43
4.4.3. Верхняя оценка числа совершенных кодов . . . . . . . . . . . . 45
121
122 Оглавление
5 Каскадные методы 48
5.1. Основная идея каскадного способа построения . . . . . . . . . . . . . 48
5.2. Коды Соловьевой (1981) . . . . . . . . . . . . . . . . . . . . . . . . . . 48
5.3. Коды Романова . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
5.4. Коды Хямяляйнена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.4.1. Код Хэмминга над GF (q) . . . . . . . . . . . . . . . . . . . . . . 53
5.4.2. Конструкция Хямяляйнена . . . . . . . . . . . . . . . . . . . . . 54
5.5. Каскадная конструкция Зиновьева (1988) . . . . . . . . . . . . . . . . 55
5.6. Каскадная конструкция Фелпса (1984) . . . . . . . . . . . . . . . . . . 56
5.7. Обобщенная каскадная конструкция . . . . . . . . . . . . . . . . . . . 57
6 Поля Галуа 60
6.1. Основные определения . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.2. Строение конечных полей . . . . . . . . . . . . . . . . . . . . . . . . . . 62
6.3. Примеры конечных полей . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4. Число неприводимых многочленов . . . . . . . . . . . . . . . . . . . . 67
7 Циклические коды 69
7.1. Определение и свойства . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.2. Порождающий многочлен . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.3. Кодирование циклических кодов . . . . . . . . . . . . . . . . . . . . . . 73
7.4. Проверочный многочлен . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.5. Декодирование циклического кода . . . . . . . . . . . . . . . . . . . . . 77
7.6. Минимальный многочлен и его свойства . . . . . . . . . . . . . . . . . 77
7.7. Число циклических кодов . . . . . . . . . . . . . . . . . . . . . . . . . . 79
8 Коды БЧХ 81
8.1. Нули кода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.2. Циклическое представление кода Хэмминга . . . . . . . . . . . . . . . 82
8.3. Определитель Вандермонда . . . . . . . . . . . . . . . . . . . . . . . . 83
8.4. Граница БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.5. Коды БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
8.6. Двоичные коды БЧХ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
8.7. Коды Рида-Соломона . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
8.7.1. Определение и свойства . . . . . . . . . . . . . . . . . . . . . . . 88
8.7.2. Использование кодов Рида-Соломона для получения двоичных
кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
8.8. Коды Юстесена . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
9 Другие коды 93
9.1. Матрицы Адамара, коды Адамара . . . . . . . . . . . . . . . . . . . . 93
9.1.1. Матрицы Адамара . . . . . . . . . . . . . . . . . . . . . . . . . . 93
9.1.2. Матрица Сильвестра . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.1.3. Матрица Адамара по типу Пэйли . . . . . . . . . . . . . . . . . 96
9.1.4. Коды Адамара . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
9.1.5. Связь кодов Адамара с кодом Хэмминга . . . . . . . . . . . . . 100
9.2. Коды Рида-Маллера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
9.2.1. Коды с параметрами кодов Рида-Маллера . . . . . . . . . . . . 106
Оглавление 123
9.3. Коды Препараты . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
Заключение 115
Ф. И. Соловьева
ВВЕДЕНИЕ В ТЕОРИЮ КОДИРОВАНИЯ
Учебное пособие
Редактор С. Д. Андреева
Подписано в печать 14.06.2006 г.
Формат 84×120 / 8. Офсетная печать.
Уч.-изд. л. 17,7. Усл. печ. л. 14,4. Тираж 200 экз.
Заказ № .
Редакционно-издательский центр НГУ. 630090, Новосибирск-90, ул. Пирогова, 2.