Кудряшов Б.Д. Основы теории кодирования

СПб.: БХВ-Петербург, 2016. — 400 с.В учебное пособие, ориентированное на семестровый курс лекций, включены классические разделы теории кодирования: линейные коды, основы построения и декодирования алгебраических кодов. Рассказывается о представлении кодов решетками, о декодировании по максимуму правдоподобия. Приведены основы теории сверточных кодов, введение в каскадные коды, модуляционные коды и турбо-коды. Отдельная глава посвящена низкоплотностным кодам, находящим все более широкое применение в телекоммуникационных стандартах. Все необходимые математические сведения приведены в виде приложений к главам учебного пособия. В книге много численных примеров, детальных алгоритмов, примеров программ MatLAB.Предисловие
ВведениеПостановка задачи помехоустойчивого кодирования
Обзор кодов для защиты информации от ошибок
Выводы
Задачи
Приложение. Биномиальное и полиномиальное распределенияЛинейные коды
Арифметика пространства двоичных последовательностей
Порождающая и проверочная матрицы
Вычисление расстояния по проверочной матрице
Примеры кодов
Синдромное декодирование
Радиус покрытия и декодирование по минимуму расстояния Хэмминга
Радиус покрытия
Декодирование по соседям нулевого слова
Декодирование по информационным совокупностям
Выводы
Задачи
Приложение. Группы. Основные определенияНекоторые границы на характеристики кодов
Граница Хэмминга
Граница Варшамова–Гилберта
Граница Плоткина
Граница Грайсмера
Другие границы
Спектр кода и оценки вероятности ошибки
Граница вероятности ошибки через спектр кода для ДСК
Граница вероятности ошибки для гауссовского канала
Нижняя граница Шеннона
Задачи
Приложение. Тождество Мак-ВильямсДекодирование коротких кодов по максимуму правдоподобия
Декодирование по максимуму правдоподобия
Поиск кратчайшего пути в решетке. Алгоритм Витерби
Минимальная решетка кода
Построение решетки кода по порождающей матрице
Построение решетки кода по проверочной матрице
Декодирование по максимуму апостериорной вероятности с мягкими решениями. Алгоритм БКДР
Сложность решеток линейных кодов и сложность декодирования по максимуму правдоподобия
Свойства минимальных решеток линейных кодов
Границы сложности решеток
Практические алгоритмы декодирования
BEAST
Метод порядковых статистик
ЗадачиЦиклические коды
Порождающий и проверочный полиномы циклического кода
Примеры циклических кодов
Кодирование и вычисление синдрома
Задачи
Приложение. Конечные поля
Кольцо вычетов
Кольцо многочленов
Мультипликативная группа поля Галуа
Минимальные многочленыБЧХ-коды и РС-коды
Определение БЧХ-кода
Построение БЧХ-кодов. Примеры
Коды Рида–Соломона
ЗадачиДекодирование БЧХ- и РС-кодов
Алгоритм Питерсона–Горенстейна–Цирлера
Алгоритм Берлекэмпа–Месси
Алгоритм Форни
Исправление ошибок и стираний
Декодирование по минимуму обобщенного расстояния
Задачи
Приложение. Линейная сложность последовательностейСверточные коды
Представление сверточного кода
Свободное расстояние и спектр сверточного кода
Оценки вероятности ошибки
Декодирование по максимуму правдоподобия
Реализация алгоритма Витерби
Высокоскоростные и переменные сверточные коды
Построение блоковых кодов из сверточных
Усеченные сверточные коды
Циклически усеченные сверточные коды
ЗадачиАлгебраический подход к сверточным кодам
Кодер сверточного кода общего вида
Смитова форма
Минимальная базовая порождающая матрица
Проверочная матрица и дуальный код
Выводы
Приложение. МАТЛАБ-программа декомпозиции СмитаДлинные коды из коротких кодов
Итеративные коды
Каскадные и обобщенные каскадные коды
Турбо-коды
Выбор компонентных кодов
Турбо-декодирование
Практическая реализация
Кодированная модуляция
Коды и сигналы
Сигнально-кодовые конструкции
Кодированная модуляция с перемешиванием битов
ЗадачиКоды с малой плотностью проверок на четность
Проверочная матрица МППЧ-кода
Декодирование по принципу распространения доверия
Графы Таннера и характеристики МППЧ-кодов
Построение МППЧ-кодов
Квазициклические МППЧ-коды
Кодирование
Обзор конструкций МППЧ-кодов
Коды для стандартов: результаты моделированияЛитература
Предметный указатель