Свирид Ю. В. Основы теории информации: Курс лекций / Ю. В. Сви­рид. - Мн.: БГУ, 2003. - 139 с.

ISBN 985-445-946-2

Курс лекций содержит введение в теорию информации и ее приложения. Рассмотрены понятия информации и знтропии для слу­чайных вёличин и случайнык процессов. На основе понятия о типичных последовательностях доказаны три фундаментальные теоре­мы кодирования - о сжатии данных, о передаче данных и о сжатии и передаче данных. Рассмотрены некоторые важные каналы связи и вычислена их пропускная способность. Приведено описание и дока­ зательство оптимальности четырех алгоритмов сжатия данных - Хаффмена, Танстелла, Рябко - Элайеса и Лемпеля - Зива. Даны теоретико-информационные основы криптологии.

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

Оглавление

От автора

4

Введение

7

Глава 1. Что такое информация?

12

1.1.Некоторые понятия из теории вероятностей

12

1.2. Информация и энтропия

15

1.3. Дифференциальная и относительная энтропия

28

1.4. Максимум энтропии

33

1.5. Энтропия дискретных случайных процессов

37

1.6.Эргодические и марковские случайные процессы

41

1.7. Задачи

49

Глава 2. Фундаментальные теоремы кодирования

54

2.1. Типичные последовательности

54

2.2. Сжатие данных и избыточность

57

2.3. Совместно типичные последовательности

60

2.4.Лемма об обработке данных и лемма Фано

64

2.5. Теорема о передаче данных

67

2.6.Теорема о сжатии и передаче данных

74

2.7.Пропускная способность некоторых каналов связи

77

2.8. Задачи

86

Глава 3. Кодирование источника сообщений

89

3.1.Классы кодов источника и неравенство Крафта

89

3.2.Оптимальность кодов, алгоритмы Фано и Шеннона

97

3.3. Алгоритм Хаффмена

104

3.4. Алгоритм Танстелла

107

3.5. Префиксное кодирование натуральных чисел

111

3.6. Алгоритм Рябко – Элайеса

113

3.7. Алгоритм Лемпеля – Зива

115

3.8. Задачи

122

Глава 4. Теоретико-информационные основы криптологии

126

4.1. Классические системы шифрования

126

4.2.Основы теории Шеннона о защите информации

130

4.3. Задачи

133

Литература

134

Предметный указатель

136