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

Книга в формате pdf! Изображения и текст могут не отображаться!


 [Настройки текста]  [Cбросить фильтры]

Б. Д. Кудряшов

Допущено Учебно-методическим объединением вузов Российской Федерации
по университетскому политехническому образованию
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по направлению подготовки бакалавра 09.03.02
«Информационные системы и технологии» (230400)

Санкт-Петербург
«БХВ-Петербург»
2016

УДК 519.72
ББК 32.811.4
К88

К88

Кудряшов Б. Д.
Основы теории кодирования: учеб. пособие. — СПб.:
БХВ-Петербург, 2016. — 400 с.: ил. — (Учебная литература для вузов)
ISBN 978-5-9775-3527-4
В учебное пособие, ориентированное на семестровый курс лекций, включены классические разделы теории кодирования: линейные коды, основы построения и декодирования алгебраических кодов. Рассказывается о представлении кодов решетками, о декодировании по максимуму правдоподобия. Приведены основы теории сверточных кодов, введение в каскадные коды,
модуляционные коды и турбо-коды. Отдельная глава посвящена низкоплотностным кодам, находящим все более широкое применение в телекоммуникационных стандартах. Все необходимые математические сведения приведены
в виде приложений к главам учебного пособия. В книге много численных примеров, детальных алгоритмов, примеров программ MATLAB.

Для студентов технических вузов, обучающихся
по информационным специальностям, аспирантов и инженеров

УДК 519.72
ББК 32.811.4

Рецензенты:
Е .Т. Мирончиков — д-р техн. наук, проф. Петербургского государственного
унивеситета путей сообщения;
Ф. И. Соловьева — д-р физ.-мат. наук, проф. Новосибирского государственного
университета.

Подписано в печать 31.08.15.
Формат 70 1001/16. Печать офсетная. Усл. печ. л. 32,25.
Тираж 700 экз. Заказ №
"БХВ-Петербург", 191036, Санкт-Петербург, Гончарная ул., 20.
Первая Академическая типография "Наука"
199034, Санкт-Петербург, 9 линия, 12/28.

ISBN 978-5-9775-3527-4

© Кудряшов Б. Д., 2016
© Оформление, издательство "БХВ-Петербург", 2016

Оглавление

Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1. Введение

5

. . . . . . . . . . . . . . . . . . . . . . . . . .

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. Декодирование по информационным
совокупностям . . . . . . . . . . . . . . . .
Выводы . . . . . . . . . . . . . . . . . . . . . . . . . . .
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . .
Приложение. Группы. Основные определения . . . . .

.
.
.
.
.

.
.
.
.
.

5
19
22
23
26
32

.
.
.
.
.

32
37
42
44
48

. . .
. . .
. . .

51
52
54

.
.
.
.

57
62
63
67

.
.
.
.

.
.
.
.

IV

Оглавление

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. Метод порядковых статистик . . . . . . . . . .
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .