Информацио́нная энтропи́я - мера неопределённости или непредсказуемости некоторой системы (в статистической физике или теории информации), в частности неопределённость появления какого-либо символа первичного алфавита . В последнем случае при отсутствии информационных потерь энтропия численно равна количеству информации на символ передаваемого сообщения.
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии n {\displaystyle n} -го порядка, см. ) встречаются очень редко, то неопределённость уменьшается еще сильнее.
Понятие информационной энтропии можно проиллюстрировать при помощи демона Максвелла . Концепции информации и энтропии имеют глубокие связи друг с другом [какие? ] , но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу [ ] .
Энтропия - это количество информации, приходящейся на одно элементарное сообщение источника, вырабатывающего статистически независимые сообщения.
Энциклопедичный YouTube
1 / 5
✪ Представление об энтропии
✪ Что такое Энтропия?
✪ Информационная энтропия
✪ Энтропия и второй закон термодинамики (видео 3) | Энергия| Биология
✪ Что такое энтропия? Джефф Филлипс #TED-Ed
Субтитры
Итак, мы дали два определения энтропии как переменной состояния. Энтропия обозначается буквой S. Согласно термодинамическому определению, изменения в энтропии равны добавляемому теплу, делённому на температуру, при которой это тепло добавляется. При этом, если температура будет меняться по мере добавления тепла (что обычно и происходит), то нам придётся провести некоторые вычисления. И это вы можете рассматривать как математическое, или статистическое, или комбинаторное определение энтропии. Согласно этому определению, энтропия равняется умноженному на постоянное число натуральному логарифму количества состояний, которые может принимать система. И в подобном случае все состояния имеют одинаковую вероятность. Если мы говорим о невообразимо огромном количестве молекул, которые могут иметь ещё более огромное количество состояний, мы можем предположить, что все они будут отличаться примерно равной вероятностью. Есть и немного более сложное определение – для случаев с вероятностью различного порядка, однако сейчас мы его касаться не будем. Теперь, когда мы рассмотрели эти два определения, самое время рассказать вам о втором законе термодинамики. Вот он. Это довольно простой закон, который в то же время объясняет весьма широкий спектр различных явлений. Согласно этому закону, изменения в энтропии во Вселенной при осуществлении любого процесса всегда будут больше 0 или равны ему. То есть когда во Вселенной что-нибудь происходит, результатом этого становится увеличение энтропии. Это очень важный вывод. Давайте посмотрим, сможем ли мы приложить этот закон к конкретным ситуациям и таким образом понять его смысл. Допустим, у меня есть два связанных друг с другом резервуара. Вот у меня T1. Пусть это будет наш горячий резервуар. А вот у нас T2. Это будет холодный резервуар. Что ж, по опыту мы знаем… Что происходит, если сосуд с горячей водой имеет общую стенку с сосудом с холодной водой? Что происходит в подобном случае? Да, температура воды в них выравнивается. Если мы говорим об одном и том же веществе, то процесс остановится примерно посередине, если они находятся в одной фазе. Таким образом, мы имеем дело с передачей тепла от более горячего вещества к более холодному. У нас есть некое тепло, Q, которое передаётся от более горячего вещества к холодному. Конечно, в повседневной реальности вы не увидите, чтобы тепло передавалось от более холодного вещества к более горячему. Если вы положите кубик льда, скажем, в горячий чай, то, конечно, лёд не станет холоднее, а чай – горячее. Температура обоих веществ станет примерно равной, то есть по сути дела – чай отдаст часть тепла льду. Так же мы говорим о двух резервуарах, и я предполагаю, что их температура остаётся постоянной. Это может произойти только в том случае, если оба они являются бесконечно большими, чего, конечно, в реальном мире не существует. В реальном мире T1 будет снижаться, а T2 – повышаться. Но давайте посмотрим, должно ли это происходить, согласно второму закону термодинамики. Итак, что же происходит здесь? Каково чистое изменение энтропии для T1? Согласно второму закону термодинамики, изменение энтропии для Вселенной больше 0. Но в данном случае оно равно изменению энтропии для T1, плюс изменение энтропии для… хотя не совсем так… вместо T1 давайте назовём это просто 1… для системы 1, то есть, вот для этой горячей системы плюс изменение энтропии для системы 2. Итак, каково же изменение энтропии для системы 1? Она теряет Q1 при высокой температуре. Получается минус Q (потому что система отдаёт тепло), делённое на T1. Затем мы должны учесть тепло, добавленное системе T2. Итак, прибавим Q, делённое на Т2. У нас получится изменение энтропии для системы 2, верно? Этот резервуар, который имеет температуру 1, более высокую, теряет тепло. А резервуар, у которого более низкая температура 2, тепло получает. Не будет ли это выше 0? Давайте немного подумаем. Если мы разделим… позвольте, я перепишу это… Я запишу по-другому: Q, делённое на Т2, минус вот это. Я просто переставляю показатели... Минус Q, делённое на T1. И какой же показатель теперь больше? T2 или T1? Что ж, T1 больше, верно? Теперь, когда у нас есть более высокий показатель… Если мы используем слово «выше», мы имеем в виду определённое сравнение. Итак, T1 выше вот этого. При этом в числителе в обоих случаях мы имеем одно и то же число, так? То есть если я возьму, скажем, 1/2 минус 1/3, то получу показатель больше 0. Этот показатель больше вот этого, потому что этот имеет больший знаменатель. Вы делите на большее число. Над этим стоит поразмыслить. Вы делите Q на вот это число, а затем вычитаете Q, делённое на большее число. Таким образом, вот эта дробь будет иметь более низкое абсолютное значение. И она будет больше 0. Соответственно, второй закон термодинамики подтверждается нашим наблюдением, согласно которому тепло переходит от горячего тела к холодному. Теперь вы можете сказать – эй, Сэл, я могу доказать, что ты неправ. Вы можете сказать, если я поставлю кондиционер в комнату… Вот комната, а вот, что снаружи. И вы скажете – посмотрите, что делает кондиционер! В комнате уже холодно, а на улице уже жарко. Но что делает кондиционер? Он делает холодное ещё более холодным, а горячее – ещё более горячим. Он забирает некое Q и движется вот в этом направлении. Верно? Он забирает тепло из холодной комнаты и выпускает его в горячий воздух. И вы говорите – это нарушает второй закон термодинамики. Вы только что опровергли его. Вы заслуживаете Нобелевской премии! Но я скажу вам – вы забываете один маленький факт. Внутри этого кондиционера есть компрессор и двигатель, которые активно работают и создают такой результат. И вот этот двигатель, я выделю его розовым, тоже выпускает тепло. Давайте назовем его Q двигателя. Таким образом, если вы хотите рассчитать общую энтропию, создаваемую для всей Вселенной, это будет энтропия холодной комнаты, плюс изменение энтропии для улицы. Энтропия холодной комнаты плюс изменение энтропии для улицы. Пометим здесь комнату... Вы можете сказать – ладно. Данное изменение энтропии для комнаты, которая отдаёт тепло… допустим, что в комнате на протяжении хотя бы одной миллисекунды сохраняется постоянная температура. Комната отдаёт некоторое Q при определённой температуре T1. И затем… тут надо поставить минус… затем улица получает некоторое тепло при определённой температуре T2. И вы скажете: этот показатель меньше вот этого. Потому что знаменатель выше. Тогда это будет отрицательная энтропия, и вы можете сказать, что это нарушает второй закон термодинамики. Нет! Здесь мы должны учесть ещё один момент: что улица также получает тепло от двигателя. Тепло от двигателя, делённое на уличную температуру. И я гарантирую, что эта переменная, прямо сейчас цифр приводить не буду, сделает всё это выражение положительным. Этот переменная превратит общую чистую энтропию для Вселенной в положительную. А теперь давайте немного подумаем о том, что такое энтропия с точки зрения терминологии. На уроках химии учитель нередко может сказать, что энтропия равна беспорядку. Это не ошибка. Энтропия равна беспорядку. Это не ошибка, ведь энтропия – это действительно беспорядок, но вы должны быть очень осторожны с определением беспорядка. Потому что один из самых частых примеров гласит: возьмём чистую комнату – допустим, ваша спальня чистая, но затем она становится грязной. И они говорят – взгляните, Вселенная стала более беспорядочной. В грязной комнате больше беспорядка, чем в чистой. Но это не увеличение энтропии. Так что это не очень хороший пример. Почему? Да потому, что чистая и грязная – это лишь состояния комнаты. А мы помним, что энтропия – это макропеременная состояния. Вы используете её для описания системы, когда у вас нет настроения сидеть здесь и рассказывать мне, что конкретно делает каждая частица. И это макропеременная, которая показывает, сколько времени потребуется, чтобы рассказать мне о том, что делает каждая частица. Эта переменная указывает на то, сколько состояний существует в данном случае или сколько информации о состояниях я бы хотел от вас получить. В случае с чистой и грязной комнатой у нас есть лишь два различных состояния одной и той же комнаты. Если в комнате держится одинаковая температура и есть одинаковое количество молекул и так далее, то она будет иметь одинаковую энтропию. Итак, когда комната становится более грязной, энтропия не увеличивается. Например, у меня есть грязная холодная комната. Допустим, я вошёл в эту комнату и приложил немало усилий, чтобы убраться в ней. Так я добавляю в систему порцию тепла, и молекулы моего пота разлетаются по всей комнате - соответственно, в ней появляется больше содержимого, и она становится более тёплой, превращаясь в жаркую, чистую комнату с капельками пота. Это содержимое можно скомпоновать большим количеством способов, и поскольку в комнате жарко, то каждая молекула в ней может принять больше состояний, так? Поскольку средняя кинетическая энергия высока, то можно попытаться выяснить, каким количеством кинетических энергий может обладать каждая молекула, а в потенциале это количество может быть достаточно большим. По сути дела это и есть увеличение энтропии. От грязной, холодной комнаты - к жаркой и чистой. И это довольно хорошо согласовывается с тем, что нам известно. То есть когда я вхожу в комнату и начинаю убираться в ней, я приношу в неё тепло. И Вселенная становится более… Полагаю, мы можем сказать, что энтропия увеличивается. Так где же здесь беспорядок? Допустим, у меня есть мяч, и он падает на землю и ударяется об неё. И здесь мы должны задать вопрос, который постоянно задаётся со времён открытия первого закона термодинамики. Как только мяч ударился о землю… Мяч ударяется о землю, верно? Я его бросил: в его верхней части есть определённая потенциальная энергия, которая затем превращается в кинетическую энергию, и мяч ударяется о землю, и затем останавливается. Вот тут-то и возникает вполне закономерный вопрос – а что же произошло со всей этой энергией? Закон сохранения энергии. Куда она вся подевалась? Прямо перед тем, как удариться о землю, мяч обладал кинетической энергией, а затем остановился. Кажется, что энергия исчезла. Но это не так. Когда мяч падает, у него очень много… как известно, у всего есть своё тепло. А что же насчет земли? Её молекулы вибрировали с определённой кинетической энергией и потенциальной энергией. А затем и молекулы нашего мяча стали немного вибрировать. Но их движение было, в основном, направлено вниз, так? Движение большинства молекул мяча было направлено вниз. Когда же он ударяется о землю, то… позвольте, я нарисую поверхность мяча, соприкасающуюся с землёй. Молекулы мяча в его передней части будут выглядеть вот таким образом. И их довольно много. Это твёрдое тело. Вероятно – с решётчатой структурой. И затем мяч ударяется о землю. Когда это происходит… земля – это ещё одно твёрдое тело… Отлично, вот у нас микросостояние. Что же произойдёт? Вот эти молекулы вступят во взаимодействие с этими и передадут свою кинетическую энергию, направленную вниз… Они передадут её вот этим частицам земли. И столкнутся с ними. А когда, скажем, вот эта частица столкнётся вот с этой, то она может двинуться в этом направлении. А эта частица начнёт колебаться вот так, туда и обратно. Вот эта частица может оттолкнуться от этой и двинуться в этом направлении, а затем столкнуться вот с этой и двинуться вот сюда. А затем, поскольку вот эта частица врезается сюда, вот эта – врезается вот сюда, и поскольку вот эта ударила вот здесь, вот эта – ударяет тут. С точки зрения мяча, происходит относительно направленное движение, но при соприкосновении с молекулами земли он начинает вырабатывать кинетическую энергию и создавать движение в самых различных направлениях. Вот эта молекула сдвинет эту вот сюда, а вот эта – двинется сюда. Теперь уже движение не будет направленным, если у нас будет так много молекул… я обозначу их другим цветом… так вот, если у нас будет много молекул и все они будут двигаться точно в одном и том же направлении, то микросостояние будет выглядеть как макросостояние. Всё тело окажется вот в этом направлении. Если же у нас есть очень много v и все они движутся в разных направлениях, то мой мяч в целом будет оставаться на месте. У нас может быть такое же количество кинетической энергии на молекулярном уровне, но они все будут сталкиваться друг с другом. И в данном случае мы можем описать кинетическую энергию как внутреннюю энергию или как температуру, которая представляет собой среднюю кинетическую энергию. Таким образом, когда мы говорим, что мир становится более беспорядочным, мы думаем, о порядке скоростей или энергий молекул. Перед тем, как они будут упорядочены, молекулы могут немного вибрировать, но, в основном, они будут падать вниз. Но когда они столкнутся с землёй, они все тут же начнут вибрировать в разных направлениях немного больше. И земля тоже начинает вибрировать в разных направлениях. Итак – на уровне микросостояния – всё становится намного более беспорядочным. Есть ещё один довольно любопытный вопрос. Существует ещё одна вероятность… Вы можете подумать: «Смотрите, этот мяч упал и ударился о землю. Почему он просто не… не может ли случиться так, что молекулы земли сами поменяют свой порядок так, чтобы должным образом ударить молекулы мяча? Существует определённая вероятность того, что, благодаря беспорядочному движению, в какой-то момент времени все молекулы земли просто ударят молекулы мяча таким образом, чтобы он опять подпрыгнул вверх». Да, это так. Всегда есть бесконечно малый шанс того, что это случится. Существует вероятность того, что мяч будет просто лежать на земле… и это весьма любопытно… Вам, вероятно, придётся ждать сто миллионов лет, чтобы это произошло, если это вообще когда-нибудь произойдёт… и мяч может просто подпрыгнуть вверх. Существует очень небольшая возможность того, что эти молекулы будут беспорядочно вибрировать таким образом, чтобы упорядочиться на секунду, а затем мяч подпрыгнет. Но вероятность этого практически равняется 0. Итак, когда люди говорят о порядке и беспорядке, беспорядок усиливается, так как теперь эти молекулы будут двигаться в разных направлениях и принимать большее количество потенциальных состояний. И мы это увидели. Как известно, на определённом уровне энтропия выглядит как нечто магическое, но на других уровнях она представляется вполне логичной. В одном ролике… думаю, это был последний ролик… у меня было большое количество молекул, а затем появилось это дополнительное пространство вот здесь, после чего я убрал стенку. И мы увидели, что эти молекулы… понятно, что были какие-то молекулы, которые отталкивались от этой стенки раньше, потому что с этим было связано определённое давление. Затем, как только мы уберём эту стенку, молекулы, которые ударились бы об неё, продолжат двигаться. Остановить их нечему. Движение будет осуществляться в этом направлении. Они могут сталкиваться с другими молекулами и с этими стенками. Но что касается этого направления, то вероятность столкновения, особенно для вот этих молекул, в принципе равняется 0. Поэтому будет происходить расширение и заполнение ёмкости. Так что всё вполне логично. Но что самое главное, второй закон термодинамики, как мы увидели в этом ролике, говорит о том же самом. То есть о том, что молекулы будут двигаться и заполнять ёмкость. И очень мала вероятность того, что они все вернутся в упорядоченное состояние. Конечно, есть определённая возможность того, что беспорядочно двигаясь, они вернутся в это положение. Но эта вероятность очень и очень мала. Более того, и я хочу обратить на это особое внимание, S – это макросостояние. Мы никогда не говорим об энтропии применительно к отдельной молекуле. Если мы знаем, что делает отдельная молекула, мы не должны беспокоиться об энтропии. Мы должны думать о системе в целом. Так что если мы будем рассматривать всю систему и не будем обращать внимания на молекулы, мы не узнаем, что на самом деле произошло. При этом мы можем обратить внимание лишь на статистические свойства молекул. Сколько молекул у нас имеется, какова их температура, их макродинамика, давление… и знаете что? Ёмкость, в которую помещены эти молекулы, имеет больше состояний, чем более мелкая ёмкость со стенкой. Даже если вдруг все молекулы по случайности соберутся вот здесь, мы и не узнаем, что это произошло, потому что мы не смотрим на микросостояния. И это очень важно иметь в виду. Когда кто-то говорит, что грязная комната отличается более высокой энтропией, чем чистая, то мы должны понимать, что они рассматривают микросостояния. А энтропия – это, прежде всего, понятие, связанное с макросостоянием. Вы можете просто сказать, что комната отличается определённым объёмом энтропии. То есть понятие энтропии связано с комнатой в целом, но оно будет полезно только тогда, когда вы точно не знаете, что в ней происходит. У вас есть лишь самое общее представление о том, чем заполнена комната, какая в ней температура, какое давление. Все это общие макросвойства. Энтропия же расскажет нам, сколько макросостояний может иметь эта макросистема. Или сколько информации, ведь существует же понятие информационной энтропии, сколько информации я должен вам предоставить, чтобы вы составили точное представление о микросостоянии системы в соответствующий момент времени. Примерно так. Надеюсь, это обсуждение оказалось хоть немного полезным для вас и прояснило некоторые заблуждения относительно энтропии, а также помогло вам составить представление о том, что это такое на самом деле. До следующего ролика!
Формальные определения
Информационная двоичная энтропия для независимых случайных событий x {\displaystyle x} с n {\displaystyle n} возможными состояниями, распределённых с вероятностями ( i = 1 , . . . , n {\displaystyle i=1,...,n} ), рассчитывается по формуле
H (x) = − ∑ i = 1 n p i log 2 p i . {\displaystyle H(x)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}.}Эта величина также называется средней энтропией сообщения . Величина H i = − log 2 p i {\displaystyle H_{i}=-\log _{2}{p_{i}}} называется частной энтропией , характеризующей только i {\displaystyle i} -e состояние. В общем случае основание логарифма в определении энтропии может быть любым, большим 1; его выбор определяет единицу измерения энтропии. Так, зачастую (например, в задачах математической статистики) более удобным может оказаться применение натурального логарифма.
Таким образом, энтропия системы x {\displaystyle x} является суммой с противоположным знаком всех относительных частот появления состояния (события) с номером i {\displaystyle i} , умноженных на их же двоичные логарифмы . Это определение для дискретных случайных событий можно формально расширить для непрерывных распределений, заданных плотностью распределения вероятностей , однако полученный функционал будет обладать несколько иными свойствами (см. дифференциальная энтропия).
Определение по Шеннону
Определение энтропии Шеннона связано с понятием термодинамической энтропии . Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.
Определение с помощью собственной информации
Также можно определить энтропию случайной величины, введя предварительно понятия распределения случайной величины X {\displaystyle X} , имеющей конечное число значений:
P X (x i) = p i , p i ⩾ 0 , i = 1 , 2 , … , n {\displaystyle P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;n} ∑ i = 1 n p i = 1 {\displaystyle \sum _{i=1}^{n}p_{i}=1} I (X) = − log P X (X) . {\displaystyle I(X)=-\log P_{X}(X).}Тогда энтропия определяется как:
H (X) = E (I (X)) = − ∑ i = 1 n p (i) log p (i) . {\displaystyle H(X)=E(I(X))=-\sum _{i=1}^{n}p(i)\log p(i).}От основания логарифма зависит единица измерения количества информации и энтропии: бит , нат , трит или хартли .
Свойства
Энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию:
У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю:
−
∑
i
=
1
∞
log
2
1
=
0
{\displaystyle -\sum _{i=1}^{\infty }\log _{2}1=0}
, а количество возможных состояний
равно:
2
0
=
1
{\displaystyle 2^{0}=1}
возможное состояние
(значение) («А») и от основания логарифма не зависит.
Это тоже информация, которую тоже надо учитывать. Примером запоминающих устройств в которых используются разряды с энтропией равной нулю, но с количеством информации
равным 1 возможному состоянию
, т.е. не равным нулю, являются разряды данных записанных в ПЗУ , в которых каждый разряд имеет только одно возможное состояние
.
Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.
- Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию, или имеют идентичные секции независимо от информации в структуре данных.
- Количество энтропии не всегда выражается целым числом битов.
Математические свойства
- Неотрицательность : H (X) ⩾ 0 {\displaystyle H(X)\geqslant 0} .
- Ограниченность : H (X) = − E (log 2 p i) = ∑ i = 1 n p i log 2 1 p i = ∑ i = 1 n p i f (g i) ⩽ f (∑ i = 1 n p i g i) = log 2 n {\displaystyle H(X)=-E(\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _{2}{\frac {1}{p_{i}}}=\sum _{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum _{i=1}^{n}p_{i}g_{i}\right)=\log _{2}n} , что вытекает из неравенства Йенсена для вогнутой функции f (g i) = log 2 g i {\displaystyle f(g_{i})=\log _{2}g_{i}} и g i = 1 p i {\displaystyle g_{i}={\frac {1}{p_{i}}}} . Если все n {\displaystyle n} элементов из X {\displaystyle X} равновероятны, H (X) = log 2 n {\displaystyle H(X)=\log _{2}n} .
- Если независимы, то H (X ⋅ Y) = H (X) + H (Y) {\displaystyle H(X\cdot Y)=H(X)+H(Y)} .
- Энтропия - выпуклая вверх функция распределения вероятностей элементов.
- Если X , Y {\displaystyle X,\;Y} имеют одинаковое распределение вероятностей элементов, то H (X) = H (Y) {\displaystyle H(X)=H(Y)} .
Эффективность
Алфавит может иметь вероятностное распределение далекое от равномерного . Если исходный алфавит содержит n {\displaystyle n} символов, тогда его можно сравнить с «оптимизированным алфавитом», вероятностное распределение которого равномерное. Соотношение энтропии исходного и оптимизированного алфавита - это эффективность исходного алфавита, которая может быть выражена в процентах. Эффективность исходного алфавита с n {\displaystyle n} символами может быть также определена как его n {\displaystyle n} -арная энтропия.
Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически - типичного набора или, на практике, - кодирования Хаффмана , кодирования Лемпеля - Зива - Велча или арифметического кодирования .
Вариации и обобщения
b -арная энтропия
В общем случае b -арная энтропия (где b равно 2, 3, …) источника S = (S , P) {\displaystyle {\mathcal {S}}=(S,\;P)} с исходным алфавитом S = { a 1 , … , a n } {\displaystyle S=\{a_{1},\;\ldots ,\;a_{n}\}} и дискретным распределением вероятности P = { p 1 , … , p n } , {\displaystyle P=\{p_{1},\;\ldots ,\;p_{n}\},} где p i {\displaystyle p_{i}} является вероятностью ( p i = p (a i) {\displaystyle p_{i}=p(a_{i})} ), определяется формулой:
H b (S) = − ∑ i = 1 n p i log b p i . {\displaystyle H_{b}({\mathcal {S}})=-\sum _{i=1}^{n}p_{i}\log _{b}p_{i}.}В частности, при b = 2 {\displaystyle b=2} , мы получаем обычную двоичную энтропию, измеряемую в битах . При b = 3 {\displaystyle b=3} , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При b = e {\displaystyle b=e} , мы получаем информацию измеряемую в натах .
Условная энтропия
Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия), очевидно, меньше. Для учёта таких фактов используется условная энтропия.
Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть, вероятности двухбуквенных сочетаний):
H 1 (S) = − ∑ i p i ∑ j p i (j) log 2 p i (j) , {\displaystyle H_{1}({\mathcal {S}})=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\log _{2}p_{i}(j),}где i {\displaystyle i} - это состояние, зависящее от предшествующего символа, и p i (j) {\displaystyle p_{i}(j)} - это вероятность j {\displaystyle j} при условии, что i {\displaystyle i} был предыдущим символом.
Например, для русского языка без буквы «ё» H 0 = 5 , H 1 = 4,358 , H 2 = 3 , 52 , H 3 = 3 , 01 {\displaystyle H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01} .
Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы . Для описания потерь со стороны источника (то есть известен посланный сигнал) рассматривают условную вероятность получения приёмником символа при условии, что был отправлен символ a i {\displaystyle a_{i}} . При этом канальная матрица имеет следующий вид:
| b 1 {\displaystyle b_{1}} | b 2 {\displaystyle b_{2}} | … | b j {\displaystyle b_{j}} | … | b m {\displaystyle b_{m}} | |
|---|---|---|---|---|---|---|
| a 1 {\displaystyle a_{1}} | p (b 1 ∣ a 1) {\displaystyle p(b_{1}\mid a_{1})} | p (b 2 ∣ a 1) {\displaystyle p(b_{2}\mid a_{1})} | … | p (b j ∣ a 1) {\displaystyle p(b_{j}\mid a_{1})} | … | p (b m ∣ a 1) {\displaystyle p(b_{m}\mid a_{1})} |
| a 2 {\displaystyle a_{2}} | p (b 1 ∣ a 2) {\displaystyle p(b_{1}\mid a_{2})} | p (b 2 ∣ a 2) {\displaystyle p(b_{2}\mid a_{2})} | … | p (b j ∣ a 2) {\displaystyle p(b_{j}\mid a_{2})} | … | p (b m ∣ a 2) {\displaystyle p(b_{m}\mid a_{2})} |
| … | … | … | … | … | … | … |
| a i {\displaystyle a_{i}} | p (b 1 ∣ a i) {\displaystyle p(b_{1}\mid a_{i})} | p (b 2 ∣ a i) {\displaystyle p(b_{2}\mid a_{i})} | … | p (b j ∣ a i) {\displaystyle p(b_{j}\mid a_{i})} | … | p (b m ∣ a i) {\displaystyle p(b_{m}\mid a_{i})} |
| … | … | … | … | … | … | … |
| a m {\displaystyle a_{m}} | p (b 1 ∣ a m) {\displaystyle p(b_{1}\mid a_{m})} | p (b 2 ∣ a m) {\displaystyle p(b_{2}\mid a_{m})} | … | p (b j ∣ a m) {\displaystyle p(b_{j}\mid a_{m})} | … | p (b m ∣ a m) {\displaystyle p(b_{m}\mid a_{m})} |
Очевидно, вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал a i {\displaystyle a_{i}} , описываются через частную условную энтропию:
H (B ∣ a i) = − ∑ j = 1 m p (b j ∣ a i) log 2 p (b j ∣ a i) . {\displaystyle H(B\mid a_{i})=-\sum _{j=1}^{m}p(b_{j}\mid a_{i})\log _{2}p(b_{j}\mid a_{i}).}Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:
H (B ∣ A) = ∑ i p (a i) H (B ∣ a i) . {\displaystyle H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).}H (B ∣ A) {\displaystyle H(B\mid A)} означает энтропию со стороны источника, аналогично рассматривается H (A ∣ B) {\displaystyle H(A\mid B)} - энтропия со стороны приёмника: вместо p (b j ∣ a i) {\displaystyle p(b_{j}\mid a_{i})} всюду указывается p (a i ∣ b j) {\displaystyle p(a_{i}\mid b_{j})} (суммируя элементы строки можно получить p (a i) {\displaystyle p(a_{i})} , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).
Взаимная энтропия
Взаимная энтропия или энтропия объединения предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H (A B) {\displaystyle H(AB)} , где A {\displaystyle A} характеризует передатчик, а B {\displaystyle B} - приёмник.
Информация и энтропия
Обсуждая понятие информация, невозможно не затронуть другое смежное понятие – энтропия. Впервые понятия энтропия и информация связал К.Шеннон.
| Клод Элвуд Шеннон (Claude Elwood Shannon ), 1916-2001 - дальний родственник Томаса Эдисона, американский инженер и математик, был сотрудником Bell Laboratories с 1941 дo 1972 г. В его работе "Математическая теория связи" (http://cm.bell-labs.com/cm/ms/what/shannonday/), опубликованной в 1948 г., впервые определялась мера информационного содержания любого сообщения и понятие кванта информации - бита. Эти идеи легли в основу теории современной цифровой связи. Другая работа Шеннона "Communication Theory of Secrecy Systems", опубликованная в 1949 г., способствовала превращению криптографии в научную дисциплину. Он является основателем теории информации , нашедшей применение в современных высокотехнологических системах связи. Шеннон внес огромный вклад в теорию вероятностных схем, теорию автоматов и теорию систем управления - науки, объединяемые понятием «кибернетика». |
Физическое определение энтропии
Впервые понятие энтропии ввел Клаузиус в 1865 г. как функцию термодинамического состояния системы
где Q – теплота, T - температура.
Физический смысл энтропии проявляется как часть внутренней энергии системы, которая не может быть превращена в работу. Клаузиус эмпирически получил эту функцию, экспериментируя с газами.
Л.Больцман (1872г.) методами статистической физики вывел теоретическое выражение энтропии
где К – константа; W – термодинамическая вероятность (количество перестановок молекул идеального газа, не влияющее на макросостояние системы).
Энтропия Больцмана выведена для идеального газа и трактуется как мера беспорядка, мера хаоса системы. Для идеального газа энтропии Больцмана и Клаузиуса тождественны. Формула Больцмана стала настолько знаменитой, что начертана в качестве эпитафии на его могиле. Сложилось мнение, что энтропия и хаос есть одно и то же. Несмотря на то, что энтропия описывает только идеальные газы, ее некритично стали привлекать для описания более сложных объектов.
Сам Больцман в 1886г. попытался с помощью энтропии объяснить, что такое жизнь. По мнению Больцмана, жизнь это явление, способное уменьшать свою энтропию. Согласно Больцману и его последователям, все процессы во Вселенной изменяются в направлении хаоса. Вселенная идет к тепловой смерти. Этот мрачный прогноз долго господствовал в науке. Однако углубление знаний об окружающем Мире постепенно расшатали эту догму.
Классики не связывали энтропию с информацией .
Энтропия как мера информации
Заметим, что понятие "информация" часто трактуется как "сведения", а передача информации осуществляется с помощью связи. К. Шеннон рассматривал энтропию как меру полезной информации в процессах передачи сигналов по проводам.
Для расчета энтропии Шеннон предложил уравнение, напоминающее классическое выражение энтропии, найденное Больцманом. Рассматривается независимое случайное событие x с N возможными состояниями и p i -вероятность i-го состояния. Тогда энтропия события x
Эта величина также называется средней энтропией. Например, речь может идти о передаче сообщения на естественном языке. При передаче различных букв мы передаем разное количество информации. Количество информации на букву связано с частотой употреблений этой буквы во всех сообщениях, формируемых на языке. Чем более редкую букву мы передаем, тем больше в ней информации.
Величина
H i = P i log 2 1/P i = ‑P i log 2 P i ,
называется частной энтропией, характеризующей только i-e состояние.
Поясним на примерах
. При бросании монеты выпадает орел или решка, это определенная информация о результатах бросания.
Для монеты число равновероятных возможностей N = 2. Вероятность выпадения орла (решки) равна 1/2.
При бросании кости получаем информацию о выпадении определенного количества очков (например, трех). В каком случае мы получаем больше информации?
Для кости число равновероятных возможностей N = 6. Вероятность выпадения трех очков кости равна 1/6. Энтропия равна 2.58. Реализация менее вероятного события дает больше информации. Чем больше неопределенность до получения сообщения о событии (бросание монеты, кости), тем большее количество информации поступает при получении сообщения.
Такой подход к количественному выражению информации далеко не универсален, т. к. принятые единицы не учитывают таких важных свойств информации, как ее ценность и смысл. Абстрагирование от конкретных свойств информации (смысл, ценность ее) о реальных объектах, как в дальнейшем выяснилось, позволило выявить общие закономерности информации. Предложенные Шенноном для измерения количества информации единицы (биты) пригодны для оценки любых сообщений (рождение сына, результаты спортивного матча и т. д.). В дальнейшем делались попытки найти такие меры количества информации, которые учитывали бы ее ценность и смысл. Однако тут же терялась универсальность: для разных процессов различны критерии ценности и смысла. Кроме того, определения смысла и ценности информации субъективны, а предложенная Шенноном мера информации объективна. Например, запах несет огромное количество информации для животного, но неуловим для человека. Ухо человека не воспринимает ультразвуковые сигналы, но они несут много сведений для дельфина и т. д. Поэтому предложенная Шенноном мера информации пригодна для исследования всех видов информационных процессов, независимо от "вкусов" потребителя информации.
Измерение информации
Из курса физики вы знаете, что прежде, чем измерять значение какой-либо физической величины, надо ввести единицу измерения. У информации тоже есть такая единица - бит, но смысл ее различен при разных подходах к определению понятия “информация”.
Существует несколько разных подходов к проблеме измерения информации.
«Информация есть форма жизни», - писал американский поэт и эссеист Джон Перри Барлоу. Действительно, мы постоянно сталкиваемся со словом «информация» - ее получают, передают и сохраняют. Узнать прогноз погоды или результат футбольного матча, содержание фильма или книги, поговорить по телефону - всегда ясно, с каким видом информации мы имеем дело. Но что такое сама информация, а главное - как ее можно измерить, никто обычно не задумывается. А между тем, информация и способы ее передачи - важная вещь, которая во многом определяет нашу жизнь, неотъемлемой частью которой стали информационные технологии. Научный редактор издания «Лаба.Медиа» Владимир Губайловский объясняет, что такое информация, как ее измерять, и почему самое сложное - это передача информации без искажений.
Пространство случайных событий
В 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.
Это не случайное совпадение. Шеннон так подобрал энтропию (меру неопределенности в пространстве событий), чтобы выполнялись три условия:
- 1Энтропия достоверного события, вероятность которого 1, равна 0.
- Энтропия двух независимых событий равна сумме энтропий этих событий.
- Энтропия максимальна, если все события равновероятны.
Все эти требования вполне соответствуют нашим представлениям о неопределенности пространства событий. Если событие одно (первый пример) - никакой неопределенности нет. Если события независимы - неопределенность суммы равна сумме неопределенностей - они просто складываются (пример с бросанием двух монет). И, наконец, если все события равновероятны, то степень неопределенности системы максимальна. Как в случае с бросанием двух монет, все четыре события равновероятны и энтропия равна 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. В результате не более чем одной ошибки (ошибки мы выделили) оно может превратиться в одно из слов:
1) 111000, 0 11000, 10 1000, 110 000, 1111 00, 11101 0, 111001 .
При передаче слова 001110 может получиться любое из слов:
2) 001110, 1 01110, 01 1110, 000 110, 0010 10, 00110 0, 001111 .
Наконец, для 100011 у нас может получиться на приеме:
3) 100011, 0 00011, 11 0011, 101 011, 1001 11, 10000 1, 100010 .
Заметим, что все три списка попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка 1, получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка 2 - слово 001110, а из списка 3 - слово 100011. В этом случае говорят, что наш код исправил одну ошибку.
Исправление произошло за счет двух факторов. Во-первых, получатель знает весь «словарь» , то есть пространство событий получателя сообщения совпадает с пространством того, кто сообщение передал. Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.
Во-вторых, слова в словаре были подобраны особенным образом. Даже при возникновении ошибки получатель не мог перепутать одно слово с другим. Например, если словарь состоит из слов «дочка», «точка», «кочка», и при передаче получалось «вочка», то получатель, зная, что такого слова не бывает, исправить ошибку не смог бы - любое из трех слов может оказаться правильным. Если же в словарь входят «точка», «галка», «ветка» и нам известно, что допускается не больше одной ошибки, то «вочка» это заведомо «точка», а не «галка». В кодах, исправляющих ошибки, слова выбираются именно так, чтобы они были «узнаваемы» даже после ошибки. Разница лишь в том, что в кодовом «алфавите» всего две буквы - ноль и единица.
Избыточность такого кодирования очень велика, а количество слов, которые мы можем таким образом передать, сравнительно невелико. Нам ведь надо исключать из словаря любое слово, которое может при ошибке совпасть с целым списком, соответствующим передаваемым словам (например, в словаре не может быть слов «дочка» и «точка»). Но точная передача сообщения настолько важна, что на исследование помехоустойчивых кодов тратятся большие силы.
Сенсация
Понятия энтропии (или неопределенности и непредсказуемости) сообщения и избыточности (или предопределенности и предсказуемости) очень естественно соответствуют нашим интуитивным представлениям о мере информации. Чем более непредсказуемо сообщение (тем больше его энтропия, потому что меньше вероятность), - тем больше информации оно несет. Сенсация (например, встреча с крокодилом на Тверской) - редкое событие, его предсказуемость очень мала, и потому велика информационная стоимость. Часто информацией называют новости - сообщения о только что произошедших событиях, о которых мы еще ничего не знаем. Но если о случившемся нам расскажут второй и третий раз примерно теми же словами, избыточность сообщения будет велика, его непредсказуемость упадет до нуля, и мы просто не станем слушать, отмахиваясь от говорящего со словами «Знаю, знаю». Поэтому СМИ так стараются быть первыми. Вот это соответствие интуитивному чувству новизны, которое рождает действительно неожиданное известие, и сыграло главную роль в том, что статья Шеннона, совершенно не рассчитанная на массового читателя, стала сенсацией, которую подхватила пресса, которую приняли как универсальный ключ к познанию природы ученые самых разных специальностей - от лингвистов и литературоведов до биологов.
Но понятие информации по Шеннону - строгая математическая теория , и ее применение за пределами теории связи очень ненадежно. Зато в самой теории связи она играет центральную роль.
Семантическая информация
Шеннон, введя понятие энтропии как меры информации, получил возможность работать с информацией - в первую очередь, ее измерять и оценивать такие характеристики, как пропускная способность каналов или оптимальность кодирования. Но главным допущением, которое позволило Шеннону успешно оперировать с информацией, было предположение, что порождение информации - это случайный процесс, который можно успешно описать в терминах теории вероятности. Если процесс неслучайный, то есть он подчиняется закономерностям (к тому же не всегда ясным, как это происходит в естественном языке), то к нему рассуждения Шеннона неприменимы. Все, что говорит Шеннон, никак не связано с осмысленностью информации.
Пока мы говорим о символах (или буквах алфавита), мы вполне можем рассуждать в терминах случайных событий, но как только мы перейдем к словам языка, ситуация резко изменится. Речь - это процесс, особым образом организованный, и здесь структура сообщения не менее важна, чем символы, которыми она передается.
Еще недавно казалось, что мы ничего не можем сделать, чтобы хоть как-то приблизиться к измерению осмысленности текста, но в последние годы ситуация начала меняться. И связано это прежде всего с применением искусственных нейронных сетей к задачам машинного перевода, автоматического реферирования текстов, извлечению информации из текстов, генерированию отчетов на естественном языке. Во всех этих задачах происходит преобразование, кодирование и декодирование осмысленной информации, заключенной в естественном языке. И постепенно складывается представление об информационных потерях при таких преобразованиях, а значит - о мере осмысленной информации. Но на сегодняшний день той четкости и точности, которую имеет шенноновская теория информации, в этих трудных задачах еще нет.
что означает термин "энтропия" с точки зрения теории информации? и получил лучший ответ
Ответ от MarZ[гуру]
Информационная энтропия, как определено Шенноном и добавлено другими физиками близко, соотносится с понятием термодинамической энтропии. Это величина, обозначающая несокращаемое (несжимаемое) количество информации, содержимое в данной системе (обычно, - в принимаемом сигнале).
В теории информации
Энтропия в статистической механике имеет тесную связь с информационной энтропией - мерой неопределённости сообщений, которые описываются множеством символов x_1,ldots,x_n и вероятностей p_1,ldots,p_n появления этих символов в сообщении. В теории информации энтропией сообщения с дискретным распределением вероятностей называют величину
Sn = − ∑PkInPk,
k
где
∑Pk = 1.
k
Информационная энтропия равна нулю, когда какая-либо вероятность равна единице (а остальные - нулю), т. е. когда информация полностью предсказуема и не несёт ничего нового для приёмника. Энтропия принимает наибольшее значение для равновероятного распределения, когда все вероятности pk одинаковы; т. е. когда неопределённость, разрешаемая сообщением максимальна. Информационная энтропия также обладает всеми теми математическими свойствами, которыми обладает термодинамическая энтропия. Например, она аддитивна: энтропия нескольких сообщений равна сумме энтропий отдельных сообщений.
Источник: http://www.wikiznanie.ru/ru-wz/index.php/Рнтропия
Ответ от Александр Зонов
[гуру]
Так же, как и в термодинамике энтропия - мера беспорядочности системы.
Ответ от .
[активный]
Энтропи́я (информационная) - мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.
Ответ от 3 ответа
[гуру]
Привет! Вот подборка тем с ответами на Ваш вопрос: что означает термин "энтропия" с точки зрения теории информации?
Понятие Энтропи́и
впервые введено в 1865 Р. Клаузиусом в термодинамике для определения меры необратимого рассеяния энергии. Энтропия применяется в разных отраслях науки, в том числе и в теории информации как мера неопределенности какого-либо опыта, испытания, который может иметь разные исходы. Эти определения энтропии имеют глубокую внутреннюю связь. Так на основе представлений об информации можно вывести все важнейшие положения статистической физики. [БЭС. Физика. М: Большая российская энциклопедия, 1998].
Эта величина также называется средней энтропией
сообщения. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины .
Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотой, поэтому неопределённость появления для некоторых букв меньше, чем для других.
В 1948 году, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки теории информации, которая использует понятие вероятности. Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.
В случае равновероятных событий (частный случай), когда все варианты равновероятны, остается зависимость только от количества рассматриваемых вариантов и формула Шеннона значительно упрощается и совпадает с формулой Хартли, которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, как один из научных подходов к оценке сообщений:
, где I – количество передаваемой информации, p – вероятность события, N – возможное количество различных (равновероятных) сообщений.Задание 1. На равновероятные события.
В колоде 36 карт. Какое количество информации содержится в сообщении, что из колоды взята карта с портретом “туз”; “туз пик”?
Вероятность p1 = 4/36 = 1/9, а p2 = 1/36. Используя формулу Хартли имеем:
Ответ: 3.17; 5.17 бит
Заметим (из второго результата), что для кодирования всех карт, необходимо 6 бит.
Из результатов также ясно, что чем меньше вероятность события, тем больше информации оно содержит. (Данное свойство называется монотонностью
)
Задание 2. На неравновероятные события
В колоде 36 карт. Из них 12 карт с “портретами”. Поочередно из колоды достается и показывается одна из карт для определения изображен ли на ней портрет. Карта возвращается в колоду. Определить количество информации, передаваемой каждый раз, при показе одной карты.
