Теория информации. Курс лекций

В. М. Белов, С. Н. Новиков, О. И. Солонская
ТЕОРИЯ ИНФОРМАЦИИ
Курс  лекций
Допущено Сибирским региональным отделением 
УМО по образованию в области информационной 
безопасности в качестве учебного пособия для студентов, 
обучающихся специальности 
090302 – «Информационная безопасность 
телекоммуникационных систем»
Москва
Горячая линия - Телеком
2012

УДК 621.391 (075.8)  
ББК 32.811 
     Б78 
 
Белов В. М., Новиков С. Н., Солонская О. И. 
Б78   Теория информации. Курс лекций. Учебное пособие для 
вузов. – М.: Горячая линия–Телеком, 2012. – 143 с.: ил.  
ISBN 978-5-9912-0237-4. 
Рассмотрены в доступной форме основные положения 
теории информации. Материалы систематизированы по следующим ключевым разделам: определение информационных 
потерь в каналах связи с помехами, построение оптимальных 
кодов, обнаружение и исправление ошибок при использовании различных методов передачи и обработки информации, 
представление кодов в памяти ЭВМ в сжатом виде и в виде 
разнообразных структур.  
Для студентов специальности 090302 – «Информационная 
безопасность телекоммуникационных систем». Может быть 
полезно студентам других инфокоммуникационных и радиотехнических специальностей, аспирантам и специалистам. 
ББК 32.811 
 
Адрес издательства в Интернет www.techbook.ru 
 
Белов Виктор Матвеевич, Новиков Сергей Николаевич,  
Солонская Оксана Игоревна 
Теория информации. Курс лекций. 
Учебное пособие для вузов 
Обложка художника  В. Г. Ситникова 
 
Подписано в печать 19.02.2012. Формат 60Ч88/16. Уч. изд. л. 9,14. Тираж 500 экз. (1-й завод 100 экз.) 
ISBN 978-5-9912-0237-4                       © В. М. Белов, С. Н. Новиков,  
                                                                              О. И. Солонская, 2012 
                                © Издательство «Горячая линия–Телеком», 2012 

Содержание
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1. Введение в теорию информации . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.1. Краткая историческая справка о развитии систем
передачи информации (систем связи) и теории информации
(теории связи) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1.1. Краткая история развития систем связи . . . . . . . . . . . . . 8
1.1.2. О понятии «информация». Краткая история
развития теории информации . . . . . . . . . . . . . . . . . . . . . . . . .10
1.1.2.1. О понятии «информация». . . . . . . . . . . . . . . . . . . .10
1.1.2.2. Краткая историческая справка о развитии
теории информации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11
1.2. Информационные метрики . . . . . . . . . . . . . . . . . . . . . . . . . .13
1.2.1. Структурные меры информации. . . . . . . . . . . . . . . . . . .13
1.2.1.1. Геометрическая мера  . . . . . . . . . . . . . . . . . . . . . . .13
1.2.1.2. Комбинаторная мера  . . . . . . . . . . . . . . . . . . . . . . .14
1.2.1.3. Аддитивная мера  . . . . . . . . . . . . . . . . . . . . . . . . . .16
1.2.2. Статистическая мера  . . . . . . . . . . . . . . . . . . . . . . . . . . .16
1.2.3. Семантическая мера. . . . . . . . . . . . . . . . . . . . . . . . . . . .17
2. Энтропия вероятностной схемы . . . . . . . . . . . . . . . . . . . . . . . . . . .18
2.1. Энтропия, как мера степени неопределенности
физической системы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .18
2.2. Единицы измерения энтропии. . . . . . . . . . . . . . . . . . . . . . . .20
2.3. Основные свойства энтропии простой физической системы  .21
2.4. Энтропия и математическое ожидание. . . . . . . . . . . . . . . . . .23
2.5. Условная энтропия и энтропия объединения . . . . . . . . . . . . .24
Контрольные вопросы к главам 1 и 2 . . . . . . . . . . . . . . . . . . . . . . . .29
3. Основные теоремы Шеннона о характеризации источников
информации  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
3.1. Количество информации в дискретном сообщении.
Дискретные источники сообщений без памяти и с памятью.
Избыточность дискретного источника сообщений . . . . . . . . . . . .31
3.2. Первая теорема Шеннона . . . . . . . . . . . . . . . . . . . . . . . . . . .35
3.2.1. Прямая и обратная теоремы Шеннона для канала
связи без шума. Первый способ доказательства прямой
теоремы Шеннона  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .35
3.2.2. Второй способ доказательства прямой теоремы
Шеннона для канала связи без шума. Метод Фано.
Оптимальные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .40
3.2.3. Практическое применение первой теоремы Шеннона  . .44

3.3. Вторая теорема Шеннона и ее следствия . . . . . . . . . . . . . . . .45
3.3.1. Прямая теорема Шеннона для дискретного
постоянного канала с шумом  . . . . . . . . . . . . . . . . . . . . . . . . .45
3.3.2. Обратная теорема Шеннона для дискретного
постоянного канала с шумом  . . . . . . . . . . . . . . . . . . . . . . . . .47
3.3.3. Следствие из второй теоремы Шеннона . . . . . . . . . . . . .49
3.4. Статистический анализ случайных последовательностей.
Энтропийные и информационные характеристики
случайных последовательностей. . . . . . . . . . . . . . . . . . . . . . . . . .52
Контрольные вопросы к главе 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . .53
4. Статистические модели каналов связи . . . . . . . . . . . . . . . . . . . . . .55
4.1. Математические модели каналов связи . . . . . . . . . . . . . . . . .55
4.1.1. Схема передачи информации. Классификация
каналов связи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .55
4.1.2. Непрерывные каналы связи . . . . . . . . . . . . . . . . . . . . . .58
4.1.3. Дискретные каналы связи  . . . . . . . . . . . . . . . . . . . . . . .60
4.2. Влияние шумов на пропускную способность дискретного
канала связи  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .62
4.3. Пропускная способность систем передачи
информации  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .63
5. Оптимальное кодирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67
5.1. Префиксные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .67
5.2. Неравенство Крафта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .75
5.3. Информационная избыточность. Границы для средней
длины кодов  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .79
Контрольные вопросы к главам 4 и 5 . . . . . . . . . . . . . . . . . . . . . . . .82
6. Обнаружение и исправление ошибок в сообщениях.
Понятие об идее коррекции ошибок. . . . . . . . . . . . . . . . . . . . . . . . . .84
7. Линейное кодирование. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .88
7.1. Свойства помехозащищающих кодов . . . . . . . . . . . . . . . . . . .88
7.1.1. Помехоустойчивые коды и их применение. . . . . . . . . . .88
7.1.2. Основные параметры помехоустойчивых кодов . . . . . . .89
7.1.3. Граничные соотношения между параметрами
помехоустойчивых кодов. . . . . . . . . . . . . . . . . . . . . . . . . . . . .89
7.1.4. Классификация помехоустойчивых кодов. . . . . . . . . . . .90
7.2. Линейные коды. Параметры и свойства. . . . . . . . . . . . . . . . .92
7.3. Код Хэмминга . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .98
Контрольные вопросы к главам 6 и 7 . . . . . . . . . . . . . . . . . . . . . . . 100
8. Циклические коды. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
8.1. Определение и свойства двоичных циклических кодов  . . . . 101
8.2. Систематические циклические коды . . . . . . . . . . . . . . . . . . 105
8.3. Обнаружение пакетов ошибок . . . . . . . . . . . . . . . . . . . . . . . 108

9. Построение и декодирование конкретных циклических кодов . . . .110
9.1. Коды, исправляющие одиночную ошибку,
кодовое расстояние d0 = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .110
9.2. Коды, обнаруживающие трехкратные ошибки, d0 = 4 . . . . .112
9.3. Циклические коды, исправляющие две и большее
количество ошибок, d0 l 5. . . . . . . . . . . . . . . . . . . . . . . . . . . . .113
10. Обнаружение и исправление ошибок при передаче и обработке
информации на стандартной аппаратуре. . . . . . . . . . . . . . . . . . . . . .116
11. Сжатие информации  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .121
Контрольные вопросы к главам 8, 9, 10, 11. . . . . . . . . . . . . . . . . . .126
12. Структурное кодирование. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
Контрольные вопросы к главе 12  . . . . . . . . . . . . . . . . . . . . . . . . . .139
Примерные вопросы к экзамену по дисциплине
«Теория информации» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .140
Библиография . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .142

Предисловие
Дисциплина «Теория информации» определена в государственном
образовательном стандарте высшего профессионального образования
специальности 090302 «Информационная безопасность телекоммуникационных систем» как федеральный компонент общих математических и естественнонаучных дисциплин.
Теория информации тесно связана с другими дисциплинами, изучаемыми студентами. Она предполагает знания таких дисциплин как
«Математический анализ», «Алгебра», «Теория вероятностей и математическая статистика», является базой для дисциплин «Теория радиотехнических сигналов» и «Криптографические методы защиты информации».
Предлагаемое учебное пособие по «Теории информации» отвечает
требованиям большинства разделов программы одноименного курса,
читаемых студентам, обучающимся по специальности 090302 «Информационная безопасность телекоммуникационных систем».
Цель учебного пособия — помочь освоить основные положения теории
информации и кодирования, научить определять информационные потери в каналах связи с помехами, строить оптимальные коды, обнаруживать и исправлять ошибки при различных методах передачи и обработки информации, представлять коды в памяти ЭВМ в сжатом виде и
в виде разнообразных структур.
Материал учебного пособия разбит на 12 тем. В каждой теме предложен необходимый минимум теоретических сведений.
Авторы выражают глубокую благодарность коллегам, работающим в
области защиты информации, А. Б. Архиповой, Е. Н. Пивкину, О. В. Воробьевой за неоценимую помощь в подготовке материалов для данного
пособия.

1. Введение в теорию информации
Теорией информации и кодирования называют науку, изучающую
количественные закономерности, связанные с получением, передачей,
обработкой и хранением информации. Возникнув в 40-х годах ХХ века
из практических задач теории связи, теория информации и кодирования
в настоящее время является необходимым математическим аппаратом
при изучении всевозможных процессов управления.
Черты случайности, присущие процессам передачи информации, заставляют использовать при изучении этих процессов вероятностные методы. При этом невозможно ограничиваться классическими методами
теории вероятностей, так как постоянно возникает необходимость создания новых вероятностных категорий. Поэтому теория информации и
кодирования представляет собой не просто прикладную науку, в которой применяют вероятностные методы исследования, а еще и раздел
теории вероятностей.
Получение, обработка, передача и хранение различного рода информации — непременное условие работы любой управляющей системы.
В этом процессе всегда происходит обмен информацией между различными звеньями системы. Простейший случай — передача информации от
управляющего устройства к исполнительному органу (передача команд).
Более сложный случай — замкнутый контур управления, в котором информацию о результатах выполнения команд передают управляющему
устройству с помощью так называемой «обратной связи».
Любая информация для того, чтобы быть переданной, должна быть
соответственным образом «закодирована», то есть, переведена на язык
специальных символов или сигналов. Сигналами, передающими информацию, могут быть электрические импульсы, световые или звуковые колебания, механические перемещения и т. д.
Одной из задач теории информации является отыскание наиболее
экономных методов кодирования, позволяющих передавать заданную
информацию с помощью минимального количества символов. Эту задачу решают как при отсутствии, так и при наличии искажений (помех)
в канале связи.
Другую типичную задачу теории информации ставят следующим образом: есть источник информации (передатчик), непрерывно вырабатывающий информацию, и канал связи, по которому эту информацию передают в другую инстанцию (приемник). Какова должна быть пропускная
способность канала связи для того, чтобы канал «справлялся» со своей

1. Введение в теорию информации
задачей, то есть передавал всю поступающую информацию без задержек
и искажений?
Ряд задач теории информации относят к определению объема запоминающих устройств, предназначенных для хранения информации, к способам ввода информации в эти запоминающие устройства и вывода ее
для непосредственного использования.
1.1. Краткая историческая справка о развитии
систем передачи информации (систем связи) 
и теории информации (теории связи)
1.1.1. Краткая история развития систем связи
Проблема передачи информации существует с тех пор, как появилось
человеческое общество. Качественный скачок в развитии способов передачи сообщений произошел тогда, когда для этой цели стали использовать электромагнитные явления. Выделим только узловые моменты
на пути развития систем передачи информации, основанные на использовании электромагнитных явлений.
Исторически первой из рассматриваемых систем является телеграф:
1832 г. — первый электромагнитный телеграф был создан русским
ученым-электротехником Павлом Львовичем Шиллингом (не нашел
практического применения);
1833 г. — выдающиеся немецкие математики и физики Карл Фридрих Гаусс и Вильгельм Эдуард Вебер в Геттингене построили первый
электромагнитный игольчатый телеграф;
1837 г. — американский инженер Сэмюэл Фиинли Бриз Морзе предложил самопишущий телеграф;
1844 г. — телеграф С. Морзе получил в Америке практическое применение;
1855 г. — английский изобретатель Дэвид Эдуард Юз создал буквопечатающий телеграфный аппарат;
1866 г. — американский предприниматель Сайрус Уэст Филд проложил трансатлантическую телеграфную линию;
1874 г. — французский изобретатель Жан Морис Эмиль Бодо усовершенствовал телеграфный аппарат с целью лучшего использования
проводов;
1910 г. — осуществили машинную телеграфную передачу с перфоленты;
1927 г. — американский изобретатель и предприниматель Томас Алва
Эдисон реализовал многократную телеграфию.

1. Введение в теорию информации
Следующим по времени возникновения системной передачи информации является телефон. Отметим основные вехи его развития:
1861 г. — немецкий физик и изобретатель Иоганн Филипп Рейс
предложил первую конструкцию телефона;
1876 г. — североамериканский ученый, изобретатель и бизнесмен
Александр Грэм Белл предложил конструкцию телефона, сохранившую
свои основные черты до настоящего времени;
1878 г. — начала действовать в Хартфорде (США) первая телефонная
станция;
1884 г. — между Нью-Йорком и Филадельфией была построена первая междугородняя телефонная линия;
1889 г. — американец Алмон Браун Строуджер изобрел номеронабиратель, что явилось основой для создания автоматических телефонных станций (АТС);
1892 г. — в Ла-Порте (США) была построена первая АТС.
Длинный путь до своего практического осуществления прошло радиовещание.
1867 г. — английский физик Джеймс Кларк Максвелл предсказал существование электромагнитных волн и предложил теорию их распространения;
1887 г. — немецкий физик, лауреат Нобелевской премии по физике
Густав Людвиг Герц доказал существование электромагнитных волн;
1895 г. — русский физик и электротехник Александр Степанович
Попов впервые осуществил радиоприем, применив антенну;
1902 г. — итальянский радиотехник и предприниматель Гульельмо
Маркони принял первую радиопередачу с противоположного берега
Атлантического океана;
1904 г. — английский физик Джон Амброз Флеминг изобрел и запатентовал «выпрямитель» или двухэлектродную электронную лампу —
«диод Флеминга»;
1906 г. — американский инженер Ли де Форест изобрел триод.
Системы передачи изображений практически развивают с 1904 г.,
когда немецкому физику, математику и изобретателю Артуру Корну
удалось передать неподвижное изображение из Мюнхена в Нюрнберг,
а в 1923 г. — из Рима в Бар-Харборг (США).
В 1924 г. Аугуст Каролус использовал открытый в 1875 г. эффект
Джоном Керра (заключающийся в преобразовании колебаний электрического напряжения в колебания освещенности) в системе передачи
изображения;
1926 г. — в Англии произошла первая телепередача по системе шотландского ученого Джона Лоуги Бэрда;
1950 г. — в Америке была осуществлена первая цветная телевизионная передача.

1. Введение в теорию информации
Представленный перечень основных событий из истории развития
четырех систем передачи информации далеко не полон. В обзоре не учтены взаимные связи рассмотренных систем. Большое значение имело
применение радио для целей телеграфии и телефонии. Радиотелеграф и
радиотелефон для передачи сообщений на большие расстояния начали
применять значительно раньше, чем для этой цели смогли использовать
не только радиовещание, но и классический телефон.
Уже начиная с 1927 г., существует регулярное радиотелефонное сообщение через Атлантический океан, а первый телефонный кабель с
усилителями был проложен по дну Атлантики только в 1956 г.
В 1957 г. СССР запустил первый искусственный спутник Земли.
В 1962 г. был запущен первый гражданский телекоммуникационный
спутник «Тельстар» и положено начало созданию систем телекоммуникационных спутников.
Последними достижениями конца ХХ и начала ХХI веков в области
систем связи явились создание Глобальных сетей связи (Интернет) и
развитие сотовой связи.
1.1.2. О понятии «информация».
Краткая история развития теории информации
1.1.2.1. О понятии «информация»
С появлением кибернетики возникло большое количество новых понятий, к которым относят и понятие информации.
Несмотря на то, что слово «информация» появилось давно, оно не
отражает той сущности слова «информация», которую породила кибернетика.
Слово «информация» латинского происхождения, что в переводе означает сообщение о каком-либо факте, событии и т. д. В широком
смысле слова любые сведения, дающие представление о той или иной
стороне материального мира и происходящих в нем процессах, можно
назвать информацией.
Определений понятия информации существует много: от философского (информация есть отражение реального мира) до наиболее узкого
практического (информация есть все сведения, являющиеся объектом
хранения, передачи и преобразования).
Наиболее распространенным определением понятия информации
является следующее:
Информация есть характеристика не сообщения, а соотношения
между сообщением и его потребителем.
Без наличия потребителя говорить об информации так же бессмысленно, как и без наличия сообщения.