Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

Методическое пособие Теория информации-2

.pdf
Скачиваний:
98
Добавлен:
13.02.2015
Размер:
3.99 Mб
Скачать

Министерство образования и науки Российской федерации Российский химико-технологический университет им. Д. И. Менделеева

М. Г. Гордиенко, А. В. Матасов, Н. В. Меньшутина

ТЕОРИЯ ИНФОРМАЦИИ

Москва 2013

УДК 519.7(075)

ББК 32.811

Г68

Рецензенты:

Доктор технических наук, зав. учебно-научным центром ФГУП «ИРЕА»

А.М. Бессарабов

Доктор технических наук, зав. кафедрой информатики и компьютерного проектирования РХТУ им. Д.И. Менделеева

Т.Н. Гартман

Гордиенко М. Г.

Г68 Теория информации: учеб. пособие / М.Г. Гордиенко, А.В. Матасов – М.:

РХТУ им. Д.И. Менделеева, 2013. – __ с. ISBN 978-5-7237-1036-8

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

шумоподавление. Рассмотрены вопросы модуляции и фильтрации сигналов.

Даны базовые алгоритмы кодирования информации и основы ее сжатия и хранения; представлены основные положения теории защиты информации.

Для специалистов химико-технологических специальностей, изучающих системный анализ, и рекомендовано для студентов, обучающихся по специальности «Основные процессы химических производств и химическая кибернетика».

УДК 519.7(075)

ББК 32.811 ISBN 978-5-7237-1036-8 © Российский химико-технологический

университет, 2013 © Гордиенко М. Г., Матасов А. В.,

Меньшутина Н. В., 2013

2

Оглавление

 

Список сокращений

6

Введение

7

1. Дискретная информация

8

1.1. Вероятностный подход к математическому определению

 

дискретной информации

8

1.2. Экспоненциальный закон количества сообщений. Закон больших

 

чисел

11

1.3. Коды с вероятностным ограничением. Языки

18

1.4. Энтропия дискретной информации

21

1.5. Избыточность информации. Шум и отрицательная информация

27

2. Непрерывная информация

32

2.1. Математическое определение непрерывной информации.

 

Теорема отсчётов во временном представлении

32

2.2. Теорема отсчётов в частотном представлении

37

2.3. Преобразование отсчётных значений во времени в отсчетные

 

значения по частоте и обратное преобразование

40

2.4. Распределение вероятностей для непрерывных величин.

 

Эргодические ансамбли функций. Когерентность

41

2.5. Преобразование связей во времени в связи по частоте

46

2.6. Энтропия непрерывных распределений

50

3. Преобразование непрерывных сигналов в дискретные

57

3.1. Общая постановка задачи дискретизации сигнала

57

3.2. Равномерная дискретизация с использованием модели сигнала со

 

спектром, ограниченным частотой

59

3.3. Дискретизация по критерию наибольшего отклонения

63

3.3.1. Дискретизация сигнала с использованием

 

интерполирующих многочленов Лагранжа

64

3.3.2. Дискретизация с использованием экстраполирующих

67

3

 

многочленов Тейлора

 

3.4. Адаптивная дискретизация сигнала

68

3.5. Квантование сигналов

71

4. Системы передачи информации

82

4.1. Системы передачи информации. Общие определения

82

4.2. Скорость передачи дискретной информации и пропускная

 

способность канала. Подавление шумов и надежность

85

4.3. Передача информации непрерывными сигналами по каналам с

 

ограниченной полосой частот. Скорость передачи информации

96

4.3.1. Скорость передачи информации для сигналов с

 

ограниченной средней мощностью

100

4.3.2. Скорость передачи информации для сигналов с

 

ограниченной пиковой мощностью

105

4.4. Фильтрация

107

4.4.1. Классификация фильтров

107

4.4.2. Свойства линейных фильтров

110

4.4.3. Характеристики некоторых линейных фильтров

113

5. Модуляция сигналов

117

5.1. Классификация методов модуляции

118

5.2. Аналоговая модуляция

119

5.2.1. Амплитудная модуляция

119

5.2.2. Частотная модуляция

126

5.2.3. Фазовая модуляция

129

5.3. Импульсная модуляция

129

5.4. Цифровая модуляция (манипуляция)

131

6. Кодирование информации для передачи сообщения по каналу

 

связи

133

6.1. Кодирование информации при передаче по дискретному каналу

 

без помех

134

4

 

6.1.1. Общие принципы построения кодов. Кодовые таблицы и

 

кодовые деревья. Равномерные и неравномерные коды

134

6.1.2. Методика построения статистического кода Шеннона-Фано

138

6.1.3. Код Хаффмана

139

6.1.4. Префиксное кодирование при неизвестной статистике

 

сообщений

144

6.1.5. Недостатки неравномерного кодирования

148

6.2. Помехозащитное кодирование

149

6.2.1. Коды с обнаружением ошибок

150

6.2.2. Корректирующие коды

154

7. Методы сжатия изображений, аудио сигналов и видео

220

7.1. Методы сжатия цифровых изображений

220

7.1.1. Представление цифровых изображений

220

7.1.2. Классификация методов сжатия цифровых изображений

223

7.1.3. Ключевые характеристики алгоритмов сжатия цифровых

 

изображений

224

7.1.4. Алгоритмы сжатия изображений без потерь

226

7.1.5. Алгоритмы сжатия с потерями

 

7.2. Алгоритмы сжатия аудиосигналов

7.2.1. Параметры звукового сигнала

7.2.2. Обзор алгоритмов

7.3. Сжатие видеосигналов

7.3.1. Особенности сжатия видеоданных

7.3.2. Преобразование цветовых пространств

7.3.3. Семплирование

7.3.4. Устранение пространственной статистической избыточности

7.3.5. Стандарты сжатия видеоданных

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

5

8.1.Метод замены

8.2.Шифрование перестановкой

8.3.Шифрование гаммированием

8.4.Криптосистема без передачи ключей

8.5.Криптосистема с открытым ключем

8.6.Электронная подпись

6

Список сокращений

дв. ед. – двоичная единица

ФНЧ –

фильтр нижних частот

ФВЧ –

фильтр верхних частот

ФПП –

полосно-пропускающий фильтр

ФПЗ –

 

полосно-заграждающий фильтр

ФВП –

всепропускающий фильтр

КИХ –

конечная импульсная характеристика

БИХ –

 

бесконечная импульсная характеристика

АЧХ –

амплитудно-частотная характеристика

AЧХ –

фазово-частотная характеристика

АМ –

амплитудная модуляция

ЧМ –

частотная модуляция

ФМ –

фазовая модуляция

АИМ –

амплитудно-импульсная модуляция

ЧИМ –

частотно-импульсная модуляция

ФИМ –

фазо-импульсная модуляция

ШИМ – широтно-импульсная модуляция

ОБП –

 

одна боковая полоса

АМн –

амплитудная манипуляция

ФМн –

фазовая манипуляция

ЧМн –

частотная манипуляция

КАМн – квадратурная манипуляция БЧХ-коды – коды Боуз-Чоудхури-Хоккенгема НОК – наименьшее общее кратное

7

Введение

Информацию можно определить как нематериальную сущность, при помощи которой с любой точностью можно описать материальные,

виртуальные и понятийные сущности. Передача информации является одной из важнейших сторон нашей повседневной жизни: мы постоянно обмениваемся сообщениями, узнаём о событиях из средств массовой информации и т.д.

Информация является основным материалом мышления и лежит в основе всякой умственной деятельности.

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

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

исследующий процессы хранения, преобразования и передачи информации. В

основе его лежит определенный способ измерения количества информации.

Опираясь на основополагающую работу американского математика К. Шеннона (1948), теория информации устанавливает основные границы возможностей систем передачи информации, задаёт исходные принципы их разработки и практического воплощения.

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

коррекции и защиты информации.

8

1. Дискретная информация

1.1. Вероятностный подход к математическому определению дискретной

информации

В повседневной жизни мы часто оцениваем получаемую информацию,

разделяя её на важную и не важную. Таким образом, в соответствии с общежитейским взглядом на информацию сообщение о том, что произойдёт событие, которое должно произойти почти наверняка, содержит в себе мало информации (например, сообщение о том, что начало учебного года в российских школах – 1 сентября). Наоборот, сообщение о том, что произойдёт событие, которое не должно произойти, содержит много информации. Таким образом, сообщение о некотором событии содержит тем больше информации,

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

Поскольку далее будет применён математический аппарат теории вероятностей, то введём несколько основных определений.

Основным понятием теории вероятностей является понятие случайного события. Случайным событием называется событие, которое при осуществлении некоторых условий может произойти или не произойти.

Например, попадание в некоторый объект или промах при стрельбе по этому объекту из данного орудия является случайным событием.

Событие называется достоверным, если в результате испытания оно обязательно происходит. Вероятность достоверного события равна единице.

Невозможным называется событие, которое в результате испытания произойти не может. Вероятность невозможного события равна нулю.

Вероятность случайного события, которое может произойти, а может и не произойти – положительное число, заключённое между нулем и единицей. В

9

общем случае можно сказать, что вероятность наступления случайного события определяется отношением числа появлений события при большом числе независимых испытаний (т.е. при большом числе повторений одних и тех же первоначальных условий) к общему числу испытаний.

Два случайных события называются независимыми, если наступление одного из них не изменяет вероятность наступления другого. Вероятность одновременного наступления двух независимых событий равна произведению вероятностей каждого из этих событий:

 

 

(1.1)

 

 

Если два события взаимно исключают друг друга, то вероятность того,

что произойдет любое из этих событий, равна сумме вероятностей наступления

каждого из них:

 

 

 

(1.2)

 

 

 

Пример. Вычислить вероятность того, что при подбрасывании двух костей сумма выпавших очков будет равна семи. Возможные комбинации, при которых суммарное число очков равно семи, приведены на рис. 1.1.

Рис. 1.1. Возможные комбинации игральных костей, дающие в сумме количество

очков, равное семи

Всего таких комбинаций шесть. Вероятность выпадения любого числа от

1 до 6 равна , тогда вероятность выпадения любой из приведенных выше комбинаций будет равна ∙ = (так как события не зависимые).

Приведенные выше комбинации являются взаимоисключающими,

10