Оглавление
ВВЕДЕНИЕ .......................................... 7
Глава 1. Системные аспекты теории защиты
информации, криптологии и математической
теории информации ......................... . 8
1.1. Задачи и методы защиты информации .......... 8
1.2. Современные задачи криптологии .. . ......... 11
1.3. Шифрование и кодирование, предмет теории
информации ................................. 16
1.4. Схема кодирования информации, кодеры
источника и канала ............................ 18
1.5. Контрольные вопросы ...................... 19
Глава 2. Математические модели источников
открытых сообщений . . . . . . . . . . . . . . . . . . . . . . . 21
2.1. Дискретные источники открытых сообщений ... 21
2.2. Детерминированные модели дискретных
источников открытых сообщений ................ 23
2.3. Стационарные вероятностные модели
дискретных источников сообщений .............. 24
2.4. Модели независимых букв алфавита .......... 25
2.5. Модели независимых биграмм алфавита ....... 27
2.6. Модели марковски зависимых букв алфавита,
глубина зависимости .................. . ...... . 28
2.7. Усложнение моделей. Нестационарные модели
источников сообщений .................... . .... 32
2.8. Построение и использование математических
моделей источников открытых сообщений .......... 33
2.9. Задачи и упражнения ....................... 35
Глава 3. Использование математических моделей
источников сообщений в криптографии . . . . . . 40
3.1. Симметричные и асимметричные шифры ..... . 40
3.2. Шенноновские вероятностные модели шифра ... 44
3.3. Совершенные шифры, шифры Вернама ....... 45
3.4. Задачи и упражнения ...................... 49
Глава 4. Количество информации и энтропия . . . . . . . . . 52
4.1. Измерение информации, генерируемой
дискретным источником ....................... 52
4.2. Энтропия и избыточность дискретного
источника ...................... . ............ 55
4.3. Энтропия двоичного ансамбля ............... 58
4.4. У славна.я энтропия ансамбля ................ 60
4.5. Энтропия ансамбля последовательностей ДПИ .. 63
4.6. Задачи и упражнения ...................... 68
Глава 5. Равномерное кодирование источника
сообщений . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
5.1. Равномерное кодирование дискретного
постоянного источника ......................... 73
5.2. Вероятность ошибки равномерного
кодирования ................................. 74
5. 3. Скорость создания информации .............. 77
5.4. Пряма.я теорема равномерного кодирования .... 78
5.5. Обратна.я теорема равномерного кодирования ... 80
5.6. Свойства типичных последовательностей
для дпи ..................................... 83
5.7. Задачи и упражнения ...................... 85
Глава 6. Теоретические основы неравномерного
кодирования ............................. 90
6.1. Неравномерное побуквенное кодирование
с помощью префиксных кодов ................... 90
6.2. Неравенство Крафта ....................... 95
6.3. Пряма.я и обратна.я теоремы для неравномерного
побуквенного кодирования ..................... 97
6.4. Задачи и упражнения ..................... 100
Глава 7. Неравномерное кодирование
упорядоченных ансамблей .............. . 101
7.1. Коды Шеннона-Фано ...................... 101
7.2. Свойства оптимальных побуквенных кодов ... 103
7.3. Коды Хаффмана, их избыточность ........... 106
7.4. Коды Шеннона ........................... 108
7.5. Задачи и упражнения ..................... 114
Глава 8. Неравномерное кодирование
неупорядоченных ансамблей ............. 117
8.1. Коды Гилберта-Мура ...................... 117
8.2. Неравномерное непобуквенное кодирование
сообщений стационарного источника ............ 122
8.3. Арифметическое кодирование .............. 125
8.4. Сложность вычисления арифметического
кода ....................................... 130
8.5. Декодирование кода Гилберта-Мура
для дискретного постоянного источника .......... 133
8.6. Декодирование арифметического кода для
дискретного постоянного источника ............. 135
8.7. Снижение вычислительной сложности
арифметического кода ........................ 137
8.8. Задачи и упражнения ..................... 139
Глава 9. Универсальное кодирование ............ 144
9.1. Определяющие свойства универсального
кодирования ................................ 144
9.2. Двухпроходное кодирование на примере
кодов Хаффмена ............................. 146
9.3. Регулярные коды ......................... 151
9.4. Задачи и упражнения ..................... 156
Глава 10. Кодирование в дискретных каналах
с шумом .............................. . 158
1 О .1. Проблема помехоустойчивого кодирования
в дискретных каналах с шумом ................. 158
10.2. Постановка задачи помехоустойчивого
кодирования ................................ 159
10.3. Математические модели каналов ........... 163
10.4. Взаимная информация сообщений
и источников сообщений ...................... 167
10.5. Информационная емкость и пропускная
способность канала ........................... 170
10.6. Неравенство Фано ....................... 171
10.7. Обратная теорема кодирования
для дискретных постоянных каналов ............ 174
10.8. Вычисление информационной емкости
каналов без памяти ........................... 175
10.9. Информационная емкость симметричных
каналов .................................... 175
10.10. Прямая теорема кодирования
для дискретных постоянных каналов ............ 179
10.11. Типичные пары последовательностей ...... 180
10.12. Задачи и упражнения ................... 181
Приложения .................................... 184
П.0. Основные обозначения .................... 184
П.1. Выпуклые функции нескольких переменных . 184
П.2. Определяющие понятия и формулы теории
вероятностей ................................ 186
П.3. Неравенства Чебышева. Закон больших чисел. 189
П.4. Асимптотический анализ величин .......... 194
П.5. Понятие об алгоритмах и сложности
вычислений ................................. 196
П.6. Битовая вычислительная сложность операций
сравнения, сложения и умножения чисел. Оценка
Карацубы ................................... 199
П.7. Сложность поиска числа в упорядоченном
массиве . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
П.8. Сложность сортировки неупорядоченного
множества. Сложность сортировки вставками
и слиянием ................................. 209
П.9. Таблицы для расчетов ..................... 214
Использованная литература . ..................... 216