Основы теории кодирования (Кудряшов Б.Д.) [2015, учебное пособие, PDF]

Предисловие

1. Введение
1.1. Постановка задачи помехоустойчивого кодирования
1.2. Обзор кодов для защиты информации от ошибок
Выводы
Задачи
Приложение. Биномиальное и полиномиальное распределения

2. Линейные коды
2.1. Арифметика пространства двоичных последовательностей
2.2. Порождающая и проверочная матрицы
2.3. Вычисление расстояния по проверочной матрице
2.4. Примеры кодов
2.5. Синдромное декодирование
2.6. Радиус покрытия и декодирование по минимуму расстояния Хэмминга
2.6.1. Радиус покрытия
2.6.2. Декодирование по соседям нулевого слова
2.6.3. Декодирование по информационным совокупностям
Выводы
Задачи
Приложение. Группы. Основные определения

3. Некоторые границы на характеристики кодов
3.1. Граница Хэмминга
3.2. Граница Варшамова–Гилберта
3.3. Граница Плоткина
3.4. Граница Грайсмера
3.5. Другие границы
3.6. Спектр кода и оценки вероятности ошибки
3.6.1. Граница вероятности ошибки через спектр кода для ДСК
3.6.2. Граница вероятности ошибки для гауссовского канала
3.6.3. Нижняя граница Шеннона
Задачи
Приложение. Тождество Мак-Вильямс

4. Декодирование коротких кодов по максимуму правдоподобия
4.1. Декодирование по максимуму правдоподобия
4.2. Поиск кратчайшего пути в решетке. Алгоритм Витерби
4.3. Минимальная решетка кода
4.4. Построение решетки кода по порождающей матрице
4.5. Построение решетки кода по проверочной матрице
4.6. Декодирование по максимуму апостериорной вероятности с мягкими решениями. Алгоритм БКДР
4.7. Сложность решеток линейных кодов и сложность декодирования по максимуму правдоподобия
4.7.1. Свойства минимальных решеток линейных кодов
4.7.2. Границы сложности решеток
4.8. Практические алгоритмы декодирования
4.8.1. BEAST
4.8.2. Метод порядковых статистик
Задачи

5. Циклические коды
5.1. Порождающий и проверочный полиномы циклического кода
5.2. Примеры циклических кодов
5.3. Кодирование и вычисление синдрома
Задачи
Приложение. Конечные поля
Кольцо вычетов
Кольцо многочленов
Мультипликативная группа поля Галуа
Минимальные многочлены

6. БЧХ-коды и РС-коды
6.1. Определение БЧХ-кода
6.2. Построение БЧХ-кодов. Примеры
6.3. Коды Рида–Соломона
Задачи

7. Декодирование БЧХ- и РС-кодов
7.1. Алгоритм Питерсона–Горенстейна–Цирлера
7.2. Алгоритм Берлекэмпа–Месси
7.3. Алгоритм Форни
7.4. Исправление ошибок и стираний
7.5. Декодирование по минимуму обобщенного расстояния
Задачи
Приложение. Линейная сложность последовательностей

8. Сверточные коды
8.1. Представление сверточного кода
8.2. Свободное расстояние и спектр сверточного кода
8.3. Оценки вероятности ошибки
8.4. Декодирование по максимуму правдоподобия
8.4.1. Реализация алгоритма Витерби
8.5. Высокоскоростные и переменные сверточные коды
8.6. Построение блоковых кодов из сверточных
8.6.1. Усеченные сверточные коды
8.6.2. Циклически усеченные сверточные коды
Задачи

9. Алгебраический подход к сверточным кодам
9.1. Кодер сверточного кода общего вида
9.2. Смитова форма
9.3. Минимальная базовая порождающая матрица
9.4. Проверочная матрица и дуальный код
Выводы
Приложение. МАТЛАБ-программа декомпозиции Смита

10. Длинные коды из коротких кодов
10.1. Итеративные коды
10.2. Каскадные и обобщенные каскадные коды
10.3. Турбо-коды
10.3.1. Выбор компонентных кодов
10.3.2. Турбо-декодирование
10.3.3. Практическая реализация
10.4. Кодированная модуляция
10.4.1. Коды и сигналы
10.4.2. Сигнально-кодовые конструкции
10.4.3. Кодированная модуляция с перемешиванием битов
Задачи

11. Коды с малой плотностью проверок на четность
11.1. Проверочная матрица МППЧ-кода
11.2. Декодирование по принципу распространения доверия
11.3. Графы Таннера и характеристики МППЧ-кодов
11.4. Построение МППЧ-кодов
11.4.1. Квазициклические МППЧ-коды
11.4.2. Кодирование
11.4.3. Обзор конструкций МППЧ-кодов
11.5. Коды для стандартов: результаты моделирования

Литература

Предметный указатель