Тема 2.1.1. Теорема отсчетов Котельникова и Найквиста — Шеннона

Базисным понятием всей теории информации является понятие энтропии. Энтропия – мера неопределенности некоторой ситуации. Можно также назвать ее мерой рассеяния и в этом смысле она подобна дисперсии. Но если дисперсия является адекватной мерой рассеяния лишь для специальных распределений вероятностей случайных величин (а именно – для двухмоментных распределений, в частности, для гауссова распределения), то энтропия не зависит от типа распределения. С другой стороны, энтропия вводится так, чтобы обладать, кроме универсальности и другими желательными свойствами. Так, если некий опыт имеет n равновероятных исходов, а другой опыт m равновероятных исходов, то составной опыт имеет nm таких исходов. Если мы вводим меру неопределенности f, то естественно потребовать, чтобы она была такова, чтобы во-первых, неопределенность росла с ростом числа возможных исходов, а во-вторых, неопределенность составного опыта была равна просто сумме неопределенности отдельных опытов, иначе говоря, мера неопределенности была аддитивной: f(nm)=f(n)+f(m). Именно такая удобная мера неопределенности была введена К. Шенноном:

H(X)= — P (X_i) log P (X_i),

где Х – дискретная случайная величина с диапазоном изменчивости N, P(X_i) – вероятность i – го уровня X.

В дальнейшем мы будем рассматривать Х как некоторую физическую величину, меняющуюся во времени или пространстве. Временной или пространственный ряд X_j (j – индекс временной или пространственной координаты r) будем называть, как это принято в ряде естественных наук, “вариацией”. В самой теории информации такое пространственно-временное упорядочение совершенно не обязательно, но, во-первых, анализ именно таких вариаций составляет суть всех естественных наук, во-вторых, это с первых шагов позволяет лучше ощутить смысл новых понятий. Заметим также, что если даже пространственная или временная упорядоченность величины Х в явном виде отсутствует, она неизбежно существует неявно. Например, положим, что j – номер различимой частицы, а Х_j – ее импульс. Х – неупорядоченная случайная величина (ее номер j присваивается произвольно), но все эти частицы неизбежно разнесены в пространстве (раз мы можем их различить) и, при необходимости, мы можем их соединить некоторой (ломаной) осью и восстановить упорядоченность. Но для понимания проще представлять Х как сигнал, который может быть записан самописцем, как рельеф местности вдоль некоторого профиля, как пространственное распределение плотности энергии поля и т.п.

Таким образом, чтобы рассчитать H(X), берется запись вариации X_j , разность между максимальным и минимальными значениями Х_j разбивается на N квантов (обычно равных разрешающей способности прибора) и подсчитывается число m_i заполнения каждого i -го уровня (число благоприятных случаев). Общее число случаев M – это число пространственных или временных ячеек, опять-таки обычно определяемых разрешением прибора. В результате мы получаем распределение вероятностей P(X_i)=m_i/M, которое подставляем в формулу H(x).

В теории информации в формуле для энтропии обычно используют двоичные логарифмы, тогда (энтропия и информация) измеряется в битах. Это удобно тем, что выбор между двумя равновероятными уровнями X_i (как в двоичном) сигнале характеризуется неопределенностью 1 бит. В популярной литературе иногда пользуются десятичными логарифмами и единицей энтропии является дит. В физике удобнее пользоваться натуральными логарифмами и единицей энтропии является нат (поскольку в дальнейшем наш подход существенно физический, мы также используем натуральные логарифмы). Выбор основания – лишь вопрос масштаба, в любом случае энтропия безразмерна. Возможная величина энтропии заключена в пределах:

0£ H(X)£ logN.

Нижняя грань соответствует вырожденному распределению. Неопределенность величинs Х отсутствует. В вариационном ряду это соответствует X_j=const. Верхняя грань соответствует равномерному распределению. Все N значений X_i встречаются с равной вероятностью. В вариационном ряду это может соответствовать, в частности, линейному тренду X_j=ar_j.

Если две случайные величины X и Y, каким-то образом связанные друг с другом (например на входе и выходе какой-то системы), то знание одной из них, очевидно уменьшает неопределенность значений другой. Остающаяся неопределенность оценивается условной энтропией. Так, условная энтропия Х при условии знания Y определяется как:

H(X|Y)=

где – условные вероятности (вероятность i -го значения X при условии Y=Y_k), диапазоны изменчивости X и Y (соответственно N и K) не обязательно совпадают.

Чтобы рассчитать H(X|Y), рассчитывают К энтропий Х, соответствующих фиксированному Y_k и затем суммируют результаты с весами P(Y_k). Очевидно, условная энтропия меньше безусловной, точнее:

0£ H(X|Y)£ H(X).

Нижняя грань соответствует однозначной зависимости Х от Y, верхняя – полной независимости.

Информация определяется разностью между безусловной и условной энтропиями. Это уменьшение неопределенности “знания чего-то за счет того, что известно что-то”. При этом замечательно, что информация I симметрична, т.е. I_YX=I_XY:

I_XY=H(X)-H(X|Y)=H(Y)-H(Y|X)= I_YX.

Информация всегда неотрицательна; она равна нулю, когда Х и Y независимы; информация максимальна и равна безусловной энтропии, когда между Х и Y имеется однозначная зависимость. Таким образом, безусловная энтропия – это максимальная информация, потенциально содержащаяся в системе (вариационном ряде). Заметим, что мы сказали однозначная, но не взаимно-однозначная зависимость. Это значит, что несмотря на симметрию, верхние грани I_XY и I_YX отличаются:

0£ I_XY£ H(X), 0£ I_YX£ H(Y).

Как это может быть? Положим, XÞ Y (но обратное неверно). Тогда H(Y|X)= 0, H(X|Y)¹ 0, I_YX=H(Y)= I_XY. Очевидно, это возможно только когда H(X)> H(Y).

Информация – это всего лишь характеристика степени зависимости некоторых переменных, ничего более загадочного в ней нет. Зато это предельно общая характеристика. Ее можно сравнить с корреляцией, но если корреляция характеризует лишь линейную связь переменных, информация характеризует любую связь. Тип связи может быть совершенно любым и, более того, неизвестным нам. Это не помешает рассчитать информацию, количественно сравнивать между собой разнотипные зависимости и т.д. Платой за общность является лишь невозможность, зная количество информации написать уравнение связи переменных (в отличие от того, как корреляция позволяет легко переходить к регрессии). Можно определить и совместную энтропию Х и Y по их двумерному распределению. При этом:

H(XY)=H(X)+H(Y|X)=H(Y)+H(X|Y).

Иначе говоря, энтропия субаддитивна, аддитивность (H(XY)= H(X)+H(Y)) достигается только при полной независимости X и Y.

С помощью совместной энтропии можно написать выражение для информации I_XY= I_YX=I в симметричном виде:

I=H(X)+H(Y)-H(XY).

Интуитивно ясно, что включение в рассмотрение третьей переменной может лишь увеличить информацию. Это действительно так:

I_(YX)Z³ I_XZ, I_(XY)Z³ I_YZ.

Симметрия случая трех переменного описывается формулой тройной информации:

I_(XY)Z+I_XY=I_(YZ)X+I_YZ=I_(XZ)Y+I_XZ.

Важную роль в теории информации играет представление о максимальной скорости передачи сообщения. При этом имеется в виду скорость при которой еще возможен безошибочное получение информации на приемном конце канала связи. “Канал связи” при создании теории информации рассматривался действительно как технический канал (и задача состояла в изучении его потенциальных возможностей, тех теоретических пределов его использования, которые нельзя превзойти в принципе). В действительности “каналом связи” является любая естественная или искусственная система в которой можно выделить начальное состояние (входной сигнал) X и конечное (выходной сигнал) Y. Законы передачи информации по каналу связи универсальны, поэтому, например, любое физическое взаимодействие в реальных системах подчиняется не только соответствующему физическому закону, но и им также. Несмотря на сложившуюся терминологию, лучше говорить не о скорости передачи, а о скорости приема информации, которая ограничена неравенством

где C – пропускная способность канала (иногда ее называют также информационной емкостью, иногда емкостью называется произведение dt· C, где dt – длительность элементарного сигнала).При отсутствии шумов:

при наличии шумов:

максимум отыскивается при возможном варьировании входного сигнала X. Таким образом, в общем случае:

Чем больше шумов или, на физическом языке, чем более открыта система, тем медленнее выход (конечное состояние) может воспроизвести изменения входа (начального состояния). Важную роль играет также понятие избыточности R:

Нижняя грань достигается при равномерном распределении, верхняя – при вырожденном (X_j=const). Чем больше избыточность поля, тем, очевидно, меньше скорость передачи информации. Но тем меньше вероятность ошибки при приеме! Например, чрезмерно избыточный текст скучно читать (избыток “воды”). Но малоизбыточный читать трудно, он требует крайнего внимания, в пределе (недостижимом в обычном языке) ни одну утерянную букву невозможно восстановить по смыслу. Таким образом, избыточный сигнал содержит внутренние корреляции, которые используются при восстановлении (декодировании) сообщения. Увеличивая избыточность и, соответственно, уменьшая скорость приема-передачи можно воспроизвести на выходе информацию, поданную на вход при любом уровне шумов.

Канал, для которого H(Y|X)= 0 называют детерминированным, для которого H(X|Y)= 0 – бесшумовым. Последний термин неудачен, поскольку зашумленной может быть не только величина X, но и Y. Канал, для которого H(Y|X)=H(X|Y)= 0, называют идеальным. В идеальном канале X и Y являются взаимно – однозначными функциями. Среди нескольких теорем Шеннона особую роль в естественно- научных приложениях играет 7-я теорема, которая гласит, что в замкнутой системе энтропия при любом преобразовании не увеличивается:

H(Y)£ H(X).

На менее строгом языке это можно перефразировать так, что информацию на пути от входа к выходу можно только потерять, но не увеличить. Интуитивно это очевидно. Но если Х – начальное состояние замкнутой физической системы, а Y – конечное, то эта теорема означает необратимое уменьшение энтропии, что диаметрально противоположно общеизвестной формулировке второго начала термодинамики. Мы рассмотрим этот вопрос в п.4.

Следует отметить одну исторически обусловленную особенность приложений теории информации. С момента зарождения [11] и после наиболее мощного импульса в ее развитии приданного работами К. Шеннона [2], несмотря на общность математического аппарата и быстро замеченную ассоциированность с термодинамикой [1, 2], теория информации развивалась как раздел теории связи, Приложения быстро вышли за пределы теории связи как таковой [12]. Но и в расширенных приложениях от теории связи в неявном виде унаследовано представление об одушевленном потребителе информации. Более того, на начальном этапе авторы специально приносили своего рода извинения за то, что термин “информация” в теории имеет более широкий смысл, чем его бытовое употребление, подразумевающее некоторую ценность для потребителя. В дальнейшем оказалось, что и понятие ценности информации может быть формализовано [9].

Существует однако более общая концепция приложения понятия информации как универсальной меры физического взаимодействия. Этому посвящен ряд работ с достаточно специальным подходом, например, [13-17], наиболее общая трактовка дана Х. Хармутом [18]. Наша трактовка опирается именно на эту концепцию. Но прежде чем применить ее, необходимо подробно разобрать такое базисное понятие как энтропия, поскольку, с одной стороны возможны различные формулировки, а с другой, наоборот – одинаковые математические формы имеют разный смысл (и приводят к различным результатам) взависимости от наполнения.

1. Различные формы энтропии

Энтропия (S или H) независимо вводилась Клазиусом:

(1)

где Q – энергия, Т – температура; Л. Больцманом:

S = H = ln W, (2)

где W – вероятность состояния; К. Шенноном:

(3)

где Р – вероятность i -го уровня переменной (сигнала) Х с диапазоном изменчивости N; фон Нейманом:

H=-trr lnr, (4)

где плотность r определяется через волновую функцию y: r= |y > < y |.

Оказалось, что (1) и (3) являются следствиями (1) [1, 2, 10], хотя для их применения, соответственно в термодинамике и в теории информации, это не имеет большого значения. (4) является квантовомеханическим обобщением (3), при этом (4) (3) для чистых состояний. Классический уровень предоставляет слишком широкие возможности для обобщений, чтобы затрагивать в данном обзоре и квантовый, поэтому мы не будем переходить на последний и лишь слегка коснемся удивительных особенностей квантовой энтропии в Заключении.

Можно заметить, что в отличие от (2) – (4) согласно определению (1) энтропии размерна (Дж/К). Здесь мы просто сохранили оригинальные определения. Безразмерная энтропия, конечно удобнее и, чтобы привести (1) к безразмерному виду, надо просто разделить правую часть на постоянную Больцмана k. Эта постоянная не имеет большего смысла, чем коэффициент связи между единицами измерения энергии и температуры. Если бы мы стали измерять температуру в джоулях (что неудобно, но законно), то надобность в этой константе отпала бы. Однако здесь есть чисто количественный нюанс. Величина k весьма мала: 1, 38· 10^-23 Дж/К. Разделив (1) на k мы сразу получаем представление о том, насколько велики изменения энтропии в самых заурядных термодинамических процессах по сравнению с теми, которыми мы оперируем в информатике. Это дает представление о том, насколько велика недоступная на макроуровне информация о микросостоянии вещества. Определение (1) – практически самое важное для теплофизике [1], но, пользуясь им, трудно увидеть универсальность понятия энтропии. Принципиальным недостатком (1) является также то, что это формула верна только для квазиравновесных состояний. Поэтому мы сосредоточимся на определениях (2) и (3).

Вероятность состояния W определяется как отношение числа микросостояний K, благоприятных данному макросостоянию, к полному числу возможных микросостояний L:

W = K/L. (5)

Пусть рассматриваются пространственные или временные вариации некоторого параметра Х (в дискретном виде). Тогда К – это число вариаций, удовлетворяющих данному распределению вероятностей P (X_i), L – полное число возможных вариаций.

Пусть М – число членов статистического ансамбля (в нашем контексте это объем, а для одномерного случая – длина ряда, выраженная числом искусственных квантов пространства, т.е. отсчетов), m_i – число заполнения i -го уровня (т.е. P(X_i)=m_i/M). Тогда

(6)

Число L однозначно определить обычно сложнее. Поэтому вместо W пользуются К (так называемая абсолютная или термодинамическая вероятность) и определяют не нормированную энтропию (2), а абсолютную Н_а:

(7)

Можно показать[10], что энтропия Клазиуса (1) является частным случаем (7). Нормируя на число членов ансамбля (длину ряда), получаем абсолютную удельную энтропию

(8)

0£ H_ay£ ln N, (9)

совпадающую с (3), которая была введена К.Шенноном просто как удобный функционал и была названа им “энтропия” именно из-за обнаруженного родства с термодинамической энтропией. Верхняя грань достигается при равномерном распределении, нижняя – при вырожденном (Х не зависит от координаты r: X_j = const).

Микросостояния в нашем случае различимы, следовательно ансамбль удовлетворяет статистике Максвелла-Больцмана. Роль различимой частицы в геофизической интерпретации играет квант пространства (или времени). Для этой статистики в термодинамике число L определяется как [10]:

L₁=N^M (10)

и соответствует в теории информации числу возможных сообщений [8]. На нашем языке это можно перефразировать как число различимых вариаций в диапазоне N при объеме (или длине ряда) М. Тогда согласно (5) нормированная удельная энтропия равна:

(11)

Вполне естественное для термодинамики (М – число частиц в фиксированном объеме N) и теории технического канала связи (М – длина сообщения, N – фиксированный диапазон уровней) определение l₁ трудно считать адекватным в контексте естественных процессов. Здесь М может быть естественным образом ограничена, и даже искусственное ограничение не вызывает особых затруднений (подобно спектральному анализу и вообще выборочной статистике), но диапазон N трудно считать фиксированным, в особенности для естественных полей. Так при гауссовом распределении

В статистике Бозе-Эйнштейна принято другое определение L [10], которое в нашем контексте может быть интерпретировано как число различимых вариаций с данным интегралом (точнее, суммой) U при объеме М:

(12)

где U= причем все X_j³ 0 (практически это легко достигается рассмотрением вместо уровней Х “энергетических” уровней Х ² ). Тогда

(13)

При M> > 1, U> > 1 (естественное условие применения любой статистики):

(13`)

где u=U/M.

Таким образом, L – это, в итоге, не вообще полное число различимых вариаций (которое бесконечно), а полное число при некоторых ограничениях – при фиксированном диапазоне N или при фиксированном интеграле U, который может в ряде случаев интерпретироваться как энергия вариации. Возможны и другие варианты ограничений.

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

Так из (9) и (11) следует

- ln N£ H_{1y £} 0.

Но для геофизических вариационных рядов N определяется естественно только из самой реализации. Нижняя грань соответствует X_j= const, т.е. N = 1, и оба противоположных случая равномерного и вырожденного распределений смыкаются.

Нижняя грань H_2y для вырожденного распределения (Х j = const) определяется из (13`) как

inf H_2y = -2 ln 2.

Заметим, что это выражение совпадает с классическим пределом энтропии квантовомеханического ансамбля, выведенным из других соображений [15].

Верхняя грань H_2y соответствует, однако, не равномерному распределению, а определяется из уравнения

Единственное решение этого уравнения U =1 соответствует импульсной функции в вариационном ряду X_j. Для геофизического вариационного ряда естественная длина для финитной функции X_j в данном случае получается М =1. Это вырожденный случай для самого функционала энтропии. Таким образом, формальное соотношение

-2ln2 £ H_2y £ 0

не имеет такого же ясного смысла как (9).

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