Основы теории информации

1.

ОСНОВЫ
ТЕОРИИ
ИНФОРМАЦИИ

2.

Основные понятия и термины
Понятие информации.
Формы представления информации.
Термин «информация» происходит от латинского слова «informatio»,
что означает сведения, разъяснения, изложение.
Это понятие во многом остается интуитивным и получает различные
смысловые наполнения в различных отраслях человеческой
деятельности:
• в обиходе информацией называют любые данные или сведения,
которые кого-либо интересуют. Например, сообщение о каких-либо
событиях, о чьей-либо деятельности и т.п. «Информировать» в этом
смысле означает «сообщить нечто, неизвестное раньше»;
• в технике под информацией понимают сообщения, передаваемые в
форме знаков или сигналов;
• в кибернетике под информацией понимает ту часть знаний, которая
используется для ориентирования, активного действия, управления,
т.е. в целях сохранения, совершенствования, развития системы.
2

3.

Понятие информации
в переводе с латинского
языка (informatio)
разъяснение, изложение
в широком смысле
отражение реального мира, выражаемое в виде сигналов и
знаков
в теории смысла слова
отражение реального мира, выражаемое в виде сигналов и
знаков
в теории информации
сведения, которые уменьшают существенную до их
получения неопределенность
в философии
отраженное многообразие, возникающее в результате
взаимодействия объектов
в информатике
результат взаимодействия данных и методов их обработки,
адекватных этим данным и решаемой задаче

4.

Понятие информации
Понятие ИНФОРМАЦИЯ является первичным. Отсюда сложность
в формулировании определения.
Основные признаки:
1) информация приносит сведения, об окружающем мире которых в
рассматриваемой точке не было до ее получения;
2) информация не материальна, но она проявляется в форме
материальных носителей дискретных знаков или первичных
сигналах;
3) знаки и первичные сигналы несут информацию только для
получателя способного их распознать.
4

5.

Понятие информации
Понятие ИНФОРМАЦИЯ является первичным. Отсюда сложность
в формулировании определения.
При этом в узком практическом смысле
под информацией обычно понимают совокупность
сведений об окружающем мире являющихся объектом
хранения, передачи и преобразования.
5

6.

Понятие информации
В современном информационном обществе доля рабочей силы занятой
вопросами обеспечения информацией превышает долю рабочей силы
занятой непосредственно в производстве.
Эффективная организация обмена информацией приобретает все
большее значение как условие успешной практической деятельности людей.
Поэтому науки изучающие структуру и закономерности протекания
информационных процессов, к числу которых относится
теория информации (ТИ) в такой ситуации становиться исключительно
актуальной.

7.

Информационные процессы
Событие
Потребитель
информации
Сбор
Воспроизведение
информации
Преобразование
информации
Передача
Обработка на
ЭВМ
Хранение
Передача
7

8.

Понятие информации
Люди обмениваются информацией в форме сообщений.
Сообщение – это форма представления информации в виде речи,
текстов, жестов, взглядов, изображений, цифровых данных, графиков,
таблиц и т.п.
Информация есть характеристика не сообщения, а соотношения
между сообщением и его потребителем. Без наличия потребителя,
хотя бы потенциального, говорить об информации бессмысленно.
8

9.

Понятие информации
Информация, основанная на однозначной связи знаков
или сигналов с объектами реального мира,
называется семантической или смысловой.
Информация, заключенная в характере (порядке и
взаимосвязи)
следования
знаков
сообщения
называется синтаксической.
9

10.

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

11.

Понятие информации
Понятие «информация» можно трактовать как
совокупность трех основных составляющих:
данные (синтаксическая составляющая) – форма
представления информации
смысл (семантическая составляющая)
польза (прагматическая составляющая)
11

12.

Понятие информации
Очевидно, что наибольший практический интерес
представляют смысловой и прагматический аспекты.
Однако до сих пор не определены объективные
количественные критерии меры ценности и полезности
информации.
Единственная
объективная
составляющая
информации – это данные (форма её представления)!
12

13.

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

14.

Основные понятия и термины теории информации
Информация передается, и храниться в виде сообщений.
Под сообщением понимают совокупность
первичных сигналов содержащих информацию.
знаков
или
Иначе говоря, сообщение - это информация представленная
в какой-либо форме.
Пример сообщений: текст телеграммы, данные на выходе ЭВМ,
речь, музыка и т.д.
14

15.

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

16.

Основные понятия и термины теории информации
Сигнал всегда является функцией времени.
В зависимости от того, какие значения могут принимать аргумент (время t) и
уровни сигналов их делят на 4 типа:
1) Непрерывный или аналоговый сигнал
(случайные сигналы этого типа называются
непрерывными случайными процессами).
Они определены для всех моментов времени и могут
принимать все значения из заданного диапазона.
Чаще всего физические процессы, порождающие
сигналы являются непрерывными. Этим и
объясняется второе название сигналов данного типа
аналоговый - аналогичный порождающим
процессам.
16

17.

Основные понятия и термины теории информации
Сигнал всегда является функцией времени.
В зависимости от того, какие значения могут принимать аргумент (время t) и
уровни сигналов их делят на 4 типа:
2) Дискретизированный или дискретно
непрерывный сигнал
(случайные сигналы этого типа называют
процессами с дискретным временем или
непрерывными случайными
последовательностями).
Они определены лишь в отдельные моменты
времени и могут принимать любые значения уровня.
Временной интервал ∆t между соседними отсчетами
называется шагом дискретизации. Часто такие
сигналы называют дискретными по времени.
17

18.

Основные понятия и термины теории информации
Сигнал всегда является функцией времени.
В зависимости от того, какие значения могут принимать аргумент (время t) и
уровни сигналов их делят на 4 типа:
3) Дискретные по уровню или квантованные
сигналы (случайные сигналы этого типа называют
дискретными случайными процессами).
Они определены для всех моментов времени и
принимают лишь разрешенные значения уровней
отделенные от друг друга на величину шага
квантования ∆x=xk+1+xk
18

19.

Основные понятия и термины теории информации
Сигнал всегда является функцией времени.
В зависимости от того, какие значения могут принимать аргумент (время t) и
уровни сигналов их делят на 4 типа:
4) Дискретные по уровню и по времени сигналы
(случайные сигналы этого типа называют
дискретными случайными последовательностями).
Они определены лишь в отдельные разрешенные
моменты времени и могут принимать лишь разрешенные
значения уровней.
19

20.

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

21.

Основные понятия и термины теории информации
Общая схема системы связи
1) Источник - создаёт (генерирует) сообщения или последовательность
сообщений, которые должны быть переданы.
Сообщения могут быть разных типов: последовательность букв или
цифр как в системах телеграфа и передачи данных.
2) Передатчик - перерабатывает некоторым образом сообщения в
сигналы соответственного типа определенного характеристиками
используемого канала.
21

22.

Основные понятия и термины теории информации
Общая схема системы связи
3) Канал - это комплекс технических средств, обеспечивающий передачу
сигналов от передатчика к приемнику.
В состав канала входит каналообразующая аппаратура, осуществляющая сопряжение
выходного и входного сигналов (передатчика и приемника) с линией связи, и самой линии связи.
Линией связи называется среда, используемая для передачи сигнала от передатчика к
приемнику.
Канал называется дискретным, если на его входе и выходе присутствуют сигналы дискретные
по уровню (сигналы типа 3,4).
Если сигналы на входе и выходе канала непрерывны по времени (типа 1 или 2) то он называется
непрерывным.
В общем случае в процессе передачи в канале сигнал искажается шумом, что соответствует
наличию источника шума.
22

23.

Основные понятия и термины теории информации
Общая схема системы связи
4) Приемник – устройство, которое обычно выполняет операцию обратную
по отношению к операции, производимой передатчиком, т.е.
восстанавливает сообщение по сигналу.
Сложность построения приемника обусловлена изменением формы
принимаемых сигналов, что связано с наличием шума.
5) Получатель - это лицо или аппарат, для которого предназначено
сообщение.
23

24.

Основные понятия и термины теории информации
Процесс преобразования сообщения в сигнал, осуществляющийся в
передатчике и обратный ему процесс, реализующийся в приемнике назовем
соответственно кодированием и декодированием.
Основное содержание теории информации (ТИ) - исследование
методов кодирования для экономического представления сообщений
различных источников и для надежной передачи сообщений по каналам
связи с шумом.
24

25.

Основные понятия и термины теории информации
В основе ТИ лежит статистическое описание источников сообщений и
каналов связи, а так же измерение количества информации в сообщениях,
базирующееся на этом описании.
Основные вопросы, решаемые ТИ:
- определение предельных возможностей (т.е. о максимально
достижимых характеристиках) различных систем связи,
- оценка проектируемой системы с точки зрения соответствия
теоретически возможным показателям.
В некоторых случаях логика рассуждений, используемая в ТИ, подсказывает
путь, на котором может быть найдено конструктивное решение для
реальной системы.
25

26.

Основные понятия и термины
Информация относится к предельно широким понятиям
(как пространство, время, материя и т.п.)
информация
данные
сведения
и т.п.
Для решения инженерных задач
требуется количественная
характеристика.
В теории и технике связи используется
определение количества информации,
предложенное Клодом Шéнноном
(Claude Elwood Shannon, 1916 2001)
26

27.

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

28.

Определение количества информации
источник
сообщений
a ( a1,..., an )
n длина, ak A
1,..., K алфавит источника (K – объем
алфавита)
P(a) распределение вероятностей, заданное
на множестве всех последовательностей
произвольной длины
может быть каким угодно, но способ вычисления
вероятностей д.б. достаточно простым и удобным
28

29.

Источник без памяти – простейший случай дискретного
источника:
символы в последовательности являются
независимыми, и распределение полностью
определяется набором априорных вероятностей
отдельных символов
n
P(a) P( a1,..., an ) P( a1) P( a2 )...P(an ) P( ak )
k 1
условная вероятность появления конкретного
символа в любой позиции последовательности
равна безусловной (априорной) вероятности этого
символа
29

30.

В моделях источников с памятью условная
вероятность символа зависит от того, какие символы
ему предшествуют.
В телеграмме на русском языке после буквы «щ» можно
ожидать букв «а», «у», «е», но не «ю», «я», «й» и т.п.
Щ
А
Б
В
…
Й
…
Э
Ю
Я
30

31.

Если условная вероятность очередного символа зависит от одного
предшествующего символа марковский источник 1 порядка.
Марковские источники могут иметь порядок 2, 3 и т.д.
Обычно чем выше порядок учитываемых связей, тем сильнее
условные вероятности символов отличаются от безусловных
(априорных). Чем больше учитывается предшествующих символов,
тем вернее предсказание очередного:
…(.)
в скобках может быть всё что угодно
…и(.)
…ни(.)
…чни(.) в скобках могут быть буквы в, к, л, м, ц, с, т
…очни(.)
…точни(.)
…сточни(.)
…источни(.) в скобках может быть только буква к
Далее рассматриваются источники без памяти
31

32.

Кодирование
Информационная последовательность символов,
представляющая собой сообщение, может быть
заменена другой, кодовой последовательностью,
состоящей из символов кодового алфавита.
Целью кодирования может быть:
1.более полное использование канала связи
(эффективное кодирование) или
2.Повышение верности передачи (помехоустойчивое
кодирование).
3.согласование сообщения с каналом (напр.,
32
кодирование в аппарате Бодо).

33.

Кодирование
Естественно, кодовые последовательности
характеризуются другими распределениями
вероятностей, нежели информационные
последовательности.
a, b, c, d ,..., z
,...,
кодер
33

34.

Дискретный канал связи
X x1,..., xL
Y y1,..., yM
канал связи
Полное описание P(y | x) для всех возможных x и y
описывает вероятностный механизм действия помех в канале.
В случае канала без памяти полностью определяется набором
условных вероятностей для всех пар отдельных символов
P ( y j | xi ), xi X, y j Y
Если количество символов не изменяется в канале, то
n
n
P( y1 y2 ... yn | x1x2 ...xn ) P( y j | xi )
j 1 i 1
для канала с памятью всё сложнее
34

35.

Согласно теории информации Шеннона*
Информация – это свойство сообщения снимать (или
уменьшать) неопределенность относительно исхода
некоторого случайного опыта (например, относительно
переданного символа).
Количество получаемой информации, очевидно,
должно быть связано со степенью снятия
неопределенности. Так, получая сообщение о событии,
которое достоверно известно, информации мы не
получаем (неопределенности нет, и снимать нечего).
*известна ещё алгоритмическая теория информации А.Н. Колмогорова,
35
не получившая (пока?) широкого применения

36.

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

37.

Требования к количественной мере
информации
Если определить «неожиданность» сообщения 1/ P(a) ,
то выполняется только второе требование
А если ввести логарифмическую меру, то все три:
1
log m
log m P(a)
P(a)
m 2 [бит]
m e [нат]
m 10 [хартли]
Ральф Хартли
(Ralph Hartley
1888-1970)
37

38.

Количество информации дискретного источника
Поскольку событие, состоящее в выдаче
сообщения, случайно и происходит с некоторой
вероятностью, то и количество информации,
связанное с этим сообщением, также является
случайной величиной.
Введем собственное количество информации,
доставляемой символом (собственную
информацию символа)
I ( i ) log p ( i )
38

39.

Количество информации, вырабатываемой
дискретным источником
Информационная производительность дискретного
источника – среднее количество информации на символ
– математическое ожидание этой случайной величины.
Для источника без памяти среднее количество
информации, приходящееся на один символ
K
H ( ) p ( k ) log p( k )
k 1
Энтропия мера информационной производительности
(на символ) источника сообщений
39

40.

Основные свойства энтропии
K
H ( ) p ( k ) log p( k )
k 1
1. Энтропия любого источника неотрицательна H ( A) 0.
Это следует из того, что вероятность любого события
неотрицательна и не превосходит единицы
2. Энтропия равна нулю, если один из символов имеет
вероятность 1, а остальные – вероятности 0.
log1/ p
log q
1/ q log e
lim
lim
0
1
p 0 1/ p
q q
q
lim ( p log p) lim
p 0
40

41.

3. При заданном объеме алфавита энтропия максимальна,
если все символы равновероятны
H ( ) max
K
при
pk 1
k 1
Составим целевую функцию (по методу неопр. мн. Лагранжа)
K
( p1,..., pK ) pk log pk pk 1
k 1
k 1
K
Условие экстремума
K
K
p 1 0, i 1, K
pk log pk
k
pi
k 1
k 1
Жозе́ф Луи́ Лагра́нж
(Joseph Louis
Lagrange, 1736-1813)
41

42.

Условие экстремума
K
K
pk 1 0, i 1, K
pk log pk
pi
k 1
k 1
pi
1
1 ln pi 0
ln 2
ln pi
1 1
0
ln 2 pi
ln 2
Решая относительно pi
получаем
pi exp( ln 2 1)
вероятность не зависит от i, т.о., энтропия
максимальна при равных вероятностях символов
42