Информационная энтропия

Шаблон:Теория информации Информацио́нная энтропи́я — мера неопределённости некоторой системы (в статистической физике или теории информации). Энтропия дискретного источника равна среднему количеству информации, приходящейся на один символ<ref>Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 264.</ref> (сообщение<ref>Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 59.</ref>, элемент<ref>Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 26.</ref><ref>Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 23.</ref>) источника. Характеризует непредсказуемость появления какого-либо символа алфавита.

Например, в последовательности букв, составляющих какое-либо предложение на русском языке, разные буквы появляются с разной частотностью, поэтому неопределённость появления для некоторых букв меньше, чем для других. Если же учесть, что некоторые сочетания букв (в этом случае говорят об энтропии <math>n</math>-го порядка, см. ниже) встречаются очень редко, то рассчитанная энтропия языка уменьшается ещё сильнее<ref name="Лось">Лось А. Б., Нестеренко А. Ю., Рожков М. И. Криптографические методы защиты информации, 2016. — С. 64.</ref>.

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

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

<math>H = \log_r(M)</math>,

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

Для случайной величины <math>A</math>, принимающей <math>M</math> независимых случайных значений <math>a_i</math> с вероятностями <math>p(a_i)=p_i</math> (<math>i=1,...M</math>), для энтропии используется формула Шеннона:

Здесь

<math>(-\log_2 p_i)</math> означает измеряемое в битах количество информации, содержащейся в том событии, что случайная величина приняла значение <math>a_i</math> (для предложений на русском языке — количество информации, содержащейся в конкретной букве, имеющей номер <math>i</math> в русском алфавите, <math>i=1,\ldots,33</math>),

<math>H</math> — среднее количество информации, приходящейся на один символ (для предложений на русском языке — количество информации на одну букву). Эта величина также называется средней энтропией источника. Величина <math>H_i = -\log_2 p_i</math> называется частной энтропией, характеризующей только <math>i</math>-e состояние.

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

В случае марковского источника <math>n</math>-го порядка, когда условная вероятность появления текущего символа <math>a_i</math> зависит только от <math>n</math> предыдущих символов, то есть при наличия вероятностных связей между символами (что имеет место в текстовом сообщении), энтропия источника определяется по формуле<ref name="Варгаузин">Варгаузин В. А., Цикин И. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи, 2013. — С. 18.</ref><ref name="Shannon">C. E. Shannon. Prediction and Entropy of Printed English, 1951. — P. 51.</ref>:

где <math>P(q)</math> — вероятность <math>q</math>-го состояния источника, которое определяется <math>n</math> символами, предшествующих текущему символу <math>a_i</math>, <math>Q</math> — число состояний, <math>p_q(a_i)</math> — условная вероятность выбора источником символа <math>a_i</math> в <math>q</math>-ом состоянии, <math>b_q</math> — <math>q</math>-ая последовательность из <math>n</math> символов, предшествующая символу <math>a_i</math>, <math>p(b_q, a_i)=P(q)p_q(a_i)</math> — вероятность появления последовательности <math>b_q</math> и <math>a_i</math>.

Клодом Шенноном было уcтановлено, что энтропия английского текста при <math>n=100</math> равна 0.6—1.3 бит/символ<ref>Angelo Vulpiani, Roberto Livi. The Kolmogorov Legacy in Physics, 2003. — P. 98.</ref>. Также с помощью экспериментальных оценок установлено, что энтропия русского языка с учетом вероятностных связей между элементами равна 1.4 бит/символ для разговорной речи, 1.19 бит/символ для литературного текста, 0.83 бит/символ для делового текста. Энтропия французского языка с учетом вероятностных связей между элементами равна 1.5, 1.38, 1.22 бит/символ соответственно<ref name="Лось"/>.

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

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

функция должна быть непрерывной относительно <math>p_i</math>; то есть изменение значения величины вероятности на малую величину должно вызывать малое результирующее изменение функции;
в случае, когда все события равновероятны (<math>p_i=1/M, i=1...M</math>), увеличение количества событий <math>M</math> должно увеличивать значение функции, то есть функция должна быть монотонно возрастающей при увеличении <math>M</math>;
Если выбор распадается на два последовательных выбора, то первоначальное значение функции должна быть взвешенной суммой индивидуальных значений функции<ref>Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 260.</ref>.

Эти требования к энтропии <math>H</math> можно записать в виде:

<math>H(p_1,\;\ldots,\;p_M)</math> определена и непрерывна для всех <math>p_1,\dotsc,p_M</math>, где <math>p_i\in[0,\;1]</math> для всех <math>i=1,\dotsc,M</math> и <math>p_1+\dotsb+p_M=1</math>. (Эта функция зависит только от распределения вероятностей, но не от алфавита.)
Для целых положительных <math>M</math>, должно выполняться следующее неравенство:
<math>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}.</math>
Для целых положительных <math>b_i</math>, где <math>b_1+\ldots+b_k=M</math>, должно выполняться равенство
<math>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}.</math>

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

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

Шеннон определил, что измерение энтропии (<math>H=-p_1\log_2 p_1-\ldots-p_M\log_2 p_M</math>), применяемое к источнику информации, может определить требования к пропускной способности канала, необходимой для надёжной передачи информации в виде закодированных двоичных чисел.

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

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

Также можно определить энтропию случайной величины, предварительно введя понятие распределения случайной величины <math>A</math>, имеющей конечное число значенийШаблон:Source-ref:

<math>p(a_i)=p_i,\quad p_i\geqslant 0,\;i=1,\;2,\;\ldots,\;M,</math>

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

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

<math>H=\mathbb{E}\{I(a_i)\}=-\sum_{i=1}^M p_i\log_2 p_i.</math>

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

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

Свойства

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

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

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

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

Свойствами энтропии являются<ref name="Шеннон">Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 262.</ref>:

Неотрицательность: <math>H \geq 0</math>. Энтропия равна нулю, когда все вероятности <math>p_i</math>, кроме одной, равны нулю, и эта вероятность равна единице.
Максимальное значение энтропии равно <math>H = \log_2 (M)</math> и достигается в случае, когда все символы алфавита равновероятны, где <math>M</math> — основание алфавита.
Энтропия — выпуклая вверх функция распределения вероятностей элементов<ref>Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 56.</ref>.
Если <math>A,\;B</math> имеют одинаковое распределение вероятностей элементов, то <math>H(A)=H(B)</math>.

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

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

В общем случае b-арная энтропия (где b равно 2, 3, …) источника <math>\mathcal{S}=(S,\;P)</math> с исходным алфавитом <math>S=\{a_1,\;\ldots,\;a_M\}</math> и дискретным распределением вероятности <math>P=\{p_1,\;\ldots,\;p_M\},</math> где <math>p_i</math> является вероятностью символа <math>a_i</math> (<math>p_i=p(a_i)</math>), определяется формулой:

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

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

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

Условной энтропией (для марковской модели) называется энтропия для алфавита, где известны вероятности появления одного символа <math>x_{n+1}</math> после известной последовательности из <math>n</math> предыдущих символов <math>y_q=\{x_n, x_{n-1},..., x_1\}</math>:

где <math>M</math> — основание алфавита, <math>y_q</math> — <math>q</math>-ая последовательность из <math>n</math> символов, предшествующая символу <math>x_{n+1}</math>, <math>p(y_q, x_{n+1})</math> — совместная вероятность появления последовательности <math>y_q</math> и <math>x_{n+1}</math>, <math>p_q(x_{n+1})</math> — условная вероятность появления символа <math>x_{n+1}</math> после последовательности <math>y_q</math><ref name="Shannon"/><ref>Cover, T., King, R. A. convergent gambling estimate of the entropy of English, 1978. — P. 413.</ref>.

Например, для русского текста без буквы «ё» <math>H_0=\log_2(32)=5</math> (так принимается по определению), <math>H_1=4{,}358,\;H_2=3{,}52,\;H_3=3{,}01</math><ref>Лебедев Д. С., Гармаш В. А. О возможности увеличения скорости передачи телеграфных сообщений. — М.: Электросвязь, 1958. — № 1. — С. 68—69.</ref>.

При <math>n\rightarrow \infty </math> эта условная энтропия называется энтропией текста.

Условную энтропию можно использовать при определении информационных потерь при передаче данных в канале с помехами. Для этого применяются так называемые канальные матрицы. Для описания потерь со стороны источника (то есть известен посланный символ) рассматривают условную вероятность <math>p(b_j\mid a_i)</math> получения приёмником символа <math>b_j</math> при условии, что был отправлен символ <math>a_i</math>. При этом канальная матрица имеет следующий вид:

	<math>b_1</math>	<math>b_2</math>	…	<math>b_j</math>	…	<math>b_M</math>
<math>a_1</math>	<math>p(b_1\mid a_1)</math>	<math>p(b_2\mid a_1)</math>	…	<math>p(b_j\mid a_1)</math>	…	<math>p(b_M\mid a_1)</math>
<math>a_2</math>	<math>p(b_1\mid a_2)</math>	<math>p(b_2\mid a_2)</math>	…	<math>p(b_j\mid a_2)</math>	…	<math>p(b_M\mid a_2)</math>
…	…	…	…	…	…	…
<math>a_i</math>	<math>p(b_1\mid a_i)</math>	<math>p(b_2\mid a_i)</math>	…	<math>p(b_j\mid a_i)</math>	…	<math>p(b_M\mid a_i)</math>
…	…	…	…	…	…	…
<math>a_M</math>	<math>p(b_1\mid a_M)</math>	<math>p(b_2\mid a_M)</math>	…	<math>p(b_j\mid a_M)</math>	…	<math>p(b_M\mid a_M)</math>

Вероятности, расположенные по диагонали, описывают вероятность правильного приёма, а сумма всех элементов любой строки даёт 1. Потери, приходящиеся на передаваемый символ <math>a_i</math>, описываются через частную условную энтропию (условная энтропия источника из принятых символов <math>B</math> при фиксированном переданном символе <math>a_i</math>):

Для вычисления потерь при передаче всех символов используется средняя условная энтропия<ref>Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 60.</ref>:

<math>H(B\mid A)</math> означает энтропию со стороны источника, аналогично рассматривается <math>H(A\mid B)</math> — энтропия со стороны приёмника: вместо <math>p(b_j\mid a_i)</math> всюду указывается <math>p(a_i\mid b_j)</math>.

Свойства условной энтропии<ref name="Фомичёв">Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 61.</ref>:

<math>H(B|A) \geq 0</math>,
<math>H(B|A) \leq H(B)</math>,
<math>H(B|A)=H(B)</math>, в случае, когда символы источников <math>B</math> и <math>A</math> независимы.
<math>H(B|A)=0</math>, в случае, когда символы источников <math>B</math> и <math>A</math> полностью зависимы<ref>Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 33.</ref>.
<math>H(B|A) = H(AB) - H(A)</math>,
<math>H(B|AC) \leq H(B|A)</math>.

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

Энтропия объединения<ref>Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 32.</ref> (совместная энтропия, энтропия произведения) предназначена для расчёта энтропии взаимосвязанных систем (энтропии совместного появления символов источника) и обозначается <math>H(AB)</math>, где <math>A</math> характеризует передатчик, а <math>B</math> — приёмник.

Взаимосвязь переданных и полученных сигналов описывается вероятностями совместных событий <math>p(a_i, b_j)</math>, и для полного описания характеристик канала требуется только одна матрица:

<math>p(a_1, b_1)</math>	<math>p(a_1, b_2)</math>	…	<math>p(a_1, b_j)</math>	…	<math>p(a_1, b_M)</math>
<math>p(a_2, b_1)</math>	<math>p(a_2, b_2)</math>	…	<math>p(a_2, b_j)</math>	…	<math>p(a_2, b_M)</math>
…	…	…	…	…	…
<math>p(a_i, b_1)</math>	<math>p(a_i, b_2)</math>	…	<math>p(a_i, b_j)</math>	…	<math>p(a_i, b_M)</math>
…	…	…	…	…	…
<math>p(a_M, b_1)</math>	<math>p(a_M, b_2)</math>	…	<math>p(a_M, b_j)</math>	…	<math>p(a_M, b_M)</math>

Для более общего случая, когда описывается не канал, а в целом взаимодействующие системы, матрица необязательно должна быть квадратной. Сумма всех элементов столбца с номером <math>j</math> даёт <math>p(b_j)</math>, сумма строки с номером <math>i</math> есть <math>p(a_i)</math>, а сумма всех элементов матрицы равна 1. Совместная вероятность <math>p(a_i, b_j)</math> событий <math>a_i</math> и <math>b_j</math> вычисляется как произведение исходной и условной вероятности:

Условные вероятности производятся по формуле Байеса. Таким образом, имеются все данные для вычисления энтропий источника и приёмника<ref name="Шеннон"/>:

<math>H(A)=-\sum_i\left(\sum_j p(a_i, b_j)\log_2\sum_j p(a_i, b_j)\right),</math>

<math>H(B)=-\sum_j\left(\sum_i p(a_i, b_j)\log_2 \sum_i p(a_i, b_j)\right).</math>

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

где <math>p(a_i, b_j)</math> — совместная вероятность того, что символ алфавита <math>A</math> примет значение <math>a_i</math>, а символ алфавита <math>B</math> примет значение <math>b_j</math>.

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

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

Свойства энтропии объединения<ref name="Фомичёв"/>:

<math>H(AB) \leq H(A)+H(B)</math>,
<math>H(AB) = H(A)+H(B)</math>, в случае когда символы источников <math>B</math> и <math>A</math> независимы.
<math>H(AB) = H(A) = H(B)</math>, в случае когда символы источников <math>B</math> и <math>A</math> полностью зависимы<ref>Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 32—33.</ref>.

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

Шаблон:Main Средняя взаимная информация (взаимная энтропия)<ref>Усенко О. А. Приложения теории информации и криптографии в радиотехнических системах, 2017. — С. 36.</ref> определяется через энтропию и условную энтропию как<ref>Кудряшов В. Д. Теория информации, 2009. — С. 107.</ref>:

Средняя взаимная информация представляет собой среднее количество информации в источнике <math>A</math>, содержащейся в источнике <math>B</math><ref name="Фомичёв_2">Фомичёв В. М. Элементы теории информации в защите информации, 2021. — С. 168.</ref>.

Величина <math>H(A \mid B )</math> называется средней условной собственной информацией, то есть средним количеством информации в символах источника <math>A</math> после получения символов источника <math>B</math><ref>Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 61.</ref>.

Средняя взаимная информация вычисляется по формуле<ref name="Фомичёв_2"/><ref>Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 65.</ref>:

<math>I(A, B)=\sum_i\sum_j p(a_i, b_j)\log_2 \frac{p(a_i|b_j)}{p(a_i)}</math>.

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

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

Шаблон:Main Пропускная способность канала — максимальная скорость передачи информации по каналу связи<ref>Мазор Ю. Л. и др. Энциклопедия Радиотехника, 2002. — 136.</ref>. При этом максимум ищется по всевозможным распределениям вероятностей входных символов канала.

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

где

<math>R = \frac{I(A, B)}{T_s} = H'(A) - H'(A|B)</math> — скорость передачи информации по дискретному каналу связи<ref name="Финк_2">Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 23, 24, 49.</ref>,

<math>I(A, B) = H(A) - H(A|B)</math> — средняя взаимная информация между входными <math>A</math> символами канала и выходными <math>B</math> символами канала,

<math>T_s</math> — среднее время, затрачиваемое на передачу одного символа.

<math>H'(A)=\frac{1}{T_s}H(A)</math> — производительность источника сообщений (скорость создания информации<ref name="Шеннон_1">Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 277.</ref>), <math>H(A)</math> — энтропия источника сообщений.

Величина

называется ненадежностью, отнесённой к единице времени, <math>H(A|B)</math> является условной энтропией и называется ненадежностью, то есть средним количеством информации, теряемой при передаче информации и являющейся мерой неопределённости принятого символа<ref name="Шеннон_1"/><ref>Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 47.</ref>. Эта величина зависит от вероятности ошибочного приема символов источника<ref>Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 90.</ref>.

В случае отсутствия шума ненадежность <math>H(A|B)</math> равна нулю, поэтому скорость передачи информации равна производительности источника. Так как максимальное значении энтропии <math>H(A)</math> равно <math>\log_2(M)</math>, то пропускная способность дискретного канала без шума равна:

где <math>M</math> — основание алфавита источника.

Так как при равномерном кодировании <math>T_s=T_b\log_2(M)</math>, где <math>T_b</math> — длительность бита, то пропускная способность дискретного канала без шума равна скорости передачи битов <math>R_b=1/T_b</math>.

Пропускная способность канала c шумом меньше пропускной способности канала без шума<ref>Варгаузин В. А., Цикин И. А. Методы повышения энергетической и спектральной эффективности цифровой радиосвязи, 2013. — С. 25.</ref>.

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

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

<math>H'(A)=\frac{H(A)}{T_s}</math> — производительность источника,

<math>H(A)</math> — энтропия источника,

<math>T_s</math> — среднее время, затрачиваемое на передачу одного символа источника,

<math>C = \frac{\log_2(D)}{T_c}</math> — пропускная способность канала между выходом кодера источника и входом декодера источника,

<math>T_c</math> — длительность кодового символа,

<math>D</math> — основание кодового алфавита (число различных символов кода)<ref>Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 67.</ref>.

Теорема Шеннона для дискретного канала c шумом гласит, что символы источника с производительностью <math>H'(A)</math> можно закодировать так, чтобы передавать их сколь угодно точно (со сколь угодной малой ненадёжностью) по дискретному каналу с шумом, при условии что <math>H'(A) \leq C</math>, где <math>C</math> — пропускная способность канала. Если <math>H'(A) \geq C</math>, то можно закодировать источник таким образом, что ненадежность будет меньше чем <math>H'(A) - C + \epsilon</math>, где <math>\epsilon </math> сколь угодно мало. Не существует способа кодирования, обеспечивающего ненадёжность, меньшую чем <math>H'(A) - C</math><ref>Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 281.</ref>.

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

Шаблон:Main Избыточностью алфавита (языка, информации) называется степень неодинаковости распределения вероятностей различных элементов алфавита (символов источника), а также степень взаимной зависимости элементов алфавита (символов источника), проявляющиеся в уменьшении его энтропии по сравнению с максимальным значением. Таким образом, если алфавит имеет вероятностное распределение, отличное от равномерного, то его энтропия <math>H(A)</math>, рассчитанная с учетом вероятностных связей между его элементами<ref name="Варгаузин"/>, отлична от максимального значения, равного <math>H_{max}(A)=\log_2(M)</math>, где <math>M</math> — основание алфавита.

Избыточность языка (избыточность информации) определяется по формуле<ref name="Лось"/><ref>Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 27.</ref>:

Избыточность можно уменьшить с помощью сжатия источника. В случае, когда источник не имеет избыточности (<math>H(A)=H_{max}(A)</math>), то есть вероятности всех символов одинаковы, оптимальным кодированием является равномерное кодирование, при котором каждый символ источника кодируется одинаковым числом битов, равным <math>\log_2(M)</math>. В случае, когда <math>H(A) < H_{max}(A)</math> источник имеет избыточность, и равномерное кодирование не является оптимальным, так как требует <math>\log_2(M)</math> битов для кодирования каждого символа источника. Однако избыточность может быть уменьшена полностью или частично, если при кодировании представлять наиболее вероятные символы короткими последовательностями битов, а менее вероятные — более длинными. В этом случае среднее количество битов, приходящихся на один символ, окажется меньшей, чем в случае равномерного кодирования<ref>Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 70.</ref>. Поэтому источник (файл) будет занимать меньший размер, и его символы могут быть переданы по каналу связи более быстро.

Основная теорема кодирования канала без шума гласит, что символы источника с основанием алфавита <math>M</math>, имеющего энтропию <math>H(A)</math>, можно так закодировать посредством кодовых символов с основанием алфавита <math>D</math>, что среднее число кодовых символов на один символ источника <math>\bar{n}</math> удовлетворяет неравенству<ref>Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 93—94.</ref>:

где <math>\epsilon</math> — сколь угодно мало.

Это неравенство выполняется в случае, когда символы источника объединяются в группы по <math>N</math> символов, и производится кодирование этих групп кодовыми символами, причём величина <math>N</math> стремится к бесконечности<ref>Фано Р. М. Передача информации. Статистическая теория связи, 1965. — С. 94.</ref><ref>Шеннон К. Работы по теории информации и кибернетике, 1963. — С. 272.</ref>.

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

Если кодирование производится двоичными кодовыми символами <math>D=2</math>, то это означает, что при кодировании без потерь среднее число битов, приходящихся на символ источника, может быть сделано очень близким к энтропии источника, которая и является средним количеством информации (битов), приходящееся на символ источника.

При использовании кодирования избыточность источника после кодирования вычисляется по формуле<ref name="Финк">Финк Л. М. Теория передачи дискретных сообщений, 1970. — С. 71.</ref>:

где <math>H(X)</math> — энтропия кодовых символов <math>X</math>, <math>H_{max}(X)</math> — максимальное значение энтропии кодовых символов, <math>H_{max}(X)=\log_2(D)</math>, где <math>D</math> — основание кодового алфавита (число различных символов кода).

Энтропия источника <math>H(A)</math> при однозначном декодировании связана с энтропией кодовых символов <math>H(X)</math> по формуле:

<math>H(A)=\bar{n}H(X)</math>.

Таким образом, формула для избыточности источника после кодирования примет вид<ref name="Финк"/>:

Следовательно, использование кода, у которого <math>\bar{n} \rightarrow H(A)/\log_2(D)</math>, почти полностью устраняет избыточность без потери информации. В этом случае <math>H(X) \rightarrow H_{max}(X)</math>, то есть кодовые символы должны быть практически равновероятными и независимыми друг от друга<ref name="Финк"/>.

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

История

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

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

См. также

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

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Внешние ссылки

Информационная энтропия

Содержание

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

История

См. также

Примечания

Литература

Ссылки

Навигация

Информационная энтропия

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

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

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

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

Свойства

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

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

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

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

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

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

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

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

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

История

См. также

Примечания

Литература

Ссылки

Навигация

Поиск