Теорема кодирования источника Шеннона - Shannons source coding theorem

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

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

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

Заявления

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

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

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

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

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

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

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

Если $ж$ оптимален в том смысле, что он имеет минимальную ожидаемую длину слова для $Икс$ , затем (Шеннон, 1948):

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

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

Доказательство: теорема о кодировании источника

Данный $Икс$ является i.i.d. источник, его Временные ряды $Икс 1, ..., Икс п$ это i.i.d. с энтропия $ЧАС (Икс)$ в дискретнозначном случае и дифференциальная энтропия в непрерывнозначном случае. Теорема исходного кода утверждает, что для любого $ε > 0$ , т.е. для любого ставка $ЧАС (Икс) + ε$ больше, чем энтропия источника достаточно большой $п$ и кодировщик, который принимает $п$ i.i.d. повторение источника, $Икс 1: п$ , и сопоставляет его с $п (ЧАС (Икс) + ε)$ двоичные биты, такие что исходные символы $Икс 1: п$ восстанавливаются из двоичных разрядов с вероятностью не менее $1 - ε$ .

Доказательство достижимости. Исправить некоторые $ε > 0$ , и разреши

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

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

{ Displaystyle 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) показывает, что для достаточно больших $п$ , вероятность того, что последовательность, порожденная источником, принадлежит типичному набору, $А ε п$ , как определено, приближается к одному. В частности, для достаточно больших $п$ , ${ Displaystyle P ((X_ {1}, X_ {2}, cdots, X_ {n}) in A_ {n} ^ { varepsilon})}$ можно сделать сколь угодно близким к 1 и, в частности, больше, чем ${ displaystyle 1- varepsilon}$ (Видеть AEP для доказательства).

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

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

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

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

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

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

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

Доказательство: теорема кодирования источника для кодов символов.

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

{ Displaystyle { begin {align} 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 конец {выровнено}}}

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

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

так $бревно C \leq 0$ .

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

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

так что

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

и так

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

и

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

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

{ displaystyle { begin {align} 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 конец {выровнено}}}

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

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

Определить типовой набор $А ε п$ в качестве:

{ displaystyle 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$ , за $п$ достаточно большой, $Pr (А ε п) > 1 - δ$ . Теперь мы просто кодируем последовательности в типичном наборе, а обычные методы кодирования исходного кода показывают, что мощность этого набора меньше, чем ${ displaystyle 2 ^ {n ({ overline {H_ {n}}} (X) + varepsilon)}}$ . Таким образом, в среднем $ЧАС п (Икс) + ε$ битов достаточно для кодирования с вероятностью больше, чем $1 - δ$ , куда $ε$ и $δ$ можно сделать сколь угодно малым, сделав $п$ больше.