Теорема Шеннона о кодировании источника

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

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

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

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

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

Заявления [ править ]

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

Теорема исходного кода [ править ]

В теории информации теорема кодирования источника (Shannon 1948) ^[1] неформально утверждает, что (MacKay 2003, pg. 81, ^[2] Cover 2006, Chapter 5 ^[3] ):

$N$ i.id случайных величин, каждая с энтропией $H (X),$ может быть сжато до более чем $N H (X)$ битов с пренебрежимо малым риском потери информации при $N \to \infty$ ; но, наоборот, если они сжаты до менее чем $N H (X)$ битов, практически наверняка информация будет потеряна.

Теорема исходного кода для кодов символов [ править ]

Пусть $Σ 1, Σ 2$ обозначают два конечных алфавита и пусть $Σ * 1$ и $Σ * 2$ обозначают набор всех конечных слов из этих алфавитов (соответственно).

Предположим, что $X$ - случайная величина, принимающая значения в $Σ 1,$ и пусть $f$ - однозначно декодируемый код из $Σ$ $* 1$ в $Σ * 2$ где $| Σ 2 | = а$ . Пусть $S$ обозначает случайную величину, заданную длиной кодового слова $f$ $($ $X$ $)$ .

Если $f$ оптимален в том смысле, что он имеет минимальную ожидаемую длину слова для $X$ , то (Shannon 1948):

{\frac {H(X)}{\log _{2}a}}\leq \mathbb {E} [S]<{\frac {H(X)}{\log _{2}a}}+1

Где обозначает оператор ожидаемого значения . $\mathbb {E}$

Доказательство: теорема о кодировании исходного кода [ править ]

Если $X$ является источником iid , его временные ряды $X 1, ..., X n$ являются iid с энтропией $H (X)$ в дискретнозначном случае и дифференциальной энтропией в непрерывнозначном случае. Теорема кодирования источника утверждает, что для любого $ε > 0$ , то есть для любой скорости $H (X) + ε,$ большей, чем энтропия источника, существует достаточно большое $n$ и кодировщик, который принимает $n$ iid повторений источника, $X 1: n$ , и отображает его в $n (H (X) + ε)$ двоичных битов, так что исходные символы $X 1: n$ восстанавливаются из двоичных битов с вероятностью по меньшей мере $1 - ε$ .

Доказательство достижимости. Зафиксируем некоторое $ε > 0$ и пусть

p(x_{1},\ldots ,x_{n})=\Pr \left[X_{1}=x_{1},\cdots ,X_{n}=x_{n}\right].

Типовой набор, $А ε n$ , определяется следующим образом:

A_{n}^{\varepsilon }=\left\{(x_{1},\cdots ,x_{n})\ :\ \left|-{\frac {1}{n}}\log p(x_{1},\cdots ,x_{n})-H_{n}(X)\right|<\varepsilon \right\}.

Свойство асимптотической равнораспределенности (AEP) показывает, что для достаточно большого $n$ вероятность того, что последовательность, сгенерированная источником, принадлежит типичному набору $A ε n$ , как определено, приближается к одному. В частности, при достаточно больших $п$ , можно сделать сколь угодно близким к 1, и , в частности, больше , чем (см AEP для доказательства). $P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })$ $1-\varepsilon$

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

2^{-n(H(X)+\varepsilon )}\leq p\left(x_{1},\cdots ,x_{n}\right)\leq 2^{-n(H(X)-\varepsilon )}

Обратите внимание, что:

Вероятность того, что последовательность будет взята из $A$ $(X_{1},X_{2},\cdots X_{n})$ $ε n$ больше $1 - ε$ .
$\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )}$ , что следует из левой части (нижней оценки) для . $p(x_{1},x_{2},\cdots x_{n})$
$\left|A_{n}^{\varepsilon }\right|\geq (1-\varepsilon )2^{n(H(X)-\varepsilon )}$ , что следует из оценок сверху и снизу полной вероятности всего множества $A$ $p(x_{1},x_{2},\cdots x_{n})$ $ε n$ .

Поскольку битов достаточно, чтобы указать на любую строку в этом наборе. $\left|A_{n}^{\varepsilon }\right|\leq 2^{n(H(X)+\varepsilon )},n(H(X)+\varepsilon )$

Алгоритм кодирования: кодировщик проверяет, находится ли входная последовательность в пределах типичного набора; если да, он выводит индекс входной последовательности в типичном наборе; в противном случае кодировщик выдает произвольное $n (H (X) + ε)$ разрядное число. Пока входная последовательность находится в пределах типичного набора (с вероятностью не менее $1 - ε$ ), кодировщик не делает ошибок. Таким образом, вероятность ошибки кодировщика ограничена сверху $величиной ε$ .

Доказательство обратного. Обратное утверждение доказывается, показывая , что любой набор меньшего размера , чем $A ε n$ (в смысле экспоненты) охватывал бы набор вероятностей, ограниченный от $1$ .

Доказательство: теорема исходного кода для кодов символов [ править ]

Для $1 \leq i \leq n$ пусть $s i$ обозначает длину слова каждого возможного $x i$ . Определим , где $C$ выбрано так, чтобы $q$ $1$ $+ ... +$ $q$ $n$ $= 1$ . потом $q_{i}=a^{-s_{i}}/C$

{\begin{aligned}H(X)&=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}\\&\leq -\sum _{i=1}^{n}p_{i}\log _{2}q_{i}\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\sum _{i=1}^{n}p_{i}\log _{2}C\\&=-\sum _{i=1}^{n}p_{i}\log _{2}a^{-s_{i}}+\log _{2}C\\&\leq -\sum _{i=1}^{n}-s_{i}p_{i}\log _{2}a\\&\leq \mathbb {E} S\log _{2}a\\\end{aligned}}

где вторая строка следует из неравенства Гиббса, а пятая строка следует из неравенства Крафт :

C=\sum _{i=1}^{n}a^{-s_{i}}\leq 1

так что $журнал C \leq 0$ .

For the second inequality we may set

s_{i}=\lceil -\log _{a}p_{i}\rceil

so that

-\log _{a}p_{i}\leq s_{i}<-\log _{a}p_{i}+1

and so

a^{-s_{i}}\leq p_{i}

and

\sum a^{-s_{i}}\leq \sum p_{i}=1

and so by Kraft's inequality there exists a prefix-free code having those word lengths. Thus the minimal $S$ satisfies

{\begin{aligned}\mathbb {E} S&=\sum p_{i}s_{i}\\&<\sum p_{i}\left(-\log _{a}p_{i}+1\right)\\&=\sum -p_{i}{\frac {\log _{2}p_{i}}{\log _{2}a}}+1\\&={\frac {H(X)}{\log _{2}a}}+1\\\end{aligned}}

Extension to non-stationary independent sources[edit]

Fixed Rate lossless source coding for discrete time non-stationary independent sources[edit]

Define typical set $A ε n$ as:

A_{n}^{\varepsilon }=\left\{x_{1}^{n}\ :\ \left|-{\frac {1}{n}}\log p\left(X_{1},\cdots ,X_{n}\right)-{\overline {H_{n}}}(X)\right|<\varepsilon \right\}.

Then, for given $δ > 0$ , for $n$ large enough, $Pr(A ε n) > 1 - δ$ . Now we just encode the sequences in the typical set, and usual methods in source coding show that the cardinality of this set is smaller than $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$ . Thus, on an average, $H n (X) + ε$ bits suffice for encoding with probability greater than $1 - δ$ , where $ε$ and $δ$ can be made arbitrarily small, by making $n$ larger.

References[edit]

^ C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948
^ David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
^ Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.

[Shannon-1] C.E. Shannon, "A Mathematical Theory of Communication", Bell System Technical Journal, vol. 27, pp. 379–423, 623-656, July, October, 1948

[MacKay-2] David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1

[Cover-3] Cover, Thomas M. (2006). "Chapter 5: Data Compression". Elements of Information Theory. John Wiley & Sons. ISBN 0-471-24195-4.

[1]