Теорема Шеннона о кодировании источника - Shannon's source coding theorem

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

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

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

Заявления

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

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

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

$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):

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

Где обозначает оператор ожидаемого значения . ${\ displaystyle \ 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$ и пусть

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

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

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

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

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

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

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

Так как битов достаточно, чтобы указать на любую строку в этом наборе. ${\ displaystyle \ 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$ . Затем ${\ displaystyle q_ {i} = a ^ {- s_ {i}} / C}$

{\ 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_ {я} = \ 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 \\\ конец {выровнено}}}

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

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

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

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

Languages

In other projects