Мы измеряем массу в граммах, расстояние в метрах, силу тока в амперах, а информацию в битах. Но измерять количество информации достаточно сложно из-за её абстрактности. По этой причине было придумано несколько подходов, среди которых определение количества информации по Хартли является наиболее простым и понятным.
Определения
О различии информации и данных мы говорили ранее (тут). Подчеркну, что сейчас мы говорим об информации - нам не важно, какими именно способами она будет представлена в памяти компьютера.
Пусть сигнал - это одно событие появления чего-либо. Примеры сигналов:
- Появление буквы "S"
- Длинный гудок
- Загоревшаяся зелёная лампочка у светофора
Сообщение - это последовательность, состоящая из нескольких появляющихся друг за другом сигналов.
Таким образом можем считать фразу "Привет, мир" сообщением, где каждая буква - это один сигнал. Пиксельное изображение тоже может рассматриваться как сообщение, где каждый пиксель - это тоже один сигнал. Количество сигналов в сообщении будем называть длиной сообщения.
Множество всех уникальных сигналов, которые мы можем встречать в сообщениях назовём алфавитом. А количество элементов в алфавите - это мощность алфавита.
Будем обозначать мощность алфавита буквой N.
Длину сообщения обозначим буквой k.
Формула Хартли
Если мы предполагаем, что все сигналы в сообщении равновероятны, то для подсчёта количества информации в сообщении можно воспользоваться формулой, предложенной Ральфом Хартли:
В этой формуле N обозначает мощность рассматриваемого алфавита, а i - количество информации, которое несёт в себе один любой сигнал.
Обычно мы измеряем информацию в битах, поэтому формула традиционно используется с числом "2" (т.к. 1 бит - это либо единица, либо ноль). Но если бы мы использовали что-то экзотичное типа тритов, децитов и пр., то и "2" в формуле пришлось бы изменить.
В литературе часто приводят формулу Хартли через логарифм. По факту это та же самая формула, что и выше:
Запоминайте любую.
А зная, сколько бит несёт в себе один сигнал, достаточно умножить число i на количество сигналов в сообщении, чтобы узнать, сколько всего бит содержит всё сообщение.
Может ли количество информации быть дробным числом
В теории количество информации может быть дробным числом, но в современных компьютерах - нет. В современных компьютерах количество информации всегда округляется до целого числа в большую сторону.
Рассмотрим задачу:
По каналу связи передаются сообщения, содержащие только буквы из алфавита: А, Б, В, Г, Д. Сколько бит информации содержит сообщение: АГГД?
Мощность алфавита N = 5.
По формуле Хартли можно найти количество бит, которое несёт в себе один сигнал:
Получается, что один сигнал содержит 2.32 бита, а всё сообщение "АГГД" будет содержать 2.32 * 4 = 9.28 бит
Но в компьютерах биты могут быть только целыми числами. Поэтому всегда округляем i до целого числа в большую сторону.
Получается, что один сигнал содержит 3 бита, а всё сообщение "АГГД" будет содержать 3 * 4 = 12 бит
В ЕГЭ всегда задания с целыми битами, поэтому i округляем. В самих же заданиях всегда есть приписка: "<Сигнал> кодируется минимальным целым количеством бит".
Интерпретация, почему биты - это целые числа
Современный персональный компьютер спроектирован под работу с двоичными целыми числами. При передаче электрических сигналов высокое напряжение - это "1", а низкое - "0". Если логическое высказывание истинно - это "1", а если ложно - "0". Даже в жёстком диске намагниченная ячейка - это "1", а ненамагниченная - "0". И нигде нет промежуточных значений.
Когда мы составляем таблицу кодирования, мы каждому символу придумываем уникальное двоичное кодовое слово. Если мы хотим, чтобы условие Фано выполнялось всегда, то все кодовые слова должны быть одной длины (о равномерном коде тут).
Так вот длина кодового слова - это и есть количество бит, которое несёт закодированный сигнал.
А формула Хартли как раз и позволяет выяснить, сколько бит должно быть в каждом кодовом слове.
В решённой нами задаче i = 3 бит, поэтому для длина каждого кодового слова потребуется 3 символа. Но 3 битами максимально можно закодировать 8 кодовых слов, а мы используем всего 5. Поэтому весь потенциал системы не задействован.
Память расходуется неэффективно, но зато нам не нужно проверять условие Фано. Такие ситуации, когда расходуется дополнительная память ради облегчения работы, не редкость.
Заключение
Существуют и другие способы подсчёта количества информации. Формула Хартли применяется в тех случаях, когда все сигналы равновероятны.