Теорема Шеннона о кодировании исходного кода

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

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

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

Обратите внимание, что для данных, которые демонстрируют больше зависимостей (источником которых не является случайная величина iid), сложность Колмогорова , которая количественно определяет минимальную длину описания объекта, более подходит для описания пределов сжатия данных. Энтропия Шеннона учитывает только частотные закономерности, тогда как сложность Колмогорова учитывает все алгоритмические закономерности, поэтому последняя, как правило, меньше. С другой стороны, если объект генерируется случайным процессом таким образом, что он имеет только частотные закономерности, энтропия с высокой вероятностью близка к сложности (Шен и др., 2017). ^{[ 1 ]}

Заявления

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

Теорема исходного кодирования

В теории информации теорема исходного кодирования (Шеннон, 1948) ^{[ 2 ]} неофициально утверждает, что (MacKay 2003, стр. 81, ^{[ 3 ]} Обложка 2006 г., Глава 5 ^{[ 4 ]}):

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

The $NH(X)$ кодированная последовательность представляет сжатое сообщение двузначным образом, при условии, что декодер знает источник. С практической точки зрения эта гипотеза не всегда верна. Следовательно, когда применяется энтропийное кодирование, передаваемое сообщение $NH(X)+(inf.source)$ . Обычно информация, характеризующая источник, вставляется в начало передаваемого сообщения.

Теорема исходного кодирования для кодов символов

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

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

Если $f$ оптимален в том смысле, что он имеет минимальную ожидаемую длину слова для $X$ , то (Шеннон 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 (H (X) + ε)$ двоичных битов так, что исходные символы $X 1: н$ восстанавливаются из двоичных битов с вероятностью не менее $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$ , как определено, приближается к единице. В частности, для достаточно $n$ больших $P((X_{1},X_{2},\cdots ,X_{n})\in A_{n}^{\varepsilon })$ можно сделать сколь угодно близким к 1 и, в частности, больше, чем $1-\varepsilon$ (Видеть АЭП за доказательство).

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

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

Вероятность последовательности $(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 )}$ , что следует из верхней оценки для $p(x_{1},x_{2},\cdots x_{n})$ и нижняя граница полной вероятности всего множества $A е н$ .

С $\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$ . Определять $q_{i}=a^{-s_{i}}/C$ , где $C$ выбран так, что $q 1 + ... + q n = 1$ . Затем

{\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\\&=\mathbb {E} S\log _{2}a\\\end{aligned}}

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

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

поэтому $журнал C \leq 0$ .

Для второго неравенства можно положить

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

так что

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

и так

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

и

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

и поэтому согласно неравенству Крафта существует код без префиксов, имеющий такую длину слова. Таким образом, минимальное $S$ удовлетворяет

{\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}}

Распространение на нестационарные независимые источники.

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

Определите типовой набор $A е н$ как:

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\}.

Тогда для заданного $δ > 0$ и $n$ достаточно большого $Pr(A е п) > 1 - δ$ . Сейчас мы просто кодируем последовательности в типичном наборе, а обычные методы кодирования исходников показывают, что мощность этого набора меньше, чем $2^{n({\overline {H_{n}}}(X)+\varepsilon )}$ . Таким образом, в среднем $H n (X) + ε$ битов достаточно для кодирования с вероятностью большей, чем $1 - δ$ , где $ε$ и $δ$ можно сделать сколь угодно малыми, увеличив $n$ .

См. также

Ссылки

^ Шен А., Успенский В.А. и Верещагин Н. (2017). «Глава 7.3.: Сложность и энтропия». Колмогоровская сложность и алгоритмическая случайность . Американское математическое общество. п. 226. ИСБН 9781470431822 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )
^ CE Шеннон , « Математическая теория связи, заархивировано 16 февраля 2009 г. в Wayback Machine », Технический журнал Bell System , том. 27, стр. 379–423, 623–656, июль, октябрь 1948 г.
^ Дэвид Дж. К. Маккей. Теория информации, вывод и алгоритмы обучения. Кембридж: Издательство Кембриджского университета, 2003. ISBN 0-521-64298-1
^ Обложка, Томас М. (2006). «Глава 5: Сжатие данных». Элементы теории информации . Джон Уайли и сыновья. стр. 103–142. ISBN 0-471-24195-4 .

[Shen2017-1] Шен А., Успенский В.А. и Верещагин Н. (2017). «Глава 7.3.: Сложность и энтропия». Колмогоровская сложность и алгоритмическая случайность . Американское математическое общество. п. 226. ИСБН 9781470431822 . {{cite book}}: CS1 maint: несколько имен: список авторов ( ссылка )

[Shannon-2] CE Шеннон , « Математическая теория связи, заархивировано 16 февраля 2009 г. в Wayback Machine », Технический журнал Bell System , том. 27, стр. 379–423, 623–656, июль, октябрь 1948 г.

[MacKay-3] Дэвид Дж. К. Маккей. Теория информации, вывод и алгоритмы обучения. Кембридж: Издательство Кембриджского университета, 2003. ISBN 0-521-64298-1

[Cover-4] Обложка, Томас М. (2006). «Глава 5: Сжатие данных». Элементы теории информации . Джон Уайли и сыновья. стр. 103–142. ISBN 0-471-24195-4 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]