Чем больше информации тем меньше энтропия
4.2. Энтропия и информация
Разность Н(β) и Нα(β), очевидно, показывает, какие новые сведения относительно β получаем, произведя опыт α. Эта величина называется информацией относительно опыта β, содержащейся в опыте α.
Данное выражение открывает возможность численного измерения количества информации. Запишем ряд следствий:
Следствие 1. Поскольку единицей измерения энтропии является бит, то в этих же единицах может быть измерено количество информации.
Следствие 2 . Пусть опыт α = β, т.е. просто произведен опыт β. Поскольку он несет полную информацию о себе самом, неопределенность его исхода полностью снимается, т.е. Ηᵦ(β)=0. Тогда I(β,β)=Η(β). Исходя из этого, можно считать, что:
энтропия равна информации относительно опыта, которая содержится в нем самом.
энтропия опыта равна той информации, которую получаем в результате его осуществления.
1. Информация всегда положительна и равна нулю тогда и только тогда, когда опыты независимы.
2.Информация симметрична относительно последовательности опытов.
3. Информация опыта равна среднему значению количества информации, содержащейся в каком-либо одном его исходе.
Какое количество информации требуется, чтобы узнать исход броска монеты?
В данном случае n=2 и события равновероятны, т.е. р1 = р2 = 0,5.
Игра «Угадай-ка-4». Некто задумал целое число в интервале от 0 до 3. Наш опыт состоит в угадывании этого числа. На наши вопросы Некто может отвечать лишь «Да» или «Нет» Какое количество информации должны получить, чтобы узнать задуманное число, т.е полностью снять начальную неопределенность? Как правильно построить процесс угадывания?
Рис. 1.5. Выборочный каскад
Таким образом, для решения задачи оказалось достаточно 2-х вопросов независимо от того, какое число было задумано. Совпадение между количеством информации и числом вопросов с бинарными ответами неслучайно.
Количество информации численно равно числу вопросов с равновероятными бинарными вариантами ответов, которые необходимо задать, чтобы полностью снять неопределенность задачи.
В рассмотренном примере два полученных ответа в выборочном каскаде полностью сняли начальную неопределенность. Подобная процедура позволяет определить количество информации в любой задаче, интерпретация которой может быть сведена к парному выбору. Например, определение символа некоторого алфавита, использованного для представления сообщения. Приведенное утверждение перестает быть справедливым в том случае, если каждый из двух возможных ответов имеет разную вероятность.
Легко получить следствие формулы (1.24) для случая, когда все n исходов равновероятны (собственно, именно такие и рассматривались в примерах 1.10 и 1.13). В этом случае все
Эта формула была выведена в 1928 г. американским инженером Р. Хартли. Она связывает количество равновероятных состояний (n) и количество информации в сообщении (I), что любое из этих состояний реализовалось. Ее смысл в том, что, если некоторое множество содержит n элементов и х принадлежит данному множеству, то для его выделения (однозначной идентификации) среди прочих требуется количество информации, равное log2n.
Частным случаем применения формулы (1.27) является ситуация, когда n=2ᵏ, подставляя это значение в (1.27), получим:
Именно эта ситуация реализовалась в примерах 1.10 и 1.13.Анализируя результаты решения, можно прийти к выводу, что k как раз равно количеству вопросов с бинарными равновероятными ответами, которые определяли количество информации в задачах.
Случайным образом вынимается карта из колоды в 32 карты. Какое количество информации требуется, чтобы угадать, что это за карта? Как построить угадывание?
Следуя из ранее рассмотренного, справедливы следующие утверждения:
Утверждение 1. Выражение (1.24) является статистическим определением понятия «информация», поскольку в него входят вероятности возможных исходов опыта. По сути, дается операционное определение новой величины, т.е. устанавливается процедура (способ) измерения величины.
Выражение (1.23) можно интерпретировать следующим образом:
если начальная энтропия опыта H1, а в результате сообщения информации I энтропия становится равной H2 (очевидно, Н1≥ Н2), то I=H1-H2, т.е. информация равна убыли энтропии. В частном случае, если изначально равновероятных исходов было n1, а в результате передачи информации I неопределенность уменьшилась, и число исходов стало n2 (очевидно, n2≤n1), то из (1.27) получается:
Таким образом, справедливо следующее определение:
В случае равновероятных исходов информация равна логарифму отношения числа возможных исходов до и после (получения сообщения).
Утверждение 3 . Следствием аддитивности энтропии независимых опытов (1.13) оказывается аддитивность информации. Пусть с выбором одного из элементов (XA) множества А, содержащего nA элементов, связано формула, информации, а с выбором ХB из В с nB элементами информации связано формула и второй выбор никак не связан с первым, то при объединении множеств число возможных состояний (элементов) будет n=nA∙nB и для выбора комбинации ХAХB потребуется количество информации:
Однако представим, что одновременно играем в шесть таких же игр (кубик). Тогда необходимо отгадать одну из возможных комбинаций, которых всего
Следовательно, для угадывания всей шестизначной комбинации требуется I = 17 бит информации, т.е. нужно задать 17 вопросов. В среднем на один элемент (одну игру) приходится 17/6 = 2,833 вопроса, что близко к значению log2(7).
Таким образом, справедливо следующее утверждение:
Величина I, определяемая описанным выше образом, показывает, сколько в среднем необходимо сделать парных выборов для установления результата (полного снятия неопределенности), если опыт повторить многократно (n→∞).
Утверждение 5. Не всегда с каждым из ответов на вопрос, имеющий только с два варианта ответа (такие вопросы называются бинарными), связан ровно 1 бит информации. Ответ на бинарный вопрос может содержать не более 1 бит информации. Информация равна 1 бит только для равновероятных ответов. В остальных случаях она меньше 1 бит.
При угадывании результата броска игральной кости задается вопрос «Выпало 6?». Какое количество информации содержит ответ?
р=1/6, 1-р=5/6, следовательно из (1.24):
Утверждение 6 . Формула (1.24) приводит еще к одному выводу.
Утверждение 8. Объективность информации. При использовании людьми одна и та же информация может иметь различную оценку с точки зрения значимости (важности, ценности). Определяющим в такой оценке оказывается содержание (смысл) сообщения для конкретного потребителя. Однако при решении практических задач технического характера содержание сообщения может не играть роли.
Утверждение 9. Информация и знание. На бытовом уровне, в науках социальной направленности, например в педагогике «информация» отождествляется с «информированностью», т.е. человеческим знанием, которое, в свою очередь, связано с оценкой смысла информации.
В теории информации же, напротив, информация является мерой нашего незнания чего-либо (но что в принципе может произойти); как только это происходит и узнаем результат, информация, связанная с данным событием, исчезает. Состоявшееся событие не несет информации, поскольку пропадает его неопределенность (энтропия становится равной нулю), и согласно (1.23) I=0.
Энтропия? Это просто!
Этот пост является вольным переводом ответа, который Mark Eichenlaub дал на вопрос What’s an intuitive way to understand entropy?, заданный на сайте Quora
Энтропия. Пожалуй, это одно из самых сложных для понимания понятий, с которым вы можете встретиться в курсе физики, по крайней мере если говорить о физике классической. Мало кто из выпускников физических факультетов может объяснить, что это такое. Большинство проблем с пониманием энтропии, однако, можно снять, если понять одну вещь. Энтропия качественно отличается от других термодинамических величин: таких как давление, объём или внутренняя энергия, потому что является свойством не системы, а того, как мы эту систему рассматриваем. К сожалению в курсе термодинамики её обычно рассматривают наравне с другими термодинамическими функциями, что усугубляет непонимание. 
Так что же такое энтропия?
Энтропия — это то, как много информации вам не известно о системе
Например, если вы спросите меня, где я живу, и я отвечу: в России, то моя энтропия для вас будет высока, всё-таки Россия большая страна. Если же я назову вам свой почтовый индекс: 603081, то моя энтропия для вас понизится, поскольку вы получите больше информации.
Почтовый индекс содержит шесть цифр, то есть я дал вам шесть символов информации. Энтропия вашего знания обо мне понизилась приблизительно на 6 символов. (На самом деле, не совсем, потому что некоторые индексы отвечают большему количеству адресов, а некоторые — меньшему, но мы этим пренебрежём). 
Или рассмотрим другой пример. Пусть у меня есть десять игральных костей (шестигранных), и выбросив их, я вам сообщаю, что их сумма равна 30. Зная только это, вы не можете сказать, какие конкретно цифры на каждой из костей — вам не хватает информации. Эти конкретные цифры на костях в статистической физике называют микросостояниями, а общую сумму (30 в нашем случае) — макросостоянием. Существует 2 930 455 микросостояний, которые отвечают сумме равной 30. Так что энтропия этого макросостояния равна приблизительно 6,5 символам (половинка появляется из-за того, что при нумерации микросостояний по порядку в седьмом разряде вам доступны не все цифры, а только 0, 1 и 2).
А что если бы я вам сказал, что сумма равна 59? Для этого макросостояния существует всего 10 возможных микросостояний, так что его энтропия равна всего лишь одному символу. Как видите, разные макросостояния имеют разные энтропии.
Пусть теперь я вам скажу, что сумма первых пяти костей 13, а сумма остальных пяти — 17, так что общая сумма снова 30. У вас, однако, в этом случае имеется больше информации, поэтому энтропия системы для вас должна упасть. И, действительно, 13 на пяти костях можно получить 420-ю разными способами, а 17 — 780-ю, то есть полное число микросостояний составит всего лишь 420х780 = 327 600. Энтропия такой системы приблизительно на один символ меньше, чем в первом примере.
Мы измеряем энтропию как количество символов, необходимых для записи числа микросостояний. Математически это количество определяется как логарифм, поэтому обозначив энтропию символом S, а число микросостояний символом Ω, мы можем записать:
Это есть ничто иное как формула Больцмана (с точностью до множителя k, который зависит от выбранных единиц измерения) для энтропии. Если макросостоянию отвечают одно микросостояние, его энтропия по этой формуле равна нулю. Если у вас есть две системы, то полная энтропия равна сумме энтропий каждой из этих систем, потому что log(AB) = log A + log B. 
Из приведённого выше описания становится понятно, почему не следует думать об энтропии как о собственном свойстве системы. У системы есть опеделённые внутренняя энергия, импульс, заряд, но у неё нет определённой энтропии: энтропия десяти костей зависит от того, известна вам только их полная сумма, или также и частные суммы пятёрок костей.
Другими словами, энтропия — это то, как мы описываем систему. И это делает её сильно отличной от других величин, с которыми принято работать в физике.
Физический пример: газ под поршнем
Классической системой, которую рассматривают в физике, является газ, находящийся в сосуде под поршнем. Микросостояние газа — это положение и импульс (скорость) каждой его молекулы. Это эквивалентно тому, что вы знаете значение, выпавшее на каждой кости в рассмотренном раньше примере. Макросостояние газа описывается такими величинами как давление, плотность, объём, химический состав. Это как сумма значений, выпавших на костях.
Величины, описывающие макросостояние, могут быть связаны друг с другом через так называемое «уравнение состояния». Именно наличие этой связи позволяет, не зная микросостояний, предсказывать, что будет с нашей системой, если начать её нагревать или перемещать поршень. Для идеального газа уравнение состояния имеет простой вид:
Величины типа давления, температуры и плотности называются усреднёнными, поскольку являются усреднённым проявлением постоянно сменяющих друг друга микросостояний, отвечающих данному макросостоянию (или, вернее, близким к нему макросостояниям). Чтобы узнать в каком микросостоянии находится система, нам надо очень много информации — мы должны знать положение и скорость каждой частицы. Количество этой информации и называется энтропией.
Как меняется энтропия с изменением макросостояния? Это легко понять. Например, если мы немного нагреем газ, то скорость его частиц возрастёт, следовательно, возрастёт и степень нашего незнания об этой скорости, то есть энтропия вырастет. Или, если мы увеличим объём газа, отведя поршень, увеличится степень нашего незнания положения частиц, и энтропия также вырастет.
Твёрдые тела и потенциальная энергия
Если мы рассмотрим вместо газа какое-нибудь твёрдое тело, особенно с упорядоченной структурой, как в кристаллах, например, кусок металла, то его энтропия будет невелика. Почему? Потому что зная положение одного атома в такой структуре, вы знаете и положение всех остальных (они же выстроены в правильную кристаллическую структуру), скорости же атомов невелики, потому что они не могут улететь далеко от своего положения и лишь немного колеблются вокруг положения равновесия. 
Если кусок металла находится в поле тяготения (например, поднят над поверхностью Земли), то потенциальная энергия каждого атома в металле приблизительно равна потенциальной энергии других атомов, и связанная с этой энергией энтропия низка. Это отличает потенциальную энергию от кинетической, которая для теплового движения может сильно меняться от атома к атому.
Если кусок металла, поднятый на некоторую высоту, отпустить, то его потенциальная энергия будет переходить в кинетическую энергию, но энтропия возрастать практически не будет, потому что все атомы будут двигаться приблизительно одинаково. Но когда кусок упадёт на землю, во время удара атомы металла получат случайное направление движения, и энтропия резко увеличится. Кинетическая энергия направленного движения перейдёт в кинетическую энергию теплового движения. Перед ударом мы приблизительно знали, как движется каждый атом, теперь мы эту информацию потеряли.
Понимаем второй закон термодинамики
Второй закон термодинамики утверждает, что энтропия (замкнутой системы) никогда не уменьшается. Мы теперь можем понять, почему: потому что невозможно внезапно получить больше информации о микросостояниях. Как только вы потеряли некую информацию о микросостоянии (как во время удара куска металла об землю), вы не можете вернуть её назад. 
Давайте вернёмся обратно к игральным костям. Вспомним, что макросостояние с суммой 59 имеет очень низкую энтропию, но и получить его не так-то просто. Если бросать кости раз за разом, то будут выпадать те суммы (макросостояния), которым отвечает большее количество микросостояний, то есть будут реализовываться макросостояния с большой энтропией. Самой большой энтропией обладает сумма 35, и именно она и будет выпадать чаще других. Именно об этом и говорит второй закон термодинамики. Любое случайное (неконтролируемое) взаимодействие приводит к росту энтропии, по крайней мере до тех пор, пока она не достигнет своего максимума.
Перемешивание газов
И ещё один пример, чтобы закрепить сказанное. Пусть у нас имеется контейнер, в котором находятся два газа, разделённых расположенной посередине контейнера перегородкой. Назовём молекулы одного газа синими, а другого — красными.
Если открыть перегородку, газы начнут перемешиваться, потому что число микросостояний, в которых газы перемешаны, намного больше, чем микросостояний, в которых они разделены, и все микросостояния, естественно, равновероятны. Когда мы открыли перегородку, для каждой молекулы мы потеряли информацию о том, с какой стороны перегородки она теперь находится. Если молекул было N, то утеряно N бит информации (биты и символы, в данном контексте, это, фактически, одно и тоже, и отличаются только неким постоянным множителем).
Разбираемся с демоном Максвелла
Ну и напоследок рассмотрим решение в рамках нашей парадигмы знаменитого парадокса демона Максвелла. Напомню, что он заключается в следующем. Пусть у нас есть перемешанные газы из синих и красных молекул. Поставим обратно перегородку, проделав в ней небольшое отверстие, в которое посадим воображаемого демона. Его задача — пропускать слева направо только красных, и справа налево только синих. Очевидно, что через некоторое время газы снова будут разделены: все синие молекулы окажутся слева от перегородки, а все красные — справа.
Получается, что наш демон понизил энтропию системы. С демоном ничего не случилось, то есть его энтропия не изменилась, а система у нас была закрытой. Получается, что мы нашли пример, когда второй закон термодинамики не выполняется! Как такое оказалось возможно?
Решается этот парадокс, однако, очень просто. Ведь энтропия — это свойство не системы, а нашего знания об этой системе. Мы с вами знаем о системе мало, поэтому нам и кажется, что её энтропия уменьшается. Но наш демон знает о системе очень много — чтобы разделять молекулы, он должен знать положение и скорость каждой из них (по крайней мере на подлёте к нему). Если он знает о молекулах всё, то с его точки зрения энтропия системы, фактически, равна нулю — у него просто нет недостающей информации о ней. В этом случае энтропия системы как была равна нулю, так и осталась равной нулю, и второй закон термодинамики нигде не нарушился.
Но даже если демон не знает всей информации о микросостоянии системы, ему, как минимум, надо знать цвет подлетающей к нему молекулы, чтобы понять, пропускать её или нет. И если общее число молекул равно N, то демон должен обладать N бит информации о системе — но именно столько информации мы и потеряли, когда открыли перегородку. То есть количество потерянной информации в точности равно количеству информации, которую необходимо получить о системе, чтобы вернуть её в исходное состояние — и это звучит вполне логично, и опять же не противоречит второму закону термодинамики.
Бит, информационная энтропия Шеннона и код Хэмминга. Как измерить любую информацию и передать ее без потерь
«Информация есть форма жизни», — писал американский поэт и эссеист Джон Перри Барлоу. Действительно, мы постоянно сталкиваемся со словом «информация» — ее получают, передают и сохраняют. Узнать прогноз погоды или результат футбольного матча, содержание фильма или книги, поговорить по телефону — всегда ясно, с каким видом информации мы имеем дело. Но что такое сама информация, а главное — как ее можно измерить, никто обычно не задумывается. А между тем, информация и способы ее передачи — важная вещь, которая во многом определяет нашу жизнь, неотъемлемой частью которой стали информационные технологии. Научный редактор издания «Лаба.Медиа» Владимир Губайловский объясняет, что такое информация, как ее измерять, и почему самое сложное — это передача информации без искажений.
Читайте «Хайтек» в
Пространство случайных событий
В 1946 году американский ученый-статистик Джон Тьюки предложил название БИТ (BIT, BInary digiT — «двоичное число» — «Хайтек») — одно из главных понятий XX века. Тьюки избрал бит для обозначения одного двоичного разряда, способного принимать значение 0 или 1. Клод Шеннон в своей программной статье «Математическая теория связи» предложил измерять в битах количество информации. Но это не единственное понятие, введенное и исследованное Шенноном в его статье.
Представим себе пространство случайных событий, которое состоит из бросания одной фальшивой монеты, на обеих сторонах которой орел. Когда выпадает орел? Ясно, что всегда. Это мы знаем заранее, поскольку так устроено наше пространство. Выпадение орла — достоверное событие, то есть его вероятность равна 1. Много ли информации мы сообщим, если скажем о выпавшем орле? Нет. Количество информации в таком сообщении мы будем считать равным 0.
Теперь давайте бросать правильную монету: с одной стороны у нее орел, а с другой решка, как и положено. Выпадение орла или решки будут двумя разными событиями, из которых состоит наше пространство случайных событий. Если мы сообщим об исходе одного бросания, то это действительно будет новая информация. При выпадении орла мы сообщим 0, а при решке 1. Для того, чтобы сообщить эту информацию, нам достаточно 1 бита.
Что изменилось? В нашем пространстве событий появилась неопределенность. Нам есть, что о нем рассказать тому, кто сам монету не бросает и исхода бросания не видит. Но чтобы правильно понять наше сообщение, он должен точно знать, чем мы занимаемся, что означают 0 и 1. Наши пространства событий должны совпадать, и процесс декодирования — однозначно восстанавливать результат бросания. Если пространство событий у передающего и принимающего не совпадает или нет возможности однозначного декодирования сообщения, информация останется только шумом в канале связи.
Если независимо и одновременно бросать две монеты, то разных равновероятных результатов будет уже четыре: орел-орел, орел-решка, решка-орел и решка-решка. Чтобы передать информацию, нам понадобится уже 2 бита, и наши сообщения будут такими: 00, 01, 10 и 11. Информации стало в два раза больше. Это произошло, потому что выросла неопределенность. Если мы попытаемся угадать исход такого парного бросания, то имеем в два раза больше шансов ошибиться.
Чем больше неопределенность пространства событий, тем больше информации содержит сообщение о его состоянии.
Немного усложним наше пространство событий. Пока все события, которые случались, были равновероятными. Но в реальных пространствах далеко не все события имеют равную вероятность. Скажем, вероятность того, что увиденная нами ворона будет черной, близка к 1. Вероятность того, что первый встреченный на улице прохожий окажется мужчиной, — примерно 0,5. Но встретить на улице Москвы крокодила почти невероятно. Интуитивно мы понимаем, что сообщение о встрече с крокодилом имеет гораздо большую информационную ценность, чем о черной вороне. Чем ниже вероятность события, тем больше информации в сообщении о таком событии.
Пусть пространство событий не такое экзотическое. Мы просто стоим у окна и смотрим на проезжающие машины. Мимо проезжают автомобили четырех цветов, о которых нам необходимо сообщить. Для этого мы закодируем цвета: черный — 00, белый — 01, красный — 10, синий — 11. Чтобы сообщить о том, какой именно автомобиль проехал, нам достаточно передать 2 бита информации.
Но довольно долго наблюдая за автомобилями, замечаем, что цвет автомобилей распределен неравномерно: черных — 50% (каждый второй), белых — 25% (каждый четвертый), красных и синих — по 12,5% (каждый восьмой). Тогда можно оптимизировать передаваемую информацию.
Больше всего черных автомобилей, поэтому обозначим черный — 0 — самый короткий код, а код всех остальных пусть начинается на 1. Из оставшихся половина белые — 10, а оставшиеся цвета начинаются на 11. В заключение обозначим красный — 110, а синий — 111.
Теперь, передавая информацию о цвете автомобилей, мы можем закодировать ее плотнее.
Энтропия по Шеннону
Пусть наше пространство событий состоит из n разных событий. При бросании монеты с двумя орлами такое событие ровно одно, при бросании одной правильной монеты — 2, при бросании двух монет или наблюдении за автомобилями — 4. Каждому событию соответствует вероятность его наступления. При бросании монеты с двумя орлами событие (выпадение орла) одно и его вероятность p1 = 1. При бросании правильной монеты событий два, они равновероятны и вероятность каждого — 0,5: p1 = 0,5, p2 = 0,5. При бросании двух правильных монет событий четыре, все они равновероятны и вероятность каждого — 0,25: p1 = 0,25, p2 = 0,25, p3 = 0,25, p4 = 0,25. При наблюдении за автомобилями событий четыре, и они имеют разные вероятности: черный — 0,5, белый — 0,25, красный — 0,125, синий — 0,125: p1 = 0,5, p2 = 0,25, p3 = 0,125, p4 = 0,125.
Это не случайное совпадение. Шеннон так подобрал энтропию (меру неопределенности в пространстве событий), чтобы выполнялись три условия:
Все эти требования вполне соответствуют нашим представлениям о неопределенности пространства событий. Если событие одно (первый пример) — никакой неопределенности нет. Если события независимы — неопределенность суммы равна сумме неопределенностей — они просто складываются (пример с бросанием двух монет). И, наконец, если все события равновероятны, то степень неопределенности системы максимальна. Как в случае с бросанием двух монет, все четыре события равновероятны и энтропия равна 2, она больше, чем в случае с автомобилями, когда событий тоже четыре, но они имеют разную вероятность — в этом случае энтропия 1,75.
Величина H играет центральную роль в теории информации в качестве меры количества информации, возможности выбора и неопределенности.
Клод Шеннон
Клод Элвуд Шеннон — американский инженер, криптоаналитик и математик. Считается «отцом информационного века». Основатель теории информации, нашедшей применение в современных высокотехнологических системах связи. Предоставил фундаментальные понятия, идеи и их математические формулировки, которые в настоящее время формируют основу для современных коммуникационных технологий.
В 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы информации. Он также продемонстрировал, что введенная им энтропия эквивалентна мере неопределенности информации в передаваемом сообщении. Статьи Шеннона «Математическая теория связи» и «Теория связи в секретных системах» считаются основополагающими для теории информации и криптографии.
Во время Второй мировой войны Шеннон в Bell Laboratories занимался разработкой криптографических систем, позже это помогло ему открыть методы кодирования с коррекцией ошибок.
Шеннон внес ключевой вклад в теорию вероятностных схем, теорию игр, теорию автоматов и теорию систем управления — области наук, входящие в понятие «кибернетика».
Кодирование
И бросаемые монеты, и проезжающие автомобили не похожи на цифры 0 и 1. Чтобы сообщить о событиях, происходящих в пространствах, нужно придумать способ описать эти события. Это описание называется кодированием.
Кодировать сообщения можно бесконечным числом разных способов. Но Шеннон показал, что самый короткий код не может быть меньше в битах, чем энтропия.
Именно поэтому энтропия сообщения и есть мера информации в сообщении. Поскольку во всех рассмотренных случаях количество бит при кодировании равно энтропии, — значит кодирование прошло оптимально. Короче закодировать сообщения о событиях в наших пространствах уже нельзя.
При оптимальном кодировании нельзя потерять или исказить в сообщении ни одного передаваемого бита. Если хоть один бит потеряется, то исказится информация. А ведь все реальные каналы связи не дают 100-процентной уверенности, что все биты сообщения дойдут до получателя неискаженными.
Для устранения этой проблемы необходимо сделать код не оптимальным, а избыточным. Например, передавать вместе с сообщением его контрольную сумму — специальным образом вычисленное значение, получаемое при преобразовании кода сообщения, и которое можно проверить, пересчитав при получении сообщения. Если переданная контрольная сумма совпадет с вычисленной, вероятность того, что передача прошла без ошибок, будет довольно высока. А если контрольная сумма не совпадет, то необходимо запросить повторную передачу. Примерно так работает сегодня большинство каналов связи, например, при передаче пакетов информации по интернету.
Сообщения на естественном языке
Рассмотрим пространство событий, которое состоит из сообщений на естественном языке. Это частный случай, но один из самых важных. Событиями здесь будут передаваемые символы (буквы фиксированного алфавита). Эти символы встречаются в языке с разной вероятностью.
Самым частотным символом (то есть таким, который чаще всего встречается во всех текстах, написанных на русском языке) является пробел: из тысячи символов в среднем пробел встречается 175 раз. Вторым по частоте является символ «о» — 90, далее следуют другие гласные: «е» (или «ё» — мы их различать не будем) — 72, «а» — 62, «и» — 62, и только дальше встречается первый согласный «т» — 53. А самый редкий «ф» — этот символ встречается всего два раза на тысячу знаков.
Будем использовать 31-буквенный алфавит русского языка (в нем не отличаются «е» и «ё», а также «ъ» и «ь»). Если бы все буквы встречались в языке с одинаковой вероятностью, то энтропия на символ была бы Н = 5 бит, но если мы учтем реальные частоты символов, то энтропия окажется меньше: Н = 4,35 бит. (Это почти в два раза меньше, чем при традиционном кодировании, когда символ передается как байт — 8 бит).
Но энтропия символа в языке еще ниже. Вероятность появления следующего символа не полностью предопределена средней частотой символа во всех текстах. То, какой символ последует, зависит от символов уже переданных. Например, в современном русском языке после символа «ъ» не может следовать символ согласного звука. После двух подряд гласных «е» третий гласный «е» следует крайне редко, разве только в слове «длинношеее». То есть следующий символ в некоторой степени предопределен. Если мы учтем такую предопределенность следующего символа, неопределенность (то есть информация) следующего символа будет еще меньше, чем 4,35. По некоторым оценкам, следующий символ в русском языке предопределен структурой языка более чем на 50%, то есть при оптимальном кодировании всю информацию можно передать, вычеркнув половину букв из сообщения.
Другое дело, что не всякую букву можно безболезненно вычеркнуть. Высокочастотную «о» (и вообще гласные), например, вычеркнуть легко, а вот редкие «ф» или «э» — довольно проблематично.
Естественный язык, на котором мы общаемся друг с другом, высоко избыточен, а потому надежен, если мы что-то недослышали — нестрашно, информация все равно будет передана.
Но пока Шеннон не ввел меру информации, мы не могли понять и того, что язык избыточен, и до какой степени мы может сжимать сообщения (и почему текстовые файлы так хорошо сжимаются архиватором).
Избыточность естественного языка
В статье «О том, как мы ворпсиманием теcкт» (название звучит именно так!) был взят фрагмент романа Ивана Тургенева «Дворянское гнездо» и подвергнут некоторому преобразованию: из фрагмента было вычеркнуто 34% букв, но не случайных. Были оставлены первые и последние буквы в словах, вычеркивались только гласные, причем не все. Целью было не просто получить возможность восстановить всю информацию по преобразованному тексту, но и добиться того, чтобы человек, читающий этот текст, не испытывал особых трудностей из-за пропусков букв.
Почему сравнительно легко читать этот испорченный текст? В нем действительно содержится необходимая информация для восстановления целых слов. Носитель русского языка располагает определенным набором событий (слов и целых предложений), которые он использует при распознавании. Кроме того, в распоряжении носителя еще и стандартные языковые конструкции, которые помогают ему восстанавливать информацию. Например, «Она бла блее чвствтльна» — с высокой вероятностью можно прочесть как «Она была более чувствительна». Но взятая отдельно фраза «Она бла блее», скорее, будет восстановлена как «Она была белее». Поскольку мы в повседневном общении имеем дело с каналами, в которых есть шум и помехи, то довольно хорошо умеем восстанавливать информацию, но только ту, которую мы уже знаем заранее. Например, фраза «Чрты ее не бли лшны приятнсти, хтя нмнго рспхли и спллсь» хорошо читается за исключением последнего слова «спллсь» — «сплылись». Этого слова нет в современном лексиконе. При быстром чтении слово «спллсь» читается скорее как «слиплись», при медленном — просто ставит в тупик.
Оцифровка сигнала
Звук, или акустические колебания — это синусоида. Это видно, например, на экране звукового редактора. Чтобы точно передать звук, понадобится бесконечное количество значений — вся синусоида. Это возможно при аналоговом соединении. Он поет — вы слушаете, контакт не прерывается, пока длится песня.
При цифровой связи по каналу мы можем передать только конечное количество значений. Значит ли это, что звук нельзя передать точно? Оказывается, нет.
Разные звуки — это по-разному модулированная синусоида. Мы передаем только дискретные значения (частоты и амплитуды), а саму синусоиду передавать не надо — ее может породить принимающий прибор. Он порождает синусоиду, и на нее накладывается модуляция, созданная по значениям, переданным по каналу связи. Существуют точные принципы, какие именно дискретные значения надо передавать, чтобы звук на входе в канал связи совпадал со звуком на выходе, где эти значения накладываются на некоторую стандартную синусоиду (об этом как раз теорема Котельникова).
Теорема Котельникова (в англоязычной литературе — теорема Найквиста — Шеннона, теорема отсчетов) — фундаментальное утверждение в области цифровой обработки сигналов, связывающее непрерывные и дискретные сигналы и гласящее, что «любую функцию F(t), состоящую из частот от 0 до f1, можно непрерывно передавать с любой точностью при помощи чисел, следующих друг за другом через 1/(2*f1) секунд.
Помехоустойчивое кодирование. Коды Хэмминга
Если по ненадежному каналу передать закодированный текст Ивана Тургенева, пусть и с некоторым количеством ошибок, то получится вполне осмысленный текст. Но вот если нам нужно передать все с точностью до бита, задача окажется нерешенной: мы не знаем, какие биты ошибочны, потому что ошибка случайна. Даже контрольная сумма не всегда спасает.
Именно поэтому сегодня при передаче данных по сетям стремятся не столько к оптимальному кодированию, при котором в канал можно затолкать максимальное количество информации, сколько к такому кодированию (заведомо избыточному) при котором можно восстановить ошибки — так, примерно, как мы при чтении восстанавливали слова во фрагменте Ивана Тургенева.
Существуют специальные помехоустойчивые коды, которые позволяют восстанавливать информацию после сбоя. Один из них — код Хэмминга. Допустим, весь наш язык состоит из трех слов: 111000, 001110, 100011. Эти слова знают и источник сообщения, и приемник. И мы знаем, что в канале связи случаются ошибки, но при передаче одного слова искажается не более одного бита информации.
Предположим, мы сначала передаем слово 111000. В результате не более чем одной ошибки (ошибки мы выделили) оно может превратиться в одно из слов:
При передаче слова 001110 может получиться любое из слов:
Наконец, для 100011 у нас может получиться на приеме:
Заметим, что все три списка попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка 1, получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка 2 — слово 001110, а из списка 3 — слово 100011. В этом случае говорят, что наш код исправил одну ошибку.
Исправление произошло за счет двух факторов. Во-первых, получатель знает весь «словарь», то есть пространство событий получателя сообщения совпадает с пространством того, кто сообщение передал. Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.
Во-вторых, слова в словаре были подобраны особенным образом. Даже при возникновении ошибки получатель не мог перепутать одно слово с другим. Например, если словарь состоит из слов «дочка», «точка», «кочка», и при передаче получалось «вочка», то получатель, зная, что такого слова не бывает, исправить ошибку не смог бы — любое из трех слов может оказаться правильным. Если же в словарь входят «точка», «галка», «ветка» и нам известно, что допускается не больше одной ошибки, то «вочка» это заведомо «точка», а не «галка». В кодах, исправляющих ошибки, слова выбираются именно так, чтобы они были «узнаваемы» даже после ошибки. Разница лишь в том, что в кодовом «алфавите» всего две буквы — ноль и единица.
Избыточность такого кодирования очень велика, а количество слов, которые мы можем таким образом передать, сравнительно невелико. Нам ведь надо исключать из словаря любое слово, которое может при ошибке совпасть с целым списком, соответствующим передаваемым словам (например, в словаре не может быть слов «дочка» и «точка»). Но точная передача сообщения настолько важна, что на исследование помехоустойчивых кодов тратятся большие силы.
Сенсация
Понятия энтропии (или неопределенности и непредсказуемости) сообщения и избыточности (или предопределенности и предсказуемости) очень естественно соответствуют нашим интуитивным представлениям о мере информации. Чем более непредсказуемо сообщение (тем больше его энтропия, потому что меньше вероятность), — тем больше информации оно несет. Сенсация (например, встреча с крокодилом на Тверской) — редкое событие, его предсказуемость очень мала, и потому велика информационная стоимость. Часто информацией называют новости — сообщения о только что произошедших событиях, о которых мы еще ничего не знаем. Но если о случившемся нам расскажут второй и третий раз примерно теми же словами, избыточность сообщения будет велика, его непредсказуемость упадет до нуля, и мы просто не станем слушать, отмахиваясь от говорящего со словами «Знаю, знаю». Поэтому СМИ так стараются быть первыми. Вот это соответствие интуитивному чувству новизны, которое рождает действительно неожиданное известие, и сыграло главную роль в том, что статья Шеннона, совершенно не рассчитанная на массового читателя, стала сенсацией, которую подхватила пресса, которую приняли как универсальный ключ к познанию природы ученые самых разных специальностей — от лингвистов и литературоведов до биологов.
Но понятие информации по Шеннону — строгая математическая теория, и ее применение за пределами теории связи очень ненадежно. Зато в самой теории связи она играет центральную роль.
Семантическая информация
Шеннон, введя понятие энтропии как меры информации, получил возможность работать с информацией — в первую очередь, ее измерять и оценивать такие характеристики, как пропускная способность каналов или оптимальность кодирования. Но главным допущением, которое позволило Шеннону успешно оперировать с информацией, было предположение, что порождение информации — это случайный процесс, который можно успешно описать в терминах теории вероятности. Если процесс неслучайный, то есть он подчиняется закономерностям (к тому же не всегда ясным, как это происходит в естественном языке), то к нему рассуждения Шеннона неприменимы. Все, что говорит Шеннон, никак не связано с осмысленностью информации.
Пока мы говорим о символах (или буквах алфавита), мы вполне можем рассуждать в терминах случайных событий, но как только мы перейдем к словам языка, ситуация резко изменится. Речь — это процесс, особым образом организованный, и здесь структура сообщения не менее важна, чем символы, которыми она передается.
Еще недавно казалось, что мы ничего не можем сделать, чтобы хоть как-то приблизиться к измерению осмысленности текста, но в последние годы ситуация начала меняться. И связано это прежде всего с применением искусственных нейронных сетей к задачам машинного перевода, автоматического реферирования текстов, извлечению информации из текстов, генерированию отчетов на естественном языке. Во всех этих задачах происходит преобразование, кодирование и декодирование осмысленной информации, заключенной в естественном языке. И постепенно складывается представление об информационных потерях при таких преобразованиях, а значит — о мере осмысленной информации. Но на сегодняшний день той четкости и точности, которую имеет шенноновская теория информации, в этих трудных задачах еще нет.