Как найти энтропию информации - Сайт, где вы сможете решить свои вопросы

Теория информации

Энтропия Дифференциальная энтропия Условная энтропия Совместная энтропия Взаимная информация Условная взаимная информация Относительная энтропия Энтропийная скорость
Свойство асимптотической равнораспределенности Теория частотных искажений
Теорема Шеннона об источнике шифрования Пропускная способность Теоремы Шеннона для канала с шумами Теорема Шеннона — Хартли

Информацио́нная энтропи́я — мера неопределённости некоторой системы (в статистической физике или теории информации), в частности, непредсказуемость появления какого-либо символа первичного алфавита. В последнем случае при отсутствии информационных потерь энтропия численно равна количеству информации на символ передаваемого сообщения.

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотностью, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии -го порядка, см. ниже) встречаются очень редко, то неопределённость уменьшается еще сильнее.

Формальные определения[править | править код]

Информационная двоичная энтропия, при отсутствии информационных потерь, рассчитывается по формуле Хартли:

${displaystyle I=log _{2}N}$ ,

где — мощность алфавита, — количество информации в каждом символе сообщения. Для случайной величины , принимающей независимых случайных значений $x_{i}$ с вероятностями $p_{i}$ (), формула Хартли переходит в формулу Шеннона:

${displaystyle H(x)=-sum _{i=1}^{n}p_{i}log _{2}p_{i}.}$

Здесь ${displaystyle (-log_{2}p_{i})}$ означает измеряемое в битах количество информации, содержащейся в том событии, что случайная величина приняла значение $x_{i}$ (для предложений на русском языке – количество информации, содержащейся в конкретной букве, имеющей номер в русском алфавите, ),

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

Эта величина также называется средней энтропией сообщения и означает измеряемое в битах среднее количество информации на символ передаваемого сообщения. Величина ${displaystyle H_{i}=-log _{2}{p_{i}}}$ называется частной энтропией, характеризующей только -e состояние.

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

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

Определение по Шеннону[править | править код]

Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

мера должна быть непрерывной; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
в случае, когда все варианты (буквы в приведённом примере) равновероятны, увеличение количества вариантов (букв) должно всегда увеличивать значение функции;
должна быть возможность сделать выбор (в нашем примере — букв) в два шага, в которых значение функции конечного результата должно являться суммой функций промежуточных результатов.^{[прояснить]}

Поэтому функция энтропии должна удовлетворять условиям

$H(p_{1},;ldots ,;p_{n})$ определена и непрерывна для всех ${displaystyle p_{1},dotsc ,p_{n}}$ , где $p_{i}in [0,;1]$ для всех и ${displaystyle p_{1}+dotsb +p_{n}=1}$ . (Эта функция зависит только от распределения вероятностей, но не от алфавита.)
Для целых положительных , должно выполняться следующее неравенство:

$Hunderbrace {left({frac {1}{n}},;ldots ,;{frac {1}{n}}right)}_{n}<Hunderbrace {left({frac {1}{n+1}},;ldots ,;{frac {1}{n+1}}right)}_{{n+1}}.$
Для целых положительных $b_{i}$ , где $b_{1}+ldots +b_{k}=n$ , должно выполняться равенство

$Hunderbrace {left({frac {1}{n}},;ldots ,;{frac {1}{n}}right)}_{n}=Hleft({frac {b_{1}}{n}},;ldots ,;{frac {b_{k}}{n}}right)+sum _{{i=1}}^{k}{frac {b_{i}}{n}}Hunderbrace {left({frac {1}{b_{i}}},;ldots ,;{frac {1}{b_{i}}}right)}_{{b_{i}}}.$

Шеннон показал,^[2] что единственная функция, удовлетворяющая этим требованиям, имеет вид

$-Ksum _{{i=1}}^{n}p(i)log _{2}p(i),$

где — положительная константа (и в действительности нужна только для выбора единицы измерения энтропии; изменение этой константы равносильно изменению основания логарифма).

Шеннон определил, что измерение энтропии ( $H=-p_{1}log _{2}p_{1}-ldots -p_{n}log _{2}p_{n}$ ), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надёжной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидание «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т. д. (см. цепи Маркова).

Определение энтропии Шеннона связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Определение с помощью собственной информации[править | править код]

Также можно определить энтропию случайной величины, предварительно введя понятие распределения случайной величины , имеющей конечное число значений:^[3]

$P_{X}(x_{i})=p_{i},quad p_{i}geqslant 0,;i=1,;2,;ldots ,;n$

$sum _{{i=1}}^{n}p_{i}=1$

и собственной информации:

$I(X)=-log P_{X}(X).$

Тогда энтропия определяется как:

${displaystyle H(X)=mathbb {E} (I(X))=-sum _{i=1}^{n}p(i)log p(i).}$

Единицы измерения информационной энтропии[править | править код]

От основания логарифма зависит единица измерения количества информации и энтропии: бит, нат, трит или хартли.

Свойства[править | править код]

Энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию:

$-2left({frac {1}{2}}log _{2}{frac {1}{2}}right)=-log _{2}{frac {1}{2}}=log _{2}2=1$

бит на одно кидание (при условии его независимости), а количество возможных состояний равно: $2^{1}=2$

возможных состояния (значения) («орёл» и «решка»).

У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: $-sum _{{i=1}}^{infty }log _{2}1=0$ , а количество возможных состояний равно: $2^{0}=1$ возможное состояние (значение) («А») и от основания логарифма не зависит.
Это тоже информация, которую тоже надо учитывать. Примером запоминающих устройств, в которых используются разряды с энтропией, равной нулю, но с количеством информации, равным одному возможному состоянию, то есть не равным нулю, являются разряды данных записанных в ПЗУ, в которых каждый разряд имеет только одно возможное состояние.

Так, например, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для их (данных) зашифровки без потери информации, при оптимальном кодировании.

Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию или имеют идентичные секции независимо от информации в структуре данных.
Количество энтропии не всегда выражается целым числом битов.

Математические свойства[править | править код]

Неотрицательность: .
Ограниченность: ${displaystyle H(X)=-mathop {mathbb {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 fleft(sum _{i=1}^{n}p_{i}g_{i}right)=log _{2}n}$ , что вытекает из неравенства Йенсена для вогнутой функции $f(g_{i})=log _{2}g_{i}$ и $g_{i}={frac {1}{p_{i}}}$ . Если все элементов из равновероятны, $H(X)=log _{2}n$ .
Если независимы, то .
Энтропия — выпуклая вверх функция распределения вероятностей элементов.
Если имеют одинаковое распределение вероятностей элементов, то .

Эффективность[править | править код]

Алфавит может иметь вероятностное распределение, далекое от равномерного. Если исходный алфавит содержит символов, тогда его можно сравнить с «оптимизированным алфавитом», вероятностное распределение которого — равномерное. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах. Эффективность исходного алфавита с символами может быть также определена как его -арная энтропия.

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля — Зива — Велча или арифметического кодирования.

Вариации и обобщения[править | править код]

b-арная энтропия[править | править код]

В общем случае b-арная энтропия (где b равно 2, 3, …) источника с исходным алфавитом $S={a_{1},;ldots ,;a_{n}}$ и дискретным распределением вероятности $P={p_{1},;ldots ,;p_{n}},$ где $p_{i}$ является вероятностью $a_{i}$ ( $p_{i}=p(a_{i})$ ), определяется формулой:

$H_{b}({mathcal {S}})=-sum _{{i=1}}^{n}p_{i}log _{b}p_{i}.$

В частности, при b=2 , мы получаем обычную двоичную энтропию, измеряемую в битах. При b=3 , мы получаем тринарную энтропию, измеряемую в тритах (один трит имеет источник информации с тремя равновероятными состояниями). При b=e мы получаем информацию, измеряемую в натах.

Условная энтропия[править | править код]

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а, следовательно, и энтропия) меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (то есть вероятности двухбуквенных сочетаний):

$H_{1}({mathcal {S}})=-sum _{i}p_{i}sum _{j}p_{i}(j)log _{2}p_{i}(j),$

где — это состояние, зависящее от предшествующего символа, и $p_{i}(j)$ — это вероятность при условии, что был предыдущим символом.

Например, для русского языка без буквы «ё» $H_{0}=5,;H_{1}=4{,}358,;H_{2}=3{,}52,;H_{3}=3{,}01$ ^[4].

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Для описания потерь со стороны источника (то есть известен посланный сигнал) рассматривают условную вероятность $p(b_{j}mid a_{i})$ получения приёмником символа $b_{j}$ при условии, что был отправлен символ $a_{i}$ . При этом канальная матрица имеет следующий вид:

	$b_{1}$	$b_{2}$	…	$b_{j}$	…	$b_{m}$
$a_{1}$	$p(b_{1}mid a_{1})$	$p(b_{2}mid a_{1})$	…	$p(b_{j}mid a_{1})$	…	$p(b_{m}mid a_{1})$
$a_{2}$	$p(b_{1}mid a_{2})$	$p(b_{2}mid a_{2})$	…	$p(b_{j}mid a_{2})$	…	$p(b_{m}mid a_{2})$
…	…	…	…	…	…	…
$a_{i}$	$p(b_{1}mid a_{i})$	$p(b_{2}mid a_{i})$	…	$p(b_{j}mid a_{i})$	…	$p(b_{m}mid a_{i})$
…	…	…	…	…	…	…
	$p(b_{1}mid a_{m})$	$p(b_{2}mid a_{m})$	…	$p(b_{j}mid a_{m})$	…	$p(b_{m}mid a_{m})$

Вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый сигнал $a_{i}$ , описываются через частную условную энтропию:

$H(Bmid a_{i})=-sum _{{j=1}}^{m}p(b_{j}mid a_{i})log _{2}p(b_{j}mid a_{i}).$

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

$H(Bmid A)=sum _{i}p(a_{i})H(Bmid a_{i}).$

означает энтропию со стороны источника, аналогично рассматривается — энтропия со стороны приёмника: вместо $p(b_{j}mid a_{i})$ всюду указывается $p(a_{i}mid b_{j})$ (суммируя элементы строки можно получить $p(a_{i})$ , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, то есть вероятность правильной передачи).

Взаимная энтропия[править | править код]

Взаимная энтропия или энтропия объединения предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается H(AB) , где характеризует передатчик, а — приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий $p(a_{i}b_{j})$ , и для полного описания характеристик канала требуется только одна матрица:

$p(a_{1}b_{1})$	$p(a_{1}b_{2})$	…	$p(a_{1}b_{j})$	…	$p(a_{1}b_{m})$
$p(a_{2}b_{1})$	$p(a_{2}b_{2})$	…	$p(a_{2}b_{j})$	…	$p(a_{2}b_{m})$
…	…	…	…	…	…
$p(a_{i}b_{1})$	$p(a_{i}b_{2})$	…	$p(a_{i}b_{j})$	…	$p(a_{i}b_{m})$
…	…	…	…	…	…
$p(a_{m}b_{1})$	$p(a_{m}b_{2})$	…	$p(a_{m}b_{j})$	…	$p(a_{m}b_{m})$

Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Сумма всех элементов столбца с номером даёт $p(b_{j})$ , сумма строки с номером есть $p(a_{i})$ , а сумма всех элементов матрицы равна 1. Совместная вероятность $p(a_{i}b_{j})$ событий $a_{i}$ и $b_{j}$ вычисляется как произведение исходной и условной вероятности:

$p(a_{i}b_{j})=p(a_{i})p(b_{j}mid a_{i})=p(b_{j})p(a_{i}mid b_{j}).$

Условные вероятности производятся по формуле Байеса. Таким образом, имеются все данные для вычисления энтропий источника и приёмника:

$H(A)=-sum _{i}left(sum _{j}p(a_{i}b_{j})log sum _{j}p(a_{i}b_{j})right),$

$H(B)=-sum _{j}left(sum _{i}p(a_{i}b_{j})log sum _{i}p(a_{i}b_{j})right).$

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

$H(AB)=-sum _{i}sum _{j}p(a_{i}b_{j})log p(a_{i}b_{j}).$

Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов: отправленного и полученного. Путём несложных преобразований также получаем

Взаимная энтропия обладает свойством информационной полноты — из неё можно получить все рассматриваемые величины.

История[править | править код]

В 1948 году, исследуя проблему рациональной передачи информации через зашумлённый коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки двух основных направлений: теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, и теории кодирования, в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных кодов.

Понятие энтропии как меры случайности введено Шенноном в его статье «Математическая теория связи» (англ. A Mathematical Theory of Communication), опубликованной в двух частях в Bell System Technical Journal в 1948 году.

Примечания[править | править код]

↑ Данное представление удобно для работы с информацией, представленной в двоичной форме; в общем случае основание логарифма может быть другим.
↑ Shannon, Claude E. A Mathematical Theory of Communication (неопр.) // Bell System Technical Journal (англ.) (рус.. — 1948. — July (т. 27, № 3). — С. 419. — doi:10.1002/j.1538-7305.1948.tb01338.x. Архивировано 1 августа 2016 года.
↑ Габидулин Э. М., Пилипчук Н. И. Лекции по теории информации — МФТИ, 2007. — С. 16. — 214 с. — ISBN 978-5-7417-0197-3
↑ Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. — № 1. — С. 68—69.

См. также[править | править код]

Дифференциальная энтропия (энтропия для непрерывного распределения)
Взаимная информация
Энтропийное кодирование
Цепь Маркова
Расстояние Кульбака — Лейблера

Ссылки[править | править код]

Shannon Claude E. A Mathematical Theory of Communication Архивная копия от 31 января 1998 на Wayback Machine (англ.)
Коротаев С. М. Энтропия и информация — универсальные естественнонаучные понятия.

Литература[править | править код]

Шеннон К. Работы по теории информации и кибернетике. — М.: Изд. иностр. лит., 2002.
Волькенштейн М. В. Энтропия и информация. — М.: Наука, 2006.
Цымбал В. П. Теория информации и кодирование. — К.: Вища Школа, 2003.
Martin, Nathaniel F.G. & England, James W. Mathematical Theory of Entropy. — Cambridge University Press, 2011. — ISBN 978-0-521-17738-2.
Шамбадаль П. Развитие и приложение понятия энтропии. — М.: Наука, 1967. — 280 с.
Мартин Н., Ингленд Дж. Математическая теория энтропии. — М.: Мир, 1988. — 350 с.
Хинчин А. Я. Понятие энтропии в теории вероятностей // Успехи математических наук. — Российская академия наук, 1953. — Т. 8, вып. 3(55). — С. 3—20.
Брюллюэн Л. Наука и теория информации. — М., 1960.
Винер Н. Кибернетика и общество. — М., 1958.
Винер Н. Кибернетика или управление и связь в животном и машине. — М., 1968.
Петрушенко Л. А. Самодвижение материи в свете кибернетики. — М., 1974.
Эшби У. Р. Введение в кибернетику. — М., 1965.
Яглом А. М., Яглом И. М. Вероятность и информация. — М., 1973.
Волькенштейн М. В. Энтропия и информация. — М.: Наука, 1986. — 192 с.
Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. — М.: ФМОП, МЦНМО, 2012. — 238 с. — ISBN 978-5-94057-920-5.

Источник

Энтропи́я (информационная) — мера хаотичности информации, неопределённость появления какого-либо символа первичного алфавита. При отсутствии информационных потерь численно равна количеству информации на символ передаваемого сообщения.

Так, возьмём, например, последовательность символов, составляющих какое-либо предложение на русском языке. Каждый символ появляется с разной частотой, следовательно, неопределённость появления для некоторых символов больше, чем для других. Если же учесть, что некоторые сочетания символов встречаются очень редко, то неопределённость ещё более уменьшается (в этом случае говорят об энтропии n-ого порядка, см. Условная энтропия).

Концепции информации и энтропии имеют глубокие связи друг с другом, но, несмотря на это, разработка теорий в статистической механике и теории информации заняла много лет, чтобы сделать их соответствующими друг другу. Ср. тж. Термодинамическая энтропия

Формальные определения

Информационная энтропия для независимых случайных событий x с n возможными состояниями (от 1 до n) рассчитывается по формуле:

${displaystyle H(x)=-sum _{i=1}^{n}p(i)log _{2}p(i)}$

Эта величина также называется средней энтропией сообщения. Величина ${displaystyle log _{2}{1 over p(i)}}$ называется частной энтропией, характеризующей только i-e состояние.

Таким образом, энтропия события x является суммой с противоположным знаком всех произведений относительных частот появления события i, умноженных на их же двоичные логарифмы (основание 2 выбрано только для удобства работы с информацией, представленной в двоичной форме). Это определение для дискретных случайных событий можно расширить для функции распределения вероятностей.

Шеннон вывел это определение энтропии из следующих предположений:

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

Шеннон показал, что любое определение энтропии, удовлетворяющее этим предположениям, должно быть в форме:

${displaystyle -Ksum _{i=1}^{n}p(i)log _{2}p(i)}$

где K — константа (и в действительности нужна только для выбора единиц измерения).

Шеннон определил, что измерение энтропии (H = − p₁ log₂ p₁ − … − p_n log₂ p_n), применяемое к источнику информации, может определить требования к минимальной пропускной способности канала, требуемой для надежной передачи информации в виде закодированных двоичных чисел. Для вывода формулы Шеннона необходимо вычислить математическое ожидания «количества информации», содержащегося в цифре из источника информации. Мера энтропии Шеннона выражает неуверенность реализации случайной переменной. Таким образом, энтропия является разницей между информацией, содержащейся в сообщении, и той частью информации, которая точно известна (или хорошо предсказуема) в сообщении. Примером этого является избыточность языка — имеются явные статистические закономерности в появлении букв, пар последовательных букв, троек и т.д. См. Цепи Маркова.

В общем случае b-арная энтропия (где b равно 2,3,… ) источника = (S,P) с исходным алфавитом S = {a₁, …, a_n} и дискретным распределением вероятности P = {p₁, …, p_n} где p_i является вероятностью a_i (p_i = p(a_i)) определяется формулой:

${displaystyle H_{b}({mathcal {S}})=-sum _{i=1}^{n}p_{i}log _{b}p_{i}}$

Определение энтропии Шеннона очень связано с понятием термодинамической энтропии. Больцман и Гиббс проделали большую работу по статистической термодинамике, которая способствовала принятию слова «энтропия» в информационную теорию. Существует связь между термодинамической и информационной энтропией. Например, демон Максвелла также противопоставляет термодинамическую энтропию информации, и получение какого-либо количества информации равно потерянной энтропии.

Условная энтропия

Если следование символов алфавита не независимо (например, во французском языке после буквы «q» почти всегда следует «u», а после слова «передовик» в советских газетах обычно следовало слово «производства» или «труда»), количество информации, которую несёт последовательность таких символов (а следовательно и энтропия) очевидно меньше. Для учёта таких фактов используется условная энтропия.

Условной энтропией первого порядка (аналогично для Марковской модели первого порядка) называется энтропия для алфавита, где известны вероятности появления одной буквы после другой (т.е. вероятности двухбуквенных сочетаний):

${displaystyle H_{1}({mathcal {S}})=-sum _{i}p_{i}sum _{j} p_{i}(j)log _{2}p_{i}(j)}$

где — это состояние, зависящее от предшествующего символа, и ${displaystyle displaystyle p_{i}(j)}$ — это вероятность , при условии, что был предыдущим символом.

Так, для русского алфавита без буквы «ё» ${displaystyle H_{0}=5, H_{1}=4,358, H_{2}=3,52, H_{3}=3,01}$ ^[1]

Через частную и общую условные энтропии полностью описываются информационные потери при передаче данных в канале с помехами. Для этого применяются т.н. канальные матрицы. Так, для описания потерь со стороны источника (т.е. известен посланный сигнал), рассматривают условную вероятность ${displaystyle displaystyle p(b_{j}|a_{i})}$ получения приёмником символа ${displaystyle displaystyle b_{j}}$ при условии, что был отправлен символ ${displaystyle displaystyle a_{i}}$ . При этом канальная матрица имеет следующий вид:

	${displaystyle displaystyle b_{1}}$	${displaystyle displaystyle b_{2}}$	…	${displaystyle displaystyle b_{j}}$	…	${displaystyle displaystyle b_{m}}$
${displaystyle displaystyle a_{1}}$	${displaystyle displaystyle p(b_{1}\|a_{1})}$	${displaystyle displaystyle p(b_{2}\|a_{1})}$	…	${displaystyle displaystyle p(b_{j}\|a_{i})}$	…	${displaystyle displaystyle p(b_{m}\|a_{1})}$
${displaystyle displaystyle a_{2}}$	${displaystyle displaystyle p(b_{1}\|a_{2})}$	${displaystyle displaystyle p(b_{2}\|a_{2})}$	…	${displaystyle displaystyle p(b_{j}\|a_{2})}$	…	${displaystyle displaystyle p(b_{m}\|a_{2})}$
…	…	…	…	…	…	…
${displaystyle displaystyle a_{i}}$	${displaystyle displaystyle p(b_{1}\|a_{i})}$	${displaystyle displaystyle p(b_{2}\|a_{i})}$	…	${displaystyle displaystyle p(b_{j}\|a_{i})}$	…	${displaystyle displaystyle p(b_{m}\|a_{i})}$
…	…	…	…	…	…	…
${displaystyle displaystyle a_{m}}$	${displaystyle displaystyle p(b_{1}\|a_{m})}$	${displaystyle displaystyle p(b_{2}\|a_{m})}$	…	${displaystyle displaystyle p(b_{j}\|a_{m})}$	…	${displaystyle displaystyle p(b_{m}\|a_{m})}$

Очевидно, вероятности, расположенные по диагонали описывают вероятность правильного приёма, а сумма всех элементов столбца даст вероятность появления соответствующего символа на стороне приёмника — ${displaystyle displaystyle p(b_{j})}$ . Потери, приходящиеся на предаваемый сигнал ${displaystyle displaystyle a_{i}}$ , описываются через частную условную энтропию:

${displaystyle H(B|a_{i})=-sum _{j=1}^{m}p(b_{j}|a_{i})log _{2}p(b_{j}|a_{i})}$

Для вычисления потерь при передаче всех сигналов используется общая условная энтропия:

${displaystyle displaystyle H(B|A)=sum _{i}p(a_{i})H(B|a_{i})}$

означает энтропию со стороны источника, аналогично рассматривается — энтропия со стороны приёмника: вместо ${displaystyle displaystyle p(b_{j}|a_{i})}$ всюду указывается ${displaystyle displaystyle p(a_{i}|b_{j})}$ (суммируя элементы строки можно получить ${displaystyle displaystyle p(a_{i})}$ , а элементы диагонали означают вероятность того, что был отправлен именно тот символ, который получен, т.е. вероятность правильной передачи).

Взаимная энтропия

Взаимная энтропия, или энтропия объединения, предназначена для рассчёта энтропии взаимосвязанных систем (энтропии совместного появления статистически зависимых сообщений) и обозначается , где , как всегда, характеризует передатчик, а — приёмник.

Взаимосязь переданных и полученных сигналов описывается вероятностями совместных событий ${displaystyle displaystyle p(a_{i}b_{j})}$ , и для полного описания характеристик канала требуется только одна матрица:

${displaystyle displaystyle p(a_{1}b_{1})}$	${displaystyle displaystyle p(a_{1}b_{2})}$	…	${displaystyle displaystyle p(a_{i}b_{j})}$	…	${displaystyle displaystyle p(a_{1}b_{m})}$
${displaystyle displaystyle p(a_{2}b_{1})}$	${displaystyle displaystyle p(a_{2}b_{2})}$	…	${displaystyle displaystyle p(a_{2}b_{j})}$	…	${displaystyle displaystyle p(a_{2}b_{m})}$
…	…	…	…	…	…
${displaystyle displaystyle p(a_{i}b_{1})}$	${displaystyle displaystyle p(a_{i}b_{2})}$	…	${displaystyle displaystyle p(a_{i}b_{j})}$	…	${displaystyle displaystyle p(a_{i}b_{m})}$
…	…	…	…	…	…
${displaystyle displaystyle p(a_{m}b_{1})}$	${displaystyle displaystyle p(a_{m}b_{2})}$	…	${displaystyle displaystyle p(a_{m}b_{j})}$	…	${displaystyle displaystyle p(a_{m}b_{m})}$

Для более общего случая, когда описывается не канал, а просто взаимодействующие системы, матрица необязательно должна быть квадратной. Очевидно, сумма всех элементов столбца с номером даст ${displaystyle displaystyle p(b_{j})}$ , сумма строки с номером есть ${displaystyle displaystyle p(a_{i})}$ , а сумма всех элементов матрицы равна 1. Совместная вероятность ${displaystyle displaystyle p(a_{i}b_{j})}$ событий ${displaystyle displaystyle a_{i}}$ и ${displaystyle displaystyle b_{j}}$ вычисляется как произведение исходной и условной вероятности,

${displaystyle displaystyle p(a_{i}b_{j})=p(a_{i})p(b_{j}|a_{i})=p(b_{j})p(a_{i}|b_{j}).}$

Условные вероятности производятся по формуле Байеса. Таким образом имеются все данные для вычисления энтропий источника и приёмника:

${displaystyle H(A)=-sum _{i}left(sum _{j}p(a_{i}b_{j})log sum _{j}p(a_{i}b_{j})right)}$

${displaystyle H(B)=-sum _{j}left(sum _{i}p(a_{i}b_{j})log sum _{i}p(a_{i}b_{j})right)}$

${displaystyle displaystyle H(AB)=-sum _{i}sum _{j}p(a_{i}b_{j})log p(a_{i}b_{j})}$

Единица измерения — бит/два символа, это объясняется тем, что взаимная энтропия описывает неопределённость на пару символов — отправленного и полученного. Путём несложных преобразований также получаем

{displaystyle displaystyle H(AB)=H(A)+H(B|A)=H(B)+H(A|B).}

Свойства

Важно помнить, что энтропия является количеством, определённым в контексте вероятностной модели для источника данных. Например, кидание монеты имеет энтропию ${displaystyle -2(0,5log _{2}0,5)=1}$ бита на одно кидание (при условии его независимости). У источника, который генерирует строку, состоящую только из букв «А», энтропия равна нулю: ${displaystyle -sum _{i=1}^{infty }log _{2}1=0}$ . Так, к примеру, опытным путём можно установить, что энтропия английского текста равна 1,5 бит на символ, что конечно будет варьироваться для разных текстов. Степень энтропии источника данных означает среднее число битов на элемент данных, требуемых для её зашифровки без потери информации, при оптимальном кодировании.

Некоторые биты данных могут не нести информации. Например, структуры данных часто хранят избыточную информацию, или имеют идентичные секции независимо от информации в структуре данных.
Количество энтропии не всегда выражается целым числом бит.

Альтернативное определение

Другим способом определения функции энтропии H является доказательство, что H однозначно определена (как указано ранее), если и только если H удовлетворяет пунктам 1)—3):

1) H(p₁, …, p_n) определена и непрерывна для всех p₁, …, p_n, где p_i [0,1] для всех i = 1, …, n и p₁ + … + p_n = 1. (Заметьте, что эта функция зависит только от распределения вероятностей, а не от алфавита.)

2) Для целых положительных n, должно выполняться следующее неравенство:

${displaystyle Hunderbrace {left({frac {1}{n}},ldots ,{frac {1}{n}}right)} _{n mathrm {arguments} }<Hunderbrace {left({frac {1}{n+1}},ldots ,{frac {1}{n+1}}right).} _{n+1 mathrm {arguments} }}$

3) Для целых положительных b_i, где b₁ + … + b_n = n, должно выполняться равенство:

${displaystyle Hleft({frac {1}{n}},ldots ,{frac {1}{n}}right)=Hleft({frac {b_{1}}{n}},ldots ,{frac {b_{k}}{n}}right)+sum _{i=1}^{k}{frac {b_{i}}{n}}Hleft({frac {1}{b_{i}}},ldots ,{frac {1}{b_{i}}}right).}$

Эффективность

Исходный алфавит, встречающийся на практике, имеет вероятностное распределение, которое далеко от оптимального. Если исходный алфавит имел n символов, тогда он может может быть сравнён с «оптимизированным алфавитом», вероятностное распределение которого однородно. Соотношение энтропии исходного и оптимизированного алфавита — это эффективность исходного алфавита, которая может быть выражена в процентах.

Из этого следует, что эффективность исходного алфавита с n символами может быть определена просто как равная его n-арной энтропии.

Энтропия ограничивает максимально возможное сжатие без потерь (или почти без потерь), которое может быть реализовано при использовании теоретически — типичного набора или, на практике, — кодирования Хаффмана, кодирования Лемпеля-Зива или арифметического кодирования.

История

В 1948 году, исследуя проблему рациональной передачи информации через зашумленный коммуникационный канал, Клод Шеннон предложил революционный вероятностный подход к пониманию коммуникаций и создал первую, истинно математическую, теорию энтропии. Его сенсационные идеи быстро послужили основой разработки двух основных направлений: теории информации, которая использует понятие вероятности и эргодическую теорию для изучения статистических характеристик данных и коммуникационных систем, и теории кодирования, в которой используются главным образом алгебраические и геометрические инструменты для разработки эффективных шифров.

Понятие энтропии, как меры случайности, введено Шенноном в его статье «A Mathematical Theory of Communication», опубликованной в двух частях в Bell System Technical Journal в 1948 году.

Литература

↑ Д.С. Лебедев, В.А. Гармаш. О возможности увеличения скорости передачи телеграфных сообщений. — М.:Электросвязь, 1958, №1. с.68-69

2.Цымбал В.П. Теория информации и кодирование. — К.:Выща Школа, 1977. — 288 с.

См. также

Энтропийное кодирование
Цепь Маркова
Для понимания информационной энтропии можно прибегнуть к примеру из области термодинамической энтропии получившему широко известное название Демона Максвелла.

Внешние ссылки

http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html
С.М. Коротаев. Энтропия и информация — Универсальные естественнонаучные понятия

Эта статья содержит материал из статьи Информационная энтропия русской Википедии.

Источник

Энтропия источника дискретных сообщений

А.
Энтропия источника независимых
сообщений

Мы
определили количество информации,
содержащееся в отдельном
сообщении. Во многих случаях, например
при согласовании канала с источником
информации, возникает необходимость в
характеристиках, позволяющих оценивать
информационные свойства источника
сообщений в
целом. Одной
из важнейших характеристик такого типа
является среднее
количество информации,
приходящееся
на одно сообщение.

В
простейшем случае, когда все сообщения
равновероятны, количество информации
в каждом из них одинаково и равно

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

Однако
в реальных условиях сообщения, как
правило, имеют разную вероятность.
Например, буквы О, Е и А встречаются в
тексте сравнительно часто, тогда как
Щ, Ы и Ъ – достаточно редко. Поэтому
знания числа сообщений m
в ансамбле недостаточно и требуется
иметь сведения о вероятности каждого
сообщения
.
Так как вероятности сообщений неодинаковы,
то они несут различное количество
информации:

Среднее
количество информации, приходящееся
на одно сообщение источника, определяется
как математическое ожидание
:

Величина

называетсяэнтропией.
Этот термин заимствован из термодинамики,
где он характеризует неопределенность
состояния физической системы.

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

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

Зависимость
энтропии от величины p
приведена на Рис. 1.

Рис. 1. Зависимость
энтропии от вероятности

Максимум
энтропии имеет место при
,
т.е. когда ситуация является наиболее
неопределенной. Приили,
что соответствует передаче одного из
сообщенийили,
неопределенностьотсутствует.
В этих случаях энтропия равна нулю.

Среднее
количество информации, содержащееся в
последовательности из n
сообщений, равно

Отсюда
следует, что количество передаваемой
информации можно увеличить не
только за счет числа сообщений,
но и путем
повышения энтропии источника,
т.е. информационной емкости его сообщений.

Обобщая
эти результаты, можно сформулировать
основные свойства энтропии источника
независимых сообщений:

Энтропия
– величина всегда положительная, так
как
;
При
равновероятных сообщениях, когда

энтропия
максимальна и равна

Энтропия
равняется нулю лишь в тех случаях, когда
все вероятности равны нулю, за
исключением одной, величина которой
равна единице;
Энтропия
нескольких независимых источников
равна сумме
энтропий этих источников

Б.
Энтропия источника зависимых
сообщений

Рассмотренный
нами источник независимых сообщений
является простейшим типом источника.
В реальных условиях картина значительно
усложняется из-за наличия статистических
связей
между сообщениями. Примером может
служить обычный текст, где появление
той или иной буквы зависит от предыдущих
буквенных сочетаний. Так например, после
сочетания ЧТ вероятность следования
гласных букв О, Е или И значительно
выше, чем согласных.

Статистическая
связь ожидаемого сообщения с предыдущим
сообщением количественно оценивается
совместной вероятностью
или условной вероятностью,
которая выражает вероятность появления
сообщенияпри
условии, что известно предыдущее
сообщение
.
Количество информации, содержащейся в
сообщении при условии, что известно
предыдущее сообщение согласно (1)
будет равно

Среднее
количество информации при этом
определяется условной
энтропией
,
которая вычисляется как математическое
ожидание информации
по всем возможным сообщениям.

Важным
свойством условной энтропии источника
зависимых сообщений является то, что
при неизменном количестве сообщений в
ансамбле источника его энтропия
уменьшается с увеличением числа
сообщений, между которыми существует
статистическая взаимосвязь. В соответствии
с этим свойством, а также свойством
энтропии источника независимых сообщений
можно записать неравенства

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

Избыточность
источника сообщений

Уменьшение
энтропии источника с увеличением
статистической взаимосвязи (14) можно
рассматривать как снижение информационной
емкости сообщений. Одно и то же сообщение
при наличии взаимосвязи содержит в
среднем меньше информации, чем при ее
отсутствии. Иначе говоря, если источник
создает последовательность сообщений,
обладающих статистической связью, и
характер этой связи известен, то часть
сообщений, выдаваемых источником,
является избыточной,
так как она может быть восстановлена
по известным статистическим связям.
Появляется возможность передавать
сообщения в сокращенном виде без потери
информации. Например при передаче
телеграммы из текста исключаются союзы,
предлоги, знаки препинания, так как они
легко восстанавливаются при чтении
телеграммы на основании известных
правил построения фраз и слов.

Говорят,
что любой источник зависимых сообщений
обладает
избыточностью.
Количественное определение избыточности
может быть получено из следующих
соображений. Для того чтобы передать
количество информации
, источник без избыточности должен
выдать в среднемсообщений, а источник с избыточностьюсообщений.

Поскольку

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

Величина
избыточности согласно (14) является
неубывающей функцией. Для русского
языка, например, избыточность составляет
порядка 50%.

Коэффициент

называется
коэффициентом
сжатия.
Он показывает, до какой величины можно
сжать передаваемые сообщения, если
устранить избыточность. В связи с тем,
что обладающий избыточностью источник
передает излишнее количество сообщений,
увеличивается продолжительность
передачи и снижается эффективность
использования канала связи. Требуется
проводить сжатие сообщений, которое
реализуется с помощью соответствующего
кодирования. Информацию необходимо
передавать такими сообщениями, емкость
которых используется наиболее полно.

Вместе
с тем избыточность источника далеко не
всегда является отрицательным свойством.
Наличие взаимосвязи между буквами
текста дает возможность восстановить
его при искажении отдельных букв, т.е.
использовать избыточность для повышения
достоверности
передачи информации.

Лекция
6. Пропускная способность дискретных
каналов и эффективность систем передачи
информации

Скорость
передачи информации и пропускная
способность дискретного канала без
помех

Так
как передача информации происходит во
времени, естественно ввести понятие
скорости
передачи
как количество информации, передаваемой
в среднем за единицу времени

Здесь

– количество информации, содержащейся
в последовательности сообщений,
общая длительность которых равнаT.

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

Величина
для независимых сообщений может быть
вычислена как математическое ожидание

где

– вероятность сообщениядлительностью. Если длительность всех сообщений
одинакова и равна,
формула (2) принимает вид

Отсюда
следует, что наибольшей производительностью
обладает источник с максимальной
энтропией
(см.
ф.(12) прошлой лекции),
т.е.

Выданная
источником информация в виде отдельных
сообщений поступает в канал связи, где
осуществляется кодирование и ряд других
преобразований, в результате которых
информация переносится уже сигналами

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

Высокая
скорость передачи является одним из
основных требований, предъявляемых к
системам передачи информации. В реальных
условиях всегда существует ряд причин,
ведущих к ее ограничению.

Во-первых,
в реальном канале число используемых
сигналов всегда конечно и энтропия в
соответствии с
ф.(12) прошлой лекции,
есть величина ограниченная

С
другой стороны,
уменьшение длительности сигнала приводит
к расширению спектра, что при учете
ограниченной полосы пропускания канала
ставит предел уменьшению средней
длительности .

Максимально
возможная скорость передачи информации
по каналу связи называется пропускной
способностью канала

Максимум
скорости R
здесь ищется по всем возможным ансамблям
сигналов u
.

Пусть
число используемых сигналов не превышает
m,
а их длительность не может быть меньше

секунд. Так как
инезависимы, то по формуле (8) следует
искать максимуми минимум, что дает

Для
двоичных сигналов m
= 2 и пропускная способность

Оптимальное
статистическое кодирование сообщений

Для
дискретных каналов
без помех
Шенноном была доказана следующая
теорема:
если производительность источника
меньше пропускной способности канала
(),
то всегда существует способ кодирования,
позволяющий передавать по каналу все
сообщения источника. Передачу всех
сообщений приосуществить невозможно.

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

Для
рационального использования пропускной
способности канала необходимо применять
соответствующие способы кодирования
сообщений.

Статистическим
или оптимальным
называется кодирование, при котором
наилучшим образом используется пропускная
способность канала без помех. При
оптимальном кодировании фактическая
скорость передачи информации по каналу
R
приближается к пропускной способности
C,
что достигается путем согласования
источника с каналом.
Сообщения источника кодируются таким
образом, чтобы они в наибольшей степени
соответствовали ограничениям, которые
накладываются на сигналы, передаваемые
по каналу связи. Поэтому структура
оптимального кода зависит как от
статистических характеристик источника,
так и от особенностей канала.

Рассмотрим
основные принципы оптимального
кодирования на примере источника
независимых сообщений, который необходимо
согласовать с двоичным каналом без
помех. Здесь процесс кодирования
заключается в преобразовании сообщений
источника в двоичные кодовые комбинации.
Поскольку существует однозначное
соответствие между сообщениями источника
и комбинациями кода, то энтропия кодовых
комбинаций равна энтропии источника

а скорость передачи
в канале определяется с помощью (6) как

Здесь
– средняя длительность кодовой комбинации,
которая в общем случае неравномерного
кода записывается по аналогии с (3) как

где

– длительность одного элемента кода и– число элементов в комбинации,
присваиваемой сообщению.

Подстановка в
формулу (12) выражений

и (13) дает

в
котором числитель определяется
исключительно статистическими свойствами
источника, а величина
– характеристиками канала.

Возникает
вопрос: можно ли так закодировать
сообщение, чтобы скорость передачи (14)
достигала своего максимального значения,
равного пропускной способности двоичного
канала
. Легко заметить, что это условие
выполняется, если

что
соответствует минимуму
и максимумуR.

Одним
из кодов, удовлетворяющих условию (33),
является код Шеннона – Фано, который
мы рассмотрим позднее.

Необходимо
подчеркнуть, что при оптимальном способе
кодирования в сигналах, передающих
сообщения источника, совершенно
отсутствует избыточность. Устранение
избыточности приводит к тому, что процесс
декодирования становится весьма
чувствительным к воздействию помех.
Это особенно сильно проявляется при
оптимальном кодировании зависимых
сообщений. Иногда одна единственная
ошибка может вызвать неправильное
декодирование всех последующих сигналов.
Поэтому оптимальные коды применимы
только для каналов с чрезвычайно низким
уровнем помех.

Скорость
передачи информации и пропускная
способность дискретных каналов с
помехами

Каналы
без помех
характеризуются тем, что количество
принятой на выходе канала информации
всегда равно
количеству информации, переданной
источником сообщений.

При
этом, если на вход канала поступил сигнал
, то на выходе возникает сигнал,однозначно
определяющий
переданный сигнал
. Количество информации, прошедшее по
каналу без помех в случае передачии приема,
равно количеству информации, содержащейся
в сигнале:

Здесь
величина вероятности
характеризует ту неопределенность в
отношении сигнала, которая существоваладо
его передачи.
После приема
в силу однозначного соответствия междуинеопределенность полностью устраняется.

Совершенно
другое положение имеет место для каналов,
где присутствуют различного рода помехи.

Воздействие
помех на передаваемый сигнал приводит
к необратимой потере части информации,
поступающей от источника сообщений.
Так как в канале с помехами принятому
сигналу
может соответствовать передача
одного из нескольких сигналов
,
то после приемаостается некоторая неопределенность
в отношении переданного сигнала. Здесь
соответствие междуиноситслучайный
характер, и степень неопределенности
характеризуется условной апостериорной
вероятностью
. Количество информации, необходимое
для устранения оставшейся неопределенности

очевидно,
равно той части информации, которая
была потеряна вследствие помех. Количество
принятой информации определяется как
(см. ф. (9) прошлой лекции)

Для
оценки среднего количества принятой
информации при передаче одного сообщения
выражение (17) необходимо усреднить по
всему ансамблю
и:

где

–
совместная вероятность переданного и
принятого сигналов,– количество сигналов в ансамбле на
входе канала и– количество сигналов в ансамбле на
выходе канала (в общем случае).

Величина

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

Выражение (18) можно
представить в виде

где

представляет
энтропию источника сигналов
и

–
условная энтропия или ненадежность.

Формула
(19) показывает, что среднее количество
принятой информации равно среднему
количеству переданной информации
минус среднее количество информации,
потерянное в канале вследствие воздействия
помех.

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

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

Для
каналов с сигналами одинаковой
длительности ,
пропускная способность равна

где
максимум ищется по всем возможным
ансамблям сигнала
.

Выведем
выражение для пропускной способности
двоичного канала с помехами, по которому
передаются независимые дискретные
сигналы
с априорными вероятностями. На выходе канала образуются сигналы,
при правильном приеме отражающие сигналы.
В результате действия помех возможны
ошибки, которые характеризуются при
передачеусловной вероятностью,
а при передаче– условной вероятностью.

Будем
полагать, что канал симметричен, т.е.
для него вероятности переходов одинаковы

,
а полная вероятность ошибки равна

При
этих условиях можно показать, что
пропускная способность двоичного
симметричного канала равна

На Рис. 1. приведена
зависимость пропускной способности
канала С от вероятности ошибки для
двоичного канала согласно формуле (26)

Рис.
1. Зависимость пропускной способности
двоичного канала от вероятности ошибки
.

Видно,
что увеличение вероятности ошибки
приводит к снижению пропускной
способности, которая становится равной
нулю при=
0,5. В этом случае полностью исчезает
какая-либо зависимость между передаваемым
и принятым сигналами. Таким образом,
значение
=
0,5 для бинарного симметричного канала
является предельным.

Теорема Шеннона
для дискретного канала с помехами

Данная
теорема имеет фундаментальное значение
для теории и техники передачи информации.

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

Таким
образом, наличие помех в канале не
препятствует
передаче сообщений со сколь угодно
малой вероятностью ошибок декодирования,
а лишь ограничивает максимальную
скорость передачи информации С. Высокая
достоверность декодирования и конечная
скорость передачи не исключают друг
друга.

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

Пропускная
способность непрерывного канала. Формула
Шеннона

Шенноном
была получена также формула для пропускной
способности непрерывного канала, в
котором помехой является аддитивный
шум
.
Если средние мощности сигнала и шума
ограничены величинами,
и ширина их спектра равнаF,
то формула Шеннона имеет вид

Данная
формула очень важна, т.к. она показывает
те предельные возможности, к которым
следует стремиться при разработке
систем передачи информации. Формула
выведена для равномерных спектров
сигнала и шума, но может быть распространена
и на более реальный случай неравномерных
спектров. Оказывается, при заданных
спектрах сигнала и шума максимума
пропускной способности можно добиться
путем увеличения мощности сигнала на
тех частотах, где уменьшается мощность
шума и наоборот. Минимальная пропускная
способность соответствует равномерному
спектру шума, т.е. “белый шум” является
самым вредным
видом помех.

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

Пропускная
способность канала связи С является
тем пределом, которого можно достигнуть
при идеальном кодировании. Естественно,
что в реальных каналах скорость передачи
всегда будет меньше С. Степень отличия
R
от С зависит от того, насколько рационально
выбрана и эффективно используется та
или иная система передачи информации.
Наиболее общей оценкой эффективности
системы передачи информации является
коэффициент
использования канала

Для
дискретных систем передачи информации
справедливо соотношение
,
гдеи–
эффективностьсистемы
кодирования
и эффективность системы
модуляции
соответственно.

Вводя
избыточность сообщения
и избыточностьсигнала
, можно показать, что

где

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

Избыточность
сообщения
обусловлена тем, что элементы сообщения
не являются равновероятными и между
ними имеется статистическая связь. При
кодировании можно перераспределить
вероятности исходного сообщения так,
чтобы распределение вероятностей
символов кода приближалось к оптимальному.

Избыточность
сигнала
зависит от способа модуляции и вида
переносчика. Процесс модуляции обычно
сопровождается расширением полосы
частот сигнала по сравнению с полосой
частот передаваемого сообщения. Это
расширение полосы и является избыточным.

Говоря
об эффективности системы передачи
информации, нельзя забывать о ее
помехоустойчивости. Устранение
избыточности повышает эффективность
передачи, но снижает при этом
помехоустойчивость. При кодировании в
ряде случаев избыточность вводится
специально с целью повышения достоверности
передачи. Пример такого кодирования
являются корректирующие
коды,
которые мы рассмотрим позднее.

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

Источник

Содержание

Для понимания материалов настоящего раздела рекомендуется ознакомиться с разделом ТЕОРИЯ ВЕРОЯТНОСТЕЙ.
.

Статус документа: черновик.

Теория информации по Шеннону

Энтропия

Пусть случайное событие заключается в осуществлении одного из несовместимых состояний $ S_{1},dots,S_n $, вероятности появления которых даются таблицей
$$
begin{array}{l|l|l|l}
S_1 & S_2 & dots & S_n \
hline
P_1 & P_2 & dots & P_n
end{array} quad mbox{ при } quad P_1+P_2+dots+P_n=1.
$$
Эти вероятности известны, но это — все, что нам известно относительно того какое состояние осуществится. Можно ли найти «меру» насколько велик выбор из такого набора состояний и сколь неопределено для нас событие?

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

Для практики важно уметь численно оценивать степень неопределенности самых разнообразных случайных событий (опытов), чтобы иметь возможность сравнивать их с этой стороны. Искомая численная характеристика должна быть функцией числа $ n_{} $ возможных состояний. Некоторые свойства этой функции $ f(n) $ определяются соображениями здравого смысла. При $ n_{}=1 $ событие вообще не является случайным, т.е. следует положить $ f(1)=0 $. При возрастании числа $ n_{} $ возможных состояний эта функция должна возрастать поскольку увеличение количества возможных исходов опыта увеличивает неопределенность в предсказании его результатов.

Идем далее: рассмотрим два независимых события $ A_{} $ и $ B_{} $. Пусть событие $ A_{} $ имеет $ k_{} $ равновероятных исходов, а событие $ B_{} $ имеет $ ell_{} $ равновероятных исходов. Рассмотрим событие, состоящее в произведении (совместном осуществлении) событий $ A_{} $ и $ B_{} $, обозначим это событие $ AB_{} $. Например, если событие $ A_{} $ заключается в появлении масти карты — бубновой

♦

, червовой

♥

, трефовой

♣

или пиковой

♠

—
при выборе ее из колоды в $ 36_{} $ карт, а событие $ B_{} $
заключается в появлении достоинства карты — шестерки,семерки, восьмерки, девятки, десятки, валета, дамы, короля или туза — при выборе ее из той же колоды, то событие $ AB_{} $ заключается в появлении конкретной карты колоды. Очевидно, что неопределенность события $ AB_{} $ больше неопределенности события $ A_{} $, так как к неопределенности $ A_{} $ добавляется неопределенность события $ B_{} $. Естественно потребовать, чтобы мера неопределенности события $ AB_{} $ была равна сумме неопределенностей, характеризующих события $ A_{} $ и $ B_{} $. Это требование обеспечивается следующим следующим свойством функции $ f_{} $:
$$
f(kell)=f(k)+f(ell) ,
$$
имеющего тот смысл, что число $ kell $ как раз и дает число возможных исходов события $ AB_{} $.

Последнее равенство наталкивает на мысль принять за меру неопределенности опыта, имеющего $ n_{} $ равновероятных исходов, число $ log n $. Можно доказать, что логарифмическая функция является единственной непрерывной функцией аргумента $ nin mathbb R $, удовлетворяющей такому функциональному уравнению. При этом выбор основания системы логарифмов несуществен, так как, в силу известной формулы $ log_b n = log_b a cdot log_a n $, переход от одной системы логарифмов к другой сводится лишь к умножению функции $ f(n)=log n $ на постоянный множитель $ log_b a $, т.е. равносилен простому изменению единицы измерения степени неопределенности. Единственным ограничением является естественное требование, чтобы основание было большим $ 1 $: число $ log_b n $ должно быть положительным

Как правило, в дальнейшем будем пользоваться логарифмом по основанию $ 2_{} $; такой выбор в одном из последующих пунктов будет подкреплен некоторыми дополнительными «бонусами». В ближайших же пунктах будем просто писать $ log $ без указания основания.

Таблица вероятностей события, имеющего $ n_{} $ равновероятных состояний, имеет вид
$$
begin{array}{l|l|l|l}
S_1 & S_2 & dots & S_n \
hline
1/n & 1/n & dots & 1/n
end{array}
$$
Так как общая неопределенность события по нашему условию равна $ log n $, то можно считать, что каждое в отдельности состояние вносит неопределенность равную $ frac{1}{n} log n = – frac{1}{n} log frac{1}{n} $. Но тогда естественно считать, что в событие, таблица вероятностей состояний которого имеет вид
$$
begin{array}{l|l|l}
S_1 & S_2 & S_3 \
hline
1/2 & 1/3 & 1/6
end{array}
$$
состояние $ S_1 $ вносит неопределенность, равную $ left( – frac{1}{2} log frac{1}{2} right) $, состояние $ S_2 $ — неопределенность, равную $ left( – frac{1}{3} log frac{1}{3} right) $, а состояние $ S_3 $ — неопределенность, равную
$ left( – frac{1}{6} log frac{1}{6} right) $, так что суммарная неопределенность события равна
$$
– frac{1}{2} log frac{1}{2} – frac{1}{3} log frac{1}{3} – frac{1}{6} log frac{1}{6} .
$$
Аналогично этому можно положить, что для события $ A_{} $ с таблицей вероятностей
$$
begin{array}{l|l|l|l}
S_1 & S_2 & dots & S_n \
hline
P_1 & P_2 & dots & P_n
end{array} quad mbox{ при } quad P_1+P_2+dots+P_n=1
$$
мера его неопределенности равна
$$
-sum_{j=1}^n P_j log P_j = – P_1 log P_1 – P_2 log P_2 – dots – P_n log P_n = log frac{1}{P_1^{P_1} P_2^{P_2}times
dots times P_n^{P_n}} .
$$
Это число будем называть энтропией события $ A_{} $ и обозначать либо $ H(A) $ либо $ H(P_1,P_2,dots,P_n) $. Величина энтропии зависит от выбранного основания логарифмической функции; в случае основания $ 2_{} $ единицу измерения энтропии называют «бит», в случае основания $ 10_{} $ — «дит», в случае основания $ e=2.718281828459045dots $ — «нат».

В случае, когда $ P_j=0 $ при каком-то значении $ j_{} $, полагают $ P_j log P_j=0 $ (на основании известного из мат.анализа факта $ displaystyle lim_{xto +0} x log x = 0 $).

Можно проверить, что функция $ H(P_1,P_2,dots,P_n) $ симметрична относительно своих переменных; этот факт имеет тот
смысл, что мера неопределенности события не зависит от способа нумерации его возможных состояний. Кроме того эта функция
обладает следующими свойствами.

$ H_{} $ непрерывна по каждой своей переменной;

Если все вероятности одинаковы: $ P_1=1/n,P_2=1/n,dots,P_n=1/n $, то $ H_{} $ монотонно возрастающая функцией по $ n_{} $:
$$H bigg(underbrace{frac{1}{n},dots,frac{1}{n}}_n bigg)<Hbigg(underbrace{frac{1}{n+1},frac{1}{n+1},dots,frac{1}{n+1}}_{n+1}bigg) $$
(при равновероятности состояний, неопределенность события тем больше, чем больше количество этих состояний).

При распадении какого-то события на два последовательных, величина $ H_{} $ должна вычисляться как взвешенная сумма составляющих значений $ H_{} $. Иллюстрирую на примере, который беру у Шеннона, но при этом излагаю в русском фольклорном стиле.

Пример. Предположим, что найденная Иваном-царевичем лягушка в течение минуты либо

превращается в бабу-Ягу с вероятностью $ 1/3 $;
превращается в красавицу Василису Премудрую с вероятностью $ 1/6 $;
остается лягушкой, и вероятность этого события равна $ 1/2 $.

Мера неопределенности этого события $ H(1/3,1/6,1/2) $. Теперь посчитаем меру неопределенности по-другому, объединив сначала первые два состояния в одно. Лягушка в течение минуты

превращается в женщину с вероятностью $ 1/2 $;
остается лягушкой с вероятностью $ 1/2 $.

Кроме того известно, что если лягушка точно превратилась в женщину, то ( условная ) вероятность того, что она стала бабой-Ягой равна $ 2/3 $, и, следовательно, вероятность появления Василисы Премудрой оказывается равной $ 1/3 $. В результате получаем два значения для функции $ H_{} $, именно $ H(1/2,1/2 ) $ и $ H(2/3 , 1/3 ) $.

Как должны быть связаны эти новые величины со старой — с $ H(1/3,1/6,1/2) $? Конечный результат у обоих событий одинаков, во втором случае мы просто искусственно «вставили» одно промежуточное событие. Так вот, имеет место равенство:
$$H(1/3,1/6,1/2)=H(1/2,1/2 )+frac{1}{2} H(2/3 , 1/3 ) , $$
здесь весовой множитель $ 1/2 $ в составе второго слагаемого возникает из-за того, что ситуация второго события происходит только в половине случаев.

♦

Формализуем: утверждается, что функция $ H_{} $ удовлетворяет условию
$$
H(P_1,P_2,P_3,dots,P_n)=H(P_1+P_2,P_3,dots,P_n)+(P_1+P_2)Hleft(frac{P_1}{P_1+P_2}, frac{P_2}{P_1+P_2} right) ;
$$
а уж из последнего можно вывести и еще более общее:
$$
H(P_1,dots,P_n)=H(P_1+dots+P_m,P_{m+1},dots,P_n)+
$$
$$
+(P_1+dots+P_m)Hleft(frac{P_1}{P_1+dots+P_m}, frac{P_2}{P_1+dots+P_m},dots,
frac{P_m}{P_1+dots+P_m} right)
$$
при $ forall min {2,dots,n-1} $.

Перечисленные свойства

1

–

3

оказываются настолько «жесткими», что будучи формально наложенными на произвольную функцию $ H_{} $, задают ее, фактически,
однозначно:

Теорема [Шеннон]. Единственной функцией, удовлетворяющей условиям

1

–

3

,
является функция
$$ H=- K sum_{j=1}^n P_j log P_j . $$
Здесь $ K_{} $ — положительная константа, а логарифм берется по произвольному основанию большему $ 1_{} $.

Можно сказать, что свойства

1

–

3

являются определяющими свойствами энтропии — по аналогии с определяющими свойствами определителя как функции столбцов (или строк) матрицы.

После приведения этой формулировки, Шеннон пишет:

Эта теорема, равно как и необходимые для ее доказательства условия, не являются необходимыми для собственно излагаемой теории. Она приведена, главным образом, для придания правдоподобия¹⁾ некоторым последующим определениям. Действительное же обоснование этих определений, однако, остается за их применениями.

Образно говоря, следующее определение энтропии как меры неопределенности само в себе имеет некоторую меру неопределенности ^_^

Происхождение слова «энтропия»

☞

ЗДЕСЬ.

В дальнейшем, если не оговаривается особо, будем считать энтропию при логарифмической функции, взятой по основанию $ 2_{} $, и этот индекс при написании будем часто опускать.

Пример. Графики энтропии для $ n_{}=2 $

и для $ n_{}=3 $:

Формула для энтропии была получена в XIX веке Больцманом в его работах по статистической физике. Больцман показал, что если в газе, состоящем из большого числа молекул, вероятности состояний отдельных молекул равны $ P_1,dots,P_n $, то энтропия системы определяется соотношением
$$ H=- c sum_{j=1}^n P_j ln P_j , $$
где $ c_{} $ — некоторая константа. Можно считать, что энтропия системы является мерой неопределенности состояния молекул, составляющих эту систему. Эта интерпретация позволяет понять, почему Шеннон использовал ту же формулу в теории информации. Информация — это убыль неопределенности. До осуществления случайного события мы пребываем в полной неопределенности относительно того, какое из своих состояний оно может принять. После осуществления события, неопределенность устраняется. В одном из следующих пунктов мы покажем, что величина энтропии $ H_{} $ может быть интерпретирована как количество информации, содержащейся в событии.

Свойства энтропии

Проанализируем теперь формулу для энтропии.

Теорема 1. $ H=0 $ тогда и только тогда, когда одна из вероятностей равна $ 1_{} $ при всех остальных, равных нулю (мера недостоверности наверняка осуществимого события равна $ 0_{} $).

Теорема 2. При фиксированном $ n_{} $ максимум функции $ H_{} $ достигается при всех вероятностях одинаковых:
$$ max_{P_1+dots+P_n=1} H(P_1,dots,P_n)=Hleft(frac{1}{n},dots,frac{1}{n} right) = log n $$
(при равновероятности состояний предсказание об осуществимости какого-то конкретного из них максимально недостоверно).

Теорема 3. Пусть случайные события $ A_{} $ и $ B_{} $ независимы. Тогда энтропия произведения (совместного осуществления) событий $ A cdot B $ равна сумме энтропий перемножаемых событий:

$$ H ( A cdot B) = H(A) + H(B) . $$

Доказательство. Пусть случайное событие $ A_{} $ может находиться в состояниях $ S_1,dots,S_n $ с вероятностями, заданными таблицей
$$
begin{array}{l|l|l|l}
S_1 & S_2 & dots & S_n \
hline
P_1 & P_2 & dots & P_n
end{array} quad mbox{ при } quad P_1+P_2+dots+P_n=1,
$$
а случайная величина $ B_{} $ может находиться в состояниях $ U_1,dots,U_m $ с вероятностями, заданными таблицей
$$
begin{array}{l|l|l|l}
U_1 & U_2 & dots & U_m \
hline
Q_1 & Q_2 & dots & Q_m
end{array} quad mbox{ при } quad Q_1+Q_2+dots+Q_m=1.
$$
Тогда случайная величина $ Acdot B $ может находиться в состояниях
$$ { S_jU_k mid quad jin {1,dots,n}, kin {1,dots,m } } ; $$
здесь $ S_jU_k $ означает такое состояние «сложного» события, которое заключается в одновременном выполнении двух условий: событие $ A_{} $ находится в состоянии $ S_j $, a событие $ B_{} $ — в состоянии $ U_k $. Поскольку, по предположению, события $ A_{} $ и $ B_{} $ независимы, то вероятность такого состояния равна $ P_jQ_k $.
Тогда
$$ H(Acdot B)= sum_{j=1}^n sum_{k=1}^{m} P_jQ_k log frac{1}{P_jQ_k}=
sum_{j=1}^n sum_{k=1}^{m} P_jQ_k left( log frac{1}{P_j} + log frac{1}{Q_k}right)=
$$
$$
= underbrace{left( sum_{k=1}^{m} Q_k right)}_{=1} sum_{j=1}^n P_j log frac{1}{P_j} +
underbrace{left( sum_{j=1}^{n} P_j right)}_{=1}
sum_{k=1}^{m} Q_klog frac{1}{Q_k}= H(A) + H(B) .
$$

♦

Для любых случайных событий $ A_{} $ и $ B_{} $ энтропия их произведения (совместного появления) $ A cdot B $ не превосходит суммы энтропий перемножаемых событий:

$$ H ( A cdot B) le H(A) + H(B) . $$

Условная энтропия

Предположим теперь, что события $ A_{} $ и $ B_{} $ не являются независимыми. Выясним, чему равна энтропия произведения этих событий.
Общая формула для энтропии дает
$$
H(AB)=-sum_{j=1}^n sum_{k=1}^{m} P(S_jU_k) log P(S_jU_k) .
$$
В общем случае уже нельзя заменить вероятность $ P(S_jU_k) $ на произведение соответствующих вероятностей; в соответствии с теоремой из пункта

☞

УСЛОВНЫЕ ВЕРОЯТНОСТИ имеет место равенство
$$ P(S_jU_k)=P(S_j)P_{S_j}(U_k)=P_j P_{S_j}(U_k) , $$
где $ P_{S_j}(U_k) $ означает условную вероятность состояния $ U_k $ при условии нахождения события $ A_{} $ в состоянии $ S_j $. Каждое слагаемое под знаком суммы в выражении для энтропии представляется тогда в виде
$$
P(S_jU_k) log P(S_jU_k)=P_j P_{S_j}(U_k) left( log P_j + log P_{S_j}(U_k) right) .
$$
Тогда
$$
H(AB)=-sum_{j=1}^n P_j log P_j left( sum_{k=1}^{m} P_{S_j}(U_k) right)- sum_{j=1}^n P_j left( sum_{k=1}^m P_{S_j}(U_k) log P_{S_j}(U_k) right) .
$$
Сумма
$$
sum_{k=1}^{m} P_{S_j}(U_k)=P_{S_j}(U_1+U_2+dots+U_k)=1 ,
$$
поскольку событие $ U_1+U_2+dots+U_k $ — достоверное (какое-то из состояний $ U_1,U_2,dots,U_k $ событие $ B_{} $ принимает). Поэтому первое слагаемое в правой части формулы для $ H(AB) $ равно просто $ H(A_{}) $. Во втором слагаемом сумма
$$
– sum_{k=1}^m P_{S_j}(U_k) log P_{S_j}(U_k)
$$
представляет собой энтропию события $ B_{} $ при условии, что событие $ A_{} $ оказалось в состоянии $ S_{j} $. Эта энтропия называется условной энтропией события $ B_{} $ при условии нахождения события $ A_{} $ в состоянии $ S_{j} $ (или частной условной энтропией) и обозначается $ H_{S_j}(B) $ или $ H(B mid S_j) $. Тогда сумму
$$
sum_{j=1}^n P_j H_{S_j}(B)
$$
естественно считать средней условной энтропией события $ B_{} $ при условии выполнения события $ A_{} $; эту величину называют условной энтропией $ B_{} $ при условии выполнения $ A_{} $ и обозначается $ H_A(B) $ или $ H(B mid A) $.

Перепишем теперь все эти определения с использованием матричного формализма. Если обозначить
$$ P_{jk}=P_{S_j}(U_k) , $$
т.е. условную вероятность состояния $ U_k $ при условии $ S_{j} $, то из этих вероятностей можно составить матрицу
$$ mathfrak P=left[ P_{jk} right]_{j=1,dots,n atop k=1,dots,m} $$
по следующей схеме
$$
begin{array}{c}
\
S_1 \
dots \
S_n
end{array}
begin{array}{c}
begin{array}{llll}
U_1 & U_2 & dots & U_m
end{array} \
left( begin{array}{llll}
P_{11} & P_{12} & dots & P_{1m} \
dots &&& dots \
P_{n1} & P_{n2} & dots & P_{nm}
end{array} right) .
end{array}
$$
В одном из следующих ПУНКТОВ эта матрица получит специальное название и обозначение, а пока подчеркну только, что элементы этой матрицы неотрицательны и сумма их в каждой строке равна $ 1_{} $.
Введем в рассмотрение новую матрицу:
$$
tilde{mathfrak P}
=
left( begin{array}{llll}
P_{11} log P_{11} & P_{12} log P_{12} & dots & P_{1m} log P_{1m} \
dots &&& dots \
P_{n1} log P_{n1} & P_{n2} log P_{n2} & dots & P_{nm} log P_{nm}
end{array} right) .
$$
Тогда условная энтропия $ H_{S_j}(B) $ равна сумме элементов $ j_{} $-й строки этой матрицы. С использованием операции умножения матриц условные энтропии можно собрать в один столбец:
$$
left( begin{array}{c}
H_{S_1}(B) \
vdots \
H_{S_n}(B)
end{array}
right)= -tilde{mathfrak P}
left( begin{array}{c}
1 \
vdots \
1
end{array}
right) .
$$
Тогда условная энтропия $ B_{} $ при условии выполнения $ A_{} $ вычисляется по формуле
$$ H_A(B) = sum_{j=1}^n P_j H_{S_j}(B) = – (P_1,dots,P_n) tilde{mathfrak P}
left( begin{array}{c}
1 \
vdots \
1
end{array}
right) .
$$

Теорема 4. Для энтропии произведения случайных событий $ A_{} $ и $ B_{} $ имеет место правило сложения энтропий:
$$ H(AB)=H(A)+ H_A(B) . $$

Проиллюстрируем результат теоремы на примере, который подробно будем разбирать во всех последующих пунктах. Источник приведенных в нем данных

☞

ЗДЕСЬ.

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

	и	м	о	т	пробел
$ P_{} $	0.219	0.104	0.295	0.148	0.234

Таким образом, случайным событием $ A_{} $ является появление какой-то из указанных букв и
$$ H(A) = – sum_{j=1}^5 P_j log_2 P_j approx 2.237 quad mbox{ бит .} $$
Теперь предположим, что каждое следующее событие $ B_{} $ — появление на экране буквы — зависит от результата предыдущего по времени (но только от одного предыдущего). Условные вероятности, полученные в результате натурных экспериментов, соберем в матрицу
$$
mathfrak P= left[ P_{jk} right]_{j,k=1}^5=

left(
begin{array}{ccccc}
0.170 & 0.130 & 0.144 & 0.065 & 0.491 \
0.259 & 0.029 & 0.231 & 0.111 & 0.370 \
0.204 & 0.116 & 0.268 & 0.206 & 0.206 \
0.161 & 0.077 & 0.523 & 0.052 & 0.187 \
0.304 & 0.113 & 0.356 & 0.227 & 0
end{array} right)
.
$$
Так, значение $ P_{3,2}=0.116 $ означает, что если в данный момент времени на экране появилась буква о, то в следующий момент времени буква м появится примерно в $ 116 $ случаях из $ 1000 $. Выражение для матрицы $ tilde{mathfrak P} $ приведено в одном из последующих

☞

ПУНКТОВ. С ее помощью вычисляем условную энтропию события $ B_{} $ при условии события $ A_{} $:
$$ H_A(B)=
– (P_1,P_2,P_3,P_4,P_5) tilde{mathfrak P}
left( begin{array}{c}
1 \
1 \
1 \
1 \
1
end{array}
right) approx 2.036 quad mbox{ бит .}
$$
Теперь вычислим энтропию произведения событий $ A_{} $ и $ B_{} $, то есть события, заключающемся в последовательном появлении двух букв. Для этого нам потребуются вероятности появления каждой пары букв, приведенные ☞ ВСЁ ТАМ ЖЕ.

	ии	им	ио	ит	и_	ми	мм	мо	мт	м_	ои	ом	оо	от	о_	ти	тм	то	тт	т_	_и	_м	_o	_т	_
$ hat P $	0.037	0.028	0.031	0.014	0.108	0.027	0.003	0.024	0.011	0.038	0.060	0.034	0.079	0.061	0.061	0.024	0.011	0.077	0.008	0.028	0.071	0.027	0.084	0.053	0.000

Имеем:
$$H(AB)=- sum_{j=1}^{25} hat P_j log_2 hat P_j approx 4.268 quad mbox{ бит .} $$
Проверка: $ H(A)+H_A(B)approx 4.273 $ бит.

♦

Пока мы только лишь формально осваиваем введенный математический аппарат, оставляя обсуждение лежащего под ним здравого смысла до следующих пунктов.

Теорема 5. Для условной энтропии выполняются неравенства
$$ 0 le H_A(B) le H(B) . $$

Это утверждение хорошо согласуется со смыслом энтропии как меры неопределенности: предварительное осуществление события $ A_{} $ может лишь уменьшить степень неопределенности события $ B_{} $, но никак не может ее увеличить. Здесь необходимо отметить, что частная условная энтропия $ H_{S_j}(B) $ может быть и больше $ H(B) $, но усреднение всего набора частных энтропий по вероятностям всё-таки
приводит к ограничению типа $ le $.

Поскольку события $ AB_{} $ и $ BA_{} $ одинаковы, то
$$ H(AB)=H(A)+ H_A(B) =H(B)+H_B(A) . $$
Из последнего равенства можно определить и условную энтропию события $ A_{} $ при условии осуществления события $ B_{} $:
$$ H_B(A)=H(A)-H(B)+H_A(B) . $$

Пример. Пусть события $ A_{} $ и $ B_{} $ заключаются в извлечении одного шара из ящика, содержащего $ m_{} $ черных и
$ n-m $ белых шаров. Чему равны энтропии $ H(A), H(B), H_A(B), H_B(A) $?

Понятие об информации

Рассмотрим величину $ H(B) $, характеризующую степень неопределенности события $ B_{} $. Равенство этой величины нулю означает, что
состояние события $ B_{} $ заранее известно; большее или меньшее значение числа $ H(B) $ отвечает большей или меньшей неопределенности события. Какое-либо состояние события $ A_{} $, предшествующее событию $ B_{} $, может ограничить количество возможных состояний для события $ B_{} $ и тем самым уменьшить степень его неопределенности. Для того чтобы состояние события $ A_{} $ могло сказаться на последующем событии $ B_{} $, необходимо, чтобы это состояние не было известно заранее; поэтому $ A_{} $ можно рассматривать как вспомогательное событие, также имеющее несколько допустимых состояний. Тот факт, что осуществление $ A_{} $ уменьшает степень неопределенности $ B_{} $, находит свое отражение в том, что условная энтропия $ H_A(B) $ события $ B_{} $ при условии выполнения события
$ A_{} $ оказывается не больше первоначальной энтропии $ H(B) $ того же события. При этом, если событие $ B_{} $ не зависит от $ A_{} $,
то $ H_A(B)=H(B) $; если же состояние события $ A_{} $ полностью предопределяет событие $ B_{} $, то $ H_A(B)=0 $. Таким образом, разность
$$ I(A,B)=H(B)-H_A(B) $$
указывает, насколько осуществление события $ A_{} $ уменьшает неопределенность $ B_{} $, т.е. сколько нового мы узнаем о событии $ B_{} $, осуществив событие $ A_{} $. Эту разность называют количеством информации относительно события $ B_{} $, содержащимся в событии $ A_{} $.

Введенное таким образом определение можно «развернуть», определив энтропию $ H(B) $ события как информацию о событии $ B_{} $, содержащуюся в самом этом событии (поскольку осуществление события $ B_{} $ полностью определяет его исход и, следовательно, $ H_B(B)=0 $), или как наибольшую информацию относительно $ B_{} $, какую только можно иметь. Иными словами, энтропия $ H(B) $ события $ B_{} $ равна той информации, которую мы получаем при осуществлении этого события, т.е. средней информации, содержащейся в состояниях $ U_1,dots, U_m $ события $ B_{} $. Чем больше неопределенность какого-то события, тем бóльшую информацию дает определение его состояния.

Следует также иметь в виду, что информация относительно события $ B_{} $, содержащаяся в событии $ A_{} $, по определению представляет собой среднее значение (математическое ожидание) случайной величины $ { H(B)-H_{S_j}(B) }_{j=1}^n $, связанной с отдельными состояниями $ { S_{j} }_{j=1}^n $ события $ A_{} $; поэтому ее можно назвать средней информацией относительно $ B_{} $, содержащейся в $ A_{} $. Часто может случиться, что при определении состояния какого-либо события $ B_{} $ мы можем по-разному выбирать вспомогательные состояния (опыты, измерения, наблюдения) события $ A_{} $; так, например, при нахождении самого тяжелого груза из заданного набора грузов мы можем в разном порядке сравнивать отдельные грузы.

Информационная избыточность

Задача. Имея сообщение, записанное символами некоторого алфавита $ {S_1,dots,S_n} $, закодировать его наиболее выгодным способом.
Здесь кодирование понимается как процесс перехода от исходного алфавита к некоторому новому $ {U_1,dots,U_m} $, в котором каждому символу $ S_{j} $ однозначно сопоставляется последовательность символов $ (U_{j_1},dots, U_{j_k}) $.
Будем считать кодирование тем более выгодным, чем меньше элементарных сигналов приходится затратить на передачу данного сообщения.

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

Пример. Пусть $ n=10, m=2 $, т.е., к примеру, исходный алфавит, состоящий из цифр $ 0,1,dots, 9 $, мы кодируем двоичным кодом. Кодовая таблица

$$
begin{array}{c|c|c|c|c|c|c|c|c|c}
0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \
hline
0000 & 0001 & 0010 & 0011 & 0100 & 0101 & 0110 & 0111 & 1000 & 1001
end{array}
$$
фактически соответствует переводу десятичных чисел в двоичную систему счисления. С одним только различием: каждый блок кода состоит из $ 4 $-х цифр, разрядов²⁾ , т.е. код является равномерным. Требование равномерности понятно: оно позволяет получателю закодированного сообщения однозначно выделить блоки, соответствующие закодированным символам. Заметим, что вопрос о количестве этих разрядов равносилен задаче о том сколько вопросов, имеющих ответы «да» или «нет» надо задать, чтобы отгадать задуманное целое число среди $ 0,1,dots, 9 $.

Рассмотрим теперь вопрос о выгодности (т.е. экономности) построенного кода. Каждая цифра числового сообщения, записанного в привычной десятичной системе счисления, может принимать одно из десяти значений, т.е. может содержать информацию, равную, самое большее, $ log_2 10 approx 3.32 $ бит. Следовательно, сообщение, состоящее из $ N_{} $ десятичных цифр, может содержать, самое большее, $ N log_2 10 approx 3.32 N $ бит. Каждый разряд закодированного сообщения может принимать одно из двух значений, т.е. может содержать информацию, равную, самое большее $ log_2 2=1 $ биту. Но при использовании рассмотренного нами двоичного кода мы затрачиваем на передачу одного символа алфавита $ 4_{} $ разряда, а на передачу сообщения из $ N_{} $ символов алфавита — $ 4, N $ разрядов. Однако с помощью $ 4, N $ двоичных разрядов можно было бы передать информацию, равную $ 4, N $ бит. Разность $ 4,N-3.32, N=0.68, N $ отражает величину неэкономичности нашего кода. Нетрудно также объяснить, почему предложенный код не будет наиболее экономичным: в нем значения $ 0_{} $ и $ 1_{} $ не являются равновероятными: если в кодируемом сообщении все цифры $ 0,1,dots, 9 $ равновероятны, то в закодированном сообщении $ 0_{} $ будет встречаться в $ 25/15=5/3 $ раз чаще, чем $ 1_{} $. Между тем для того, чтобы последовательность из определенного количества символов $ 0_{} $ и $ 1_{} $ содержала наибольшую информацию, требуется, чтобы все цифры этой последовательности принимали оба значения с одинаковой вероятностью (и были взаимно независимы).

Легко понять, как можно построить более выгодный двоичный код. Разобьем наше сообщение на последовательные пары цифр и будем переводить в двоичную систему счисления не отдельно каждую цифру, к каждое двузначное десятичное число разбиения. Число двоичных разрядов кодовых блоков, требуемое для записи всех двузначных чисел $ 00,01,dots,99 $ равно $ 7_{} $:
$$
begin{array}{c|c|c|c}
0 & 1 & dots & 99 \
hline
0000000 & 0000001 & dots & 1100011
end{array}
$$
При такой схеме кодирования на два символа исходного алфавита тратится $ 7_{} $ бит, а не $ 8_{} $ — как в первой схеме, т.е. для передачи числа из $ N_{} $ десятичных цифр надо передать $ 7, (N+1)/2 approx 3.5 N $ двоичных цифр.

Еще выгоднее было бы разбить передаваемое число на триплеты — блоки из трех цифр. В этом случае «стоимость» кодирования понижается до $ approx 3.33 N $ бит. Выгода от перехода к разбиению сообщения на еще более крупные блоки практически оказывается уже совсем небольшой.
При переходе от триплетов к квадруплетам (блокам из четырех цифр) экономность кодирования даже уменьшается: на передачу последних требуются $ 14 $-тиразрядные двоичные блоки. Тем не менее, применяя разбиение кодируемого $ N_{} $-значного числа на еще более крупные блоки, мы можем еще более «сжать» получаемый двоичный, подойдя максимально близко к значению $ N log_2 10 $.

♦

Эта последняя граница может быть получена и из других соображений — без использования понятия информации. Количество всевозможных
$ N_{} $-буквенных слов, составленных из букв алфавита $ { S_1,dots,S_n } $, равно $ n^N $, количество всевозможных $ k_{} $-разрядных двоичных блоков равно $ 2^k $. Для однозначности кодирования необходимо, чтобы $ 2^k ge n^N $.

Способ кодирования $ k_{} $-разрядными двоичными блоками фактически заключается в том, что мы разбиваем множество всевозможных $ k_{} $-значных чисел на две равные части и числам из одной части сопоставляем первую разрядную цифру равную $ 0_{} $, а числам из второй части — равную $ 1_{} $. Далее, каждая из половинок множества снова разбивается на две равные части, каждой из которых приписывается $ 0_{} $ или $ 1_{} $.

Теорема [Хартли]. Если в заданном множестве $ mathbb S $, состоящем из $ mathfrak N $ элементов:

$$ operatorname{Card}(mathbb S) = mathfrak N $$
выделен какой-то элемент $ U_{} $, о котором заранее известно, лишь что $ U in mathbb S $, то, для того, чтобы найти $ U_{} $ необходимо получить информацию, равную $ log_2 mathfrak N $ бит.

На первый взгляд кажется, что если число букв в исходном алфавите равно $ n_{} $, а в кодирующем алфавите равно $ m_{} $, то число $ log_m n $ характеризует наиболее экономичный код. Однако это утверждение ошибочно. Разумеется, верно, что текст из $ N_{} $ букв $ n_{} $-буквенного алфавита может содержать информацию, самое большее равную $ N log_2 n $ бит, но в действительности такой текст, если только он является осмысленным, никогда такой информации не содержит. Это ясно из свойств энтропии: каждая буква текста может содержать наибольшую информацию $ log_2 n $ бит лишь в том случае, когда все буквы алфавита будут встречаться одинаково часто. Известно, однако, что частоты встречаемости букв o или е во много раз больше частот встречаемости букв ф или щ.

Частота встречаемости букв в обычном (неспециальном) тексте (без учета пробелов) [2]:

a	б	в	г	д	е,ё	ж	з	и	й	к	л	м	н	о	п	р
0.075	0.017	0.046	0.016	0.030	0.087	0.009	0.018	0.075	0.012	0.034	0.042	0.031	0.065	0.110	0.028	0.048
с	т	у	ф	х	ц	ч	ш	щ	ъ,ь	ы	э	ю	я
0.055	0.065	0.025	0.002	0.011	0.005	0.015	0.007	0.004	0.017	0.019	0.003	0.007	0.022

Энтропия достигает своего максимума, если все символы алфавита $ {S_1,dots,S_n} $ независимы и генерируются источником с одинаковой вероятностью. Можно сказать, что в равновероятном алфавите все символы несут максимальную информационную нагрузку. Если же алфавит неравновероятен, то некоторые его символы будут иметь меньшую информационную нагрузку, чем другие. Так, если считать, что в русском алфавите $ 31_{} $ буква (отождествляем е и ё, а также ь и ъ) и все они равновероятны, то
$$ H_0= – sum_{j=1}^{31} 1/31 log_2 (1/31) = log_2 31 approx 4.954 mbox{ бит } . $$
Если учитывать частоты букв в соответствии с приведенной таблицей, то получим:
$$ H_1= – sum_{j=1}^{31} P_j log_2 (P_j) approx 4.460 mbox{ бит } , $$
т.е. средняя информация, приходящаяся на одну букву русского текста, заметно понижается.

Аналогичные результаты справедливы и для других языков.
Если латинский алфавит содержит $ 26_{} $ букв и, следовательно, $ H_0 = log_2 26 approx 4.700 $ бит,
то значения $ H_{1} $ для основных европейских языков приведены в таблице

	английский	французский	немецкий
$ H_{1} $	4.126	3.986	4.096

Однако, даже с учетом частот появления букв в тексте языков, мы все равно получим значение средней удельной информации на единицу текста,
превосходящую фактическое значение этой величины. В самом деле, для русского алфавита, например, информация в $ 4.460 $ бит на одну букву получилась бы, если бы каждая буква текста определялась с помощью извлечения карточки из ящика с перемешанными $ 1000 $ карточками, среди которых на $ 110 $ карточках написана буква о, на $ 87 $ карточках — буква е, и т.д., на $ 2_{} $ карточках — буква ф. Энтропия каждого такого события (извлечения карточки) $ A_1 $ примерно равна $ 4.460 $ бит; если $ [A_1,A_2,dots,A_N] $ обозначают $ N_{} $ последовательных событий³⁾, то
$$ H([A_1, A_2, dots , A_N])= sum_{ell=1}^N H(A_{ell}) approx N cdot 4.460 mbox{ бит } . $$
Однако, появление каждой буквы текста на “естественном” языке не является независимым событием: вероятности появления каждой буквы зависят от предыдущих букв. Так, например, в русском языке после появления гласной буквы, существенно увеличивается вероятность появления согласной; если последняя появившаяся буква ч, то следующей уже никак не может быть ы, ю, или я, а весьма вероятно появление одной из букв
и, е или т. Аналогичные закономерности имеются и во всех других языках. Поэтому, если $ [A_1,A_2] $ — сложное событие, состоящее в последовательном появлении двух, то информация, содержащаяся в этом событии, равна
$$ H([A_1,A_2])=H(A_1)+H_{A_1}(A_2) le H(A_1)+H(A_2) . $$
Среднюю информацию на одну букву следует вычислять как условную энтропию:
$$
H_2=H_{A_1}(A_2)=-sum_{j,ell=1}^n P([S_j,S_{ell}]) log_2 P_{jell} ,
$$
где $ n_{} $ — число букв алфавита, $ P_{jell}= P_{S_j}(S_{ell}) $
— условная вероятность появления буквы $ S_{ell} $, если известно, что непосредственно перед ней стоит буква $ S_{j} $,
а $ P([S_j,S_{ell}]) $ — вероятность появления двухбуквенного сочетания (диграммы) $ [S_j,S_{ell}] $.

Как правило, $ P([S_j,S_{ell}]) ne P([S_{ell},S_j]) $; сочетание ый встречается значительно чаще йы⁴⁾.

Можно переписать последнюю формулу в матричном виде с использованием условных вероятностей.
По правилу умножения вероятностей:
$$
P([S_j,S_{ell}])=P(S_j)P_{S_j}(S_{ell})=P_j P_{jell} .
$$
Составим из условных вероятностей матрицу:
$$
mathfrak P =left[ P_{jk} right]_{j,k=1}^n
$$
— она называется матрицей условных (или переходных) **вероятностей. На ее основе построим матрицу
$$
tilde{mathfrak P}= left[P_{jk} log P_{jk} right]_{j,k=1}^n
left( begin{array}{llll}
P_{11} log P_{11} & P_{12} log P_{12} & dots & P_{1n} log P_{1n} \
dots &&& dots \
P_{n1} log P_{n1} & P_{n2} log P_{n2} & dots & P_{nn} log P_{nn}
end{array} right) ;
$$
В нашем случае — в отличие от общего случая пункта

☞

УСЛОВНАЯ ЭНТРОПИЯ — матрицы $ mathfrak P $ и $ tilde{mathfrak P} $ будут квадратными. В полном соответствии с пунктом

☞

УСЛОВНАЯ ЭНТРОПИЯ можем записать:
$$
H_2=
– (P_1,dots,P_n) tilde{mathfrak P}
left( begin{array}{c}
1 \
vdots \
1
end{array}
right) .
$$

Пример. Обратимся к примеру сокращенного русского языка из букв $ S_1= $и, $ S_2= $м, $ S_3= $о, $ S_4= $т и $ S_5= $пробел, рассмотренному

☞

ЗДЕСЬ. Сделаем сначала «привязку» к только что введенным обозначениям:

$$ P_1=0.219, P_2=0.104, P_3= 0.295, P_4=0.148, P_5=0.234 . $$
Матрица условных вероятностей:
$$
mathfrak P=left[P_{jk}right]_{j,k=1}^5 =
left(
begin{array}{ccccc}
0.170 & 0.130 & 0.144 & 0.065 & 0.491 \
0.259 & 0.029 & 0.231 & 0.111 & 0.370 \
0.204 & 0.116 & 0.268 & 0.206 & 0.206 \
0.161 & 0.077 & 0.523 & 0.052 & 0.187 \
0.304 & 0.113 & 0.356 & 0.227 & 0
end{array} right)
$$
Вычисляем матрицу
$$
tilde{mathfrak P}=left[P_{jk} log_2 P_{jk} right]_{j,k=1}^5 =
left(
begin{array}{ccccc}
-0.435 & -0.383 & -0.403 & -0.256 & -0.504 \
-0.505 & -0.148 & -0.488 & -0.352 & -0.530 \
-0.467 & -0.360 & -0.509 & -0.470 & -0.470 \
-0.424 & -0.285 & -0.489 & -0.222 & -0.452 \
-0.522 & -0.355 & -0.530 & -0.486 & 0
end{array} right) .
$$
Величины энтропий (в битах):
$$ H_0=log_2 5 approx 2.322, H_1=-sum_{j=1}^5 P_j log_2 P_j approx 2.237,
$$
$$
H_2 =
– (P_1,P_2,P_3,P_4,P_5) tilde{mathfrak P}
left( begin{array}{c}
1 \
1 \
1 \
1 \
1
end{array}
right) approx 2.036 . $$

♦

Продолжаем дальнейшее продвижение в намеченном направлении. Если учесть информацию о двух предыдущих буквах текста, то для средней информации на одну букву получается формула:
$$
H_3=H_{A_1A_2}(A_3)=- sum_{j,ell,r=1}^n P([S_j,S_{ell},S_r]) log_2 P_{[S_j,S_{ell}]}(S_r) ,
$$
где $ P([S_j,S_{ell},S_r]) $ — вероятность трехбуквенного сочетания (триграммы) $ [S_j,S_{ell},S_r] $, а
$ P_{[S_j,S_{ell}]}(S_r) $ — условная вероятность появления буквы $ S_r $ после появления биграммы $ [S_j,S_{ell}] $.

Нетрудно понять как строятся величины $ H_M $ при $ M> 3 $. Также понятно, что с возрастанием $ M_{} $ величины $ H_M $ будут убывать, приближаясь к некоторому предельному значению $ H_{infty} $, которое и можно считать теоретическим значением средней удельной информации при передаче длинного текста.

Значения $ H_{M} $ (в битах) для русского⁵⁾ и английского языков⁶⁾:

$ M $	$ 0_{} $	$ 1_{} $	$ 2_{} $	$ 3_{} $
русский	5.000	4.348	3.521	3.006
английский	4.754	4.029	3.319	3.099

Учтя также и статистические данные о частотах появления различных слов в английском языке, Шеннон сумел приблизительно оценить и значения величин $ H_5 $ и $ H_8 $:
$$ H_{5} approx 2.1, H_{8} approx 1.9 . $$

Пример [обезьяна за клавиатурой]. Известна теорема о бесконечных обезьянах: абстрактная обезьяна, ударяя случайным образом по клавишам печатной машинки⁷⁾ в течение неограниченно долгого времени, рано или поздно напечатает любой наперёд заданный текст (например «Войны и мира»). В указанной ссылке приводятся оценки времени наступления этого события. Следующие примеры⁸⁾ показывают, что может произойти, если обезьяна будет бить по клавиатуре специально сконструированной машинки, в которой клавиши соответствуют биграммам, триграммам и т.п. русского языка и при этом размеры клавиш пропорциональны частотам встречаемости в русском языке (а обезьяна будет чаще ударять по большим клавишам).

Картинка в тему

☞

ЗДЕСЬ

Приближения нулевого порядка (символы независимы и равновероятны):

ФЮНАЩРЪФЬНШЦЖЫКАПМЪНИФПЩМНЖЮЧГПМ ЮЮВСТШЖЕЩЭЮКЯПЛЧНЦШФОМЕЦЕЭДФБКТТР МЮЕТ

Приближение первого порядка (символы независимы, но с частотами, свойственными русскому языку):

ИВЯЫДТАОАДПИ САНЫАЦУЯСДУДЯЪЛЛЯ Л ПРЕЬЕ БАЕОВД ХНЕ АОЛЕТЛС И

Приближение второго порядка (частотность диграмм такая же как в русском языке):

ОТЕ ДОСТОРО ННЕДИЯРИТРКИЯ ПРНОПРОСЕБЫ НРЕТ ОСКАЛАСИВИ ОМ Р ВШЕРГУ П

Приближение третьего порядка (частотности триграмм такие же как в русском языке):

С ВОЗДРУНИТЕЛЫБКОТОРОЧЕНЯЛ МЕСЛОСТОЧЕМ МИ ДО

Вместо того, чтобы продолжить процесс приближения с помощью тетраграмм, пентаграмм и т.д., легче и лучше сразу перейти к словарным единицам. Приближение первого порядка на уровне слов⁹⁾: cлова выбираются независимо, но с соответствующими им частотами.

СВОБОДНОЙ ДУШЕ ПРОТЯНУЛ КАК ГОВОРИТ ВСПОМНИТЬ МИЛОСТЬ КОМНАТАМ РАССКАЗА ЖЕНЩИНЫ МНЕ ТУДА ПОНЮХАВШЕГО КОНЦУ ИСКУСНО КАЖДОМУ РЯСАХ К ДРУГ ПЕРЕРЕЗАЛО ВИДНО ВСЕМ НАЧИНАЕТЕ НАД ДВУХ ЭТО СВЕТА ХОДУНОМ ЗЕЛЕНАЯ МУХА ЗВУК ОН БЫ ШЕЮ УТЕР БЕЗДАРНЫХ

Приближение второго порядка на уровне слов. Переходные вероятности от слова к слову соответствуют русскому языку,
но «более дальние» зависимости не учитываются:

ОБЩЕСТВО ИМЕЛО ВЫРАЖЕНИЕ МГНОВЕННОГО ОРУДИЯ К ДОСТИЖЕНИЮ ДОЛЖНОСТЕЙ ОДИН В РАСЧЕТЫ НА БЕЗНРАВСТВЕННОСТИ В ПОЭЗИИ РЕЗВИТЬСЯ ВСЕ ГРЫЗЕТ СВОИ БРАЗДЫ ПРАВЛЕНИЯ НАЧАЛА ЕГО ПОШЛОЙ

С каждым проделанным шагом сходство с обычным текстом заметно возрастает. До текста «Войны и мира» осталось совсем немного… ;-)

♦

Уменьшение информационной нагрузки на один символ алфавита вследствие неравновероятности, а также взаимозависимости появления, символов называют избыточностью языка¹⁰⁾. Информационная избыточность рассчитывается по формуле
$$ R_{}= frac{H_0-H_{infty}}{H_0}=1-frac{H_{infty}}{log n} . $$
Величина $ H_0-H_{infty} $ называется недогруженностью алфавита, а отношение $ H_{infty}/H_0 = H_{infty}/log n $ — коэффициентом его оптимальности. Равенство избыточности величине $ 1/L_{} $ огрубленно эквивалентно утверждению о том, что каждая $ L_{} $-я буква алфавита является «лишней», однозначно восстанавливаемой по $ (L-1) $-й предыдущей. Избыточность наиболее распространенных европейских языков близка к $ 1/2 $, т.е., огрубляя, можно утверждать, что в тексте на одном из этих языков можно исключить до 50 % букв с тем, чтобы затем восстановить содержание текста по его оставшейся части.

Как определить величину $ H_M $ и оценить $ H_{infty} $ ? Для малых значений $ M_{} $ еще можно произвести частотный анализ, но вот уже для определения $ H_9 $ требуется знание вероятностей $ 32^9 approx 3.5 cdot 10^{13} $
всех девятибуквенных комбинаций. Шеннон предложил для оценки $ H_M $ использовать экспертное оценивание

☞

ЗДЕСЬ.

Явление избыточности влечет за собой как отрицательные, так и положительные последствия. Отрицательные последствия вызваны тем, что наличие «лишних» символов увеличивает затраты ресурсов при коммуникации. Положительный аспект избыточности заключается в повышении помехоустойчивости процесса коммуникации. Наличие высокой избыточности естественных языков позволяет понимать речь при значительных дефектах произношения, смене диалектов, а тексты — при лингвистических ошибках, сокращении слов и плохом почерке. См. также по этому поводу феномены Глокой куздры и Пушистых браздов.

Код Шеннона – Фано

Для понимания материалов настоящего пункта крайне желательно ознакомиться с материалами пункта

☞

ПРЕФИКСНЫЕ КОДЫ.

Для решения задачи наиболее экономичного кодирования приходится расширять алфавит. Поясню эту фразу. Если считать, что «исходный» алфавит состоит из символов $ S_1,dots,S_{n} $, то рассуждения из начала предыдущего пункта показывают, что уже переход к алфавиту, состоящему из набора биграмм $ {[S_j,S_{ell}]}_{j,ell=1}^n $ с последующим кодированием двоичным кодом может существенно снизить «стоимость» кодирования текста. А соображения предыдущего пункта позволят еще больше сэкономить — но, правда, при наличии дополнительной информации о новом алфавите — информации о частоте встречаемости каждой из биграмм в кодируемом тексте. Требование равномерности кода (одинакового количества разрядов в кодовых словах) снимается и в кодовую таблицу допускаются кодовые наборы с варьируемым количеством разрядов. Основным принципом кодирования становится:

чаще встречаемость – короче кодовая последовательность.

Реализация последнего принципа возможна различными способами. Исторически первым является кодирование по методу Шеннона-Фано. Чтобы не вводить новых обозначений, будем считать что алфавит состоит из «букв» $ S_1,dots,S_{n} $, при этом каждая «буква» может быть произвольным символом или набором символов, например: $ S_1 = $

в

, $ S_2 $=

о

с

, $ S_3 = 210 $ Д, $ S_4 = $

शब्द

, $ S_5=sqrt[3]{int_{3}^{-5} sin x^{2y} d, x} $,… лишь бы только алфавит был «полон» («покрывал» весь текст) и не «переполнен» (включенные в него символы реально в тексте присутствовали). И главное требование: частоты встречаемости «букв» в тексте должны быть нам известны. Для кодирования этих «букв» бинарным кодом ранжируем «буквы» по частоте встречаемости и разбиваем алфавит
$ {S_1,S_2,dots,S_n } $ на два подмножества, по возможности, равной вероятности. «Буквам» из одного подмножества ставим в соответствие $ 0_{} $, из второго — $ 1_{} $. Это — первые разряды соответствующих кодовых последовательностей. Далее процесс повторяется для каждого из подмножеств — производится деление их на подмножества по возможности равной вероятности с последующим присвоением им номера $ 0_{} $ или $ 1_{} $. Процесс заканчивается когда в каждом из образовавшихся подмножеств не останется ровно по одной «букве». В результате каждая из них получает свой индивидуальный бинарный «номер» — то есть, кодировку.

Пример. Рассмотрим пример с кодированием $ 10_{} $ букв русского алфавита с частотами, полученными на основании искусственного текста, созданного ☞ ЗДЕСЬ.

	е	и	а	в	д	к	з	б	г	ж	всего
количество	236	231	195	111	94	94	46	42	40	30	1119
вероятность	0.211	0.206	0.174	0.099	0.084	0.084	0.041	0.038	0.036	0.027

Множество этих букв разобьем на два подмножества, (примерно) одинаковые по вероятности. Например, суммарная вероятность букв е,
и, д равна $ 0.51 $. Так что два образуемых подмножества: $ { mbox{ е, } mbox{ и, } mbox{ д } } $ и
$ { mbox{ а, } mbox{ б, } mbox{ г, } mbox{ в, } mbox{ ж, } mbox{ к, } mbox{ з } } $. Каждое из этих подмножеств снова разобьем на два подмножества (примерно) одинаковые по вероятности. Первое подмножество делится плохо, но что поделать — делим как получится! Продолжаем процесс деления пока не дойдем в таких разбиениях до отдельных букв. Последовательность построения схемы разбиения приведена на рисунке.

Оформляем эту схему в виде дерева и, идя от корня к листьям, нумеруем ветви после каждого узла (точки ветвления): верхней даем номер $ 0_{} $, а нижней — номер $ 1_{} $.

Результатом оказывается кодовая таблица

е	и	д	а	б	г	в	ж	к	з
00	010	011	100	1010	1011	1100	1101	1110	1111

Стоимость кодирования текста по такой таблице равна
$$ 236cdot 2+231cdot 3+94 cdot 3+195 cdot 3+42 cdot 4+40 cdot 4+111 cdot 4+30 cdot 4+94 cdot 4+46 cdot 4=3423 mbox{ бит, } $$
то есть, в среднем, $ 3.11_{} $ бит на букву. Это неплохое достижение, но оно всё-таки хуже полученного использованием кода Хаффмана, также основанного на частотном анализе букв алфавита.

♦

Сходство кода Шеннона-Фано с кодом Хаффмана проявляется и в алгоритмах построения обоих кодов, только направление построения кодового дерева меняется на противоположное: от корня к листьям. Так же как и код Хаффмана, код Шеннона-Фано относится к префиксным кодам: ни одно его кодовое слово не совпадает с начальным отрезком какого-то другого кодового слова. И при всех при этих сходствах, код Шеннона-Фано менее экономичен, чем код Хаффмана и поэтому практически не используется.

Алгоритм построения кода Шеннона-Фано основан на решении задачи из раздела computer science, известной как partition problem: для заданного конечного набора $ mathbb S $ чисел¹¹⁾ требуется найти такое разбиение его на два набора $ mathbb S_1 $ и $ mathbb S_2 $, чтобы разность между суммами чисел составляющих наборов была минимальной. Проблема известна как $ NP $-сложная.

А теперь перейдем к фундаментальному результату теории кодирования, связав код Шеннона-Фано с понятием энтропии.

Теорема [Шеннон]. Сообщение из большого количества $ N_{} $ букв алфавита $ {S_1,dots,S_n} $, частоты встречаемости которых в сообщении заданы таблицей:

$$
begin{array}{l|l|l|l}
S_1 & S_2 & dots & S_n \
hline
P_1 & P_2 & dots & P_n
end{array} quad mbox{ при } quad P_1+P_2+dots+P_n=1,
$$
всегда можно закодировать бинарным кодом таким образом, чтобы количество двоичных разрядов в кодовой последовательности было сколь угодно близким к величине
$$Hcdot N quad mbox{ где } quad H=-sum_{j=1}^n P_j log_2 P_j ; $$
но никогда не меньшим ее.

Доказательство (совершенно нестрогое: очень сильная «выжимка» из рассуждений, приведенных в [2]; которые, в свою очередь, тоже не абсолютно строги). Пусть источник сообщений случайным образом генерирует символы из алфавита $ {S_1,dots,S_n} $. Пусть передаваемое сообщение состоит из достаточно большого числа $ N_{} $ символов. Рассмотрим подмножество $ mathbb S $ всевозможных сообщений длины $ N_{} $, в которых количества вхождений символов $ { S_j }_{j=1}^n $ примерно соответствуют указанным вероятностям. Именно, если $ N_j $ — количество вхождений символа $ S_j $, то $ N_j/N approx P_j $. Тогда вероятность вхождения в сообщение всех символов $ S_{j} $ в количестве $ N_{j} $ при $ jin {1,dots,n} $, в соответствии с теоремой об умножении вероятностей, равна
$$ P_1^{N_1} P_2^{N_2}times dots times P_n^{N_n} approx P_1^{N, P_1} P_2^{N,P_2}times dots times P_n^{N,P_n}=underbrace{left(P_1^{P_1}P_2^{P_2} times dots times P_n^{P_n} right)^N}_{=Q} . $$

Строго говоря, здесь надо сослаться на закон больших чисел, но пока не буду с этим заморачиваться.

Будем для простоты считать, что это — вероятность любого сообщения из подмножества $ mathbb S_{} $, т.е. количество элементов во множестве $ mathbb S_{} $ примерно совпадает с $ 1/Q $:
$$ mathfrak N = operatorname{Card} (mathbb S) approx 1/Q . $$
Сколько стоит найти один-единственный элемент этого множества: как найти во множестве $ mathbb S $ какое-то конкретное сообщение — не просто состоящее из нужных букв в требуемом количестве — но, например, определяющее осмысленный текст? В соответствии с теоремой Хартли, это число
$$ approx log_2 mathfrak N approx – N cdot left(P_1 log_2 P_1+P_2 log_2 P_2+dots+ P_n log_2 P_n right) mbox{ бит.} $$

♦

Теперь обсудим полученный результат. Итак, «на входе» имеем документ — самый произвольный, содержащий возможно осмысленный, но не обязательно нам понятный текст (он записан на неизвестном языке, содержит специфические символы из неизвестной нам научной отрасли и т.п.). Наша цель — закодировать его бинарным кодом, с тем, чтобы иметь возможность передать по каналу связи. Первое, что мы делаем — строим алфавит. Слово «алфавит» понимается в том смысле, что упомянут в начале пункта. Пытаемся, по-возможности, определять часто повторяющиеся блоки — их будем включать в состав алфавита целиком, как отдельные «буквы». Стоп.

Стоп!

— Что же получается: для каждого документа — делать свой отдельный алфавит?! :-O — Вообще говоря, да¹²⁾. Другое дело, что если этот документ не единствен, а предполагается коммуникация целой серии документов, и эти документы написаны на одном языке, и в них содержится разве лишь строго ограниченное количество специальных символов,… — и вот при всех при этих обстоятельствах имеет смысл предварительным анализом составить алфавит общий для всех документов. После того как алфавит создан, вычисляем частоты вхождений составляющих его букв в исходный документ. Кодируем по методу Шеннона-Фано. Кодовую таблицу храним в надежном файле и передаем адресату (на бумажном (электронном) носителе при личной встрече, курьером, по электронной почте и т.п.). И что у нас имеется для оценки стоимости кодирования нашего документа? — Оценка снизу для количества бит на букву: $ H_{} $. Что такое $ H_{} $? — Энтропия случайного события, состоящего в появлении в тексте букв алфавита при известных их вероятностях (т.е. как если бы случайный источник генерировал буквы алфавита независимо друг от друга, но с частотами, примерно соответствующими их вероятностям). Хорошо подобрали алфавит, каждый документ — достаточно длинный, этих документов много — тогда, в среднем, результаты нашего кодирования не должны слишком уж сильно превосходить этой величины. Сколько это: «слишком сильно»? — Решает заказчик. Если ему хочется улучшить результат — придется увеличивать алфавит. Но тогда решение одной проблемы приведет к появлению другой…

Пример. Обратимся к рассмотренному

☞

ЗДЕСЬ примеру сокращенного русского языка

	и	м	о	т	пробел
$ P_{} $	0.219	0.104	0.295	0.148	0.234

Для алфавита, состоящего из этих букв, с указанными в таблице вероятностями
величина энтропии $ H approx 2.237 $. Следовательно, кодирование приведенного ЗДЕСЬ текста из $ 1050 $ букв по теореме Шеннона оценивается в $ 2349 $ двоичных разряда. Код Шеннона-Фано для этого алфавита имеет вид

и	м	о	т	пробел
11	010	10	011	00

и точная стоимость кодирования — $ 2364 $ разряда.

Если же перейти к алфавиту, составленному из биграмм

	ии	им	ио	ит	и_	ми	мм	мо	мт	м_	ои	ом	оо	от	о_	ти	тм	то	тт	т_
$ hat P $	0.037	0.028	0.031	0.014	0.108	0.027	0.003	0.024	0.011	0.038	0.060	0.034	0.079	0.061	0.061	0.024	0.011	0.077	0.008	0.028
	_и	_м	_o	_т	__
$ hat P $	0.071	0.027	0.084	0.053	0.000

то код Хаффмана этого алфавита (уже из $ 25_{} $ «букв») имеет вид

ии	им	ио	ит	и_	ми	мм	мо	мт	м_	ои	ом	оо	от	о_	ти	тм	то	тт	т_
11000	10001	10100	010001	000	01101	0010100	00100	010000	11001	0101	10101	1110	0111	1001	01001	001011	1101	0010101	10000
_и	_м	_o	_т
1011	01100	1111	0011

и стоимость кодирования текста, разбитого на $ 525 $ биграмм по схеме

Ои

|

то

|

ми

|

и_

|

о_

|

им

|

и_

|

оо

|

ои

|

тм

|

и_

|

о_

|

о_

|

о_

|

оо

|

ии

|

им

|

то

|

ми

|

им

|

от

|

ои

|

м_

|

…

будет равна $ 2193 $ бит. Величина энтропии $ H approx 2.036 $ бит и теорема Шеннона дает оценку в $ 2138 $ двоичных разрядов.

♦

Пропускная способность канала связи

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

Предполагаем, что по каналу связи передается последовательность бит (т.е. $ 0_{} $ или $ 1_{} $), задающая символы (или буквы некоторого алфавита) $ S_{1},dots, S_n $. Предполагается, что символ $ S_j $ представлен набором из $ t_{j} $ двоичных сигналов. На передачу по каналу связи каждого информационного двоичного сигнала тратится некоторая единица времени. Исходя из этого будем говорить о сигнале $ S_j $
как имеющем длительность $ t_{j} $.

Пример. Шеннон рассматривает пример из телеграфии, где имеется всего $ 4_{} $ «символа алфавита»:

точка, создаваемая замыканием линии на $ 1_{} $ единицу времени и последующим размыканием на $ 1_{} $ единицу времени;

тире, создаваемая замыканием на $ 3_{} $ единицы времени и последующим размыканием на $ 1_{} $ единицу;

пробел между буквами¹³⁾, создаваемый размыканием линии на $ 3_{} $ единицы времени;

пробел между словами, создаваемый размыканием линии на $ 6_{} $ единиц времени.

Если заменить слова «замыкание линии» на $ 1_{} $, а «размыкание линии» — на $ 0_{} $, то получим двоичную кодировку алфавита

$ mathfrak C ( $

точка

$ )=10 $,
$ mathfrak C ( $

тире

$ )=1110 $,
$ mathfrak C ( $

пробел между буквами

$ )=000 $,

$ mathfrak C ( $

пробел между словами

$ )=000000 $.

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

SOS

=

••• − − − •••

$ = 101010000111011101110000101010000000 $

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

♦

Пропускная способность канала связи без помех задается формулой
$$ C=lim_{Tto infty} frac{log_2 N(T)}{T} . $$
Здесь $ N(T) $ — число сигналов длительности $ T_{} $. Очевидно, что $ N(T)le 2^T $.
Пусть все символы алфавита $ S_1,dots,S_n $ допустимы и имеют длительности $ t_1,dots,t_n $.
Если $ N(t) $ число сигналов длительности $ t_{} $, то справедлива следующая формула:
$$ N(t)=N(t-t_1)+N(t-t_2)+dots+N(t-t_n) . $$
Последняя формула представляет тот очевидный факт, что концом любого сигнала длительности $ t_{} $ должен быть один из символов множества $ {S_{j}}_{j=1}^n $ (или набор этих символов).

Эта формула определяет линейное разностное уравнение порядка
$$ tau= max_{jin {1,dots,n}} t_j . $$
Его общее решение может быть явно выражено через корни уравнения
$$ 1= lambda^{-t_1}+lambda^{-t_2}+dots+lambda^{-t_n} . $$
Это уравнение — домножением на $ lambda^{tau} $ — может быть преобразовано в характеристический полином разностного уравнения.
Предположив, для простоты рассуждений, что все корни этого полинома $ lambda_1,dots,lambda_{tau} $ различны, получим общее решение разностного уравнения в виде
$$ N(t)=C_1lambda_1^t+C_2lambda_2^t+dots+C_{tau}lambda_{tau}^t $$
при величинах $ C_1,C_2,dots,C_{tau} $, не зависящих от $ t_{} $.
Тогда если через $ lambda_{ast} $ обозначить максимальный по модулю корень полинома:
$$ | lambda_{ast} | =max_{jin{1,dots,tau}} | lambda_j | , $$
то
$$ lim_{Tto infty} frac{log_2 N(T)}{T} = lim_{Tto infty} frac{log_2 C_{ast} lambda_{ast}^T }{T} = log_2 lambda_{ast} . $$

Тут надо бы проверить несколько предположений, например, что максимальный по
модулю корень характеристического полинома единствен — тогда, хотя бы, он обязательно будет веществен. Пока могу с определенностью утверждать, что при $ nge 2 $ у этого полинома все корни по модулю не превосходят $ 2_{} $ (см. ☞ теорему Маклорена ),что существует единственный положительный вещественный корень (см. ☞ правило знаков Декарта ), и что этот корень лежит в интервале $ ]1,2[ $. Еще одно преположение, нуждающееся в обосновании: коэффициент $ C_{ast} $ не должен равняться нулю,… Но поскольку сам Шеннон не заморачивался такими мелочами, то и я пока не буду.

Пример. Для рассмотренного выше «телеграфного» примера имеем разностное уравнение в виде

$$ N(t)=N(t-2)+N(t-4)+N(t-5)+N(t-7)+N(t-8)+N(t-10) . $$
Это уравнение имеет порядок $ 10_{} $, его характеристический полином
$$ lambda^{10}=lambda^{8}+lambda^{6}+lambda^{5}+lambda^{3}+lambda^{2}+1 $$
имеет максимальный по модулю корень $ lambda_{ast} approx 1.453 $. Таким образом,
пропускная способность канала равна $ approx 0.539 $.

♦

Пусть символы алфавита имеют вероятности появления в любом месте сообщения, заданные таблицей
$$
begin{array}{l|l|l|l}
S_1 & S_2 & dots & S_n \
hline
P_1 & P_2 & dots & P_n
end{array} quad mbox{ при } quad P_1+P_2+dots+P_n=1.
$$
Тогда при отсутствии помех сообщение по линии связи может быть передано со скоростью сколь угодно близкой к
$$ v=C/H quad mbox{ букв } / mbox{ единица времени } , $$
где $ C_{} $ — пропускная способность линии связи, а $ H=-sum_{j=1}^n P_j log_2 P_i $ — энтропия одной буквы передаваемого сообщения; однако скорость передачи, превосходящая $ v_{} $ никогда не может быть достигнута.

При наличии помех в линии связи дело будет обстоять иначе. В этом случае только наличие избыточности в передаваемой последовательности сигналов может помочь нам точно восстановить переданное сообщение по принятым данным. Ясно, что использование кода, приводящего к наименьшей избыточности закодированного сообщения здесь уже нецелесообразно и скорость передачи сообщения должна быть уменьшена. Насколько уменьшена?

Для ответа на этот вопрос придется предварительно описать линию связи с помехами. Пусть линия связи использует $ m_{} $ различных элементраных сигналов $ A_1,A_2,dots,A_m $, но из-за наличия помех переданный сигнал $ A_j $ может оказаться по выходе из канала каким-то другим сигналом $ A_k $; пусть известна вероятность этого события $ hat P_{jk}^{} $. Из этих вероятностей можно составить квадратную матрицу
$$
hat{mathfrak P} =
left( begin{array}{llll}
hat P_{11} & hat P_{12} & dots & hat P_{1m} \
hat P_{21} & hat P_{22} & dots & hat P_{2m} \
dots & & & dots \
hat P_{m1} & hat P_{m2} & dots & hat P_{mm}
end{array}
right)
$$

Предположим, для простоты, что по линии связи передается два элементарных сигнала — $ A_1=0 $ и $ A_{2}=1 $ (и на выходе канала связи других сигналов быть не может). Предположим, что вероятность безошибочного приема любого из передаваемых сигналов равна $ 1-p_{} $, а вероятность ошибки равна $ p_{} $. Можно составить матрицу переходных вероятностей:
$$
begin{array}{l}
\
A_1 \
A_2
end{array}
begin{array}{l}
begin{array}{llll}
& & A_{1} & A_{2}
end{array} \
left(begin{array}{cc}
1-p & p \
p & 1-p
end{array}
right)
end{array}
$$
Пусть $ P(A_{j}) $ — вероятность того, что передаваемым сигналом является $ A_{j} $, имеем: $ P(A_1)+P(A_2)=1 $.
Опыт $ B_{} $, заключающийся в выяснении того, какой сигнал передается, будет иметь энтропию
$$ H(B)=-P(A_{1}) log P(A_1) – P(A_2) log P(A_{2}) . $$
Опыт $ A_{} $, заключающийся в выяснении того, какой именно сигнал при этом будет принят на выходе, является опытом
с двумя исходами, зависящими от опыта $ B_{} $. Условные энтропии
$$ H_{A_1}(B)=-(1-p) log (1-p)-p log p,quad H_{A_2}(B)=-p log p – (1-p) log (1-p) $$
оказываются одинаковыми и
$$ H_{A}(B)=P(A_1) H_{A_1}(B) + P(A_2) H_{A_2}(B)=-(1-p) log (1-p)-p log p_{} $$
независимо от величин вероятностей $ P(A_{1}), P(A_{2}) $.

Статья не закончена!

Источники

[1]. Шеннон К. Математическая теория связи. (Shannon C.E. A Mathematical Theory of Communication. Bell System Technical Journal. — 1948. — Т. 27. — С. 379-423, 623–656.)

[2]. Яглом А.М., Яглом И.М. Вероятность и информация. М. Наука. 1973.

Источник

«Информация есть форма жизни», — писал американский поэт и эссеист Джон Перри Барлоу. Действительно, мы постоянно сталкиваемся со словом «информация» — ее получают, передают и сохраняют. Узнать прогноз погоды или результат футбольного матча, содержание фильма или книги, поговорить по телефону — всегда ясно, с каким видом информации мы имеем дело. Но что такое сама информация, а главное — как ее можно измерить, никто обычно не задумывается. А между тем, информация и способы ее передачи — важная вещь, которая во многом определяет нашу жизнь, неотъемлемой частью которой стали информационные технологии. Научный редактор издания «Лаба.Медиа» Владимир Губайловский объясняет, что такое информация, как ее измерять, и почему самое сложное — это передача информации без искажений.

Читайте «Хайтек» в

Пространство случайных событий

В 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.

Клод Элвуд Шеннон — американский инженер, криптоаналитик и математик. Считается «отцом информационного века». Основатель теории информации, нашедшей применение в современных высокотехнологических системах связи. Предоставил фундаментальные понятия, идеи и их математические формулировки, которые в настоящее время формируют основу для современных коммуникационных технологий.

В 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, 011000, 101000, 110000, 111100, 111010, 111001.

При передаче слова 001110 может получиться любое из слов:

2) 001110, 101110, 011110, 000110, 001010, 001100, 001111.

Наконец, для 100011 у нас может получиться на приеме:

3) 100011, 000011, 110011, 101011, 100111, 100001, 100010.

Заметим, что все три списка попарно не пересекаются. Иными словами, если на другом конце канала связи появляется любое слово из списка 1, получатель точно знает, что ему передавали именно слово 111000, а если появляется любое слово из списка 2 — слово 001110, а из списка 3 — слово 100011. В этом случае говорят, что наш код исправил одну ошибку.

Исправление произошло за счет двух факторов. Во-первых, получатель знает весь «словарь», то есть пространство событий получателя сообщения совпадает с пространством того, кто сообщение передал. Когда код передавался всего с одной ошибкой, выходило слово, которого в словаре не было.

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

Избыточность такого кодирования очень велика, а количество слов, которые мы можем таким образом передать, сравнительно невелико. Нам ведь надо исключать из словаря любое слово, которое может при ошибке совпасть с целым списком, соответствующим передаваемым словам (например, в словаре не может быть слов «дочка» и «точка»). Но точная передача сообщения настолько важна, что на исследование помехоустойчивых кодов тратятся большие силы.

Сенсация

Понятия энтропии (или неопределенности и непредсказуемости) сообщения и избыточности (или предопределенности и предсказуемости) очень естественно соответствуют нашим интуитивным представлениям о мере информации. Чем более непредсказуемо сообщение (тем больше его энтропия, потому что меньше вероятность), — тем больше информации оно несет. Сенсация (например, встреча с крокодилом на Тверской) — редкое событие, его предсказуемость очень мала, и потому велика информационная стоимость. Часто информацией называют новости — сообщения о только что произошедших событиях, о которых мы еще ничего не знаем. Но если о случившемся нам расскажут второй и третий раз примерно теми же словами, избыточность сообщения будет велика, его непредсказуемость упадет до нуля, и мы просто не станем слушать, отмахиваясь от говорящего со словами «Знаю, знаю». Поэтому СМИ так стараются быть первыми. Вот это соответствие интуитивному чувству новизны, которое рождает действительно неожиданное известие, и сыграло главную роль в том, что статья Шеннона, совершенно не рассчитанная на массового читателя, стала сенсацией, которую подхватила пресса, которую приняли как универсальный ключ к познанию природы ученые самых разных специальностей — от лингвистов и литературоведов до биологов.

Но понятие информации по Шеннону — строгая математическая теория, и ее применение за пределами теории связи очень ненадежно. Зато в самой теории связи она играет центральную роль.

Семантическая информация

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

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

Еще недавно казалось, что мы ничего не можем сделать, чтобы хоть как-то приблизиться к измерению осмысленности текста, но в последние годы ситуация начала меняться. И связано это прежде всего с применением искусственных нейронных сетей к задачам машинного перевода, автоматического реферирования текстов, извлечению информации из текстов, генерированию отчетов на естественном языке. Во всех этих задачах происходит преобразование, кодирование и декодирование осмысленной информации, заключенной в естественном языке. И постепенно складывается представление об информационных потерях при таких преобразованиях, а значит — о мере осмысленной информации. Но на сегодняшний день той четкости и точности, которую имеет шенноновская теория информации, в этих трудных задачах еще нет.

Источник

Формальные определения[править | править код]

Определение по Шеннону[править | править код]

Определение с помощью собственной информации[править | править код]

Единицы измерения информационной энтропии[править | править код]

Свойства[править | править код]

Математические свойства[править | править код]

Эффективность[править | править код]

Вариации и обобщения[править | править код]

b-арная энтропия[править | править код]

Условная энтропия[править | править код]

Взаимная энтропия[править | править код]

История[править | править код]

Примечания[править | править код]

См. также[править | править код]

Ссылки[править | править код]

Литература[править | править код]

Формальные определения

Условная энтропия

Взаимная энтропия

Свойства

Альтернативное определение

Эффективность

История

Литература

См. также

Внешние ссылки

Энтропия источника дискретных сообщений

Содержание

Теория информации по Шеннону

Энтропия

Свойства энтропии

Условная энтропия

Понятие об информации

Информационная избыточность

Код Шеннона – Фано

Пропускная способность канала связи

Источники

Читайте «Хайтек» в

Пространство случайных событий

Энтропия по Шеннону

Кодирование

Сообщения на естественном языке

Избыточность естественного языка

Оцифровка сигнала

Помехоустойчивое кодирование. Коды Хэмминга

Сенсация

Семантическая информация

Вам также может понравиться

Как составить рассказ про свою семью по немецкому

Как найти значения для функции гаусса

Как найти есть ли ипотека

Добавить комментарий Отменить ответ