Формула Хартли: как посчитать количество информации

Формула Хартли - первая строгая мера количества информации: она отвечает на вопрос, сколько бит несёт сообщение о том, какой из N равновероятных исходов произошёл на самом деле. Её предложил инженер Ральф Хартли ещё в 1928 году, и с неё же обычно начинают тему измерения информации в школьном и вузовском курсе информатики. Ниже разберём саму формулу, условие равновероятности, без которого она не работает, и то, как перейти от абстрактного log2(N) к реальному числу бит, которое нужно под кодировку. Чтобы сразу увидеть, как число исходов превращается в биты, покрути калькулятор ниже - он строит ту же кривую логарифма, которую вы будете чертить в задачах, и одновременно считает объём целого сообщения.

Что означает формула Хартли

Пусть событие - это один из N возможных равновероятных исходов: цвет вынутого шара, буква в сообщении, ответ на вопрос с несколькими равновозможными вариантами. Формула Хартли даёт количество информации, которое несёт сообщение о том, какой именно исход реализовался:

$I = \log_2 N,$

где N - число равновероятных исходов, а I - количество информации в битах. Смысл формулы прозрачен: I показывает, сколько раз нужно разделить множество из N исходов пополам, чтобы остаться с единственным вариантом, то есть сколько двоичных вопросов «да/нет» нужно задать, чтобы гарантированно угадать исход. Формулу легко развернуть в обратную сторону: если известно, что сообщение несёт I бит и представляет собой один из равновероятных вариантов, то число этих вариантов равно $N = 2^I$.

Условие равновероятности и связь с формулой Шеннона

Ключевое ограничение формулы Хартли - все N исходов должны быть равновероятны, то есть вероятность каждого равна $p = 1/N$. Если это не так (шестёрка на кубике выпадает не так часто, как определённая буква в тексте), нужна более общая формула Шеннона:

$I = -\sum_{i=1}^{N} p_i \log_2 p_i.$

Легко проверить, что при равных вероятностях $p_i = 1/N$ формула Шеннона превращается ровно в формулу Хартли - это её частный случай для однородного распределения. Подробный разбор общего случая - в статье про формулу Шеннона и количество информации.

Наглядно формула Хартли соответствует игре в угадывание числа бинарным поиском: если число загадано из диапазона в N вариантов, и на каждом шаге диапазон делится пополам, то количество обязательных вопросов равно $\log_2 N$, округлённому вверх до целого.

Рассчитать для своей задачи

Почему log2(N) нужно округлять вверх

Формула Хартли в чистом виде часто даёт дробное число: например, $\log_2 100 \approx 6{,}644$. Но реальная кодировка не умеет использовать «0,644 бита» - под каждый символ отводится целое число двоичных разрядов. Поэтому на практике вычисляют не сам логарифм, а ближайшее целое число бит, способное различить N вариантов:

$i = \lceil \log_2 N \rceil,$

то есть логарифм округляется вверх (в сторону большего целого), а не по обычным правилам округления. Округление вниз здесь недопустимо: если $\log_2 100 \approx 6{,}644$ округлить до 6 бит, то 6 бит различают только $2^6 = 64$ варианта - этого не хватит для 100 исходов, часть из них останется неразличимой. Округление вверх до 7 бит даёт запас: $2^7 = 128 \ge 100$, и все варианты кодируются однозначно.

Рассчитать для своей задачи

На графике видно, что ступенчатая линия всегда лежит на уровне ближайшей полки сверху от плавной кривой логарифма. Ступеньки происходят ровно в степенях двойки: при $N = 2, 4, 8, 16, 32, 64, 128, 256$ значение $\log_2 N$ уже целое и округление ничего не меняет, а между соседними степенями двойки разрыв между кривой и ступенькой максимален у правого края интервала.

Информационный объём сообщения через мощность алфавита

Формулу Хартли часто применяют не к одному символу, а к целому сообщению. Если алфавит содержит N равновероятных символов, то на кодирование одного символа нужно $i = \lceil \log_2 N \rceil$ бит. Тогда сообщение из n символов этого алфавита имеет информационный объём

$V = n \cdot i,$

измеренный в битах; переводя в байты, делим результат на 8. Это стандартная связка «мощность алфавита → биты на символ → объём всего текста», на которой строится большинство задач про измерение информации в информатике.

Пример решения типовой задачи

Разберём классическую формулировку. Сообщение занимает 3 страницы, на каждой странице 25 строк, в каждой строке 30 символов. Алфавит, которым набрано сообщение, содержит 256 равновероятных символов. Нужно найти информационный объём сообщения в байтах.

Сначала находим число бит на один символ по формуле Хартли:

$i = \log_2 256 = 8 \ \text{бит},$

и округлять здесь не нужно - 256 является точной степенью двойки ($2^8 = 256$), поэтому логарифм уже целый. Далее считаем общее число символов в сообщении:

$n = 3 \cdot 25 \cdot 30 = 2250 \ \text{символов}.$

Информационный объём сообщения в битах:

$V = n \cdot i = 2250 \cdot 8 = 18\,000 \ \text{бит}.$

Переводим в байты, разделив на 8:

$V_{\text{байт}} = \frac{18\,000}{8} = 2250 \ \text{байт} \approx 2{,}2 \ \text{Кбайт}.$

Такая цепочка - мощность алфавита, биты на символ, число символов, итоговый объём - встречается почти в каждой контрольной по этой теме, и калькулятор выше повторяет её автоматически при любых N и длине сообщения.

Частые ошибки

• Применение формулы Хартли к неравновероятным событиям. Если исходы не равновозможны (буквы русского текста, грани несимметричного кубика), формула Хартли даёт неверный результат - нужна формула Шеннона с учётом вероятностей каждого события.
• Округление $\log_2 N$ вниз вместо вверх. Дробную часть отбрасывать нельзя: округление всегда идёт в сторону большего целого, иначе часть исходов останется неразличимой при кодировании.
• Путаница между I (точным логарифмом) и i (практическим числом бит). Первое - теоретическая мера в формуле Хартли, второе - реальное число разрядов кодировки; они совпадают только когда N - степень двойки.
• Забытый перевод бит в байты. Итоговый объём информации часто нужен в байтах или килобайтах - не забывайте делить результат на 8 (и дальше на 1024 для Кбайт).
• Подстановка вероятности вместо количества исходов. В формулу Хартли подставляется именно N - число вариантов, а не вероятность одного исхода $p = 1/N$; их можно перепутать местами.

FAQ

Сколько бит несёт сообщение об одном из 8 равновероятных событий? По формуле Хартли $I = \log_2 8 = 3$ бита - восемь равновероятных исходов кодируются ровно тремя двоичными разрядами, округление здесь не требуется, так как 8 - степень двойки.

Как формула Хартли связана с двоичным поиском? Число обязательных вопросов «да/нет» для угадывания одного из N вариантов бинарным делением диапазона пополам равно $\lceil \log_2 N \rceil$ - то есть той же величине, что даёт формула Хартли, только уже округлённой до целого числа шагов.

Чем формула Хартли отличается от формулы Шеннона? Формула Хартли - частный случай формулы Шеннона для равновероятных исходов. Если вероятности событий разные, нужно применять общую формулу Шеннона с суммой $-\sum p_i \log_2 p_i$, которая учитывает неравномерность распределения.

Коротко

Формула Хартли $I = \log_2 N$ измеряет количество информации в сообщении об одном из N равновероятных исходов. На практике логарифм округляют вверх до целого числа бит $i = \lceil \log_2 N \rceil$, потому что кодировка не работает с дробными разрядами. Через мощность алфавита и число символов легко найти объём всего сообщения $V = n \cdot i$, а сама формула Хартли - это частный случай более общей формулы Шеннона для равновероятных событий.