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

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

Эта статья посвящена теории кодирования исходного кода при сжатии данных. Чтобы узнать о термине в компьютерном программировании, см. Исходный код.

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

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

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

• 1 Заявления
  • 1.1 Теорема исходного кода
  • 1.2 Теорема кодирования источника для символьных кодов
• 2 Доказательство: теорема о кодировании источника
• 3 Доказательство: теорема кодирования источника для символьных кодов
• 4 Распространение на нестационарные независимые источники
  • 4.1 Кодирование источника без потерь с фиксированной скоростью для нестационарных независимых источников с дискретным временем
• 5 См. Также
• 6 Ссылки

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

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

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

N i.id случайных величин, каждая с энтропией H ( X), может быть сжато до более чем N H ( X) битов с пренебрежимо малым риском потери информации при N → ∞ ; но, наоборот, если они сжаты до менее чем 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] lt;{\ frac {H (X)} {\ log _ {2} a }} + 1}$

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

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

Доказательство достижимости. Зафиксируем некоторое ε gt; 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 | lt;\ 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 ≤ i ≤ n пусть s i обозначает длину слова каждого возможного x i. Определим, где C выбрано так, чтобы q 1 +... + q n = 1. Затем ${\ displaystyle q_ {i} = a ^ {- s_ {i}} / C}$

${\ Displaystyle {\ begin {align} H (X) amp; = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} p_ {i} \\ amp; \ leq - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} q_ {i} \\ amp; = - \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2 } a ^ {- s_ {i}} + \ sum _ {i = 1} ^ {n} p_ {i} \ log _ {2} C \\ amp; = - \ sum _ {i = 1} ^ {n } p_ {i} \ log _ {2} a ^ {- s_ {i}} + \ log _ {2} C \\ amp; \ leq - \ sum _ {i = 1} ^ {n} -s_ {i } p_ {i} \ log _ {2} a \\ amp; \ leq \ mathbb {E} S \ log _ {2} a \\\ конец {выровнено}}}$

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

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

так что журнал C ≤ 0.

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

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

и что

${\ displaystyle - \ log _ {a} p_ {i} \ leq s_ {i} lt;- \ 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 amp; = \ sum p_ {i} s_ {i} \\ amp; lt;\ sum p_ {i} \ left (- \ log _ {a} p_ {i} +1 \ right) \\ amp; = \ sum -p_ {i} {\ frac {\ log _ {2} p_ {i}} {\ log _ {2} a}} + 1 \\ amp; = {\ 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 | lt;\ varepsilon \ right \}.}$

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

• Кодирование каналов
• Теорема о шумном канальном кодировании
• Показатель ошибки
• Свойство асимптотической равнораспределенности (AEP)
• Теория информации с конечной длиной блока