Основы теории кодирования. Учебное пособие [Б. Д. Кудряшов] (pdf) читать постранично Книга в формате pdf ! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
Цвет фона черный светло-черный бежевый бежевый 2 персиковый зеленый серо-зеленый желтый синий серый красный белый
Цвет шрифта белый зеленый желтый синий темно-синий серый светло-серый тёмно-серый красный
Размер шрифта 14px 16px 18px 20px 22px 24px
Шрифт Arial, Helvetica, sans-serif "Arial Black", Gadget, sans-serif "Bookman Old Style", serif "Comic Sans MS", cursive Courier, monospace "Courier New", Courier, monospace Garamond, serif Georgia, serif Impact, Charcoal, sans-serif "Lucida Console", Monaco, monospace "Lucida Sans Unicode", "Lucida Grande", sans-serif "MS Sans Serif", Geneva, sans-serif "MS Serif", "New York", sans-serif "Palatino Linotype", "Book Antiqua", Palatino, serif Symbol, sans-serif Tahoma, Geneva, sans-serif "Times New Roman", Times, serif "Trebuchet MS", Helvetica, sans-serif Verdana, Geneva, sans-serif
Насыщенность шрифта жирный
Обычный стиль курсив Ширина текста 400px 500px 600px 700px 800px 900px 1000px 1100px 1200px Показывать меню Убрать меню Абзац 0px 4px 12px 16px 20px 24px 28px 32px 36px 40px
Межстрочный интервал 18px 20px 22px 24px 26px 28px 30px 32px
Б. Д. Кудряшов
Допущено Учебно-методическим объединением вузов Российской Федерации
по университетскому политехническому образованию
в качестве учебного пособия для студентов высших учебных заведений,
обучающихся по направлению подготовки бакалавра 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. Метод порядковых статистик . . . . . . . . . .
Задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Последние комментарии
12 часов 4 минут назад
12 часов 59 минут назад
13 часов 2 минут назад
23 часов 53 минут назад
23 часов 55 минут назад
1 день 12 часов назад