Количество информации - NiNa.Az

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

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

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

В случае равновероятных символов источника информационная энтропия рассчитывается по формуле Хартли:

${\displaystyle H=\log _{r}(M)}$,

где ${\displaystyle M}$ — мощность (основание, объём) алфавита (количество различных символов алфавита), ${\displaystyle H}$ — количество информации в каждом символе. В общем случае, основание логарифма в определении энтропии может быть любым, большим 1 (так как алфавитом, состоящим только из одного символа, нельзя передавать информацию). Выбор основания логарифма определяет единицу измерения информации. Для информационных систем, основанных на двоичной системе счисления, единицей информации является двоичный символ — бит и основание логарифма ${\displaystyle r=2}$. В этом случае энтропия называется двоичной энтропией. В задачах математической статистики более удобным может оказаться применение натурального логарифма (${\displaystyle r=e}$), в этом случае единицей измерения информации является нат.

Для случайной величины ${\displaystyle A}$, принимающей ${\displaystyle M}$ независимых случайных значений ${\displaystyle a_{i}}$ с вероятностями ${\displaystyle p(a_{i})=p_{i}}$ (${\displaystyle i=1,...M}$), для энтропии используется формула Шеннона:

${\displaystyle H=-\sum _{i=1}^{M}p_{i}\log _{2}p_{i}.}$

Здесь

${\displaystyle (-\log _{2}p_{i})}$ означает измеряемое в битах количество информации, содержащейся в том событии, что случайная величина приняла значение ${\displaystyle a_{i}}$ (для предложений на русском языке — количество информации, содержащейся в конкретной букве, имеющей номер ${\displaystyle i}$ в русском алфавите, ${\displaystyle i=1,\ldots ,33}$),

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

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

В случае марковского источника ${\displaystyle n}$-го порядка, когда условная вероятность появления текущего символа ${\displaystyle a_{i}}$ зависит только от ${\displaystyle n}$ предыдущих символов, то есть при наличия вероятностных связей между символами (что имеет место в текстовом сообщении), энтропия источника определяется по формуле:

${\displaystyle H=-\sum _{q=1}^{Q}\sum _{i=1}^{M}P(q)p_{q}(a_{i})\log _{2}p_{q}(a_{i})=-\sum _{q=1}^{Q}\sum _{i=1}^{M}p(b_{q},a_{i})\log _{2}p_{q}(a_{i}),}$

где ${\displaystyle P(q)}$ — вероятность ${\displaystyle q}$-го состояния источника, которое определяется ${\displaystyle n}$ символами, предшествующих текущему символу ${\displaystyle a_{i}}$, ${\displaystyle Q}$ — число состояний, ${\displaystyle p_{q}(a_{i})}$ — условная вероятность выбора источником символа ${\displaystyle a_{i}}$ в ${\displaystyle q}$-ом состоянии, ${\displaystyle b_{q}}$ — ${\displaystyle q}$-ая последовательность из ${\displaystyle n}$ символов, предшествующая символу ${\displaystyle a_{i}}$, ${\displaystyle p(b_{q},a_{i})=P(q)p_{q}(a_{i})}$ — вероятность появления последовательности ${\displaystyle b_{q}}$ и ${\displaystyle a_{i}}$.

Клодом Шенноном было уcтановлено, что энтропия английского текста при ${\displaystyle n=100}$ равна 0.6—1.3 бит/символ. Также с помощью экспериментальных оценок установлено, что энтропия русского языка с учетом вероятностных связей между элементами равна 1.4 бит/символ для разговорной речи, 1.19 бит/символ для литературного текста, 0.83 бит/символ для делового текста. Энтропия французского языка с учетом вероятностных связей между элементами равна 1.5, 1.38, 1.22 бит/символ соответственно.

Определение по Шеннону

Клод Шеннон задал требования к измерению энтропии:

1. функция должна быть непрерывной относительно ${\displaystyle p_{i}}$; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
2. в случае, когда все события равновероятны (${\displaystyle p_{i}=1/M,i=1...M}$), увеличение количества событий ${\displaystyle M}$ должно увеличивать значение функции, то есть функция должна быть монотонно возрастающей при увеличении ${\displaystyle M}$;
3. Если выбор распадается на два последовательных выбора, то первоначальное значение функции должна быть взвешенной суммой индивидуальных значений функции.

Эти требования к энтропии ${\displaystyle H}$ можно записать в виде:

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

   ${\displaystyle H\underbrace {\left({\frac {1}{M}},\;\ldots ,\;{\frac {1}{M}}\right)} _{M}<H\underbrace {\left({\frac {1}{M+1}},\;\ldots ,\;{\frac {1}{M+1}}\right)} _{M+1}.}$

3. Для целых положительных ${\displaystyle b_{i}}$, где ${\displaystyle b_{1}+\ldots +b_{k}=M}$, должно выполняться равенство

   ${\displaystyle H\underbrace {\left({\frac {1}{M}},\;\ldots ,\;{\frac {1}{M}}\right)} _{M}=H\left({\frac {b_{1}}{M}},\;\ldots ,\;{\frac {b_{k}}{M}}\right)+\sum _{i=1}^{k}{\frac {b_{i}}{M}}H\underbrace {\left({\frac {1}{b_{i}}},\;\ldots ,\;{\frac {1}{b_{i}}}\right)} _{b_{i}}.}$

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

${\displaystyle H=-K\sum _{i=1}^{M}p_{i}\log _{2}p_{i},}$

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

Шеннон определил, что измерение энтропии (${\displaystyle H=-p_{1}\log _{2}p_{1}-\ldots -p_{M}\log _{2}p_{M}}$), применяемое к источнику информации, может определить требования к пропускной способности канала, необходимой для надёжной передачи информации в виде закодированных двоичных чисел.

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

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

Также можно определить энтропию случайной величины, предварительно введя понятие распределения случайной величины ${\displaystyle A}$, имеющей конечное число значений:

${\displaystyle p(a_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;M,}$

${\displaystyle \sum _{i=1}^{M}p_{i}=1}$

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

${\displaystyle I(a_{i})=-\log _{2}p_{i}.}$

Тогда энтропия определяется как математическое ожидание этой величины:

${\displaystyle H=\mathbb {E} \{I(a_{i})\}=-\sum _{i=1}^{M}p_{i}\log _{2}p_{i}.}$

Единицы измерения информационной энтропии

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

Свойства

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

${\displaystyle H=-2\left({\frac {1}{2}}\log _{2}{\frac {1}{2}}\right)=-\log _{2}{\frac {1}{2}}=\log _{2}2=1}$ бит на одно кидание (при условии его независимости), а количество возможных состояний равно: ${\displaystyle 2^{1}=2}$ возможных состояния (значения) («орёл» и «решка»).

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

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

Свойствами энтропии являются:

1. Неотрицательность: ${\displaystyle H\geq 0}$. Энтропия равна нулю, когда все вероятности ${\displaystyle p_{i}}$, кроме одной, равны нулю, и эта вероятность равна единице.
2. Максимальное значение энтропии равно ${\displaystyle H=\log _{2}(M)}$ и достигается в случае, когда все символы алфавита равновероятны, где ${\displaystyle M}$ — основание алфавита.
3. Энтропия — выпуклая вверх функция распределения вероятностей элементов.
4. Если ${\displaystyle A,\;B}$ имеют одинаковое распределение вероятностей элементов, то ${\displaystyle H(A)=H(B)}$.

Вариации и обобщения

b-арная энтропия

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

${\displaystyle H_{b}=-\sum _{i=1}^{M}p_{i}\log _{b}p_{i}.}$

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

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

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

Условной энтропией (для марковской модели) называется энтропия для алфавита, где известны вероятности появления одного символа ${\displaystyle x_{n+1}}$ после известной последовательности из ${\displaystyle n}$ предыдущих символов ${\displaystyle y_{q}=\{x_{n},x_{n-1},...,x_{1}\}}$:

${\displaystyle H_{n+1}=H(X_{n+1}|X_{n},X_{n-1},...,X_{1})=-\sum _{q=1}^{Q}\sum _{i=1}^{M}p(y_{q},x_{n+1})\log _{2}p_{q}(x_{n+1}),}$

где ${\displaystyle M}$ — основание алфавита, ${\displaystyle y_{q}}$ — ${\displaystyle q}$-ая последовательность из ${\displaystyle n}$ символов, предшествующая символу ${\displaystyle x_{n+1}}$, ${\displaystyle p(y_{q},x_{n+1})}$ — совместная вероятность появления последовательности ${\displaystyle y_{q}}$ и ${\displaystyle x_{n+1}}$, ${\displaystyle p_{q}(x_{n+1})}$ — условная вероятность появления символа ${\displaystyle x_{n+1}}$ после последовательности ${\displaystyle y_{q}}$.

Например, для русского текста без буквы «ё» ${\displaystyle H_{0}=\log _{2}(32)=5}$ (так принимается по определению), ${\displaystyle H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01}$.

При ${\displaystyle n\rightarrow \infty }$ эта условная энтропия называется энтропией текста.

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

	${\displaystyle b_{1}}$	${\displaystyle b_{2}}$	…	${\displaystyle b_{j}}$	…	${\displaystyle b_{M}}$
${\displaystyle a_{1}}$	${\displaystyle p(b_{1}\mid a_{1})}$	${\displaystyle p(b_{2}\mid a_{1})}$	…	${\displaystyle p(b_{j}\mid a_{1})}$	…	${\displaystyle p(b_{M}\mid a_{1})}$
${\displaystyle a_{2}}$	${\displaystyle p(b_{1}\mid a_{2})}$	${\displaystyle p(b_{2}\mid a_{2})}$	…	${\displaystyle p(b_{j}\mid a_{2})}$	…	${\displaystyle p(b_{M}\mid a_{2})}$
…	…	…	…	…	…	…
${\displaystyle a_{i}}$	${\displaystyle p(b_{1}\mid a_{i})}$	${\displaystyle p(b_{2}\mid a_{i})}$	…	${\displaystyle p(b_{j}\mid a_{i})}$	…	${\displaystyle p(b_{M}\mid a_{i})}$
…	…	…	…	…	…	…
${\displaystyle a_{M}}$	${\displaystyle p(b_{1}\mid a_{M})}$	${\displaystyle p(b_{2}\mid a_{M})}$	…	${\displaystyle p(b_{j}\mid a_{M})}$	…	${\displaystyle p(b_{M}\mid a_{M})}$

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

${\displaystyle H(B\mid a_{i})=-\sum _{j}p(b_{j}\mid a_{i})\log _{2}p(b_{j}\mid a_{i}).}$

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

${\displaystyle H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i})=-\sum _{i}p(a_{i})\sum _{j}p(b_{j}\mid a_{i})\log _{2}p(b_{j}\mid a_{i})=-\sum _{i}\sum _{j}p(a_{i},b_{j})\log _{2}p(b_{j}\mid a_{i}).}$

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

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

1. ${\displaystyle H(B|A)\geq 0}$,
2. ${\displaystyle H(B|A)\leq H(B)}$,
3. ${\displaystyle H(B|A)=H(B)}$, в случае, когда символы источников ${\displaystyle B}$ и ${\displaystyle A}$ независимы.
4. ${\displaystyle H(B|A)=0}$, в случае, когда символы источников ${\displaystyle B}$ и ${\displaystyle A}$ полностью зависимы.
5. ${\displaystyle H(B|A)=H(AB)-H(A)}$,
6. ${\displaystyle H(B|AC)\leq H(B|A)}$.

Энтропия объединения

Энтропия объединения (совместная энтропия, энтропия произведения) предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления символов источника) и обозначается ${\displaystyle H(AB)}$, где ${\displaystyle A}$ характеризует передатчик, а ${\displaystyle B}$ — приёмник.

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

${\displaystyle p(a_{1},b_{1})}$	${\displaystyle p(a_{1},b_{2})}$	…	${\displaystyle p(a_{1},b_{j})}$	…	${\displaystyle p(a_{1},b_{M})}$
${\displaystyle p(a_{2},b_{1})}$	${\displaystyle p(a_{2},b_{2})}$	…	${\displaystyle p(a_{2},b_{j})}$	…	${\displaystyle p(a_{2},b_{M})}$
…	…	…	…	…	…
${\displaystyle p(a_{i},b_{1})}$	${\displaystyle p(a_{i},b_{2})}$	…	${\displaystyle p(a_{i},b_{j})}$	…	${\displaystyle p(a_{i},b_{M})}$
…	…	…	…	…	…
${\displaystyle p(a_{M},b_{1})}$	${\displaystyle p(a_{M},b_{2})}$	…	${\displaystyle p(a_{M},b_{j})}$	…	${\displaystyle p(a_{M},b_{M})}$

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

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

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

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

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

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

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

где ${\displaystyle p(a_{i},b_{j})}$ — совместная вероятность того, что символ алфавита ${\displaystyle A}$ примет значение ${\displaystyle a_{i}}$, а символ алфавита ${\displaystyle B}$ примет значение ${\displaystyle b_{j}}$.

Путём несложных преобразований также получаем:

${\displaystyle H(AB)=H(A)+H(B\mid A)=H(B)+H(A\mid B).}$

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

Свойства энтропии объединения:

1. ${\displaystyle H(AB)\leq H(A)+H(B)}$,
2. ${\displaystyle H(AB)=H(A)+H(B)}$, в случае когда символы источников ${\displaystyle B}$ и ${\displaystyle A}$ независимы.
3. ${\displaystyle H(AB)=H(A)=H(B)}$, в случае когда символы источников ${\displaystyle B}$ и ${\displaystyle A}$ полностью зависимы.

Взаимная информация

Основная статья: Взаимная информация

Средняя взаимная информация (взаимная энтропия) определяется через энтропию и условную энтропию как:

${\displaystyle I(A,B)=H(A)-H(A\mid B)}$

Средняя взаимная информация представляет собой среднее количество информации в источнике ${\displaystyle A}$, содержащейся в источнике ${\displaystyle B}$.

Величина ${\displaystyle H(A\mid B)}$ называется средней условной собственной информацией, то есть средним количеством информации в символах источника ${\displaystyle A}$ после получения символов источника ${\displaystyle B}$.

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

${\displaystyle I(A,B)=\sum _{i}\sum _{j}p(a_{i},b_{j})\log _{2}{\frac {p(a_{i}|b_{j})}{p(a_{i})}}}$.

Теоретическое применение

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

Основная статья: Пропускная способность канала

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

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

${\displaystyle C=\max\{R\},}$

где

${\displaystyle R={\frac {I(A,B)}{T_{s}}}=H'(A)-H'(A|B)}$ — скорость передачи информации по дискретному каналу связи,

${\displaystyle I(A,B)=H(A)-H(A|B)}$ — средняя взаимная информация между входными ${\displaystyle A}$ символами канала и выходными ${\displaystyle B}$ символами канала,

${\displaystyle T_{s}}$ — среднее время, затрачиваемое на передачу одного символа.

${\displaystyle H'(A)={\frac {1}{T_{s}}}H(A)}$ — производительность источника сообщений (скорость создания информации), ${\displaystyle H(A)}$ — энтропия источника сообщений.

Величина

${\displaystyle H'(A|B)={\frac {1}{T_{s}}}H(A|B)}$

называется ненадежностью, отнесённой к единице времени, ${\displaystyle H(A|B)}$ является условной энтропией и называется ненадежностью, то есть средним количеством информации, теряемой при передаче информации и являющейся мерой неопределённости принятого символа. Эта величина зависит от вероятности ошибочного приема символов источника.

В случае отсутствия шума ненадежность ${\displaystyle H(A|B)}$ равна нулю, поэтому скорость передачи информации равна производительности источника. Так как максимальное значении энтропии ${\displaystyle H(A)}$ равно ${\displaystyle \log _{2}(M)}$, то пропускная способность дискретного канала без шума равна:

${\displaystyle C={\frac {\log _{2}(M)}{T_{s}}},}$

где ${\displaystyle M}$ — основание алфавита источника.

Так как при равномерном кодировании ${\displaystyle T_{s}=T_{b}\log _{2}(M)}$, где ${\displaystyle T_{b}}$ — длительность бита, то пропускная способность дискретного канала без шума равна скорости передачи битов ${\displaystyle R_{b}=1/T_{b}}$.

Пропускная способность канала c шумом меньше пропускной способности канала без шума.

Теоремы Шеннона

Теорема Шеннона для дискретного канала без шума гласит, что символы источника с производительностью ${\displaystyle H'(A)}$ можно закодировать так, чтобы передавать их сколь угодно точно по дискретному каналу без шума, при условии что ${\displaystyle H'(A)<C}$. Это невозможно, если ${\displaystyle H'(A)>C}$, где

${\displaystyle H'(A)={\frac {H(A)}{T_{s}}}}$ — производительность источника,

${\displaystyle H(A)}$ — энтропия источника,

${\displaystyle T_{s}}$ — среднее время, затрачиваемое на передачу одного символа источника,

${\displaystyle C={\frac {\log _{2}(D)}{T_{c}}}}$ — пропускная способность канала между выходом кодера источника и входом декодера источника,

${\displaystyle T_{c}}$ — длительность кодового символа,

${\displaystyle D}$ — основание кодового алфавита (число различных символов кода).

Теорема Шеннона для дискретного канала c шумом гласит, что символы источника с производительностью ${\displaystyle H'(A)}$ можно закодировать так, чтобы передавать их сколь угодно точно (со сколь угодной малой ненадёжностью) по дискретному каналу с шумом, при условии что ${\displaystyle H'(A)\leq C}$, где ${\displaystyle C}$ — пропускная способность канала. Если ${\displaystyle H'(A)\geq C}$, то можно закодировать источник таким образом, что ненадежность будет меньше чем ${\displaystyle H'(A)-C+\epsilon }$, где ${\displaystyle \epsilon }$ сколь угодно мало. Не существует способа кодирования, обеспечивающего ненадёжность, меньшую чем ${\displaystyle H'(A)-C}$.

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

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

Избыточностью алфавита (языка, информации) называется степень неодинаковости распределения вероятностей различных элементов алфавита (символов источника), а также степень взаимной зависимости элементов алфавита (символов источника), проявляющиеся в уменьшении его энтропии по сравнению с максимальным значением. Таким образом, если алфавит имеет вероятностное распределение, отличное от равномерного, то его энтропия ${\displaystyle H(A)}$, рассчитанная с учетом вероятностных связей между его элементами, отлична от максимального значения, равного ${\displaystyle H_{max}(A)=\log _{2}(M)}$, где ${\displaystyle M}$ — основание алфавита.

Избыточность языка (избыточность информации) определяется по формуле:

${\displaystyle r=1-{\frac {H(A)}{H_{max}(A)}}.}$

Избыточность можно уменьшить с помощью сжатия источника. В случае, когда источник не имеет избыточности (${\displaystyle H(A)=H_{max}(A)}$), то есть вероятности всех символов одинаковы, оптимальным кодированием является равномерное кодирование, при котором каждый символ источника кодируется одинаковым числом битов, равным ${\displaystyle \log _{2}(M)}$. В случае, когда ${\displaystyle H(A)<H_{max}(A)}$ источник имеет избыточность, и равномерное кодирование не является оптимальным, так как требует ${\displaystyle \log _{2}(M)}$ битов для кодирования каждого символа источника. Однако избыточность может быть уменьшена полностью или частично, если при кодировании представлять наиболее вероятные символы короткими последовательностями битов, а менее вероятные — более длинными. В этом случае среднее количество битов, приходящихся на один символ, окажется меньшей, чем в случае равномерного кодирования. Поэтому источник (файл) будет занимать меньший размер, и его символы могут быть переданы по каналу связи более быстро.

Основная теорема кодирования канала без шума гласит, что символы источника с основанием алфавита ${\displaystyle M}$, имеющего энтропию ${\displaystyle H(A)}$, можно так закодировать посредством кодовых символов с основанием алфавита ${\displaystyle D}$, что среднее число кодовых символов на один символ источника ${\displaystyle {\bar {n}}}$ удовлетворяет неравенству:

${\displaystyle {\frac {H(A)}{\log _{2}(D)}}\leq {\bar {n}}<{\frac {H(A)}{\log _{2}(D)}}+\epsilon ,}$

где ${\displaystyle \epsilon }$ — сколь угодно мало.

Это неравенство выполняется в случае, когда символы источника объединяются в группы по ${\displaystyle N}$ символов, и производится кодирование этих групп кодовыми символами, причём величина ${\displaystyle N}$ стремится к бесконечности.

Таким образом, среднее число кодовых символов на один символ источника не может быть сделано меньше, чем ${\displaystyle H(A)/\log _{2}(D)}$. В противном случае, символы источника нельзя достоверно восстановить. Теоретически возможен код, у которого ${\displaystyle {\bar {n}}}$ стремиться к ${\displaystyle H(A)/\log _{2}(D)}$.

Если кодирование производится двоичными кодовыми символами ${\displaystyle D=2}$, то это означает, что при кодировании без потерь среднее число битов, приходящихся на символ источника, может быть сделано очень близким к энтропии источника, которая и является средним количеством информации (битов), приходящееся на символ источника.

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

${\displaystyle r=1-{\frac {H(X)}{H_{max}(X)}},}$

где ${\displaystyle H(X)}$ — энтропия кодовых символов ${\displaystyle X}$, ${\displaystyle H_{max}(X)}$ — максимальное значение энтропии кодовых символов, ${\displaystyle H_{max}(X)=\log _{2}(D)}$, где ${\displaystyle D}$ — основание кодового алфавита (число различных символов кода).

Энтропия источника ${\displaystyle H(A)}$ при однозначном декодировании связана с энтропией кодовых символов ${\displaystyle H(X)}$ по формуле:

${\displaystyle H(A)={\bar {n}}H(X)}$.

Таким образом, формула для избыточности источника после кодирования примет вид:

${\displaystyle r=1-{\frac {H(A)}{{\bar {n}}\log _{2}(D)}}.}$

Следовательно, использование кода, у которого ${\displaystyle {\bar {n}}\rightarrow H(A)/\log _{2}(D)}$, почти полностью устраняет избыточность без потери информации. В этом случае ${\displaystyle H(X)\rightarrow H_{max}(X)}$, то есть кодовые символы должны быть практически равновероятными и независимыми друг от друга.

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

История

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

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

См. также

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

Примечания

1. Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 264.
2. Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 59.
3. Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 26.
4. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 23.
5. Лось А. Б., Нестеренко А. Ю., Рожков М. И. Криптографические методы защиты информации, 2016. — С. 64.
6. Варгаузин В. А., Цикин И. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи, 2013. — С. 18.
7. C. E. Shannon. Prediction and Entropy of Printed English, 1951. — P. 51.
8. Angelo Vulpiani, Roberto Livi. The Kolmogorov Legacy in Physics, 2003. — P. 98.
9. Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 260.
10. Shannon, Claude E. A Mathematical Theory of Communication // ^[англ.]. — 1948. — Июль (т. 27, № 3). — С. 419. — P. 11. — doi:10.1002/j.1538-7305.1948.tb01338.x.
11. Габидулин Э. М., Пилипчук Н. И. Лекции по теории информации — МФТИ, 2007. — С. 16. — 214 с. — ISBN 978-5-7417-0197-3
12. Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 262.
13. Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 56.
14. Cover, T., King, R. A. convergent gambling estimate of the entropy of English, 1978. — P. 413.
15. Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. — № 1. — С. 68—69.
16. Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 60.
17. Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 61.
18. Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 33.
19. Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 32.
20. Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 32—33.
21. Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 36.
22. Кудряшов В. Д. Теория информации, 2009. — С. 107.
23. Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 168.
24. Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 61.
25. Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 65.
26. Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — 136.
27. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 23, 24, 49.
28. Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 277.
29. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 47.
30. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 90.
31. Варгаузин В. А., Цикин И. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи, 2013. — С. 25.
32. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 67.
33. Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 281.
34. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 27.
35. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 70.
36. Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 93—94.
37. Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 94.
38. Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 272.
39. Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 71.

Литература

• Шеннон К. Работы по теории информации и кибернетике. — М.: Издательство иностранной литературы, 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.

Ссылки

• Shannon C. E. A Mathematical Theory of Communication. The Bell System Technical Journal, 1948.
• Коротаев С. М. Энтропия и информация — универсальные естественнонаучные понятия.