Теория информации (1920,00 руб.)

Стр.2

Стр.3

Стр.4

УДК 519.72(075) ББК 22.184я73 Ч-88 Рецензенты: А. И. Задорин, д-р физ.-мат. наук, зав. лабораторией «Математическое моделирование в механике» Омского филиала Института математики им. С. Л. Соболева СО РАН; Б. К. Нартов, канд. физ.-мат. наук, доцент РАН, ст. науч. сотрудник лаборатории «Методы преобразования и представления информации» Омского филиала Института математики им. С. Л. Соболева СО РАН; Т. А. Юрина, канд. техн. наук, доцент, доцент кафедры «Цифровые технологии» СибАДИ Чуканов, С. Н. Теория информации : учеб. пособие / С. Н. Чуканов, В. Н. Цыганенко ; Минобрнауки России, Ом. гос. техн. ун-т. – Омск : Изд-во ОмГТУ, 2022. – 1 CD-ROM (1,72 Мб). – Систем. требования: процессор с частотой 1,3 ГГц и выше ; 256 Мб RAM и более ; свободное место на жестком диске 300 Мб и более ; Windows XP и выше ; разрешение экрана 1024×768 и выше ; CD/DVD-ROM дисковод ; Adobe Acrobat Reader 5.0 и выше. – Загл. с титул. экрана. – ISBN 978-5-8149-3526-7. В учебном пособии рассмотрены методы анализа информационных систем. Представлены примеры и упражнения для самостоятельной работы. Предназначено для студентов бакалавриата (09.03.01) и магистратуры (09.04.01), обучающихся по направлению «Информатика и вычислительная техника». Редактор М. А. Болдырева Компьютерная верстка О. Г. Белименко –––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––––– Сводный темплан 2022 г. Для дизайна этикетки использованы материалы из открытых интернет-источников Подписано к использованию 14.10.22. Объем 1,72 Мб. 2 © ОмГТУ, 2022

Стр.2

ОГЛАВЛЕНИЕ ВВЕДЕНИЕ ........................................................................................................ 5 1. КОДЫ И ИХ ИСПОЛЬЗОВАНИЕ ............................................................... 6 1.1. Сообщения ................................................................................................ 6 1.2. Кодирование ............................................................................................. 7 1.3. Основные определения ........................................................................... 8 1 1.4. Экономичное кодирование ................................................................... 11 .5. Кодирование для повышения надежности передачи информации . 12 1.6. Кодирование для безопасной передачи информации ........................ 13 2. БЕСПРЕФИКСНЫЙ КОД ........................................................................... 16 2.1. Проблемы декодирования ..................................................................... 16 2.2. Представление кодов как деревьев ...................................................... 20 2.3. Число Крафта – Макмиллана ............................................................... 22 2.4. Однозначная декодируемость .............................................................. 26 2.5. Доказательство принципа счета ........................................................... 30 3. ЭКОНОМИЧНОЕ КОДИРОВАНИЕ ......................................................... 32 3.1. Понятие источника ................................................................................ 32 3.2. Проблема оптимизации ......................................................................... 36 3.3. Энтропия ................................................................................................. 39 3.4. Энтропия, неопределенность и информация ...................................... 41 3.5. Оптимальные коды – основные теоремы ............................................ 45 3.6. Правило Хаффмана ............................................................................... 49 3.7. Оптимальность кодов Хаффмана ......................................................... 53 4. СЖАТИЕ ДАННЫХ .................................................................................... 56 4.1. Кодирование в блоках ........................................................................... 56 4.2. Распределение произведения множеств .............................................. 59 4.3. Стационарные источники ..................................................................... 62 4.4. Кодирование стационарного источника ............................................. 66 4.5. Алгоритмы сжатия данных ................................................................... 69 4.6. Использование чисел в качестве кодовых слов ................................. 72 4.7. Арифметическое кодирование ............................................................. 75 4.8. Свойства арифметического кодирования ........................................... 79 4.9. Кодирование с динамическим словарем ............................................. 81 5. КАНАЛЫ С ШУМОМ ................................................................................ 88 5.1. Определение канала .............................................................................. 88 5.2. Передача информации источника через канал ................................... 91 3

Стр.3

5.3. Условная энтропия ................................................................................ 93 5.4. Пропускная способность канала .......................................................... 96 5.5. Расчет пропускной способности канала ............................................. 99 6. ПРОБЛЕМА НАДЕЖНОЙ СВЯЗИ ......................................................... 104 6.1. Связь при использовании канала с шумом ....................................... 104 6.2. Расширенный BSC канал .................................................................... 108 6.3. Правила принятия решений ................................................................ 111 6.4. Коррекция ошибки ............................................................................... 116 6.5. Граница упаковки ................................................................................ 118 7. ТЕОРЕМЫ КОДИРОВАНИЯ С ШУМОМ ............................................. 123 7.1. Вероятность ошибки ........................................................................... 123 7.2. Кодирование с заданной скоростью .................................................. 128 7.3. Передача с использованием расширенного BSC канала ................. 131 7.4. Скорость передачи информации ........................................................ 135 7.5. Теорема Шеннона ................................................................................ 138 7.6. Доказательство неравенства Фано ..................................................... 139 8. ЛИНЕЙНЫЕ КОДЫ .................................................................................. 141 8.1. Введение в линейные коды ................................................................. 142 8.2. Построение линейных кодов с использованием матриц ................. 146 8.3. Проверочная матрица линейного кода .............................................. 148 8.4. Код, исправляющий одну ошибку ..................................................... 152 8.5. Проблема декодирования ................................................................... 155 9. АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ КОДИРОВАНИЯ ................................. 162 9.1. Коды Хэмминга ................................................................................... 162 9.2. Циклические коды ............................................................................... 166 9.3. Классификация и свойства циклических кодов ............................... 171 9.4. Коды, которые могут исправить более одной ошибки .................... 176 9.5. Определение семейства кодов BCH .................................................. 179 9.6. Свойства кодов BCH ........................................................................... 184 Заключение ..................................................................................................... 188 БИБЛИОГРАФИЧЕСКИЙ СПИСОК .......................................................... 190 4

Стр.4