Урок № 5
Измерение информации
Алфавитный подход к измерению информации
Вопрос об измерении количества информации является очень важным. Мы храним, передаем, принимаем, обрабатываем информацию. Поэтому важно знать о способе ее измерения, позволяющем, ответить на вопросы: хватит ли места на носителе, чтобы разместить информацию, или сколько времени нужно, чтобы передать ее по каналу связи. Величина, которая нас в этих ситуациях интересует, называется объемом информации . В таком случае говорят об алфавитном подходе к измерению информации.
Алфавитный подход к измерению информации применяется в цифровых системах хранения и передачи информации. В них используется двоичное кодирование информации . При алфавитном подходе для определения количества имеет значение лишь размер (объем) кода. Если с помощью i-разрядного двоичного кода можно закодировать алфавит, состоящий из N символов, то эти величины связаны между собой по формуле:
2 i = N
N – мощность алфавита,
i – количество информации в каждом символе алфавита в битах.
Например, если i = 2 , то можно построить 4 двухразрядные комбинации из нулей и единиц, т. е. закодировать 4 символа. При i = 3 существует 8 трехразрядных комбинаций нулей и единиц (кодируется 8 символов):
i=2
00
i=3
01
000
10
001
11
010
011
100
101
110
111
Сколько двухразрядных комбинаций можно построить, если:
i = 4
i = 5
i = 8
16
32
256
Английский алфавит содержит 26 букв. Но для записи текста нужны еще как минимум шесть символов: пробел, точка, запятая, вопросительный знак, восклицательный знак, тире. В сумме получается расширенный алфавит мощностью в 32 символа .
Поскольку 32 = 2 5 , все символы можно закодировать двоичными кодами от 00000 до 11111. Именно такой код использовался в телеграфных аппаратах, появившихся в XIX веке. Телеграфный аппарат при вводе переводил английский текст в двоичный код, длина которого в 5 раз больше, чем длина исходного текста.
Жан Морис Эмиль Бодо и его телеграфный аппарат с пятиразрядным кодом
В двоичном коде каждая двоичная цифра несет одну единицу информации, которая называется 1 бит.
Бит – основная единица измерения информации.
Информационный вес символа алфавита – это длина двоичного кода, с помощью которого он кодируется. В рассмотренном выше примере информационный вес символа расширенного английского алфавита был равен 5 битам.
Алфавит русского языка включает 33 буквы. Если к нему добавить еще пробел и пять знаков препинания, то получится 39 символов. Для кодирования такого алфавита пятиразрядного кода уже недостаточно. Нужен как минимум шестиразрядный код. Поскольку 2 6 = 64, остается еще резерв для 25 символов (64 - 39 = 25). Его можно использовать для кодирования цифр, всевозможных скобок, математических знаков и других символов, встречающихся в русском тексте. Следовательно, информационный вес символа в расширенном русском алфавите будет равен 6 битам.
Если i — информационный вес одного символа алфавита, а К — количество символов в тексте, записанном с помощью этого алфавита, то информационный объем всего текста (I) выражается формулой:
I - информационный объем всего текста
K – количество символов в тексте
i – вес одного символа
I = К x i
Для определения информационного веса символа полезно знать ряд целых степеней двойки. Вот как он выглядит в диапазоне от 2 1 до 2 11 :
Поскольку мощность N алфавита может не являться целой степенью двойки, информационный вес символа определяется следующим способом. Находится ближайшее к N значение во второй строке таблицы, не меньшее чем N.
Соответствующее значение i в первой строке будет равно информационному весу символа .
Пример. Определим информационный вес одного символа алфавита, включающего в себя все строчные и прописные русские буквы (66); цифры (10); знаки препинания, скобки, кавычки (10). Всего будет 86 символов.
Поскольку 2 6 7 , информационный вес символов данного алфавита равен 7 битам. Это означает, что все 86 символов можно закодировать семиразрядными двоичными кодами.
1001011 1111110 1010101
Для двоичного представления текстов в компьютере применяется восьмиразрядный код. С помощью него можно закодировать алфавит из 256 символов, поскольку 256 = 2 8 . В стандартную кодовую таблицу (например, используемую в ОС Windows таблицу ANSI) помещаются все необходимые символы: английские и русские буквы — прописные и строчные, цифры, знаки препинания, знаки арифметических операций, всевозможные скобки и пр.
Информационный объем текста в памяти компьютера измеряется в байтах. Он равен количеству символов в тексте. В одном байте 8 бит.
Например, одна страница текста на листе формата А4 с размером шрифта 12 с одинарным интервалом между строками в компьютерном представлении будет иметь объем приблизительно 4000 байтов, так как на ней помещается примерно 4000 знаков.
Помимо бита и байта, для измерения информации используются и более крупные единицы:
Задание 1. Сообщение, записанное буквами из 64-символьного алфавита, содержит 100 символов. Какой объем информации оно несет?
2 i = N
N = 64, значит, 2 i = 64 i=6
I = К x i , значит I = 100 x 6 = 600 бит
Задание 2. Сколько символов содержит сообщение, записанное с помощью 16-символьного алфавита, если его объем составляет 1/16 Кб?
2 i = N
N = 16, значит, 2 i = 16 i=4
1 Кб = 1024 байта, значит 1024/16 = 64 байта = 512 бит
I = К x i, значит 512 = К x 4 К = 512/4 = 128 символов
Содержательный подход
Ситуация 1. В ваш класс назначен новый учитель информатики; на вопрос «Это мужчина или женщина?» вам ответили: «Мужчина».
Ситуация 2. На чемпионате страны по футболу играли «Динамо» и «Зенит». Из спортивных новостей вы узнаете, что игра закончилась победой «Зенита».
Ситуация 3. На выборах было представлено четыре кандидата. После подведения итогов голосования вы узнали, что избран Н. Н. Петров.
Вопрос: в какой из трех ситуаций полученное сообщение несет больше информации?
Неопределенность знания — это количество возможных вариантов ответа на интересовавший вас вопрос.
В первой ситуации 2 варианта ответа: мужчина или женщина; во второй ситуации 3 варианта: выиграл «Зенит», ничья, выиграло «Динамо»; в третьей ситуации — 4 варианта: 4 кандидата на пост мэра.
Сообщение, уменьшающее неопределенность знания об исходе некоторого события в два раза, несет 1 бит информации.
Рассмотрим еще один пример.
Ученик написал контрольную и спрашивает учителя о полученной оценке. Оценка может быть от 2 до 5. Учитель отвечает: «Угадай оценку за два вопроса, ответом на которые может быть "да" или "нет"». Ученик задал первый вопрос: «Оценка выше тройки?». «Да», — ответил учитель. Второй вопрос: «Это пятерка?». «Нет», — ответил учитель. Ученик понял, что он получил четверку.
Первоначально неопределенность знания была равна четырем (2,3,4,5). С ответом на каждый вопрос неопределенность уменьшалась в 2 раза и, согласно данному выше определению, передавался 1 бит информации.
Рассмотрим еще один частный пример, а затем выведем общее правило.
Вы едете на поезде, в котором 8 вагонов, а на вокзале вас встречает товарищ. Товарищ позвонил вам по мобильному телефону и спросил, в каком вагоне вы едете. Вы предлагаете угадать номер вагона, задав наименьшее количество вопросов, ответами на которые могут быть только слова «да» или «нет».
Немного подумав, товарищ стал спрашивать:
— Номер вагона больше четырех? — Да. — Номер вагона больше шести? — Нет. — Это шестой вагон? — Нет. — Ну теперь все ясно! Ты едешь в пятом вагоне!
Схематически поиск номера вагона выглядит так:
Каждый ответ уменьшал неопределенность знания ровно в два раза. Всего было задано три вопроса. То есть сообщение о том, что вы едете в пятом вагоне, несет 3 бита информации.
Формула Хартли
Если значение N равно целой степени двойки (4, 8, 16, 32, 64 и т. д.), то уравнение решить легко, поскольку i будет целым числом. А чему равно количество информации в сообщении о результате матча «Динамо»-«Зенит»? В этой ситуации N = 3. Можно догадаться, что в этом случае решение уравнения:
2 i = 3
будет дробным числом, лежащим между 1 и 2, поскольку 2 1 = 2 3.
А как точнее узнать это число?
Формула для измерения количества информации: i = log 2 N была предложена американским ученым Ральфом Хартли — одним из основоположников теории информации.
i = log 2 N
i — количество информации, содержащееся в сообщении об одном из N равновероятных исходов события.
Значения логарифмов находятся с помощью специальных логарифмических таблиц. Также можно использовать инженерный калькулятор или табличный процессор Excel.
В Microsoft Excel функция логарифма имеет следующий вид: LOG(apryмент N; основание). Аргумент — значение N находится в ячейке А2, а основание логарифма равно 2. В результате получаем с точностью до девяти знаков после запятой: i = log 2 3 = 1,584962501 (бита).
Вопросы и задания на дом 1. Что такое неопределенность знания об исходе некоторого события? 2. Придумайте несколько ситуаций, при которых сообщение несет 1 бит информации. 3. В каких случаях и по какой формуле можно вычислить количество информации, содержащейся в сообщении, используя содержательный подход? 4. Сколько бит информации несет сообщение о том, что из колоды в 32 карты достали «даму пик»? 5. Проводятся две лотереи: «4 из 32» и «5 из 64». Сообщение о результатах какой из лотерей несет больше информации? 6. Используя формулу Хартли, определите количество информации в сообщениях о равновероятных событиях: а) в следующем году ремонт в школе начнется в феврале; б) из 30 учеников дежурить в столовой назначили Дениса Скворцова.
7. Учебник, параграф 3-4.
8. Подготовиться к практической работе № 1
«Измерение информации»