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

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

Компьютер, как вычислительная машина (прибор), обрабатывает и хранит информацию, преобразованную (перекодированную) в двоичный код - последовательность "0" и "1".

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

Одним битом могут быть выражены (закодированы) два понятия:

Событие

Код

1

0

2

1
- да или нет;
- черное или белое;
- истина или ложь и т.п.

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

Событие

Код

1

00

2

01

3

10

4

11

Тремя битами можно закодировать восемь различных событий:

Событие

Код

1

000

2

001

3

010

4

011

5

100

6

101

7

110

8

111

Увеличивая на единицу количество разрядов в двоичном коде, в два раза увеличивается количество кодируемых событий.
Что описывает формула:
N=2i,
где N - количество независимых кодируемых событий;
i - разрядность двоичного кода.

Степени двойки отражают, количество событий N, закодированное с помощью i[БИТ]:

i, бит

1

2

3

4

5

6

7

8

9

10

16

24

N, событий

2

4

8

16

32

64

128

256

512

1024

65 536

16 777 216

Задача 1

Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из двух состояний («включено», «выключено»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
Дано:
N = 18
i = ? 		Решение:
1. По формуле количество событий (N) зависит от количества информации (i)
N=2i,
значение N задано в условиях, из таблицы степеней двойки выбираем ближайшее большее значение:
для N=18 это будет 32
из чего следует, что i= 5.
Ответ: 5 лампочек.

Задача 2

Световое табло состоит из лампочек. Каждая лампочка может находиться в одном из трех состояний («включено», «выключено», «мигает»). Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 18 различных сигналов?
Дано:
N = 18
i = ? 		Решение:
1. Задача отличается от предыдущей количеством состояний каждой лампочки. Это означает, что события кодируют не двоичным, а троичным кодом.
В этом случае формула зависимости количества событий (N) от количества информации (i) немного преобразуется
N=3i,
значение N задано в условиях, из таблицы степеней тройки выбираем ближайшее большее значение:

i, бит

1

2

3

N, событий

3

9

27

для N=18 это будет 27
из чего следует, что i= 3.
Ответ: 3 лампочки.

Задача 3

В велокроссе участвуют 119 спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объем сообщения, записанного устройством, после того как промежуточный финиш прошли 70 велосипедистов?
Дано:
N = 119
K = 70
V = ? 		Решение:
1. По формуле количество событий (N) зависит от количества информации (i)
N=2i,
значение N задано в условиях, из таблицы степеней двойки выбираем ближайшее большее значение:
для N=119 это будет 128
из чего следует, что i= 7.
Значит каждый комер требует минимум 7 бит.
2. Для 70 номеров потребуется:
V = 7 x 70 = 490 [бит]
Ответ: 490 бит.

Задача 4

В некоторой стране автомобильный номер длиной 7 символов составляется из заглавных букв (всего используется 26 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 20 автомобильных номеров.
Дано:
Kсимв = 7
Pалф = 26+10
K = 20
V = ? 		Решение:
1. Определим количество символов, участвующих в кодировании (мощность алфавита):
Pалф = 26 + 10 = 36 [символов]
2. Для двоичного кодирования 36 символов (событий) потребуется 6 бит на символ (5 битами можно закодировать только 32 символа)
3. Определим количество информации, занимаемое каждым номером
6 x 7 = 42 [Бит]. 4. По условию каждый номер кодируется целым числом байт
42 : 8 = 5.25
Т.е. требуется 6 [Байт] на номер
5. Значит сможем определить количество информации необходимое для хранения 20 номеров:
6 x 20 = 120[Байт]
Ответ: 120[Байт]

Задача 5

Метеорологическая станция ведет наблюдение за влажностью воздуха. Результатом одного измерения является целое число от 0 до 100 процентов, которое записывается при помощи минимально возможного количества бит. Станция сделала 80 измерений. Определите информационный объем результатов наблюдений.
Дано:
Pалф = 101
K = 80
V = ? 		Решение:
1. Количество событий (мощность алфавита) определим как количество запоминаемых величин от 0 до 100 :
Pалф = 101
2. Для двоичного кодирования 101 величины (события) потребуется 7 бит на каждую величину
3. Значит сможем определить количество информации необходимое для хранения 80 измерений:
7 x 80 = 560[Байт]
Ответ: 560[Байт]

Домашнее задание

1 Шахматная доска состоит 8 столбцов и 8 строк. Какое минимальное количество бит потребуется для кодирования координат одного шахматного поля.

2 Какое минимальное количество бит потребуется для кодирования положительных чисел, меньших 60?

3 Для кодирования секретного сообщения используются 12 специальных значков-символов. При этом символы кодируются одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения длиной в 256 символов?

4 Для кодирования нотной записи используется 7 значков-нот. Каждая нота кодируется одним и тем же минимально возможным количеством бит. Чему равен информационный объем сообщения, состоящего из 180 нот?

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

6 В некоторой стране автомобильный номер длиной 6 символов составляется из заглавных букв (всего используется 12 букв) и десятичных цифр в любом порядке. Каждый символ кодируется одинаковым и минимально возможным количеством бит, а каждый номер – одинаковым и минимально возможным количеством байт. Определите объем памяти, необходимый для хранения 32 автомобильных номеров.

7 Сколько существует различных последовательностей из символов «плюс» и «минус», длиной ровно в пять символов?

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

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

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

11 Для передачи сигналов на флоте используются специальные сигнальные флаги, вывешиваемые в одну линию (последовательность важна). Какое количество различных сигналов может передать корабль при помощи пяти сигнальных флагов, если на корабле имеются флаги четырех различных видов (флагов каждого вида неограниченное количество)?

12 Некоторое сигнальное устройство за одну секунду передает один из трех сигналов. Сколько различных сообщений длиной в четыре секунды можно передать при помощи этого устройства.

13 Вася и Петя передают друг другу сообщения, используя синий, красный и зеленый фонарики. Это они делают, включая по одному фонарику на одинаковое короткое время в некоторой последовательности. Количество вспышек в одном сообщении – 3 или 4, между сообщениями – паузы. Сколько различных сообщений могут передавать мальчики?

14 Для кодирования 300 различных сообщений используются 5 последовательных цветовых вспышек. Вспышки одинаковой длительности, для каждой вспышки используется одна лампочка определенного цвета. Лампочки скольких цветов должны использоваться при передаче (укажите минимально возможное количество)?

15 Учитель, выставляя в журнал четвертные оценки по биологии за третью четверть (3, 4, 5), обратил внимание, что комбинация из трех четвертных оценок по этому предмету у всех учеников различна. Какое может быть максимальное количество учеников в этом классе?

16 Некоторый алфавит содержит четыре различных символа. Сколько слов длиной ровно в 4 символа можно составить из слов данного алфавита (символы в слове могут повторяться)?

17 Квадратное световое табло 2х2 состоит из светящихся элементов, каждый из которых может гореть одним из четырех различных цветов. Сколько различных сигналов можно передать с помощью табло, состоящего из четырех таких элементов (при условии, что все элементы должны гореть)?

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