Что такое бит на самом деле: теория информации Шеннона

Бит — это не лампочка «вкл/выкл», а ответ на вопрос, который делит мир ровно пополам.

Информация измеряется не в буквах и не в байтах на диске, а в количестве снятой неопределённости. Чем неожиданнее сообщение, тем больше в нём информации.

Игра в угадайку

Я загадал число от 1 до 8. Сколько вопросов «да/нет» вам нужно, чтобы гарантированно его угадать? Не восемь. Достаточно трёх: «больше четырёх?», потом «больше шести?», и так далее — каждый вопрос делит оставшиеся варианты пополам. Три вопроса, потому что $2^3 = 8$.

Вот это и есть бит по Шеннону: один бит — это ответ на один идеальный вопрос «да/нет», который вдвое сокращает число вариантов. Чтобы различить $N$ равновероятных исходов, нужно $\log_2 N$ бит. Бит — не про электричество, а про выбор.

Информация — это неожиданность

Ключевой переворот Шеннона: количество информации в событии зависит от его вероятности. Сообщение «завтра в Сахаре жарко» не несёт почти ничего — вы и так это знали. А «завтра в Сахаре снег» — это бомба, потому что событие крайне маловероятно.

Математически информация одного события с вероятностью $p$ равна:

$$I = \log_2 \frac{1}{p}$$

Чем меньше $p$, тем больше информации. Достоверное событие ($p=1$) несёт ноль бит — никакого удивления. Подброшенная монетка ($p=0{,}5$) несёт ровно один бит.

Энтропия: сколько информации в источнике

Если источник выдаёт разные символы с разными вероятностями, средний объём информации на символ называется энтропией:

$$H = \sum_i p_i \log_2 \frac{1}{p_i}$$

Энтропия максимальна, когда все исходы равновероятны (полный хаос), и падает, когда какие-то символы встречаются чаще других (есть закономерность). В русском тексте буква «о» встречается куда чаще «ъ» — значит, энтропия на букву меньше пяти бит, хотя букв в алфавите больше тридцати.

Вот почему работает сжатие

Раз частые символы несут мало информации, глупо тратить на них столько же бит, сколько на редкие. Шеннон доказал: текст нельзя сжать в среднем короче его энтропии, но можно вплотную к ней приблизиться. Отсюда растёт код Хаффмана — частым буквам короткие коды, редким длинные:

Архиватор ZIP, формат JPEG, кодеки видео — все они в основе своей считают вероятности и режут предсказуемое. Когда вы видите «файл сжался в 5 раз», это значит: в нём было в 5 раз меньше настоящей информации, чем занимало места.

Граница, которую не перепрыгнуть

Самое красивое следствие — теорема Шеннона о пропускной способности канала. Она задаёт максимальную скорость, с которой можно передавать данные по зашумлённой линии без ошибок. Любой Wi-Fi, 4G, оптоволокно упираются в этот потолок. Инженеры десятилетиями приближаются к шенноновскому пределу, но превзойти его невозможно — как нельзя разогнаться быстрее света.

Итог

Шеннон в 1948 году превратил расплывчатое слово «информация» в точную физическую величину. Благодаря этому мы знаем, насколько в принципе можно сжать файл, как быстро можно качать данные по каналу и почему предсказуемость и информация — это две стороны одной монеты. Бит оказался не про железо, а про знание.