Кодирование

KPi log (1/P1) + ... + KPNlog (1/PN).

Энтропия

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

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

Другая важная концепция теории информации — энтропия. Эта концепция была предложена в 1948 г. основателем теории информации Шенноном (Shannon). Шен­нон определил энтропию как среднее количество информации, получаемое от зна­чения случайной переменной. Предположим, что имеется случайная переменная X, способная принимать значения х₁ х₂,..., x_N, и что соответствующие вероятности каждого исхода равны P(x₁), P(x₂),..., P(x_N). В последовательности из К перемен­ных X результат X_j в среднем будет выбран KP(X_j) раз. Таким образом, среднее ко­личество информации, получаемое от К событий, равно (будем использовать обо­значение P_j для P(x_j)):

Если разделить это выражение на К, то мы получим среднее количество инфор­мации для одного результата случайной переменной, называемое энтропией X и обозначаемое как Н(Х):

Функция Н часто выражается как перечень вероятностей возможных резуль­татов: H(P₁, Р₂, ... , P_n).

Для примера рассмотрим случайную переменную X, принимающую два воз­можных значения с соответствующими вероятностями Р и 1 - Р. В этом случае ас­социированная с X энтропия будет равна:

На рисунке ниже, показан график H(X) для данного случая как функция от Р. По этому графику можно отметить несколько важных особенностей энтропии. Во-первых, если одно из двух событий является достоверным (Р= 1 или Р=0), тогда энтропия равна нулю. Одно из двух событий должно произойти, и никакой информации о том, что одно из них произошло, не содержится. Во-вторых, максимального значения функция H(X) достигает, когда два результата равновероятны. Это так­же обоснованно: когда два результата равновероятны, неуверенность в результате максимальна. Этот результат можно обобщить для случайной переменной с N ре­зультатами. Энтропия случайной переменной будет максимальна, когда все ре­зультаты равновероятны:

Например,

тогда как

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