1 of 28

Информация и информационные процессы

§ 1. Количество информации

§ 2. Передача данных

1

2 of 28

Информация и информационные процессы

§ 1. Количество информации

2

3 of 28

Формула Хартли (1928)

3

I – количество информации в битах

N – количество вариантов

Ральф Хартли

Пример:� В аэропорту стоит 10 самолетов, из них один � летит в Санкт-Петербург. Оценить количество� информации в сообщении «В Санкт-Петербург летит

второй самолет»?

бита

Информация и информационные процессы, 11 класс

4 of 28

Алфавитный подход

4

M – мощность алфавита

Информационный объём

символа:

сообщения длиной L:

Пример: сообщение длиной 100 символов закодировано с помощью алфавита из 50 знаков.

бита

вверх до целого числа

6 битов

600 битов

Информация и информационные процессы, 11 класс

5 of 28

Количество различных сообщений

5

M – мощность алфавита

L – длина сообщения

N – количество различных сообщений

алфавит: А, Б, В, Г

А, Б, В, Г

А, Б, В, Г для каждого варианта

А, Б, В, Г

всего: 4

всего: 4⋅4 = 4² = 16

Информация и информационные процессы, 11 класс

6 of 28

Информация и вероятность

6

	0,175
О	0,090
Е	0,072
А	0,063
И	0,062
Т	0,053
Н	0,052
С	0,045
р	0,040
В	0,038
Л	0,035
К	0,028
М	0,026
Д	0,025
П	0,023
У	0,021

Я	0,018
Ы	0,017
З	0,016
Ь	0,015
Б	0,014
Г	0,013
Ч	0,012
Й	0,010
Х	0,009
Ж	0,007
Ю	0,006
Ш	0,005
Ц	0,004
Щ	0,003
Э	0,002
Ф	0,001

Доля символов в русских текстах:

из 1000 символов около 175 пробелов

вероятность p появления символа

Информация и информационные процессы, 11 класс

7 of 28

Вероятность

7

Вероятность события – число от 0 до 1, показывающее, как часто случается это событие в большой серии одинаковых опытов.

событие никогда не происходит �(нет неопределенности)

событие происходит в половине �случаев (есть неопределенность)

событие происходит всегда �(нет неопределенности)

x² ≥ 0

x² < 0

Информация и информационные процессы, 11 класс

8 of 28

Вероятность

8

N – количество испытаний

m – сколько раз произошло событие

ровно 2:

чётное:

меньше 3:

2 и 2:

2 чётных:

оба меньше 3:

Информация и информационные процессы, 11 класс

9 of 28

Вероятность и информация

9

…АААААААААААААААААА

получили букву «А»:

…BАААААААААААААААААА

получили букву «В»:

Чем более неожиданно событие, тем больше получено информации.

В 10 опытах будет получено в 10 раз больше информации, чем в одном (аддитивность).

Определили свойства количества�информации!

!

Информация и информационные процессы, 11 класс

10 of 28

Вероятность и информация

10

при K = 1 ⇒ информация в битах

Если событие имеет вероятность p, то количество информации в битах, полученное в сообщении об этом событии, равно

Информация и информационные процессы, 11 класс

11 of 28

Вероятность и информация

11

Аддитивность:

по 8 шариков разного цвета

всего 8⋅8 = 64 варианта

бита

битов

Аддитивность выполняется!

!

Информация и информационные процессы, 11 класс

12 of 28

Связь с формулой Хартли

12

N равновероятных событий

совпадает с �формулой Хартли

Если вероятности разные:

«Васе достался зелёный шарик».

Информация и информационные процессы, 11 класс

13 of 28

Формула Шеннона

13

Количество полученной информации равно уменьшению неопределенности.

I = ΔH = H_нач – H_кон

Как вычислить H?

?

Неопределённость знаний об источнике данных (N событий, вероятности p_i):

Клод Шеннон

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

Информация и информационные процессы, 11 класс

14 of 28

Формула Шеннона

14

«Идёт ли сейчас снег?» (1 – да, 2 – нет)

зимой:

Как вычислить p₂?

?

Сумма вероятностей всех событий, составляющих полную систему, равна 1!

!

бит

летом:

бит

Информация и информационные процессы, 11 класс

15 of 28

Когда неопределённость наибольшая?

15

Система двух событий:

Неопределенность максимальна, когда все события равновероятны.

0

1

0,5

1

0,5

H

p₁

совпадает с формулой Хартли!

Информация и информационные процессы, 11 класс

16 of 28

Информация и информационные процессы

§ 2. Передача данных

16

17 of 28

Скорость передачи данных

17

Скорость передачи данных – это количество битов (байтов, Кбайт и т.д.), которое передается по каналу связи за единицу времени (например, за 1 с).

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

От чего зависит?

?

аппаратура, мощность помех

Информация и информационные процессы, 11 класс

18 of 28

Единицы измерения

18

1 бит/с = 1 bps (bits per second)

1 кбит/с = 1000 бит/с

1 Мбит/с = 10⁶ бит/с

1 Гбит/с = 10⁹ бит/с

Информация и информационные процессы, 11 класс

19 of 28

Объём переданных данных

19

средняя скорость передачи

время

v = 512000 бит/с, t = 1 мин

I = v ⋅ t = 512000 бит/с · 60 с

= 30 720 000 битов

= 3 840 000 байтов

= 3750 Кбайт.

: 8

: 1024

Информация и информационные процессы, 11 класс

20 of 28

Обнаружение ошибок

20

Бит чётности:

00 01 10 11

⇒ 000 011 101 110

теперь число единиц в каждом блоке чётное

Если в принятом блоке нечётное число «1» – ошибка!

принято: 010 110 000 111 000

Можно ли исправить?

?

Для файлов – контрольные суммы (хэш):

CRC = Cyclic Redundancy Code

MD5, SHA-1

Верно ли переданы данные?

?

10010

Информация и информационные процессы, 11 класс

21 of 28

Помехоустойчивые коды

21

111 000 000 111 000 – утроение каждого бита

принято: 010111000101000

исправлено: 000111000111000

10010

Обнаруживает 1 или 2 ошибки, исправляет 1 ошибку!

!

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

Информация и информационные процессы, 11 класс

22 of 28

Расстояние Хэмминга

22

Расстояние Хэмминга – это количество позиций, в которых отличаются два закодированных сообщения одинаковой длины.

d(001, 100) = 2

d(000, 111) = ?

3

Обнаруживает 1 или 2 ошибки, исправляет �1 ошибку!

!

Исправление r ошибок:

d ≥ 2r + 1

Информация и информационные процессы, 11 класс

23 of 28

Передача 3-битных блоков

23

000000 001111	010011 011100	100101 101010	110110 111001

d_min= 3 ⇒ r = 1

d(000000, x) = ?

001111→4	010011→3 011100→3	100101→3 101010→3	110110→4 111001→4

Исправление ошибки

принято: 101110

Недопустимый код!

!

ближайший допустимый код:

101010

Информация и информационные процессы, 11 класс

24 of 28

Помехоустойчивые коды Хэмминга

24

1	2	3	4	5	6	7
0	1	1	1	1	0	0

4 полезных бита, 3 контрольных

избыточность 3/4 =75%

3 = 1 + 2

5 = 1 + 4

6 = 2 + 4

7 = 1 + 2 + 4

бит 1: (1 + 1 + 0) mod 2 = 0

бит 2: (1 + 0 + 0) mod 2 = 1

бит 4: (1 + 0 + 0) mod 2 = 1

d_min= 3 ⇒ r = 1

Информация и информационные процессы, 11 класс

25 of 28

Код Хэмминга: исправление ошибки

25

1	2	3	4	5	6	7
0	1	1	1	1	1	0

бит 1: (1 + 1 + 0) mod 2 = 0

бит 2: (1 + 1 + 0) mod 2 = 0

бит 4: (1 + 1 + 0) mod 2 = 0

Контрольные биты:

Номер ошибочного бита: 2 + 4 = 6

0	1	1	1	1	0	0

1	1	0	0

Информация и информационные процессы, 11 класс

26 of 28

Длинные коды Хэмминга

26

Контрольные биты:

1, 2, 4, 8, 16, … , 2^k

Исправляется только 1 ошибка в блоке!

!

Длина кодовых слов, бит	Число контрольных битов	Избыточность
4	3	75%
11	4	36%
26	5	19%
57	6	10%
247	8	3%
1013	10	1%

Информация и информационные процессы, 11 класс

27 of 28

Конец фильма

27

ПОЛЯКОВ Константин Юрьевич

д.т.н., учитель информатики

ГБОУ СОШ № 163, г. Санкт-Петербург

kpolyakov@mail.ru

ЕРЕМИН Евгений Александрович

к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

eremin@pspu.ac.ru

Информация и информационные процессы, 11 класс

28 of 28

Источники иллюстраций

28

www.newbeanbag.ru
compression.ru
maps.yandex.ru
ixbt.com
www.dinamika-avia.ru
www.transas.ru
crazypiter.ru
www.fotosearch.com
www.notebookcheck.net
www.energy2.ru
www.wlangdesign.com
www.1himplast.ru
www.applecad.com
gprs-modem.ru
en.wikipedia.org
nivo.co.za
иллюстрации художников издательства «Бином»
авторские материалы

Информация и информационные процессы, 11 класс