Полбита

А все ли знают, что бывает полбита информации? А то там в комментариях к Ээльмаа поднялся вопрос миллибайтов.

Больше года назад на ДиаLOG’е я писал:

Абстрагируемся от компьютера. Это иногда полезно. Что такое информация? Вопрос почти такой же, как «В чем смысл жизни?» — трудно что-либо внятное ответить. Тогда поставим вопрос по другому: какие цели преследуем мы, передавая информацию другим? Предположим, что кто-то чего-то не знает. Например, ваш возраст. Если этому человеку о вас ничего не известно, то, будем считать, все значения вашего возраста, лежащие в разумных пределах, например, от 0 до 49, равновероятны. Для простоты будем считать, что человеку все же известно, что вам меньше 50 лет, тогда назовем неопределенностью число возможных вариантов, которые может выбрать человек: F=50. Что происходит с этим числом, когда вы называете человеку свой возраст? Оно становится равным единице, т. к. зная, что вам, скажем, 20 лет, человек не может предполагать иного. Назвав число 20, вы передали человеку некоторую информацию, уменьшившую неопределенность в 50 раз.

Определение: 1 бит информации — это такое её количество, которое уменьшает неопределенность в 2 раза. Надеюсь, очевидно, что 1 байт уменьшает неопределенность в 256 раз, а, скажем, 3 байта — в 16777216 раз?

Вернемся к нашим баранам. Предположим, вы сказали нашему персонажу/герою, что вам меньше 25 лет. У него осталось 25 вариантов (от 0 до 24), т. е. F=25. Вы снизили неопределенность в два раза, значит, по определению, передали уважаемому товарищу один бит.

Теперь покажем, что количество информации, переданное вами, может быть и меньше одного бита.

Дело в том, что вероятность того, что вам меньше 25 лет равна вероятности обратного. В компьютере вся логика основана на том, что состояния 1/0 любого бита (в значении binary digit) равновероятны. В жизни бывает иначе. Например, вы сказали, что вам меньше 45 лет. Получил ли ваш собеседник 1 бит информации? По компьютерной логике, да, так как условие «возраст < 45» может быть либо истинным, либо ложным. Однако, повторюсь, в компьютере любые два исхода считаются равновероятными. Но мы-то понимаем, что вероятность того, что нам менее 45 лет намного выше, чем того, что нам от 45 до 49 (а больше нам быть просто не может, исходя из начальных условий). И мы прекрасно понимаем, что информативность фразы «мне меньше 45 лет» намного ниже, чем указание на диапазон 45..49. Таким образом, сказав, что вам мешьше 45 лет вы передаете собеседнику лишь долю бита информации.

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

Вот вам таблица для наглядности. Играем в угадай число (N) от 0 до 99. Слева — информация, которую вы сообщаете о загаданном числе, справа — её количество в битах.

N<100	0
N<99	0,01449957
N<75	0,415037499
N<50	1
N<25	2
N<12	3,058893689
N<6	4,058893689
N<1	6,64385619

Как я посчитал дробные биты догадайтесь сами. Это очень просто.